C++ STL中常见的容器

概要

C++ 标准库（STL，Standard Template Library）提供了多种容器，每种容器都有其特定的用途和特点。以下是一些常用的 STL 容器及其简要说明。

顺序容器

• std::vector:

• • 动态数组，可以在尾部高效地添加和删除元素，支持随机访问。
• • 存储在连续的内存块中，具有较好的缓存局部性。

• std::deque:

• • 双端队列，允许在两端高效地插入和删除元素。
• • 内部实现为多个块，适合需要频繁在两端操作的场景。

• std::list:

• • 双向链表，允许在任意位置高效地插入和删除元素。
• • 不支持随机访问，适合频繁插入和删除操作。

• std::forward_list:

• • 单向链表，与 std::list 类似，但只支持向前遍历。
• • 占用内存较少，适合只需要单向遍历的场景。

• std::array:

• • 固定大小的数组，具有与原生数组相似的性能，但提供了 STL 的接口和功能。
• • 大小在编译时确定，不支持动态扩展。

关联容器

• std::set:

• • 存储唯一元素的集合，元素按特定顺序排列（通常是升序）。
• • 支持快速查找、插入和删除操作（O(log n)）。

• std::multiset:

• • 类似于 set，但允许存储重复元素。
• • 也支持按顺序排列元素。

• std::map:

• • 存储键值对，键是唯一的，按键的顺序排列。
• • 支持快速查找和插入（O(log n)），适合需要键值关联的场景。

• std::multimap:

• • 类似于 map，但允许键重复。
• • 适合需求中键可能重复的情况。

无序关联容器

• std::unordered_set:

• • 存储唯一元素的集合，元素无序存储。
• • 基于哈希表实现，查找、插入和删除操作平均时间复杂度为 O(1)。

• std::unordered_multiset:

• • 类似于 unordered_set，但允许存储重复元素。

• std::unordered_map:

• • 存储键值对，键是唯一的，元素无序存储。
• • 基于哈希表实现，支持平均 O(1) 的查找、插入和删除操作。

• std::unordered_multimap:

• • 类似于 unordered_map，但允许键重复。

参考

https://www.runoob.com/cplusplus/cpp-libs-deque.html