C++ 八股¶

复习一下C++

不鸣面经部分¶

Q: Vector¶

C++ 中vector的底层实现？64位条件下vector容器本身的大小是多少，为什么？

A:¶

大小: vector由一个data指针(相当于数组头指针)、一个size和一个capacity组成。指针指向动态分配的内存，size表示当前元素个数，capacity表示分配的内存大小。64位条件下，vector容器本身的大小是24字节（8+8+8），因为指针占8字节，size和capacity各占8字节，总体为24 + capacity * sizeof(T)字节。

结构: vector实际是泛型的动态类型顺序表，因此底层是一段连续的内存空间，用三个指针指向内存空间,start,finish,end_of_storage 然后用他们来实现以下几种方法:begin(),end(),size(),capacity(),empty(),push_back(),pop_back()等。

扩容: 当 vector 的大小和容量相等（size==capacity）也就是满载时，如果再向其添加元素，那么 vector 就需要扩容。

vector 容器扩容的过程需要经历以下 3 步： 1. 完全弃用现有的内存空间，重新申请更大的内存空间（VS2015中以1.5倍扩容，GCC以2倍扩容。扩容倍数为2时，时间上占优势；扩容倍数为1.5时，空间上占优势。） 2. 将旧内存空间中的数据，按原有顺序移动到新的内存空间中； 3. 最后将旧的内存空间释放。

Q: 多线程Vector¶

多线程下同时修改一个vector会有什么问题？如何解决？

A:¶

在多线程环境下，如果多个线程同时修改同一个 std::vector，会遇到以下几个问题：

数据竞态 - 问题：多个线程同时修改 std::vector（如插入、删除或修改元素）时，如果没有同步机制，可能会导致数据不一致或程序崩溃。例如，一个线程正在向 vector 添加元素，而另一个线程在同一时刻也在进行修改操作（如删除或修改元素），可能会导致访问非法内存或不一致的状态。 - 解决方法：使用同步机制（如互斥锁 std::mutex）来保证在同一时刻只有一个线程访问 vector。

内存访问冲突 - 问题：std::vector 内部是动态分配内存的，在进行扩容时，它可能会重新分配更大的内存区域，并将数据复制到新位置。如果有线程正在访问或修改 vector，而另一个线程执行扩容，可能导致内存访问冲突、指针悬挂或程序崩溃。 - 解决方法：保证在对 vector 执行扩容时，其他线程不对其进行读写操作。可以通过锁保护整个 vector 或使用其他同步方式。

不确定的迭代器行为 - 问题：如果一个线程正在迭代 vector，而另一个线程在同一时间修改它（例如，增加或删除元素），则迭代器可能变得无效，导致访问越界或未定义行为。 - 解决方法：避免在多线程中同时进行迭代操作和修改操作。如果必须进行修改，使用锁或其他同步机制确保迭代和修改操作不冲突。

解决方法：使用互斥锁

使用 std::mutex 来保护对 std::vector 的访问，使得每次只能有一个线程操作 vector，其他线程必须等待。下面是一个使用 std::mutex 来同步访问 vector 的示例：

示例（C++）：

#include <iostream>
#include <vector>
#include <thread>
#include <mutex>

std::vector<int> data;
std::mutex mtx;  // 互斥锁

// 修改vector的函数
void modifyVector(int value) {
    std::lock_guard<std::mutex> lock(mtx);  // 使用锁保护对vector的修改
    data.push_back(value);
}

// 读取vector的函数
void readVector() {
    std::lock_guard<std::mutex> lock(mtx);  // 使用锁保护对vector的读取
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::thread t1(modifyVector, 10);
    std::thread t2(modifyVector, 20);
    std::thread t3(readVector);

    t1.join();
    t2.join();
    t3.join();

    return 0;
}

解释： - std::lock_guard<std::mutex>：这是一种 RAII 风格的锁，确保每次访问 vector 时都能自动获得锁，并且在操作完成后释放锁，避免手动管理锁。 - 同步访问：在修改和读取 vector 时，所有线程都需要获取锁，保证同一时间只有一个线程可以访问 vector。

解决方案总结：

使用 std::mutex 锁定 vector：确保每次访问 vector 时，只有一个线程可以操作。
避免在多线程中同时修改和遍历 vector：操作和读取 vector 时，都要加锁，以防止数据不一致和内存冲突。
如果需要频繁读写，考虑使用其他同步机制：例如 读写锁（std::shared_mutex），允许多个线程并行读取，而写入时仍然是独占访问。

这样通过使用同步机制可以有效地避免并发访问 vector 时的数据竞态问题，保证程序的正确性和稳定性。

Q: 乱序排行榜¶

乱序排行榜10万个玩家，某位玩家如何知道其位置以及如何优化性能？

A:¶

快排二分哈希表频率跳表/平衡树

在10万个玩家的乱序排行榜中，要确定某玩家的排名，通过遍历排行榜（O(N)）、二分查找（O(log N)，前提是排序），或者使用哈希表存储排名（O(1)）都是不能解决问题的，时间/空间复杂度都很高。

如果均衡时间空间复杂度，可以考虑归并排序（O(N log N)），将排行榜分成多个块，每个块内进行排序，然后使用二分查找来确定玩家的排名。综合一下，分成40块，冒泡排序O(N^2)，从第一个块向后比较，

或者哈希表+频率统计

而如果跳出内部排序方法，则可以考虑外部排序：逐块加入内存然后快排，然后进行多路归并，（最小堆）得到最终的结果。然后二分查找或者者线性查找来确定玩家的排名。

为优化性能，可以采取以下措施： 1) 分页查询，每次只加载一部分数据； 2) 数据分片与索引，将数据分块以减少查询范围； 3) 缓存技术（如 Redis）加速常查询数据； 4) 增量更新，避免每次全量排序； 5) 并行处理，分布式查询和负载均衡提高性能。这些方法可以显著提升查询效率。

Q: 地图距离¶

玩家在地图中移动，如何快速找到距离最近的城镇？

A:¶

可以使用空间划分技术（如四叉树或八叉树）来快速找到距离最近的城镇。具体步骤如下： 1) 空间划分：将地图划分为多个区域，每个区域存储其内的城镇信息。 2) 区域查询：根据玩家当前位置，快速定位到其所在的区域。 3) 距离计算：在该区域内，计算玩家与城镇的距离，找到最近的城镇。 4) 邻近区域查询：如果该区域内没有城镇，向相邻区域扩展查询，直到找到最近的城镇。 5) 缓存机制：可以使用缓存机制存储最近查询的城镇，以减少重复计算。 6) 多线程处理：在大地图中，可以使用多线程并行计算不同区域的距离，进一步提高效率。 7) A*算法：如果需要考虑路径，可以使用A算法进行路径规划，找到最短路径到达城镇。 8) 预处理：在游戏开始时预处理城镇与玩家之间的距离，存储在数据结构中，以便快速查询。 9) 动态更新：如果城镇位置或玩家位置发生变化，及时更新距离信息，以保持数据的准确性。 10) 空间索引：使用R树等空间索引结构，快速定位城镇位置，提高查询效率。 11) 距离函数优化*：使用欧几里得距离或曼哈顿距离等简单的距离函数，避免复杂计算，提高性能。

Q: 超级手雷¶

32名玩家，每位玩家指挥100位士兵，向同一个地点丢手雷同时会有很多手雷爆炸，此时会很卡，如何优化？

A:¶

对象池

对象池（Object Pool）用于管理频繁创建和销毁的对象，减少内存分配开销。对于手雷和爆炸特效，使用对象池可以避免每次爆炸时都创建新对象，提升性能。

手雷对象池：管理所有投掷的手雷，使用完后回收，不必频繁创建和销毁对象。
爆炸特效池：爆炸时从池中获取特效对象，播放后回收。
粒子池：管理爆炸的粒子效果，减少粒子创建与销毁的开销。

示例（C++）：

class GrenadePool {
private:
    std::queue<std::shared_ptr<Grenade>> pool;

public:
    GrenadePool(size_t size) { /* 初始化池 */ }

    std::shared_ptr<Grenade> getGrenade() { /* 从池中获取手雷 */ }

    void returnGrenade(std::shared_ptr<Grenade> grenade) { /* 回收手雷 */ }
};

通过对象池，减少内存分配和垃圾回收，提高游戏性能。

线程池

线程池用于并行处理爆炸计算任务，避免频繁创建线程，提高计算效率。在手雷爆炸时，可以通过线程池并行处理每个手雷的爆炸影响（如伤害计算、物理效果等），避免阻塞主线程。

示例（C++）：

class ThreadPool {
private:
    std::vector<std::thread> workers;
    std::queue<std::function<void()>> tasks;
    std::mutex queueMutex;
    std::condition_variable condition;
    bool stop = false;

public:
    void enqueueTask(std::function<void()> task) { /* 将任务加入队列 */ }
};

通过线程池，可以将爆炸任务分配给多个线程并发处理，减少卡顿。

手雷对象池：减少对象创建与销毁，复用手雷、爆炸特效和粒子。
线程池：将爆炸计算分配给多个线程并行处理，提升效率。
空间划分：使用四叉树或网格划分地图，只处理与玩家相关的爆炸区域，减少计算范围。
事件合并：对爆炸事件进行合并，避免每个手雷爆炸时都进行计算。
使用 对象池 管理手雷和爆炸特效，避免内存频繁分配和回收。
使用 线程池 并行处理爆炸影响计算，提升游戏并发性能。
空间划分 和 事件合并 减少计算量，降低性能开销。

通过这些优化，可以有效提高大量爆炸事件下的游戏性能，避免卡顿，确保游戏流畅运行。

Q: 项目拷打¶

项目为什么这么设计？后续会如何提升优化？

A:¶

为什么这么设计？

3D迷宫逃杀项目：
迷宫生成与随机性：通过结合深度优先搜索（DFS）与随机化Prim算法，确保每次生成的迷宫都有不同的挑战性，增加游戏的重复可玩性和新鲜感。
NPC路径规划优化：利用改进的A*算法，使NPC能更智能地与玩家互动，提升游戏的互动性和流畅性。
沉浸感增强：光照、阴影和音效的设计提高了游戏的沉浸感，使玩家能在复杂的视觉和听觉环境中更好地体验游戏。
多线程优化：通过多线程技术分担路径计算和音效播放，保证了游戏的实时响应与高效性能，尤其在资源密集型场景下保持流畅体验。
四键交互音游项目：
MVVM框架：使用MVVM架构将界面与逻辑分离，提升了代码的可维护性和扩展性，简化了后期的功能拓展与调试。
多线程处理：将音符的生成与消除放入独立线程，确保主线程不被阻塞，避免了游戏卡顿，并且提高了响应速度。
渲染优化：使用Qt的图形视图框架和QOpenGLBuffer优化渲染性能，减少了CPU占用，提升了游戏的流畅度。

后续提升与优化方向：

3D迷宫逃杀项目：
算法优化：未来可以引入更多的迷宫生成算法（如Prim算法与BFS结合）来进一步增强迷宫的复杂性与可玩性，甚至考虑动态调整难度以适应玩家水平。
智能NPC提升：优化NPC的AI逻辑，引入更复杂的状态机或深度学习算法，使NPC行为更加自然和多变。
渲染与性能优化：提升渲染效果，尝试使用更高效的渲染技术如Vulkan或DirectX 12，减少OpenGL的性能瓶颈。
网络与多人协作：增加多人合作模式或在线匹配系统，提升游戏的社交性与互动性。
四键交互音游项目：
用户体验优化：优化音符生成算法，使其更具挑战性，同时加强音符与玩家互动的反馈，增加更多的视觉特效。
多平台支持：扩展至移动端或VR平台，提升游戏的可玩性和受众。
AI与自动音符生成：引入AI生成音符或根据玩家表现自动调整难度，使音游体验更加个性化和富有挑战性。
音频优化：进一步优化音效与背景音乐的搭配，提升音效的立体感和沉浸感。