Containers library

容器库是一个类模板与算法的通用集合，使程序员能够轻松实现队列、列表和栈等常见数据结构。容器共分为 两类 (C++11前) 三类 (C++11起) ：

• 序列容器，
• 关联容器，

无序关联容器，

(since C++11)

每一种都旨在支持不同的操作集合。

容器管理为其元素分配的存储空间，并提供成员函数以直接或通过迭代器（具有类似指针特性的对象）来访问这些元素。

大多数容器至少拥有几个共同的成员函数，并共享功能特性。选择最适合特定应用的容器不仅要考虑其提供的功能，还要考量其在不同工作负载下的运行效率。

目录 1 序列容器 2 关联容器 3 无序关联容器 (since C++11) 4 容器适配器 5 视图 (since C++20) 6 迭代器失效 7 线程安全 8 函数表 8.1 成员函数表 8.2 非成员函数表 9 缺陷报告 10 另请参阅

顺序容器

序列容器实现了可以按顺序访问的数据结构。

array (C++11)	固定大小的就地连续数组 (类模板)
vector	可调整大小的连续数组 (类模板)
inplace_vector (C++26)	可调整大小、固定容量、就地连续数组 (类模板)
hive (C++26)	复用已删除元素内存的集合 (类模板)
deque	双端队列 (类模板)
forward_list (C++11)	单向链表 (类模板)
list	双向链表 (类模板)

关联容器

关联式容器实现了可快速搜索（ O(log n) 复杂度）的排序数据结构。

set	唯一键的集合，按键排序 (类模板)
map	键值对集合，按键排序，键唯一 (类模板)
multiset	键的集合，按键排序 (类模板)
multimap	键值对集合，按键排序 (类模板)

无序关联容器 (since C++11)

无序关联容器实现了未排序（哈希）数据结构，能够快速检索（平均时间复杂度 O(1) ，最坏情况 O(n) 复杂度）。

unordered_set (C++11)	唯一键的集合，通过键进行哈希 (类模板)
unordered_map (C++11)	键值对的集合，通过键进行哈希，键唯一 (类模板)
unordered_multiset (C++11)	键的集合，通过键进行哈希 (类模板)
unordered_multimap (C++11)	键值对的集合，通过键进行哈希 (类模板)

容器适配器

容器适配器为顺序容器提供了不同的接口。

stack	适配容器以提供栈（后进先出数据结构） (类模板)
queue	适配容器以提供队列（先进先出数据结构） (类模板)
priority_queue	适配容器以提供优先队列 (类模板)
flat_set (C++23)	适配容器以提供按键排序的唯一键集合 (类模板)
flat_map (C++23)	适配两个容器以提供按键排序的键值对集合 (类模板)
flat_multiset (C++23)	适配容器以提供按键排序的键集合 (类模板)
flat_multimap (C++23)	适配两个容器以提供按键排序的键值对集合 (类模板)

视图 (始于 C++20)

视图提供了灵活的机制，用于通过非拥有元素数组的一维或多维视图进行交互操作。

span (C++20)	对连续对象序列的非拥有视图 (类模板)
mdspan (C++23)	多维非拥有数组视图 (类模板)

迭代器失效

只读方法从不会 使迭代器或引用失效 。修改容器内容的方法可能会使迭代器和/或引用失效，如下表所示。

分类	容器	插入 操作后...		擦除 操作后...		条件说明
		迭代器 是否有效？	引用 是否有效？	迭代器 是否有效？	引用 是否有效？
序列容器	array	不适用		不适用
	vector	否		不适用		插入操作导致容量改变
		是		是		位于被修改元素之前 （对于插入操作仅当容量未改变时）
		否		否		位于被修改元素处或之后
	deque	否	是	是，除被擦除元素外		修改首元素或尾元素
			否	否		仅修改中间元素
	list	是		是，除被擦除元素外
	forward_list	是		是，除被擦除元素外
关联式容器	set multiset map multimap	是		是，除被擦除元素外
无序关联式容器	unordered_set unordered_multiset unordered_map unordered_multimap	否	是	不适用		插入操作引发重哈希
		是		是，除被擦除元素外		未发生重哈希

本小节内容不完整 原因：需要补充C++23“扁平”适配器（ std::flat_set 等）的迭代器失效说明

本小节内容不完整 原因：需补充C++26 std::inplace_vector 的迭代器失效说明

此处， 插入 指代任何向容器添加一个或多个元素的方法，而 擦除 指代任何从容器移除一个或多个元素的方法。

• 插入方法的示例包括 std::set::insert 、 std::map::emplace 、 std::vector::push_back 和 std::deque::push_front 。

注意 std::unordered_map::operator[] 同样需要计数，因为它可能向映射中插入元素。

(since C++11)

• 擦除方法的示例包括 std::set::erase 、 std::vector::pop_back 、 std::deque::pop_front 和 std::map::clear 。
  • clear 会使所有迭代器和引用失效。由于它会擦除所有元素，这在技术上符合上述规则。

除非另有说明（通过显式声明或通过其他函数定义函数），将容器作为参数传递给库函数永远不会使指向该容器内对象的迭代器失效，也不会更改这些对象的值。

尾后迭代器值得特别说明。通常这类迭代器的失效规则与指向未被删除元素的普通迭代器相同。因此 std::set::end 永远不会失效 ， std::unordered_set::end 仅在重哈希时失效 (C++11 起) ， std::vector::end 总是会失效（因为它始终位于被修改元素之后），依此类推。

存在一个例外情况：删除 std::deque 最后一个元素的擦除操作 确实会 使尾后迭代器失效，即使该迭代器并非容器的被擦除元素（或根本不是一个元素）。结合 std::deque 迭代器的通用规则，最终结果是：唯一不会使 std::deque::end 失效的修改操作是仅删除首元素（而非末元素）的擦除操作。

线程安全性 所有容器函数都可以被不同线程在不同容器上并发调用。更一般地说，C++标准库函数不会读取其他线程可访问的对象，除非这些对象可以通过函数参数（包括this指针）直接或间接访问。 所有 const 成员函数都可以被不同线程在同一容器上并发调用。此外，成员函数 begin() 、 end() 、 rbegin() 、 rend() 、 front() 、 back() 、 data() 、 find() 、 lower_bound() 、 upper_bound() 、 equal_range() 、 at() 以及（关联容器除外） operator[] 在线程安全方面表现为 const （即它们也可以被不同线程在同一容器上并发调用）。更一般地说，C++标准库函数不会修改对象，除非这些对象可以通过函数的非const参数（包括this指针）直接或间接访问。 同一容器中的不同元素可以被不同线程并发修改，但 std::vector<bool> 的元素除外（例如，一个 std::future 对象的向量可以从多个线程接收值）。 迭代器操作（例如递增迭代器）读取但不修改底层容器，并且可以与同一容器上其他迭代器的操作、const成员函数或元素读取操作并发执行。使任何迭代器失效的容器操作会修改容器，并且不能与现有迭代器上的任何操作并发执行，即使这些迭代器不会失效。 同一容器的元素可以与那些未指定访问这些元素的成员函数并发修改。更一般地说，C++标准库函数不会读取通过其参数（包括容器的其他元素）间接访问的对象，除非其规范要求这样做。 在任何情况下，只要不改变用户可见的结果，容器操作（以及算法或任何其他C++标准库函数）都可以在内部并行化（例如 std::transform 可以并行化，但 std::for_each 不行，因为它被指定要按顺序访问序列中的每个元素）。

(C++11 起)

函数表

注意： std::basic_string 在标准中虽未被视作容器，但由于其相似性，其行为与容器极为相似。为方便起见，此处将其列为“伪容器”。

	- C++03 中存在的函数
	- C++11 起存在的函数
	- C++17 起存在的函数
	- C++20 起存在的函数
	- C++23 起存在的函数

本节内容不完整 原因：需补充 C++26 "color" 并为 std::inplace_vector 填充成员/非成员函数表

成员函数表

• 注意：两条不同 extract 行中的函数具有不同的含义和语法：

1. ↑ 例如： node_type extract ( const_iterator ) 或 node_type extract ( Key & )
2. ↑ 例如： container_type extract ( ) &&

非成员函数表

< 、 <= 、 > 、 >= 和 != 运算符分别由 operator <=> 和 operator == 自动合成。

(since C++20)

缺陷报告

以下行为变更缺陷报告被追溯应用于先前发布的C++标准。

DR	适用范围	发布时的行为	正确行为
LWG 51	C++98	容器迭代器可能被任意库操作 置为无效	仅在明确规定时 才会置为无效

参见

C++ 命名要求：

• 容器
• 顺序容器
• 连续容器
• 可逆容器
• 关联容器
• 分配器感知容器
• 无序关联容器

valarray	数值数组、数组掩码和数组切片 (类模板)
basic_string	存储和操作字符序列 (类模板)
basic_string_view (C++17)	只读字符串视图 (类模板)