c++笔记容器详细介绍

C++标准库提供了多种容器来存储和管理数据。这些容器属于<vector>, <list>, <deque>, <map>, <set>, <unordered_map>, <unordered_set>等头文件中。这些容器各有优缺点，适用于不同的场景。下面详细介绍几种主要的容器及其支持的函数。

1. std::vector

std::vector 是动态数组，可以高效地进行随机访问，支持动态调整大小。

头文件：<vector>

主要函数：

• push_back：在末尾添加元素。
• pop_back：移除末尾元素。
• at：访问指定位置的元素，带有边界检查。
• operator[]：访问指定位置的元素，不带边界检查。
• front：访问第一个元素。
• back：访问最后一个元素。
• data：返回底层数组的指针。
• size：返回元素个数。
• capacity：返回当前容量。
• resize：调整大小。
• reserve：预留空间。
• clear：清空所有元素。
• empty：检查容器是否为空。
• insert：在指定位置插入元素。
• erase：移除指定位置的元素。

2. std::list

std::list 是双向链表，支持高效的插入和删除操作。

头文件：<list>

主要函数：

• push_back：在末尾添加元素。
• push_front：在头部添加元素。
• pop_back：移除末尾元素。
• pop_front：移除头部元素。
• front：访问第一个元素。
• back：访问最后一个元素。
• size：返回元素个数。
• clear：清空所有元素。
• empty：检查容器是否为空。
• insert：在指定位置插入元素。
• erase：移除指定位置的元素。
• remove：移除所有与指定值相等的元素。
• sort：对元素进行排序。
• merge：合并两个已排序的链表。
• splice：将一个链表中的元素移动到另一个链表中。

3. std::deque

std::deque 是双端队列，可以高效地在头部和尾部进行插入和删除操作。

头文件：<deque>

主要函数：

• push_back：在末尾添加元素。
• push_front：在头部添加元素。
• pop_back：移除末尾元素。
• pop_front：移除头部元素。
• at：访问指定位置的元素，带有边界检查。
• operator[]：访问指定位置的元素，不带边界检查。
• front：访问第一个元素。
• back：访问最后一个元素。
• size：返回元素个数。
• clear：清空所有元素。
• empty：检查容器是否为空。
• insert：在指定位置插入元素。
• erase：移除指定位置的元素。

4. std::map

std::map 是有序关联容器，以键值对的形式存储元素，键是唯一的。

头文件：<map>

主要函数：

• operator[]：访问或插入指定键的元素。
• at：访问指定键的元素，带有边界检查。
• insert：插入键值对。
• erase：移除指定键的元素。
• find：查找指定键的元素。
• count：返回指定键的元素个数（对于map，结果是0或1）。
• size：返回元素个数。
• clear：清空所有元素。
• empty：检查容器是否为空。
• begin：返回指向第一个元素的迭代器。
• end：返回指向最后一个元素后一个位置的迭代器。

5. std::set

std::set 是有序集合容器，只存储键，键是唯一的。

头文件：<set>

主要函数：

• insert：插入元素。
• erase：移除指定元素。
• find：查找指定元素。
• count：返回指定元素的个数（对于set，结果是0或1）。
• size：返回元素个数。
• clear：清空所有元素。
• empty：检查容器是否为空。
• begin：返回指向第一个元素的迭代器。
• end：返回指向最后一个元素后一个位置的迭代器。

6. std::unordered_map

std::unordered_map 是无序关联容器，以键值对的形式存储元素，键是唯一的，内部使用哈希表实现。

头文件：<unordered_map>

主要函数：

• operator[]：访问或插入指定键的元素。
• at：访问指定键的元素，带有边界检查。
• insert：插入键值对。
• erase：移除指定键的元素。
• find：查找指定键的元素。
• count：返回指定键的元素个数（对于unordered_map，结果是0或1）。
• size：返回元素个数。
• clear：清空所有元素。
• empty：检查容器是否为空。
• begin：返回指向第一个元素的迭代器。
• end：返回指向最后一个元素后一个位置的迭代器。

7. std::unordered_set

std::unordered_set 是无序集合容器，只存储键，键是唯一的，内部使用哈希表实现。

头文件：<unordered_set>

主要函数：

• insert：插入元素。
• erase：移除指定元素。
• find：查找指定元素。
• count：返回指定元素的个数（对于unordered_set，结果是0或1）。
• size：返回元素个数。
• clear：清空所有元素。
• empty：检查容器是否为空。
• begin：返回指向第一个元素的迭代器。
• end：返回指向最后一个元素后一个位置的迭代器。

容器特性和使用注意事项

1. std::vector

• 特性：
  • 动态数组，支持快速随机访问。
  • 连续存储，能与 C 风格数组兼容。
  • 在末尾插入和删除操作效率高（摊销时间复杂度 O(1)）。
  • 插入和删除操作会导致内存重新分配和元素拷贝（特别是当容器扩容时）。
• 注意事项：
  • 适用于需要频繁随机访问元素的场景。
  • 避免在中间位置频繁插入和删除元素。

2. std::list

• 特性：
  • 双向链表，支持双向遍历。
  • 插入和删除操作效率高，O(1)。
  • 不支持随机访问，只能通过迭代器遍历。
  • 内存使用相对较高，每个节点需要额外存储两个指针。
• 注意事项：
  • 适用于需要频繁插入和删除元素的场景。
  • 不适用于需要快速随机访问的场景。

3. std::deque

• 特性：
  • 双端队列，支持在两端快速插入和删除。
  • 随机访问效率高，O(1)。
  • 内部由多个连续块组成，分配和管理较为复杂。
• 注意事项：
  • 适用于需要在两端进行插入和删除操作的场景。
  • 插入和删除操作在中间位置的效率相对较低。

4. std::map

• 特性：
  • 有序关联容器，基于红黑树实现。
  • 键值对存储，键是唯一的。
  • 查找、插入、删除操作效率为 O(log n)。
  • 自动按键排序。
• 注意事项：
  • 适用于需要有序存储和快速查找的场景。
  • 不适用于需要频繁插入和删除的场景。

5. std::set

• 特性：
  • 有序集合容器，基于红黑树实现。
  • 只存储键，键是唯一的。
  • 查找、插入、删除操作效率为 O(log n)。
  • 自动按键排序。
• 注意事项：
  • 适用于需要有序存储和快速查找的场景。
  • 不适用于需要频繁插入和删除的场景。

6. std::unordered_map

• 特性：
  • 无序关联容器，基于哈希表实现。
  • 键值对存储，键是唯一的。
  • 查找、插入、删除操作效率平均为 O(1)。
  • 无序存储，插入顺序不定。
• 注意事项：
  • 适用于需要快速查找的场景。
  • 不适用于需要有序存储的场景。

7. std::unordered_set

• 特性：
  • 无序集合容器，基于哈希表实现。
  • 只存储键，键是唯一的。
  • 查找、插入、删除操作效率平均为 O(1)。
  • 无序存储，插入顺序不定。
• 注意事项：
  • 适用于需要快速查找的场景。
  • 不适用于需要有序存储的场景。

对比表格

特性\容器	std::vector	std::list	std::deque	std::map	std::set	std::unordered_map	std::unordered_set
随机访问	高效 (O(1))	不支持	高效 (O(1))	不支持	不支持	高效 (O(1))	高效 (O(1))
插入/删除末尾	高效 (摊销 O(1))	低效 (O(n))	高效 (O(1))	中等 (O(log n))	中等 (O(log n))	高效 (平均 O(1))	高效 (平均 O(1))
插入/删除头部	低效 (O(n))	高效 (O(1))	高效 (O(1))	中等 (O(log n))	中等 (O(log n))	高效 (平均 O(1))	高效 (平均 O(1))
插入/删除中间	低效 (O(n))	高效 (O(1))	低效 (O(n))	中等 (O(log n))	中等 (O(log n))	高效 (平均 O(1))	高效 (平均 O(1))
查找	高效 (O(1))	低效 (O(n))	高效 (O(1))	高效 (O(log n))	高效 (O(log n))	高效 (平均 O(1))	高效 (平均 O(1))
有序性	无序	无序	无序	有序	有序	无序	无序
内存使用	紧凑	高 (额外指针)	较高 (分块)	较高 (树结构)	较高 (树结构)	较高 (哈希表)	较高 (哈希表)
适用场景	频繁随机访问	频繁插入/删除	双端操作频繁	有序存储和快速查找	有序存储和快速查找	快速查找和无序存储	快速查找和无序存储

使用建议

每种容器在不同的场景中都有其优势，选择合适的容器可以大大提升程序的性能和代码的可维护性：

• std::vector：当需要高效的随机访问和动态调整大小时，使用std::vector。适合存储大量数据并且需要频繁遍历的情况。
• std::list：当需要频繁插入和删除元素，尤其是中间位置的元素时，使用std::list。适合实现双向链表。
• std::deque：当需要高效的头部和尾部操作时，使用std::deque。适合实现队列和双端队列。
• std::map：当需要有序存储和快速查找键值对时，使用std::map。适合实现有序关联容器。
• std::set：当需要有序存储唯一元素时，使用std::set。适合实现集合操作。
• std::unordered_map：当需要无序存储和高效查找键值对时，使用std::unordered_map。适合实现哈希表。
• std::unordered_set：当需要无序存储唯一元素时，使用std::unordered_set。适合实现无序集合。