1. 空間配置器 分為第一級(jí)空間配置器晚顷，和第二級(jí)空間配置器 配合使用 第一級(jí)空間配置器分配大內(nèi)存大于128bytes粘优， 第二級(jí)分配較小的小于128bytes的

第一級(jí)空間配置器 直接使用malloc分配內(nèi)存啡氢，如果分配成功則返回地址孩等；如果失敗的話斥赋，首先在拋出內(nèi)存不足異常前璃哟，進(jìn)行類似c++的new_handle例程處理氛琢，該例程由程序員給出，查看是否還有可以釋放整理随闪，然后分配的內(nèi)存阳似，如果沒有再拋出異常。

第二級(jí)空間配置器 處理小的內(nèi)存分配铐伴，維護(hù)一個(gè)free_list 空閑待分配內(nèi)存鏈表 撮奏，鏈表連接的空閑內(nèi)存區(qū)以8的倍數(shù)大小存儲(chǔ)，還維護(hù)一個(gè)內(nèi)存池当宴；當(dāng)有內(nèi)存分配請(qǐng)求時(shí)畜吊，首先看是要調(diào)用第一級(jí)還是第二級(jí)空間配置器，當(dāng)需要調(diào)用第二級(jí)空間配置器時(shí)户矢，便在內(nèi)存鏈表尋找最合適的空閑空間返回地址定拟，如果內(nèi)存表沒有合適大小的區(qū)域，就向內(nèi)存池請(qǐng)求分配最接近需求大小的空間若干個(gè)逗嫡，返回給free_list, 并將第一個(gè)分配出去青自，如果內(nèi)存池枯竭，就向系統(tǒng)空間索要新的空閑內(nèi)存區(qū)間作為內(nèi)存池使用驱证，如果沒有則使用第一級(jí)空間配置器延窜，因?yàn)榈谝患?jí)配置器可以進(jìn)行釋放整理內(nèi)存，繼續(xù)在更大范圍內(nèi)尋找空閑內(nèi)存抹锄，如果找不到逆瑞，第一級(jí)內(nèi)存配置器就拋出異常荠藤。

有三個(gè)重要的函數(shù)給容器初始化，復(fù)制获高，移動(dòng)等操作哈肖，如下
uninitialized_copy(iterator first，iterator last念秧，iterator first_new)
對(duì)內(nèi)存操作函數(shù)copy()淤井，進(jìn)行封裝，直接拷貝一塊內(nèi)存區(qū)域的數(shù)據(jù)到另一塊內(nèi)存區(qū)域摊趾，不同的是如果對(duì)象是一個(gè)類币狠，需要用構(gòu)造函數(shù)，則一個(gè)個(gè)copy砾层。具備commit or rollback特點(diǎn)
uninitialized_fill(iterator first漩绵，iterator last，const &T x)
對(duì)內(nèi)存操作函數(shù)fill()肛炮，進(jìn)行封裝止吐，在fiest到last的一塊區(qū)域內(nèi)用x初始化賦值。具備commit or rollback特點(diǎn)侨糟，可以拋出異常
uninitialized_fill_n(iterator first碍扔，size n，const &T x)
對(duì)內(nèi)存操作函數(shù)fill_n()粟害，進(jìn)行封裝蕴忆，在fiest為起始位置的一塊區(qū)域內(nèi)用x初始化賦值。具備commit or rollback特點(diǎn)悲幅，可以拋出異常

2. 迭代器
   STL的中心思想在于：將數(shù)據(jù)和算法分開套鹅，彼此獨(dú)立設(shè)計(jì)，最后再以一貼膠著劑將他們搓合在一起汰具。
   迭代器是一種行為類似指針的對(duì)象卓鹿，而指針的各種行為中最常見的也最重要的便是內(nèi)容提領(lǐng)（dereference）和成員訪問（member access），因此迭代器最重要的編程工作就是對(duì)operator*和operatoe->進(jìn)行重載（overloading）工作留荔。

神器 Traits編程技法
迭代器所指對(duì)象的型別吟孙，稱為該迭代器的value type。
traits就是扮演“特性萃取劑”角色聚蝶，可以讓我們獲取當(dāng)前是什么類型從而去優(yōu)化算法執(zhí)行效率杰妓，在對(duì)這個(gè)型別進(jìn)行構(gòu)造、析構(gòu)碘勉、拷貝巷挥、賦值等操作時(shí)，就可以采取最有效率的措施验靡。比如copy函數(shù)倍宾，如果知道了類型是int 或者char*等基本型雏节，那么可以直接進(jìn)行memove對(duì)內(nèi)存進(jìn)行復(fù)制，執(zhí)行效率非常高高职，而如果是一個(gè)復(fù)雜的類結(jié)構(gòu)钩乍，那么就要調(diào)用相應(yīng)的拷貝構(gòu)造函數(shù)一個(gè)個(gè)進(jìn)行復(fù)制，復(fù)制效率就會(huì)慢很多怔锌。
為了讓這個(gè)traits（特性萃取劑）能夠有效運(yùn)作寥粹，每一個(gè)迭代器必須遵循約定，自行以內(nèi)嵌型別定義的方式定義出相應(yīng)型別产禾。這是一個(gè)約定排作，誰不遵守這個(gè)約定就無法兼容于STL這個(gè)大家庭牵啦。

image.png

個(gè)人覺得trait中首先利用模板的自動(dòng)推導(dǎo)機(jī)制亚情，獲取數(shù)據(jù)類型，然后當(dāng)如果數(shù)據(jù)類型是被修飾符修飾的特殊類型哈雏，那么就使用偏特化的方法楞件，分類定義五種數(shù)據(jù)類型，然后就可以解決裳瘪。
在我理解偏特化土浸，就是有些沒辦法抽象成統(tǒng)一類型，所以就在完全抽象和不抽象之間定義一個(gè)偏特化的概念彭羹，這種方法中一半是完全抽象出來的（比如 基本類型抽象成T）黄伊，另一部分是沒有抽象的（比如 指針 const）。
參考：Traits 詳解

3. 容器總結(jié)
   c++容器包含deque派殷，list还最，queue，priority_queue毡惜，stack拓轻，vector，map经伙，multimap扶叉，set，multiset帕膜，bitset枣氧，forward_list，unordered_map垮刹，unordered_multimap达吞，
   unordered_set，unordered_multiset.

內(nèi)置數(shù)組array和valarray
array 數(shù)組模板 危纫，在C++11中才支持
通用格式：array<類型名, 元素個(gè)數(shù)> 數(shù)組名;
注意宗挥，因?yàn)殚L(zhǎng)度固定乌庶，這里的元素個(gè)數(shù)不能是變量。
長(zhǎng)度固定契耿，提供了更好瞒大、更安全的接口，執(zhí)行效率和內(nèi)置數(shù)組相同搪桂，可以有效替代內(nèi)置數(shù)組
valarray 面向數(shù)值計(jì)算的數(shù)組透敌，在C++11中才支持
支持很多數(shù)值數(shù)組操作，如求數(shù)組總和踢械、最大數(shù)酗电、最小數(shù)等。
這兩個(gè)數(shù)組是c++11 新加入的數(shù)組模板
有一個(gè)slice() 函數(shù)具有腳本語言的靈活性
該類主要配合valarray類使用内列，可以從valarray中提取子數(shù)組
slice( size_t _StartIndex,//截取數(shù)組的開始位置
const valarray<size_t> _Len, //子數(shù)組的最大長(zhǎng)度
const valarray<size_t> _Stride//相隔多少個(gè)元素選中一個(gè)
);

1)vector 相關(guān)操作
vector可以動(dòng)態(tài)擴(kuò)充容量撵术，相較array具有更大的靈活性，在進(jìn)行插入操作時(shí)话瞧，如果只剩一個(gè)空閑位置嫩与，就默認(rèn)擴(kuò)充size為原數(shù)組大小的兩倍，在進(jìn)行數(shù)組拼接時(shí)如果兩倍依然不能滿足所需的數(shù)組空間交排，那就按照需要的大小進(jìn)行擴(kuò)充划滋。
支持增、刪埃篓、插处坪、找、排序架专、拼接操作同窘。

在老的stl中當(dāng)需要擴(kuò)充大小時(shí)，使用復(fù)制構(gòu)造函數(shù)胶征，在最新的stl中擴(kuò)充大小可能會(huì)使用move()塞椎，移動(dòng)復(fù)制函數(shù)，move()相當(dāng)于static_cast(),類型轉(zhuǎn)換為引用睛低。

初始化：
vector<int> v1; //vector元素為 int 型
vector<string> v1(3, "3"); //vector元素為string 型 并初始化三個(gè)元素 都為"3"
vector<node> v1(10); //vector為10個(gè)node元素
vector<int>::iterator it; //定義一個(gè)迭代器
vec.size(); //向量大邪负荨：
vec.max_size();// 向量最大容量：
vec.resize();//更改向量大小：
vec.capacity();//向量真實(shí)大星住：
vec.shrink_to_fit();//減少向量大小到滿足元素所占存儲(chǔ)空間的大新钐： //shrink_to_fit
元素操作：
v1.push_back() //在數(shù)組的最后添加一個(gè)數(shù)據(jù)
v1.pop_back() //去掉數(shù)組的最后一個(gè)數(shù)據(jù)
v1.front() 　　　　//返回第一個(gè)元素(棧頂元素)
v1.begin() //得到數(shù)組頭的指針，用迭代器接受
v1.end() //得到數(shù)組的最后一個(gè)單元+1的指針罩抗，用迭代器接受
v1.clear() // 移除容器中所有數(shù)據(jù)
v1.empty() //判斷容器是否為空
v1.erase(pos) //刪除pos位置的數(shù)據(jù)
v1.erase(beg,end)// 刪除[beg,end)區(qū)間的數(shù)據(jù)
v1.insert(pos,data) //在pos處插入數(shù)據(jù)
vector 沒有查找元素存在性的成員函數(shù)拉庵，請(qǐng)使用順序容器的通用方法。
vector<int> v = { 1, 2, 3, 4 };
auto it_1 = find(v.begin(), v.end(), 1); // it_1 = v.begin();

2)list相關(guān)操作
c++ STL list模板是一個(gè)雙向鏈表

初始化
list<int>a{1,2,3}
list<int>a(n) //聲明一個(gè)n個(gè)元素的列表套蒂，每個(gè)元素都是0
list<int>a(n, m) //聲明一個(gè)n個(gè)元素的列表钞支，每個(gè)元素都是m
list<int>a(first, last) //聲明一個(gè)列表茫蛹，其元素的初始值來源于由區(qū)間所指定的序列中的元素，first和last是迭代器
resize() //調(diào)用resize(n)將list的長(zhǎng)度改為只容納n個(gè)元素烁挟，超出的元素將被刪除婴洼。如果n比list原來的長(zhǎng)度長(zhǎng)，那么默認(rèn)超出的部分元素置為0撼嗓。也可以用resize(n, m)的方式將超出的部分賦值為m柬采。
swap() //交換兩個(gè)鏈表。a.swap(b)和swap(a, b)且警，都可以完成a鏈表和b鏈表的交換粉捻。

assign() //有兩種使用情況：
（1）a.assign(n, val):將a中的所有元素替換成n個(gè)val元素
b中的元素變?yōu)?0, 10, 10, 10, 10
（2）a.assign(b.begin(), b.end())
a中的元素替換為b的
reverse() //可以實(shí)現(xiàn)list的逆置
merge() //a.merge(b) 調(diào)用結(jié)束后b變?yōu)榭眨琣中元素包含原來a和b的元素斑芜。
sort() //給list排序
splice() 實(shí)現(xiàn)list拼接的功能肩刃。將源list的內(nèi)容部分或全部元素刪除，拼插入到目的list押搪。
***********************函數(shù)有以下三種聲明：**************************
一：void splice ( iterator position, list<T,Allocator>& x );
二：void splice ( iterator position, list<T,Allocator>& x, iterator it );
三：void splice ( iterator position, list<T,Allocator>& x, iterator first, iterator last );
****************************解釋：*********************************
position 是要操作的list對(duì)象的迭代器
list&x 被剪的對(duì)象
對(duì)于一：會(huì)在position后把list&x所有的元素到剪接到要操作的list對(duì)象
對(duì)于二：只會(huì)把it的值剪接到要操作的list對(duì)象中
******************對(duì)于三：把first 到 last 剪接到要操作的list對(duì)象中*************************
transfer(iterator position, iterator first, iterator last), //遷移操作 [first, last)內(nèi)的所有元素移動(dòng)到position之前 類似splice() 函數(shù)
swap() //交換兩個(gè)list
unique() //刪除list中重復(fù)的元素
元素操作
push_front(x)：//把元素x推入（插入）到鏈表頭部
push_back(x)：//把元素x推入（插入）到雙向隊(duì)列的尾部
pop_front()：//彈出（刪除）雙向隊(duì)列的第一個(gè)元素

pop_back()：//彈出（刪除）雙向隊(duì)列的最后一個(gè)元素
begin()：//向量中第一個(gè)元素的迭代器
clear()： //清空list中的所有元素树酪。
empty()：//利用empty() 判斷l(xiāng)ist是否為空浅碾。
front()： //獲得list容器中的頭部元素
back()： //獲得list容器的最后一個(gè)元素大州。
insert() ：//在指定位置插入一個(gè)或多個(gè)元素
erase() ： //刪除一個(gè)元素或一個(gè)區(qū)域的元素
rbegin() ：//返回指向第一個(gè)元素的逆向迭代器
remove() ：//從list刪除元素 ，并不是真正的刪除 只是移到鏈表最后垂谢，通過迭代器仍可訪問厦画，真正的移除需要使用erase()函數(shù)
remove_if() ：//按指定條件刪除元素
rend() ： //指向list末尾的逆向迭代器

3)deque queue stack相關(guān)操作

• STL中沒有queue和stack容器，都是以deque為基礎(chǔ)的container adapter（配接器）
• c++ STL中deque是雙向開口的連續(xù)線性空間滥朱，即可以再deque兩端分別進(jìn)行插入刪除操作根暑，其余操作與vector相似，可以動(dòng)態(tài)擴(kuò)充徙邻，但實(shí)現(xiàn)方式完全不一樣
• queue是一端只能進(jìn)一端只能出的隊(duì)列排嫌，實(shí)現(xiàn)先進(jìn)先出的功能，沒有遍歷操作
• stack是進(jìn)出都在一端的棧缰犁，實(shí)現(xiàn)先進(jìn)后出的功能淳地，沒有遍歷操作
  這樣基于deque就很容易實(shí)現(xiàn)queue和stack的功能。這里重點(diǎn)記一下deque的實(shí)現(xiàn)方式

dueue 是一段一段的定量連續(xù)空間帅容。一旦有必要就可以在deque的前端或尾端增加新空間颇象。deque通過控制分段的連續(xù)空間使整體連續(xù)，使用了復(fù)雜的迭代器結(jié)構(gòu)并徘。deque采用一塊所謂的map（其實(shí)就是一個(gè)指針數(shù)組）遣钳，每個(gè)元素都是指針，指向一段連續(xù)性的線性空間麦乞，稱為緩沖區(qū)蕴茴，緩沖區(qū)是deque的儲(chǔ)存空間主體（默認(rèn)是512 bytes）劝评。
在增加元素時(shí)，判斷頭指針和尾指針?biāo)诘膍ap節(jié)點(diǎn)指向的緩沖區(qū)是否還有備用空間倦淀，如果有則插入付翁，調(diào)整緩沖區(qū)的狀態(tài)，沒有的話重?fù)Q一個(gè)map節(jié)點(diǎn)晃听，然后調(diào)整緩沖區(qū)的狀態(tài)百侧，如果沒有多余的map節(jié)點(diǎn)，就重新整治map能扒，重新?lián)Q一個(gè)map佣渴，就像vector數(shù)組容量不足時(shí)的操作一樣。先申請(qǐng)更大的map空間初斑，將原map內(nèi)容拷貝過來辛润，釋放原map，設(shè)定新的map的起始地址與大小见秤。

deque的map圖解.png

4)heap 和 priority_queue
大頂堆 任意一個(gè)根節(jié)點(diǎn)都比子節(jié)點(diǎn)的元素大
小頂堆 任意一個(gè)根節(jié)點(diǎn)都比子節(jié)點(diǎn)的元素小
完全二叉樹 以數(shù)組的形式進(jìn)行存儲(chǔ)（下標(biāo)從1開始）砂竖，下標(biāo)為i的節(jié)點(diǎn)的左葉子節(jié)點(diǎn)為（2 * i）,右葉子節(jié)點(diǎn)為（2*i + 1），父節(jié)點(diǎn)為（i / 2）

有三個(gè)heap算法

• push_heap()

新加入的元素放在數(shù)組最末端然后上溯直到尋找到合適的位置鹃答，滿足堆得條件約束

• pop_heap()

將第一個(gè)元素與最后一個(gè)元素互換位置乎澄，然后讓下標(biāo)為1的元素下溯直到尋找到合適的位置，滿足堆得條件約束测摔。

• sort_heap()

進(jìn)行多次pop_heap()置济，就可以將一個(gè)以數(shù)組形式存儲(chǔ)的完全堆二叉樹，排序锋八，如24浙于，21，16挟纱，19羞酗，13 sort_heap()之后變成13，16紊服，19檀轨，21，24围苫。

• make_heap()

進(jìn)行多次push_heap()裤园，將一個(gè)無序數(shù)組變成heap形式存儲(chǔ)在一維數(shù)組中，如13剂府，16拧揽，19胡桃，21掠抬，24， sort_heap()之后變成24，21桅打，16砍的，19拭嫁，13 惕医。

priority_queue就是利用上面heap的方式，具有heap特性的隊(duì)列烦周，插入的數(shù)據(jù)以優(yōu)先級(jí)的方式排序尽爆，每次插入和取出也都要是以優(yōu)先級(jí)為依據(jù)。

以上是序列化容器读慎，接下來是關(guān)聯(lián)式容器 分為兩大類
一類是以樹漱贱，二叉樹，平衡二叉樹夭委，紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)的關(guān)聯(lián)式容器有map幅狮， set， mutlimap株灸， mutliset崇摄；
另一類是以hashtable 為底層數(shù)據(jù)結(jié)構(gòu)的hash_map， hash_set慌烧， hash_mutlimap逐抑， hash_mutliset

第一類 以樹結(jié)構(gòu)為底層數(shù)據(jù)結(jié)構(gòu)的map， set杏死， mutlimap泵肄， mutliset；

• 二叉搜索樹
  任何一個(gè)節(jié)點(diǎn)的鍵值一定大于其左子樹中的每一個(gè)節(jié)點(diǎn)的鍵值淑翼，并小于其右子樹中每一個(gè)節(jié)點(diǎn)的鍵值
• 平衡二叉搜索樹
  由于二叉搜索樹可能出現(xiàn)所有節(jié)點(diǎn)都在一邊的情況，導(dǎo)致查找效率再次變成O(n)品追，所以引入平衡二叉樹的概念玄括，使得可以保持某種程度的平衡，一般而言其搜尋時(shí)間可節(jié)省25%左右肉瓦。比如AVL tree就是一種額外加了平衡條件的二叉搜索樹遭京。
• AVL tree
  其平衡條件的建立是為了保持整棵樹的深度在為O(logN)，要求任何節(jié)點(diǎn)的左右子樹高度相差最多一泞莉。
  平衡被破壞的四種條件
  （1）插入點(diǎn)位于X的左子節(jié)點(diǎn)的左子樹——左左——單旋一次 不平衡節(jié)點(diǎn)向右旋轉(zhuǎn)一次
  （2）插入點(diǎn)位于X的左子節(jié)點(diǎn)的右子樹——左右——雙旋轉(zhuǎn) 不平衡節(jié)點(diǎn)的下一級(jí)節(jié)點(diǎn)先向左旋轉(zhuǎn)一次哪雕，不平衡節(jié)點(diǎn)再向右旋轉(zhuǎn)一次
  （3）插入點(diǎn)位于X的右子節(jié)點(diǎn)的左子樹——右左——雙旋轉(zhuǎn) 不平衡節(jié)點(diǎn)的下一級(jí)節(jié)點(diǎn)先向右旋轉(zhuǎn)一次，不平衡節(jié)點(diǎn)再向左旋轉(zhuǎn)一次
  （4）插入點(diǎn)位于X的右子節(jié)點(diǎn)的右子樹——右右——單旋一次 不平衡節(jié)點(diǎn)向左旋轉(zhuǎn)一次
• 紅黑樹

STL唯一實(shí)現(xiàn)的一種搜尋樹鲫趁，作為關(guān)聯(lián)式容器的底部機(jī)制之用斯嚎。不僅在樹形的平衡上表現(xiàn)的不錯(cuò)，在效率表現(xiàn)和實(shí)現(xiàn)復(fù)雜度上也保持相當(dāng)?shù)钠胶狻?br> 滿足以下四個(gè)規(guī)則
（1）每個(gè)節(jié)點(diǎn)不是紅色就是黑色
（2）根節(jié)點(diǎn)為黑色
（3）節(jié)點(diǎn)為紅，子節(jié)點(diǎn)必須為黑（不能有連續(xù)出現(xiàn)的紅色相連接堡僻，黑色可以）
（4）任一節(jié)點(diǎn)至NULL（樹尾端）的任何路徑糠惫，所含之黑節(jié)點(diǎn)數(shù)必須相同。

插入節(jié)點(diǎn)步驟
假設(shè)我們插入的新節(jié)點(diǎn)為 X
1 .將新插入的節(jié)點(diǎn)標(biāo)記為紅色
2 .如果 X 是根結(jié)點(diǎn)(root)钉疫，則標(biāo)記為黑色
3 .如果 X 的 parent 不是黑色硼讽，同時(shí) X 也不是 root:
----3.1 如果 X 的 uncle (叔叔) 是紅色
--------3.1.1 將 parent 和 uncle 標(biāo)記為黑色
--------3.1.2 將 grand parent (祖父) 標(biāo)記為紅色
--------3.1.3 讓 X 節(jié)點(diǎn)的顏色與 X 祖父的顏色相同，然后重復(fù)步驟 2牲阁、3
９谈蟆！城菊！這里面可能會(huì)涉及到和AVL tree相同的四種旋轉(zhuǎn)您炉，見下
參考紅黑樹詳解

插入節(jié)點(diǎn)后保持二叉樹符合紅黑樹規(guī)則的偽代碼

x->color = red
while(x!=root 并且 x->parent->color==red)
{
    //新節(jié)點(diǎn)為父節(jié)點(diǎn)之左子節(jié)點(diǎn)
    if(x->parent==x->parent->parent->left)
    {
        //y等于伯父節(jié)點(diǎn)
        y=x->parent->parent->right;
        //如果伯父節(jié)點(diǎn)存在且為紅色
        if(y && y->color==red)
        {
            //更改祖父節(jié)點(diǎn)的子節(jié)點(diǎn)為黑色 祖父節(jié)點(diǎn)為紅色； 
            x->parent->color=red;
            y->color=red;
            //x上溯 
            x=x->parents
        }
        else  //無伯父節(jié)點(diǎn) 或伯父節(jié)點(diǎn)為黑
        {
            if(x==x->parent->right)
            {
                x=x->parent;
                //左旋
                rotate_left(x);
                
            }
            x->parent->color=black;
            x->parent->parent->color=red;
            //右旋
            rotate_right(x->parent->parent);
        }
    }
    else  //父節(jié)點(diǎn)為祖父節(jié)點(diǎn)之右子節(jié)點(diǎn)
    {
        //y等于伯父節(jié)點(diǎn)
        y=x->parent->parent->right;
        //如果伯父節(jié)點(diǎn)存在且為紅色
        if(y && y->color==red)
        {
            //更改祖父節(jié)點(diǎn)的子節(jié)點(diǎn)為黑色 祖父節(jié)點(diǎn)為紅色役电； 
            x->parent->color=red;
            y->color=red;
            //x上溯 
            x=x->parents
        }
        else  //無伯父節(jié)點(diǎn) 或伯父節(jié)點(diǎn)為黑
        {
            if(x==x->parent->right)
            {
                x=x->parent;
                //左旋
                rotate_right(x);
                
            }
            x->parent->color=black;
            x->parent->parent->color=red;
            //右旋
            rotate_left(x->parent->parent);
        }
    }
} //while 結(jié)束
root->color=black;

set容器

set的特性是赚爵，所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序，STL提供了一組set/mutliset相關(guān)算法法瑟，包括交集（set_intersection）冀膝、聯(lián)集（set_union）、差集（set_difference）霎挟、對(duì)稱差集（set_symmetric_difference）窝剖。
標(biāo)準(zhǔn)STL Set 即以RB-tree為底層機(jī)制。

常用操作
begin() 　　 ,返回set容器的第一個(gè)元素
end() 　　　　 ,返回set容器的最后一個(gè)元素
clear() 　　 ,刪除set容器中的所有的元素
empty() 　　　,判斷set容器是否為空
max_size() 　 ,返回set容器可能包含的元素最大個(gè)數(shù)
size() 　　　　 ,返回當(dāng)前set容器中的元素個(gè)數(shù)
rbegin　　　　 ,返回的值和end()相同
rend()　　　　 ,返回的值和rbegin()相同
count() 用來查找set中某個(gè)某個(gè)鍵值出現(xiàn)的次數(shù)酥夭。這個(gè)函數(shù)在set并不是很實(shí)用赐纱，因?yàn)橐粋€(gè)鍵值在set只可能出現(xiàn)0或1次，這樣就變成了判斷某一鍵值是否在set出現(xiàn)過了熬北。
equal_range() 疙描，返回一對(duì)定位器，分別表示第一個(gè)大于或等于給定關(guān)鍵值的元素和 第一個(gè)大于給定關(guān)鍵值的元素讶隐，這個(gè)返回值是一個(gè)pair類型起胰，如果這一對(duì)定位器中哪個(gè)返回失敗，就會(huì)等于end()的值巫延。
erase(iterator) ,刪除定位器iterator指向的值
erase(first,second),刪除定位器first和second之間的值
erase(key_value),刪除鍵值key_value的值
find() 效五，返回給定值值得定位器，如果沒找到則返回end()炉峰。
insert(key_value); 將key_value插入到set中 畏妖，返回值是pair<set<int>::iterator,bool>，bool標(biāo)志著插入是否成功疼阔，而iterator代表插入的位置戒劫，若key_value已經(jīng)在set中半夷，則iterator表示的key_value在set中的位置。
inset(first,second);將定位器first到second之間的元素插入到set中谱仪，返回值是void.
lower_bound(key_value) 玻熙，返回第一個(gè)大于等于key_value的定位器
upper_bound(key_value)，返回最后一個(gè)大于key_value的定位器

map容器

map的特性是所有元素都會(huì)根據(jù)鍵值自動(dòng)排序疯攒。map的所有元素都是pair嗦随，同時(shí)擁有實(shí)值和鍵值，map不允許兩個(gè)元素?fù)碛邢嗤逆I值
標(biāo)準(zhǔn)STL map即以RB-tree為底層機(jī)制

常用操作
begin() 返回指向map頭部的迭代器
clear(） 刪除所有元素
count() 返回指定元素出現(xiàn)的次數(shù)
empty() 如果map為空則返回true
end() 返回指向map末尾的迭代器
rbegin() 返回一個(gè)指向map尾部的逆向迭代器
rend() 返回一個(gè)指向map頭部的逆向迭代器
size() 返回map中元素的個(gè)數(shù)
equal_range() 返回特殊條目的迭代器對(duì)
erase() 刪除一個(gè)元素
find() 查找一個(gè)元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比較元素key的函數(shù)
lower_bound() 返回鍵值>=給定元素的第一個(gè)位置
upper_bound() 返回鍵值>給定元素的第一個(gè)位置
max_size() 返回可以容納的最大元素個(gè)數(shù)
swap() 交換兩個(gè)map
value_comp() 返回比較元素value的函數(shù)
map.count(key) 返回?fù)碛心?key 的元素個(gè)數(shù)(0 or 1)
map.find(key) 返回鍵等于 key 的元素的迭代器敬尺，如果 map 中不存在該 key枚尼，返回
map.at(key) 返回鍵等于 key 的元素的鍵值 value，如果 map 中不存在該 key砂吞，運(yùn)行時(shí)會(huì)拋出異常std::out_of_range
map[key] 訪問鍵值為key的元素

mutliset和mutlimap

mutliset與set操作完全相同署恍，唯一的差別在于他允許元素值重復(fù)，因此它的插入操作采用的是底層機(jī)制RB-tree的insert_equal()而非insert_unique()蜻直；

mutlimap與map操作完全相同盯质，唯一的差別在于他允許鍵值重復(fù)，因此它的插入操作采用的是底層機(jī)制RB-tree的insert_equal()而非insert_unique()概而；

第二類 以hash_table為底層數(shù)據(jù)結(jié)構(gòu)的hash_map呼巷， hash_set， hash_mutlimap赎瑰， hash_mutliset王悍；

• hash_table

使用某種映射函數(shù)，負(fù)責(zé)將某一元素映射為一個(gè)"大小可接受之索引"餐曼，這樣的函數(shù)稱為hash function（散列函數(shù)）压储。使用hash function會(huì)帶來一個(gè)問題：可能有不同的元素被映射到相同的位置。這邊是“碰撞”問題源譬，解決碰撞問題的方法有許多種集惋，包括線性探測(cè)、二次探測(cè)瓶佳、開鏈等做法芋膘。

負(fù)載系數(shù)： 意指元素個(gè)數(shù)除以表格大小。元素系數(shù)永遠(yuǎn)在0~1之間——除非采用開鏈策略霸饲。

• 線性探測(cè)

比如，取模計(jì)算元素下標(biāo)臂拓，如果重復(fù)就順延一個(gè)位置厚脉，到最后就從頭開始，直到尋找到空位胶惰。
問題：容易產(chǎn)生主集團(tuán)傻工，及大面積位置因?yàn)轫樠拥膯栴}而被占用。

• 二次探測(cè)

比如，取模計(jì)算元素下標(biāo)中捆，如果重復(fù)按照公式F(i)=i^2鸯匹，順延到下一個(gè)位置，到最后就從頭開始泄伪，直到尋找到空位殴蓬。這主要用于解決線性探測(cè)易產(chǎn)生主集團(tuán)的問題。
問題：容易產(chǎn)生次集團(tuán)蟋滴，兩個(gè)元素京hash function計(jì)算出來的位置若相同染厅，則插入時(shí)所探測(cè)的位置也相同，形成某種浪費(fèi)津函。消除次集團(tuán)的方法也有肖粮，比如復(fù)式散列。

一般為了避免探測(cè)次數(shù)過多尔苦，使表格大小為質(zhì)數(shù)

• 開鏈

這種做法是在每一個(gè)表格元素中維護(hù)一個(gè)list涩馆，hash function為我們分配某一個(gè)list，然后我們?cè)谀莻€(gè)list身上執(zhí)行元素的插入允坚、搜尋魂那、刪除等操作。

STL中的hash_table采用的開鏈法解決碰撞問題的

hash_table中使用vector數(shù)組以利動(dòng)態(tài)擴(kuò)充屋讶，然后每個(gè)元素是一個(gè)鏈表冰寻，不是STL鏈表，就是自定義的單向鏈表皿渗。
其中使用的hash function 可以自定義斩芭，在<stl_hash_func.h>中也提供了數(shù)個(gè)現(xiàn)成的hash function，但是這其中只能對(duì)int乐疆，long划乖， short，char挤土，const char格式的數(shù)據(jù)進(jìn)行hash琴庵。double，float仰美，string無法使用STL中提供的hash function進(jìn)行hash迷殿，需要自己提供。*

hash_set容器

hash_set是以hashtable為底層機(jī)制咖杂，所供應(yīng)的操作接口都是轉(zhuǎn)調(diào)用hashtable的操作行為庆寺；以RB-tree為底層機(jī)制的set容器有自動(dòng)排序功能而hash_set沒有。hashtable無法處理的型別诉字，hash_set也無法處理懦尝。

常用操作：
函數(shù)接口與set相似

hash_map容器

hash_map是以hashtable為底層機(jī)制知纷，所供應(yīng)的操作接口都是轉(zhuǎn)調(diào)用hashtable的操作行為；以RB-tree為底層機(jī)制的map容器有自動(dòng)排序功能而hash_map沒有陵霉。hashtable無法處理的型別琅轧，hash_map也無法處理。

常用操作：
函數(shù)接口與map相似

hash_mutliset和hash_mutlimap

hash_mutliset與hash_set操作完全相同踊挠，唯一的差別在于他允許元素值重復(fù)乍桂，因此它的插入操作采用的是底層機(jī)制hash_table的insert_equal()而非insert_unique()；

hash_mutlimap與hash_map操作完全相同止毕，唯一的差別在于他允許鍵值重復(fù)模蜡，因此它的插入操作采用的是底層機(jī)制hash_table的insert_equal()而非insert_unique()；

STL算法

C++ STL算法一般都包含多個(gè)版本扁凛，必如比較大小的sort算法忍疾，就可以自定義比較函數(shù)
作為仿函數(shù)（functor）傳遞進(jìn)去。再比如質(zhì)變算法（下面提及什么是質(zhì)變）一般都會(huì)提供兩個(gè)版本：一個(gè)是if-in place（就地進(jìn)行版）谨朝；一個(gè)是copy版（另地進(jìn)行）卤妒，先復(fù)制一份副本，然后在副本上進(jìn)行修改并返回副本字币。copy版一般就是replace_copy后綴加上copy则披，但也有一些算法沒有copy版，必如sort洗出，需要自己復(fù)制一份副本士复。

總攬

非質(zhì)變算法（nonmutating algorithms）意思是不改變操作對(duì)象之值
所有泛型算法的前兩個(gè)參數(shù)都是一對(duì)迭代器利耍。簡(jiǎn)倉(cāng)稱為first和last蚌本，用以表示算法的操作區(qū)間。STL習(xí)慣采用前閉后開表示法隘梨，寫成 [first程癌，last)， 表示區(qū)間涵蓋first至last（不含last）之間的所有元素轴猎。當(dāng)first==last時(shí)席楚，上述所表現(xiàn)的便是一個(gè)空區(qū)間

數(shù)值算法 <numeric> 實(shí)現(xiàn)于 <stl_numeric.h>

accumulate 累加運(yùn)算

image.png

版本二多一個(gè)二元操作運(yùn)算，傳入一個(gè)運(yùn)算符（BinaryOperation binary_op）就可以實(shí)現(xiàn)多種累計(jì)運(yùn)算税稼，如傳入乘法烦秩，就可以計(jì)算累乘。

基本算法 <stl_algobase.h>

fill_n()郎仆， 將[first只祠， last)內(nèi)的前n個(gè)元素該填新值，返回的迭代器指向被填入的最后一個(gè)元素的下一個(gè)位置

image.png

那么就會(huì)有一個(gè)問題扰肌？如果n超越了容器的現(xiàn)有大小抛寝，會(huì)造成什么結(jié)果？
從源碼容易知道曙旭，由于每次迭代進(jìn)行的都是assignment操作盗舰，是一種覆寫（overwrite）操作，所以一旦操作區(qū)間超越容器大小桂躏，就會(huì)造成不可預(yù)期的結(jié)果钻趋。解決辦法之一是，利用insert（）產(chǎn)生一個(gè)具有插入（insert）而非覆寫（overwrite）能力的迭代器剂习。inserter（）可產(chǎn)生一個(gè)用來修飾迭代器的配接器（iterator adapter）蛮位。用法如下：

int ia[3]={0, 1, 2};
vector<int> iv(ia, ia+3);
fill_n(inserter(iv.begin()), 5, 7);

copy 復(fù)制一段區(qū)間的內(nèi)容到另一端

image.png

通過上面一層層的調(diào)用，最后達(dá)到匹配使用最優(yōu)的函數(shù)完成復(fù)制的功能鳞绕，以達(dá)到最高的效率失仁。復(fù)制時(shí)有可能出現(xiàn)目標(biāo)區(qū)域與源區(qū)域重疊的部分，那就看調(diào)用哪個(gè)函數(shù)了们何，如果調(diào)用的是memove就不會(huì)對(duì)結(jié)果產(chǎn)生什么影響萄焦，因?yàn)閙emove是先保存一個(gè)副本再進(jìn)行復(fù)制的，所以不會(huì)弄臟原來的內(nèi)容冤竹。
在參數(shù)的層層傳遞中拂封，通過利用traits技巧判斷元素型別，而最終決定該調(diào)用哪一個(gè)copy函數(shù)贴见。

image.png

image.png

image.png

image.png

image.png

image.png

image.png

仿函數(shù) （函數(shù)對(duì)象）

仿函數(shù)是將“function call 操作符”重載烘苹，的一種class，任何算法接受仿函數(shù)作為參數(shù)時(shí)片部，總是在演算過程中調(diào)用仿函數(shù)的operator()

仿函數(shù)的作用是將某種“操作”當(dāng)做算法的參數(shù)镣衡，一般的做法是將該“操作”設(shè)計(jì)為一個(gè)函數(shù)，再將函數(shù)指針當(dāng)做算法的一個(gè)參數(shù)档悠。但由于函數(shù)指針不能滿足STL對(duì)抽像性的要求廊鸥，也不能讓滿足軟件積木的要求——函數(shù)指針無法和其他組件（如配接器）搭配，產(chǎn)生更靈活的變化辖所。
在STL中使用仿函數(shù)的做法惰说，叫做函數(shù)對(duì)象更加貼切一點(diǎn)，仿函數(shù)就語言層面而言是個(gè)class缘回，再以該仿函數(shù)產(chǎn)生一個(gè)對(duì)象吆视，并以此對(duì)象作為算法的一個(gè)參數(shù)典挑。

image.png

image.png

可配接（Adaptable）的關(guān)鍵
STL仿函數(shù)也有能力被函數(shù)配接器修飾，為了擁有配接能力啦吧，每一個(gè)仿函數(shù)必須定義自己的相應(yīng)型別您觉，就像迭代器如果要融入整個(gè)STL大家庭，也必須依照規(guī)定定義自己的5個(gè)相應(yīng)型別授滓。這些型別是為了讓配接器能夠取出琳水，獲得仿函數(shù)的某些信息。相應(yīng)型別都是一些typedef般堆，所以必要操作在編譯期就全部完成了在孝，對(duì)程序的執(zhí)行效率沒有任何影響，不帶來任何額外負(fù)擔(dān)淮摔。
為方便起見私沮，<stl_function.h>定義了兩個(gè)classes，分別代表一元仿函數(shù)和二元仿函數(shù)（STL不支持三元仿函數(shù)）噩咪，其中沒有成員變量和成員函數(shù)顾彰，只有一些型別定義。任何仿函數(shù)胃碾，只要一個(gè)人需求選擇繼承其中一個(gè)class涨享，便自動(dòng)擁有了那些相應(yīng)型別，也就自動(dòng)擁有了配接能力仆百。

• unary_function
  用來呈現(xiàn)一元函數(shù)的參數(shù)型別和回返值型別厕隧，定義如下

//STL規(guī)定，每一個(gè)Adaptable Unary Function都應(yīng)該繼承此類別
template <class Arg, class Result>
struct unary_function
{
typedef Arg argument_type;
typedef Result result_type;
}

實(shí)現(xiàn)一個(gè)仿函數(shù)如下俄周，示例

//以下仿函數(shù)繼承unary_function
template <class T>
struct negate:public unary_function<T,T>
{
T operator()(const T& x) const {return -x;}
}
//以下配接器用來表示某個(gè)仿函數(shù)的邏輯負(fù)值
template <class Predicate>
class unary_negate
...
public:
   bool operator() (const typename Predicate::argunment_type& x) const 
{
...
};

• binary_function
  用來呈現(xiàn)二元函數(shù)的參數(shù)型別和回返值型別吁讨，定義如下：

//STL規(guī)定，每一個(gè)Adaptable Binary Function都應(yīng)該繼承此類別
template <class Arg1, class Arg2, class Result>
struct binary_function
{
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
}

示例與unary_function相似峦朗，見上述用法建丧。

用法示例

image.png

配接器

配接器（adapters）在STL組件的靈活組合運(yùn)用功能上，扮演著軸承波势、轉(zhuǎn)換器的角色翎朱。Adapter這個(gè)概念，事實(shí)上是一種設(shè)計(jì)模式尺铣。

配接器在STL中有以下三種應(yīng)用

• 應(yīng)用于容器 container adapters

STL提供的兩個(gè)容器queue和stack拴曲，其實(shí)都是配接器。他們修飾deque的接口而成就出另一種容器風(fēng)貌凛忿。

• 應(yīng)用于迭代器 iterator adapters

STL提供許多應(yīng)用于迭代器身上的配接器澈灼，包括insert iterator，reverse iterators，iostream iterator叁熔。
insert iterator委乌，可以將一般迭代器的賦值操作轉(zhuǎn)變?yōu)椴迦氩僮鳌１热缯甙蹋瑢Ｋ疚捕瞬迦氩僮鞯腷ack_insert_iterator福澡；專司頭端插入操作的front_insert_iterator；以及可從任意位置執(zhí)行插入操作的insert_iterator

image.png

reverse iterator驹马，可以將一般迭代器的行進(jìn)方向逆轉(zhuǎn)，使原本應(yīng)該前進(jìn)的operator++操作變成后退操作除秀。這種倒轉(zhuǎn)筋脈的性質(zhì)運(yùn)用在“從尾端開始進(jìn)行”的算法上糯累，有很大的方便性。
iostream iterator册踩，可以將迭代器綁定到某個(gè)iostream對(duì)象身上泳姐。綁定到istream對(duì)象（例如std::cin）身上的，稱為ostream_iterator暂吉，擁有輸出功能胖秒。

image.png

示例

image.png

image.png

• 應(yīng)用于仿函數(shù) functor adapters

functor adapters(亦稱為function adapters)是所有配接器中數(shù)量最龐大的一個(gè)族群，其配接靈活度也是前二者所不能及慕的⊙指危可以多次疊加配接。這些配接操作包括系結(jié)（bind）肮街、否定（negate）风题、組合（compose）、以及對(duì)一般函數(shù)或者成員函數(shù)的修飾（使其成為一個(gè)仿函數(shù)）嫉父。
functor adapters的價(jià)值在于沛硅，通過它們之間的綁定、組合绕辖、修飾能力摇肌。幾乎可以無限制地創(chuàng)造出各種可能的表達(dá)式。例如：

image.png

由于仿函數(shù)就是將function call操作符重載的一種class仪际，而任何孫發(fā)就受一個(gè)仿函數(shù)時(shí)围小，總是在其演算過程中調(diào)用該仿函數(shù)的operator（），這使得不具備仿函數(shù)之形弟头、卻有真函數(shù)之實(shí)的“一般函數(shù)”和“成員函數(shù)”得以無縫隙地與其它配接器或算法結(jié)合起來吩抓。
請(qǐng)注意，所有期望獲得配接能力的組件赴恨，本身都必須是可配接的疹娶，換句話說，一元函數(shù)必須繼承自u(píng)nary_function伦连，二元函數(shù)必須繼承自binary_function雨饺，成員函數(shù)必須以mem_fun處理過钳垮。一個(gè)未經(jīng)ptr_fun處理過的一般函數(shù)，雖然也可以函數(shù)指針的形式傳遞給STL算法使用额港，卻無法擁有任何配接能力饺窿。

image.png