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分配器

得到元素的分配器

最终是一张大表: