容器库
来自cppreference.com
< cpp
容器库是类模板与算法的汇集,允许程序员简单地访问常见数据结构,例如队列、链表和栈。有三类容器——顺序容器、关联容器和无序关联容器——每种都被设计为支持不同组的操作。
容器管理为其元素分配的存储空间,并提供直接或间接地通过迭代器(拥有类似指针属性的对象)访问它们的函数。
大多数容器拥有至少几个常见的成员函数,并共享功能。特定应用的最佳容器不仅依赖于提供的功能,还依赖于对于不同工作量的效率。
顺序容器
顺序容器实现能按顺序访问的数据结构。
(C++11) |
静态的连续数组 (类模板) |
动态的连续数组 (类模板) | |
双端队列 (类模板) | |
(C++11 起) |
单链表 (类模板) |
双链表 (类模板) |
关联容器
关联容器实现能快速查找( O(log n) 复杂度)的数据结构。
唯一键的集合,按照键排序 (类模板) | |
键值对的集合,按照键排序,键是唯一的 (类模板) | |
键的集合,按照键排序 (类模板) | |
键值对的集合,按照键排序 (类模板) |
无序关联容器
无序关联容器提供能快速查找(均摊 O(1) ,最坏情况 O(n) 的复杂度)的无序(哈希)数据结构。
(C++11 起) |
唯一键的集合,按照键生成散列 (类模板) |
(C++11 起) |
键值对的集合,按照键生成散列,键是唯一的 (类模板) |
(C++11 起) |
键的集合,按照键生成散列 (类模板) |
(C++11 起) |
键值对的集合,按照键生成散列 (类模板) |
容器适配器
容器适配器提供顺序容器的不同接口。
适配一个容器以提供栈(LIFO 数据结构) (类模板) | |
适配一个容器以提供队列(FIFO 数据结构) (类模板) | |
适配一个容器以提供优先级队列 (类模板) |
span
span
是相接的对象序列上的非占有视图,某个其他对象占有序列的存储。
(C++20) |
对象的连续序列上的无所有权视图 (类模板) |
迭代器非法化
只读方法决不非法化迭代器或引用。修改容器内容的方法可能非法化迭代器和/或引用,总结于此表格。
类别 | 容器 | 插入后…… | 擦除后…… | 条件 | ||
---|---|---|---|---|---|---|
迭代器合法? | 引用合法? | 迭代器合法? | 引用合法? | |||
顺序容器 | array | N/A | N/A | |||
vector | 否 | N/A | 插入更改容量 | |||
是 | 是 | 被修改元素前 | ||||
否 | 否 | 于被修改元素或其后 | ||||
deque | 否 | 是 | 是,除了被擦除元素 | 修改首或尾元素 | ||
否 | 否 | 仅修改中部 | ||||
list | 是 | 是,除了被擦除元素 | ||||
forward_list | 是 | 是,除了被擦除元素 | ||||
关联容器 | set | 是 | 是,除了被擦除元素 | |||
无序关联容器 | unordered_set | 否 | 是 | 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++11 起) |
成员函数表格
- C++03 起存在的函数 | |
- C++11 起存在的函数 | |
- C++17 起存在的函数 | |
- C++20 起存在的函数 |