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 也许… 没啥意义 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分配器

得到元素的分配器

参考链接：http://www.jianshu.com/p/392765038d89