C++标准库(STL)中的容器
1. 序列容器
容器里的元素是有位置的,有前有后
1.1. array
静态连续数组.
C++11中新增.
大小是固定的,不能改变.
和C语言中本来支持的数组[]特性类似;
支持随机存取, 支持容器都支持的迭代器操作,支持判断数组中元素的数量等操作;
1.2. vector
动态连续数组.
大小可变
使用的内存是连续的.
所以支持随机存取
在末端的增删操作性能好,但是中间的插入删除性能差.
1.3 deque
双头队列;
可在头部和尾部插入删除;
使用的内存是不连续的, 但是一段一段的;
随机存取时间复杂度为o(1);
头尾插入删除基本也是o(1);
插入删除任意元素是o(n);
1.4 forward_list
单向链表;
c++11中新增;
不支持随机存取;
列表里增加,删除,移动一个元素, 不会使得指向其他元素的迭代器失效, 只会使自己失效;
1.5 list
双向链表
插入删除元素常量时间;
增加, 删除, 移动元素, 不会使得其他元素的迭代器失效;
2. 关联容器
关联容器里的值,都按照某种规则(元素值的大小)进行了排序;
2.1 set
集合
包含的都是关键字, 每个都是唯一的;
搜索, 删除 , 插入的时间复杂度是o(log(n))
2.2 map
映射
包含的元素都是关键字-值, 按照关键字进行了排序
搜索, 删除, 插入的时间复杂度是o(log(n))
常用红黑树实现;
2.3 multiset
可重复集合;
可以有等值的元素存在;
c++11中新增;
等值的元素, 按照插入顺序;
2.4 multimap
可重复映射
包含的元素中, 允许关键字相等
c++11中新增;
关键字等值的元素, 按照插入顺序;
3. 无序关联容器
容器中的值, 不进行排序;
都是c++11中新增
3.1 unordered_set
无序集合;
等值的元素唯一;
搜索, 插入, 删除的时间复杂度为常量;
3.2 unordered_map
无序映射;
关键字等值的元素唯一;
搜索, 插入, 删除的时间复杂度为常量;
3.3 unordered_multiset
无序的可重复集合
可以容纳等值的元素
元素不排序
搜索,插入,删除的时间复杂度为常量
3.4 unordered_multimap
无序可重复映射
可以容纳关键字等值的元素;
不排序;
搜索, 插入, 删除的时间复杂度为常量;
4. 容器适配器
为序列容器提供了不一样的接口
4.1 stack
LIFO栈
4.2 queue
FIFO队列
4.3 priority_queue
队列的第一个元素总是最大的那个
5. 容器的线程安全性
总体来说, 容器的线程安全是不靠谱的, 专家们说, 别靠容器自己来保证线程安全.
- 对于不同的线程,可以同时用任何函数(不是成员函数哦)访问不同的容器(似乎有些废话);
- 对于不同的线程,可以同时访问相同容器的只读成员函数;
- 不同的线程, 可以同时修改同一容器中的不同元素, 除了vector<bool>
- 也许... 没啥意义
- Elements of the same container can be modified concurrently with those member functions that are not specified to access these elements. More generally, the C++ standard library functions do not read objects indirectly accessible through their arguments (including other elements of a container) except when required by its specification.
- In any case, container operations (as well as algorithms, or any other C++ standard library functions) may be parallelized internally as long as this does not change the user-visible results (e.g. std::transform may be parallelized, but not std::for_each which is specified to visit each element of a sequence in order)
6 容器成员函数的分类
6.1 构造类函数
构造函数
析构函数
赋值运算符
assign方法
6.2 迭代器函数
头 begin
尾 end
常量头 cbegin
常量尾 cend
逆头 rbegin
常量逆头 crbegin
逆尾 rend
常量逆尾 crend
6.3 访问元素
at
[]
front() 第一个
back() 最后一个
6.4 容量
判断空 empty
元素数量 size
容器最大允许的元素数量 max_size
重设元素数量 resize
capacity 已经分配的内存
调整内存 reverse
让容量匹配元素数量 shrink_to_fit
6.5 修改
清空 clear
插入 insert
直接在某位置构造并插入 emplace
直接在某位置构造并插入, 而且别自动排序 emplace_hint
删除迭代器指定的元素 erase
在最前压入 push_front
直接构造并在最前压入 emplace_front
从前面弹出 pop_front
从后面压入 push_back
直接构造并在最后压入 emplace_back
从后面弹出 pop_back
交换两个容器的内容 swap
6.7 列表操作
合并 merge
切割 splice
移除元素 remove
移除符合条件的元素 remove_if
反序 reverse
清除重复元素 unique
按照增序排序 sort
6.8 查找
等值计数 count
查找 find
查找比某个元素大的第一个元素位置 lower_bound
查找比某个元素小的第一个元素的位置 upper_bound
找到等值序列 equal_range
6.9 观察者
得到键比较函数
得到值比较函数
得到哈希函数
得到键相等函数
6.10分配器
得到元素的分配器
最终是一张大表:
Bitmap 2.png
