更多专栏：

超详细的嵌入式面经专栏（适用于小白学习和大佬复习）：https://www.nowcoder.com/creation/manager/columnDetail/mGYoDz

校招公司汇总专栏:https://www.nowcoder.com/creation/manager/columnDetail/0ybKdp

目录：

1.STL中常用的容器有哪些？

2.请你说说STL容器有哪些并且说一下时间复杂度？

3.请说说vector和list有什么区别？

4.vector和deque的区别？

5.请你说明一下STL底层数据结构实现？

6.请你说说map和set区别差异？

7.请你说说STL迭代器怎样删除元素？

内容：

1.STL中常用的容器有哪些？

顺序容器

1. vector

• 动态数组，支持随机访问。
• 元素存储在连续的内存空间中，支持高效的索引操作（O(1) 时间复杂度）。
• 在尾端增删元素。

2. deque

• 双端队列，支持在两端高效地插入和删除。
• 支持随机访问。
• 相较于 vector，不需要频繁搬移整个数组，但随机访问性能稍差。
• 需要在头尾进行频繁插入或删除操作。

3.list

• 双向链表，支持高效的插入和删除。
• 不支持随机访问。
• 插入和删除操作仅需要调整指针，时间复杂度为 O(1)。
• 频繁插入和删除操作，但对随机访问要求不高。

4 .forward_list

• 单向链表，支持单向遍历和高效的插入、删除操作。
• 相较于 list，更加轻量级。
• 使用单向链表实现，元素通过单指针链接，内存不连续。
• 需要简单链表操作，内存开销较小的场景。

5. string

• 专门用于操作字符串的容器，功能类似 vector<char>。
• 基于动态数组实现，支持动态扩容。
• 提供了大量字符串处理函数，例如拼接、查找、替换等。
• 字符串操作。

关联容器

1. map

• 存储键值对，键是唯一的，支持高效的查找、插入、删除操作（O(log n)）。
• 数据按照键值排序，支持有序遍历。
• 需要按键有序存储键值对，并支持快速查找。

2. multimap

• 和 map 类似，但允许键重复。
• 和 map 一样基于红黑树实现，区别在于支持存储重复键。
• 键值对存储，但允许键重复。

3. set

• 存储唯一的键，自动按顺序排列。
• 支持高效的插入、查找、删除操作（O(log n)）。
• 基于红黑树实现。
• 元素作为键值存储，不能重复。
• 需要存储唯一值，并支持快速查找和有序遍历。

4. multiset

• 和 set 类似，但允许重复值。
• 和 set 一样基于红黑树实现，区别在于允许重复值。
• 数据存储需支持重复值，但仍需要有序存储。

5. unordered_map

• 存储键值对，键是唯一的，查找和插入操作的平均时间复杂度为 O(1)。
• 基于哈希表实现。
• 数据无序存储。
• 快速查找键值对，但对顺序无要求。

6. unordered_multimap

• 和 unordered_map 类似，但允许键重复。
• 基于哈希表实现，支持重复键。
• 快速查找键值对，允许键重复。

7. unordered_set

• 存储唯一值，无序排列。
• 基于哈希表实现。
• 无序存储唯一值，并支持快速查找。

8. unordered_multiset

• 和 unordered_set 类似，但允许重复值。
• 基于哈希表实现。
• 无序存储值，并允许重复。

总结

2.请你说说STL容器有哪些并且说一下时间复杂度？

顺序容器

顺序容器中的元素按插入顺序存储，主要用于序列存储。

关联容器

关联容器通常按键值对存储，底层实现基于红黑树，支持有序存储和快速查找。

无序关联容器

无序关联容器底层基于哈希表实现，支持快速的查找、插入和删除操作，但不保证元素的顺序。

容器适配器

3.请说说vector和list有什么区别？

相同点

• 两者都属于顺序容器，用于按插入顺序存储元素。
• 支持动态大小调整（虽然实现方式不同）。
• 都能通过 STL 提供的标准迭代器（iterator）进行元素的访问和操作。
• 两者提供类似的容器操作接口，如插入（insert）、删除（erase）、遍历（begin/end）等。
• 支持 STL 算法（如 std::sort，但需要注意 list 需要先转为其他容器才支持随机访问相关算法）。
• 容器中的元素可以是基本数据类型，也可以是用户自定义的复杂类型。

不同点

使用场景

vector 的场景

• 需要随机访问，如果需要频繁按索引访问元素，vector 是更好的选择。
• 数据量变化不频繁，数据量相对固定或变化不频繁，避免频繁的动态扩容带来的性能开销。
• 需要排序或二分查找，vector 支持快速排序和二分查找等操作，效率比 list 高。
• 空间效率高，内存连续分配，不需要额外的指针存储。

list 的场景

• 需要频繁的插入/删除操作，特别是在容器中间进行大量插入或删除操作时，list 的性能比 vector 好。
• 数据较大或变化频繁，数据量较大时，可以避免因 vector 扩容带来的大量内存分配和拷贝。
• 不需要随机访问，如果只需顺序访问，链表的性能足够且更灵活。

例子：

vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    v.push_back(4); // 在尾部插入
    v[2] = 5;       // 通过索引修改
    for (int i : v) {
        cout << i << " "; // 输出：1 2 5 4
    }
    return 0;
}

list

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l = {1, 2, 3};
    auto it = l.begin();
    advance(it, 1); // 移动迭代器到第二个元素
    l.insert(it, 5)