容器库

容器库是类模板与算法的汇集，允许程序员简单地访问常见数据结构，例如队列、链表和栈。有三类容器——顺序容器、关联容器和无序关联容器——每种都被设计为支持不同组的操作。

容器管理为其元素分配的存储空间，并提供直接或间接地通过迭代器（拥有类似指针属性的对象）访问它们的函数。

大多数容器拥有至少几个常见的成员函数，并共享功能。特定应用的最佳容器不仅依赖于提供的功能，还依赖于对于不同工作量的效率。

目录 1 顺序容器 2 关联容器 3 无序关联容器 4 容器适配器 5 span 6 迭代器非法化 7 线程安全 8 成员函数表格

顺序容器

顺序容器实现能按顺序访问的数据结构。

array (C++11)	静态的连续数组 (类模板)
vector	动态的连续数组 (类模板)
deque	双端队列 (类模板)
forward_list (C++11 起)	单链表 (类模板)
list	双链表 (类模板)

关联容器

关联容器实现能快速查找（ O(log n) 复杂度）的数据结构。

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

无序关联容器

无序关联容器提供能快速查找（均摊 O(1) ，最坏情况 O(n) 的复杂度）的无序（哈希）数据结构。

unordered_set (C++11 起)	唯一键的集合，按照键生成散列 (类模板)
unordered_map (C++11 起)	键值对的集合，按照键生成散列，键是唯一的 (类模板)
unordered_multiset (C++11 起)	键的集合，按照键生成散列 (类模板)
unordered_multimap (C++11 起)	键值对的集合，按照键生成散列 (类模板)

容器适配器

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

stack	适配一个容器以提供栈（LIFO 数据结构） (类模板)
queue	适配一个容器以提供队列（FIFO 数据结构） (类模板)
priority_queue	适配一个容器以提供优先级队列 (类模板)

span

span 是相接的对象序列上的非占有视图，某个其他对象占有序列的存储。

span (C++20)

对象的连续序列上的无所有权视图 (类模板)

迭代器非法化

只读方法决不非法化迭代器或引用。修改容器内容的方法可能非法化迭代器和/或引用，总结于此表格。

类别	容器	插入后……		擦除后……		条件
		迭代器合法？	引用合法？	迭代器合法？	引用合法？
顺序容器	array	N/A		N/A
	vector	否		N/A		插入更改容量
		是		是		被修改元素前
		否		否		于被修改元素或其后
	deque	否	是	是，除了被擦除元ç´		修改首或尾元ç´
			否	否		仅修改中部
	list	是		是，除了被擦除元ç´
	forward_list	是		是，除了被擦除元ç´
关联容器	set multiset map multimap	是		是，除了被擦除元ç´
无序关联容器	unordered_set unordered_multiset unordered_map unordered_multimap	否	是	N/A		插入导致重哈希
		是		是，除了被擦除元ç´		无重哈希

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

• 插入方法的例子是 std::set::insert 、 std::map::emplace 、 std::vector::push_back å’Œ std::deque::push_front 。
  • 注意 std::unordered_map::operator[] 也算，因为它可能插入元素到 map 中。

• 擦除方法的例子是 std::set::erase 、 std::vector::pop_back 、 std::deque::pop_front å’Œ std::map::clear 。
  • clear 非法化所有迭代器和引用。因为它擦除所有元素，这在技术上遵照上述规则。

尾后迭代器需要特别留意。通常像指向未被擦除元素的正常迭代器一般非法化此迭代器。故 std::set::end 决不被非法化， std::unordered_set::end 仅在重哈希时被非法化， 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++ 标准库函数不修改对象，除非这些对象能直接或间接地经由函数参数，包含 this 指针访问。 同一容器中不同元素能由不同线程同时修改，除了 std::vector<bool> 的元素（例如， std::future 对象的 vector 能从多个线程接收值）。 迭代器操作（例如自增迭代器）读但不修改底层容器，而且能与同一容器上的其他迭代器操作同时由 const 成员函数执行。非法化任何迭代器的容器操作修改容器，且不能与任何在既存迭代器上的操作同时执行，即使这些迭代器未被非法化。 同一容器上的元素可以同时由不指定为访问这些元素的函数修改。更广泛而言， C++ 标准库函数不间接读取能从其参数访问的对象（包含容器的其他对象），除非其规定要求如此。 任何情况下，容器操作（还有算法，或其他 C++ 标准库函数）可于内部并行化，只要不更改用户可见的结果（例如 std::transform 可并行化，但指定了按顺序观览序列的每个元素的 std::for_each 不行）

(C++11 èµ·)

成员函数表格

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