C++標(biāo)準(zhǔn)庫(kù)(STL)中的容器
1. 序列容器
容器里的元素是有位置的,有前有后
1.1. array
靜態(tài)連續(xù)數(shù)組.
C++11中新增.
大小是固定的,不能改變.
和C語(yǔ)言中本來(lái)支持的數(shù)組[]特性類(lèi)似;
支持隨機(jī)存取, 支持容器都支持的迭代器操作,支持判斷數(shù)組中元素的數(shù)量等操作;
1.2. vector
動(dòng)態(tài)連續(xù)數(shù)組.
大小可變
使用的內(nèi)存是連續(xù)的.
所以支持隨機(jī)存取
在末端的增刪操作性能好,但是中間的插入刪除性能差.
1.3 deque
雙頭隊(duì)列;
可在頭部和尾部插入刪除;
使用的內(nèi)存是不連續(xù)的, 但是一段一段的;
隨機(jī)存取時(shí)間復(fù)雜度為o(1);
頭尾插入刪除基本也是o(1);
插入刪除任意元素是o(n);
1.4 forward_list
單向鏈表;
c++11中新增;
不支持隨機(jī)存取;
列表里增加,刪除,移動(dòng)一個(gè)元素, 不會(huì)使得指向其他元素的迭代器失效, 只會(huì)使自己失效;
1.5 list
雙向鏈表
插入刪除元素常量時(shí)間;
增加, 刪除, 移動(dòng)元素, 不會(huì)使得其他元素的迭代器失效;
2. 關(guān)聯(lián)容器
關(guān)聯(lián)容器里的值,都按照某種規(guī)則(元素值的大小)進(jìn)行了排序;
2.1 set
集合
包含的都是關(guān)鍵字, 每個(gè)都是唯一的;
搜索, 刪除 , 插入的時(shí)間復(fù)雜度是o(log(n))
2.2 map
映射
包含的元素都是關(guān)鍵字-值, 按照關(guān)鍵字進(jìn)行了排序
搜索, 刪除, 插入的時(shí)間復(fù)雜度是o(log(n))
常用紅黑樹(shù)實(shí)現(xiàn);
2.3 multiset
可重復(fù)集合;
可以有等值的元素存在;
c++11中新增;
等值的元素, 按照插入順序;
2.4 multimap
可重復(fù)映射
包含的元素中, 允許關(guān)鍵字相等
c++11中新增;
關(guān)鍵字等值的元素, 按照插入順序;
3. 無(wú)序關(guān)聯(lián)容器
容器中的值, 不進(jìn)行排序;
都是c++11中新增
3.1 unordered_set
無(wú)序集合;
等值的元素唯一;
搜索, 插入, 刪除的時(shí)間復(fù)雜度為常量;
3.2 unordered_map
無(wú)序映射;
關(guān)鍵字等值的元素唯一;
搜索, 插入, 刪除的時(shí)間復(fù)雜度為常量;
3.3 unordered_multiset
無(wú)序的可重復(fù)集合
可以容納等值的元素
元素不排序
搜索,插入,刪除的時(shí)間復(fù)雜度為常量
3.4 unordered_multimap
無(wú)序可重復(fù)映射
可以容納關(guān)鍵字等值的元素;
不排序;
搜索, 插入, 刪除的時(shí)間復(fù)雜度為常量;
4. 容器適配器
為序列容器提供了不一樣的接口
4.1 stack
LIFO棧
4.2 queue
FIFO隊(duì)列
4.3 priority_queue
隊(duì)列的第一個(gè)元素總是最大的那個(gè)
5. 容器的線(xiàn)程安全性
總體來(lái)說(shuō), 容器的線(xiàn)程安全是不靠譜的, 專(zhuān)家們說(shuō), 別靠容器自己來(lái)保證線(xiàn)程安全.
- 對(duì)于不同的線(xiàn)程,可以同時(shí)用任何函數(shù)(不是成員函數(shù)哦)訪問(wèn)不同的容器(似乎有些廢話(huà));
- 對(duì)于不同的線(xiàn)程,可以同時(shí)訪問(wèn)相同容器的只讀成員函數(shù);
- 不同的線(xiàn)程, 可以同時(shí)修改同一容器中的不同元素, 除了vector<bool>
- 也許... 沒(méi)啥意義
- 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 容器成員函數(shù)的分類(lèi)
6.1 構(gòu)造類(lèi)函數(shù)
構(gòu)造函數(shù)
析構(gòu)函數(shù)
賦值運(yùn)算符
assign方法
6.2 迭代器函數(shù)
頭 begin
尾 end
常量頭 cbegin
常量尾 cend
逆頭 rbegin
常量逆頭 crbegin
逆尾 rend
常量逆尾 crend
6.3 訪問(wèn)元素
at
[]
front() 第一個(gè)
back() 最后一個(gè)
6.4 容量
判斷空 empty
元素?cái)?shù)量 size
容器最大允許的元素?cái)?shù)量 max_size
重設(shè)元素?cái)?shù)量 resize
capacity 已經(jīng)分配的內(nèi)存
調(diào)整內(nèi)存 reverse
讓容量匹配元素?cái)?shù)量 shrink_to_fit
6.5 修改
清空 clear
插入 insert
直接在某位置構(gòu)造并插入 emplace
直接在某位置構(gòu)造并插入, 而且別自動(dòng)排序 emplace_hint
刪除迭代器指定的元素 erase
在最前壓入 push_front
直接構(gòu)造并在最前壓入 emplace_front
從前面彈出 pop_front
從后面壓入 push_back
直接構(gòu)造并在最后壓入 emplace_back
從后面彈出 pop_back
交換兩個(gè)容器的內(nèi)容 swap
6.7 列表操作
合并 merge
切割 splice
移除元素 remove
移除符合條件的元素 remove_if
反序 reverse
清除重復(fù)元素 unique
按照增序排序 sort
6.8 查找
等值計(jì)數(shù) count
查找 find
查找比某個(gè)元素大的第一個(gè)元素位置 lower_bound
查找比某個(gè)元素小的第一個(gè)元素的位置 upper_bound
找到等值序列 equal_range
6.9 觀察者
得到鍵比較函數(shù)
得到值比較函數(shù)
得到哈希函數(shù)
得到鍵相等函數(shù)
6.10分配器
得到元素的分配器
最終是一張大表:
Bitmap 2.png
