C++ 容器 vector deque list forward_list map set multimap unordered_map 等访问插入性能内存特点存储结构适用场景区别汇总

表格汇总：

详细介绍：
以下是对 C++ 中各个容器按照存储结构、随机访问性能、中间插入/删除性能、两端插入/删除性能、内存管理特点、迭代器类型和适用场景的详细介绍：

一、顺序容器

1. vector：

   • 存储结构：基于动态数组实现。当创建 vector 时，它会分配一块连续的内存空间，元素存储在这块内存中。
   • 随机访问性能：由于是连续存储，可以通过指针运算快速定位元素，时间复杂度为 $O(1)$。例如，使用 vector[i] 可以直接访问第 i 个元素。
   • 中间插入/删除性能：在中间或头部插入/删除元素时，需要将插入/删除点之后的元素依次向后/向前移动，以保持元素的连续性，时间复杂度为 $O(n)$。例如，使用 vector.insert(vector.begin() + i, value) 在位置 i 插入元素时，从 i 开始的元素都需要移动。
   • 两端插入/删除性能：在尾部插入元素，通常在有足够空间时时间复杂度为 $O(1)$，但如果空间不足需要重新分配和复制元素，时间复杂度为 $O(n)$；在尾部删除元素时间复杂度为 $O(1)$。例如，使用 vector.push_back(value) 或 vector.pop_back()。
   • 内存管理特点：当添加元素超过当前容量时，会重新分配一个更大的连续内存空间（通常是当前容量的两倍），并将旧元素复制到新空间中。这可能导致性能开销，尤其是对于大型 vector。
   • 迭代器类型：随机访问迭代器，可以像指针一样进行加减操作，支持随机访问元素。
   • 适用场景：适用于需要频繁访问元素，且元素数量会动态变化，但主要在尾部进行插入和删除操作的场景。例如存储一系列数据并对其进行排序、查找或遍历操作。

2. deque：

   • 存储结构：双端队列通常由多个块组成，每个块存储多个元素，使用指针数组来管理这些块，元素在块内连续存储。
   • 随机访问性能：支持快速随机访问，时间复杂度为 $O(1)$。可以使用 deque[i] 来访问元素。
   • 中间插入/删除性能：类似于 vector，在中间插入/删除元素需要移动元素，时间复杂度为 $O(n)$。
   • 两端插入/删除性能：在头部和尾部插入/删除元素的速度很快，时间复杂度为 $O(1)$。可以使用 deque.push_front(value)、deque.pop_front()、deque.push_back(value) 和 deque.pop_back()。
   • 内存管理特点：能够在两端高效扩展，内存分配比 vector 更灵活，不会像 vector 那样需要复制整个数组，而是在头部或尾部添加新的块。
   • 迭代器类型：随机访问迭代器。
   • 适用场景：需要在队列两端快速插入和删除元素，同时又需要随机访问元素的场景，例如实现一个双端队列或滑动窗口。

3. list：

   • 存储结构：双向链表，每个元素包含数据以及指向前一个和后一个元素的指针，元素在内存中不连续。
   • 随机访问性能：由于元素不连续，要访问第 i 个元素，需要从头或尾开始遍历，时间复杂度为 $O(n)$。例如，使用迭代器遍历列表直到找到所需元素。
   • 中间插入/删除性能：在任意位置插入/删除元素只需要修改前后元素的指针，时间复杂度为 $O(1)$。例如，使用 list.insert(it, value) 在迭代器 it 处插入元素。
   • 两端插入/删除性能：在头部或尾部插入/删除元素，只需修改相应的指针，时间复杂度为 $O(1)$ 。可以使用 list.push_front(value)、list.pop_front()、list.push_back(value) 和 list.pop_back()。
   • 内存管理特点：每个元素单独分配内存，内存使用较为灵活，但会有额外的指针开销。
   • 迭代器类型：双向迭代器，可以向前或向后移动，但不支持随机访问。
   • 适用场景：适用于需要频繁在任意位置插入和删除元素，但不需要快速随机访问的场景，如实现链表数据结构，用于频繁插入和删除操作的列表操作。

4. forward_list：

   • 存储结构：单向链表，每个元素包含数据和指向下一个元素的指针，元素在内存中不连续。
   • 随机访问性能：与 list 类似，需要从头开始遍历，时间复杂度为 $O(n)$。
   • 中间插入/删除性能：在任意位置插入/删除元素只需要修改指针，时间复杂度为 $O(1)$。但由于是单向链表，插入/删除操作需要在元素之前的位置操作，例如，使用 forward_list.insert_after(it, value) 在迭代器 it 之后插入元素。
   • 两端插入/删除性能：在头部插入/删除元素很方便，时间复杂度为 $O(1)$，在尾部插入/删除元素需要遍历整个链表，时间复杂度为 $O(n)$。可以使用 forward_list.push_front(value) 和 forward_list.pop_front()。
   • 内存管理特点：每个元素单独分配内存，比 list 更节省空间，因为只有一个指针。
   • 迭代器类型：单向迭代器，只能向后移动。
   • 适用场景：适用于需要频繁在头部或链表中间位置插入和删除元素，且对空间要求严格，不需要随机访问的场景，例如实现一个简单的单向链表，减少空间开销。

5. array：

   • 存储结构：固定大小的数组，元素存储在连续的内存空间中，大小在编译时确定。
   • 随机访问性能：支持快速随机访问，时间复杂度为 $O(1)$。可以使用 array[i] 访问元素。
   • 中间插入/删除性能：不支持插入和删除元素，因为其大小是固定的。
   • 两端插入/删除性能：不支持插入和删除元素。
   • 内存管理特点：静态存储，内存分配在栈上（如果是局部 array）或静态存储区（如果是全局 array），内存连续，大小固定。
   • 迭代器类型：随机访问迭代器。
   • 适用场景：适用于元素数量固定，需要快速随机访问元素的场景，例如存储一组已知大小的元素，并且不允许元素数量变化，对性能要求较高。

二、关联容器

1. map：

   • 存储结构：基于红黑树实现，红黑树是一种自平衡二叉搜索树，每个节点存储一个键值对，根据键的大小排序。
   • 随机访问性能：不支持随机访问，查找元素根据键的顺序进行，时间复杂度为 $O(\log n)$。使用 map[key] 或 map.find(key) 查找元素。
   • 中间插入/删除性能：插入和删除元素需要调整树的结构，以保持平衡，时间复杂度为 $O(\log n)$。例如，使用 map.insert({key, value}) 插入元素。
   • 两端插入/删除性能：不适用，因为元素是按键的顺序存储，不是按位置存储。
   • 内存管理特点：节点存储元素，根据键的顺序动态分配内存，为了保持树的平衡，可能会频繁进行内存分配和释放操作。
   • 迭代器类型：双向迭代器，可以按顺序遍历元素。
   • 适用场景：适用于存储键值对，键唯一，需要根据键快速查找、插入和删除元素，且元素按关键字有序存储，需要按序遍历元素的场景，例如存储配置信息，根据键查找相应的值。

2. set：

   • 存储结构：与 map 类似，也是基于红黑树实现，但只存储键，不存储值，键即元素。
   • 随机访问性能：不支持随机访问，查找元素根据键的顺序进行，时间复杂度为 $O(\log n)$。使用 set.find(key) 查找元素。
   • 中间插入/删除性能：插入和删除元素需要调整树的结构，以保持平衡，时间复杂度为 $O(\log n)$。例如，使用 set.insert(key) 插入元素。
   • 两端插入/删除性能：不适用，因为元素是按键的顺序存储，不是按位置存储。
   • 内存管理特点：节点存储元素，根据键的顺序动态分配内存，为了保持树的平衡，可能会频繁进行内存分配和释放操作。
   • 迭代器类型：双向迭代器，可以按顺序遍历元素。
   • 适用场景：适用于存储唯一的关键字集合，需要按关键字有序存储和快速查找元素的场景，例如存储一组不重复的关键字，对关键字进行有序遍历。

3. multimap：

   • 存储结构：基于红黑树实现，允许键重复的键值对容器。
   • 随机访问性能：不支持随机访问，查找元素根据键的顺序进行，时间复杂度为 $O(\log n)。使用 multimap.find(key)` 查找元素。
   • 中间插入/删除性能：插入和删除元素需要调整树的结构，以保持平衡，时间复杂度为 $O(\log n)$。例如，使用 multimap.insert({key, value}) 插入元素。
   • 两端插入/删除性能：不适用，因为元素是按键的顺序存储，不是按位置存储。
   • 内存管理特点：节点存储元素，根据键的顺序动态分配内存，为了保持树的平衡，可能会频繁进行内存分配和释放操作。
   • 迭代器类型：双向迭代器，可以按顺序遍历元素。
   • 适用场景：适用于存储多个具有相同关键字的键值对，需要根据键查找元素，且元素按关键字有序存储，需要按序遍历元素的场景，例如存储多个具有相同键的信息，如存储一个单词在文本中出现的多个位置。

4. multiset：

   • 存储结构：与 multimap 类似，基于红黑树，允许键重复，只存储键。
   • 随机访问性能：不支持随机访问，查找元素根据键的顺序进行，时间复杂度为 $O(\log n)。使用 multiset.find(key)` 查找元素。
   • 中间插入/删除性能：插入和删除元素需要调整树的结构，以保持平衡，时间复杂度为 $O(\log n)$。例如，使用 multiset.insert(key) 插入元素。
   • 两端插入/删除性能：不适用，因为元素是按键的顺序存储，不是按位置存储。
   • 内存管理特点：节点存储元素，根据键的顺序动态分配内存，为了保持树的平衡，可能会频繁进行内存分配和释放操作。
   • 迭代器类型：双向迭代器，可以按顺序遍历元素。
   • 适用场景：适用于存储允许重复的关键字集合，需要按关键字有序存储和快速查找元素的场景，例如存储一组允许重复的关键字，对关键字进行有序遍历。

三、无序集合

1. unordered_map：

   • 存储结构：基于哈希表实现，元素存储在桶中，通过哈希函数将键映射到桶中。
   • 随机访问性能：不支持随机访问，平均查找时间复杂度为 $O(1)$，但在最坏情况下（哈希冲突严重）为 $O(n)$。使用 unordered_map[key] 或 unordered_map.find(key) 查找元素。
   • 中间插入/删除性能：平均情况下插入和删除元素时间复杂度为 $O(1)$，最坏情况下为 $O(n)$。例如，使用 unordered_map.insert({key, value}) 插入元素。
   • 两端插入/删除性能：不适用，因为元素是根据哈希函数存储，不是按位置存储。
   • 内存管理特点：使用桶存储元素，根据元素的哈希值分配到不同的桶中，可能会有较多的内存开销，尤其是哈希冲突严重时，需要处理冲突。
   • 迭代器类型：前向迭代器，可以遍历元素，但不支持随机访问。
   • 适用场景：适用于存储键值对，键唯一，需要根据键快速查找、插入和删除元素，不要求元素有序存储的场景，例如快速查找键值对，对性能要求高，不需要元素有序。

2. unordered_set：

   • 存储结构：基于哈希表实现，只存储键，不存储值。
   • 随机访问性能：不支持随机访问，平均查找时间复杂度为 $O(1)$，但在最坏情况下为 $O(n)$。使用 unordered_set.find(key) 查找元素。
   • 中间插入/删除性能：平均情况下插入和删除元素时间复杂度为 $O(1)$，最坏情况下为 $O(n)$。例如，使用 unordered_set.insert(key) 插入元素。
   • 两端插入/删除性能：不适用，因为元素是根据哈希函数存储，不是按位置存储。
   • 内存管理特点：使用桶存储元素，根据元素的哈希值分配到不同的桶中，可能会有较多的内存开销，尤其是哈希冲突严重时，需要处理冲突。
   • 迭代器类型：前向迭代器，可以遍历元素，但不支持随机访问。
   • 适用场景：适用于存储唯一的关键字集合，需要快速查找元素，不要求元素有序存储的场景，例如存储一组不重复的关键字，快速查找关键字是否存在。

3. unordered_multimap：

   • 存储结构：基于哈希表实现，允许键重复的键值对容器。
   • 随机访问性能：不支持随机访问，平均查找时间复杂度为 $O(1)$，但在最坏情况下为 $O(n)$。使用 unordered_multimap.find(key) 查找元素。
   • 中间插入/删除性能：平均情况下插入和删除元素时间复杂度为 $O(1)$，最坏情况下为 $O(n)$。例如，使用 unordered_multimap.insert({key, value}) 插入元素。
   • 两端插入/删除性能：不适用，因为元素是根据哈希函数存储，不是按位置存储。
   • 内存管理特点：使用桶存储元素，根据元素的哈希值分配到不同的桶中，可能会有较多的内存开销，尤其是哈希冲突严重时，需要处理冲突。
   • 迭代器类型：前向迭代器，可以遍历元素，但不支持随机访问。
   • 适用场景：适用于存储多个具有相同关键字的键值对，需要快速查找元素，不要求元素有序存储的场景，例如存储多个具有相同关键字的键值对，快速查找具有某个关键字的键值对。

4. unordered_multiset：

   • 存储结构：基于哈希表实现，允许键重复，只存储键。
   • 随机访问性能：不支持随机访问，平均查找时间复杂度为 $O(1)$，但在最坏情况下为 $O(n)$。使用 unordered_multiset.find(key) 查找元素。
   • 中间插入/删除性能：平均情况下插入和删除元素时间复杂度为 $O(1)$，最坏情况下为 $O(n)$。例如，使用 unordered_multiset.insert(key) 插入元素。
   • 两端插入/删除性能：不适用，因为元素是根据哈希函数存储，不是按位置存储。
   • 内存管理特点：使用桶存储元素，根据元素的哈希值分配到不同的桶中，可能会有较多的内存开销，尤其是哈希冲突严重时，需要处理冲突。
   • 迭代器类型：前向迭代器，可以遍历元素，但不支持随机访问。
   • 适用场景：适用于存储允许重复的关键字集合，需要快速查找元素，不要求元素有序存储的场景，例如存储一组允许重复的关键字，快速查找关键字是否存在。