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