[C++面试] 标准容器面试点

一、入门

1、vector和list的区别

[C++面试] vector 面试点总结

vector 是动态数组，它将元素存储在连续的内存空间中。支持随机访问，即可以通过下标快速访问任意位置的元素，时间复杂度为 O(1)，准确点是均摊O(1)。但在中间或开头插入、删除元素效率较低，因为需要移动后续元素，时间复杂度为 O(n)。

vector：需要频繁随机访问或尾部操作（如数据缓存、动态数组）

list 是双向链表，元素在内存中不连续存储。不支持随机访问，访问元素需要从头或尾开始遍历，时间复杂度为 O(n)。但在任意位置插入、删除元素效率较高，时间复杂度为 O(1)。

list 需要频繁在任意位置插入/删除（如LRU链表、需要稳定迭代器的场景）

2、set和map的主要用途是什么？

• set 关联容器，用于存储唯一的元素，并且会对元素进行自动排序（默认按升序）。主要用于需要快速查找元素是否存在的场景，插入、删除和查找操作的时间复杂度均为 O(logn)。
• map 关联容器，它存储的是键-值对，键是唯一的，并且会根据键进行排序。主要用于需要根据键快速查找对应值的场景，插入、删除和查找操作的时间复杂度同样为 O(logn)。

3、map和set的底层实现是什么？为什么？

• 底层实现：红黑树（自平衡二叉搜索树）。
• 原因：红黑树保证插入、删除、查找的时间复杂度为O(log n)，且自动维护元素有序性。

如果问你红黑树的细节，你直接回答不了解。如果坚持让你回答，那就是在劝退你，也别浪费时间了

二、进阶

1、deque相对于vector和list有什么优势，适用于什么场景？

[C++面试] 关于deque-CSDN博客

• deque 是双端队列，结合了 vector 和 list 的部分优点。它支持随机访问，虽然效率略低于 vector，但也能在O(1) 时间内访问元素。同时，在两端插入和删除元素的效率较高，时间复杂度为 O(1)，但中间插入仍需O(n)。
• 中间插入效率：与vector类似，都需要移动元素，但deque的块结构可能减少部分元素移动，实际性能需具体测试。
• deque由多个固定大小的数组块（chunk）组成，通过中控器（指针数组）管理。

整体上，deque对于给定的索引，计算出所在的块和块内偏移量并访问元素的操作次数是固定的，不随元素数量的增加而增加，所以其随机访问的时间复杂度仍然是 O(1) ，不过因为多了定位块的操作，效率会略低于 vector。

• 当需要在容器两端频繁插入和删除元素，同时也需要随机访问元素时，deque 是一个不错的选择，例如实现队列或栈。

2、priority_queue的特点是什么，如何使用？

priority_queue 是优先队列，它是一种容器适配器，默认使用 vector 作为底层容器，并且使用大顶堆（最大元素位于堆顶）来实现。它的特点是可以在 \(O(log n)\) 的时间复杂度内插入元素和删除堆顶元素，并且可以在 \(O(1)\) 的时间复杂度内访问堆顶元素。

    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(2);

3、 为什么priority_queue默认用vector而不是deque作为底层容器？

• 堆操作（如push_heap、pop_heap）需要随机访问，vector的连续内存访问更高效。
• deque的复杂内存布局可能导致堆操作性能下降。

4、forward_list和list相比，有什么优缺点，使用时需要注意什么？

• 优点：forward_list 是单向链表，只支持单向遍历，内存开销更小，插入和删除操作的效率也更高，因为只需要维护一个指针。每个节点只有后向指针 。
• 缺点：不支持反向遍历，访问元素只能从头开始依次向后遍历，并且没有 size() 成员函数，获取元素数量需要手动遍历。
• 使用注意事项：由于 forward_list 没有 push_back() 方法，只能使用 push_front() 插入元素。在插入和删除元素时，需要注意迭代器的有效性，因为操作可能会使迭代器失效。
• 场景：forward_list：内存敏感场景（如嵌入式系统），且只需单向遍历（如哈希表冲突链表）。list：需要反向操作或双向迭代器（如某些中间节点删除需前驱指针）。

5、stack是容器吗？它的默认底层容器是什么？ 

• stack是容器适配器，不是独立容器。（概念考察）
• 默认底层容器是deque（支持两端高效操作），也可用vector或list

三、高阶

1、如何为自定义类型选择容器？例如存储Student对象，需要按学号快速查找。

需求分析（开放题，仅供参考）：

• 若需有序性且频繁查找：用map<int, Student>（学号为键）。
• 若无需有序性但需更快查找：用unordered_map（哈希表，O(1)查找）。
• 若需频繁插入/删除且有序性不重要：用vector+排序（或维护有序插入）。

2、vector的迭代器失效场景有哪些？如何避免？

[C++面试] vector 面试点总结-CSDN博客

• 插入元素导致容量变化（内存重分配）：所有迭代器失效。
• 删除元素：被删位置后的迭代器失效。

避免方法 

• 预分配足够容量（reserve）减少重分配。
• 插入/删除后重新获取迭代器。

vector<bool>可能是个坑（见上述链接）

• 标准规定vector<bool>使用位压缩存储，每个元素占1 bit，但行为类似引用而非普通bool。
• 陷阱：不能直接取元素地址，且迭代器行为异常（如无法修改*iter的值）

3、map::operator[]和map::insert的陷阱是什么？ 

3.1、operator[]：若键不存在，会插入一个默认值，可能导致意外内存增长。

map<string, int> scores = {{"Alice", 90}, {"Bob", 85}};
// 尝试读取不存在的键 "Charlie"
int charlie_score = scores["Charlie"];  // 插入 {"Charlie", 0}

用 find 替代 operator[] 进行安全查找： 

auto it = scores.find("Charlie");
if (it != scores.end()) {
    int charlie_score = it->second;
} else {
    // 处理键不存在的情况
}

3.2、insert：若键已存在，不会覆盖原有值，而是保留原有值，并返回一个 pair<iterator, bool>，其中 bool 为 false。需用insert_or_assign（C++17）或先find再更新。

map<string, int> scores = {{"Alice", 90}, {"Bob", 85}};
// 尝试插入或更新 "Alice" 的分数
scores.insert({"Alice", 95});  // 插入失败，原有值 90 保留
// 输出结果
cout << "Alice's score: " << scores["Alice"] << endl;  // 输出 90

​方法1：insert_or_assign（C++17）​

• 若键存在，更新值；若不存在，插入新键值对。

int main() {
    map<string, int> scores = {{"Alice", 90}, {"Bob", 85}};

    // 更新 "Alice" 的分数为 95
    scores.insert_or_assign("Alice", 95);  // 更新成功
    scores.insert_or_assign("Charlie", 80); // 插入新键值对
}

​方法2：先 find 再更新

auto it = scores.find("Alice");
if (it != scores.end()) {
    it->second = 95;  // 直接修改迭代器指向的值
} else {
    scores.insert({"Alice", 95});
}

​方法3：operator[] + 赋值

• 若确定键需要插入或更新，可直接用 operator[]：

scores["Alice"] = 95;  // 无论 "Alice" 是否存在，值都会被设为 95

实际场景建议

1. ​只读访问：用 find 替代 operator[]，避免意外插入。

2. ​需要插入或更新：

   • C++17+：优先用 insert_or_assign。

   • C++11：用 find 检查是否存在，再决定插入或更新。

3. ​明确需要覆盖：直接使用 operator[] = value。

4、如何高效合并两个有序vector？ 

• 方法1：先insert后sort（时间复杂度高，O(n log n)）。
• 方法2：使用std::merge（时间复杂度O(n)，需额外空间）：

vector<int> merged;
merged.reserve(v1.size() + v2.size());
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(merged));

总结：