介紹一下STL

Standard Template Library糊昙，標(biāo)準(zhǔn)模板庫(kù)揭鳞，是C++的標(biāo)準(zhǔn)庫(kù)之一迟几，一套基于模板的容器類庫(kù)酿箭，還包括許多常用的算法，提高了程序開發(fā)和復(fù)用垃你，有相同的接口，利用使用和閱讀喂很。
基本組件
容器（container）惜颇、迭代器（iterator）、函數(shù)對(duì)象（function object）少辣、算法（algorithm）凌摄。在STL里，我們用容器來裝東西（數(shù)據(jù)內(nèi)容）漓帅，用迭代器來訪問他們锨亏，將他們傳送到使用到的算法里，而算法的調(diào)用在函數(shù)對(duì)象里完成的忙干。
容器：容納器予、包含一組元素的對(duì)象。順序容器順序訪問捐迫、隨機(jī)訪問其中的元素乾翔；關(guān)聯(lián)容器通過優(yōu)化關(guān)鍵值訪問。
迭代器：提供一種順序訪問容器中每個(gè)元素的方法施戴。

迭代器分類

1. 空間配置器：內(nèi)存池實(shí)現(xiàn)小塊內(nèi)存分配,對(duì)應(yīng)到設(shè)計(jì)模式--單例模式（工具類罚勾，提供服務(wù)毅人，一個(gè)程序只需要一個(gè)空間配置器即可）吭狡，享元模式（小塊內(nèi)存統(tǒng)一由內(nèi)存池進(jìn)行管理）
   2.迭代器：迭代器模式，模板方法
   3.容器：STL的核心之一丈莺，其他組件圍繞容器進(jìn)行工作：迭代器提供訪問方式划煮，空間配置器提供容器內(nèi)存分配，算法對(duì)容器中數(shù)據(jù)進(jìn)行處理缔俄，仿函數(shù)偽算法提供具體的策略弛秋，類型萃取　　實(shí)現(xiàn)對(duì)自定義類型內(nèi)部類型提取。保證算法覆蓋性俐载。其中涉及到的設(shè)計(jì)模式：組合模式（樹形結(jié)構(gòu)）蟹略，門面模式（外部接口提供），適配器模式（stack遏佣，queue通過deque適配得到）挖炬，建造者模式（不同類型樹的建立過程）。
   4.類型萃茸瓷簟：基于范型編程的內(nèi)部類型解析意敛，通過typename獲取√懦妫可以獲取迭代器內(nèi)部類型value_type,Poter,Reference等草姻。
   5.仿函數(shù)：一種類似于函數(shù)指針的可回調(diào)機(jī)制，用于算法中的決策處理走敌。涉及：策略模式碴倾，模板方法。
   6適配器：STL中的stack掉丽，queue通過雙端隊(duì)列deque適配實(shí)現(xiàn)跌榔，map，set通過RB-Tree適配實(shí)現(xiàn)捶障。涉及適配器模式僧须。

泛型程序設(shè)計(jì)

概念：不依賴于具體數(shù)據(jù)類型的設(shè)計(jì)。
將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽離出來项炼，C++的模板是它的關(guān)鍵基礎(chǔ)担平。

選擇容器準(zhǔn)則

Level 1 - 僅僅作為Map使用:采用靜態(tài)數(shù)組
Level 2 - 保存定長(zhǎng)數(shù)據(jù)，使用時(shí)也是全部遍歷:采用動(dòng)態(tài)數(shù)組(長(zhǎng)度一開始就固定的話靜態(tài)數(shù)組也行)
Level 3 - 保存不定長(zhǎng)數(shù)組锭部，需要?jiǎng)討B(tài)增加的能力暂论，側(cè)重于尋找數(shù)據(jù)的速度:采用vector
Level 3 - 保存不定長(zhǎng)數(shù)組，需要?jiǎng)討B(tài)增加的能力拌禾，側(cè)重于增加刪除數(shù)據(jù)的速度:采用list
Level 4 - 對(duì)數(shù)據(jù)有復(fù)雜操作取胎，即需要前后增刪數(shù)據(jù)的能力，又要良好的數(shù)據(jù)訪問速度:采用deque
Level 5 - 對(duì)數(shù)據(jù)中間的增刪操作比較多:采用list，建議在排序的基礎(chǔ)上闻蛀，批量進(jìn)行增刪可以對(duì)運(yùn)行效率提供最大的保證
Level 6 - 上述中找不到適合的:組合STL容器或者自己建立特殊的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)

C++ STL 的實(shí)現(xiàn)：

1.vector： 底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組 匪傍，支持快速隨機(jī)訪問。
2.list： 底層數(shù)據(jù)結(jié)構(gòu)為雙向鏈表觉痛，支持快速增刪役衡。
3.deque： 底層數(shù)據(jù)結(jié)構(gòu)為一個(gè)中央控制器和多個(gè)緩沖區(qū)，詳細(xì)見STL源碼剖析P146薪棒，支持首尾（中間不能）快速增刪手蝎，也支持隨機(jī)訪問。
4.stack ： 底層一般用23實(shí)現(xiàn)俐芯，封閉頭部即可柑船，不用vector的原因應(yīng)該是容量大小有限制，擴(kuò)容耗時(shí)
5.queue： 底層一般用23實(shí)現(xiàn)泼各，封閉頭部即可，不用vector的原因應(yīng)該是容量大小有限制亏拉，擴(kuò)容耗時(shí)（stack和queue其實(shí)是適配器,而不叫容器扣蜻，因?yàn)槭菍?duì)容器的再封裝）
6.priority_queue： 的底層數(shù)據(jù)結(jié)構(gòu)一般為vector為底層容器，堆heap為處理規(guī)則來管理底層容器實(shí)現(xiàn)
7.set： 底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹及塘，有序莽使，不重復(fù)。
8.multiset： 底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹笙僚，有序芳肌，可重復(fù)。
9.map： 底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹肋层，有序亿笤，不重復(fù)。
10.multimap： 底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹栋猖，有序净薛，可重復(fù)。
11.hash_set： 底層數(shù)據(jù)結(jié)構(gòu)為hash表蒲拉，無序肃拜，不重復(fù)。
12.hash_multiset： 底層數(shù)據(jù)結(jié)構(gòu)為hash表雌团，無序燃领，可重復(fù) 。
13.hash_map ： 底層數(shù)據(jù)結(jié)構(gòu)為hash表锦援，無序猛蔽，不重復(fù)。
14.hash_multimap： 底層數(shù)據(jù)結(jié)構(gòu)為hash表雨涛，無序枢舶，可重復(fù)懦胞。

順序容器

std::vector的底層（存儲(chǔ)）機(jī)制
vector就是一個(gè)動(dòng)態(tài)數(shù)組，里面有一個(gè)指針指向一片連續(xù)的內(nèi)存空間凉泄，當(dāng)空間不夠裝下數(shù)據(jù)時(shí)躏尉，會(huì)自動(dòng)申請(qǐng)另一片更大的空間（一般是增加當(dāng)前容量的50%或100%），然后把原來的數(shù)據(jù)拷貝過去后众，接著釋放原來的那片空間胀糜；當(dāng)釋放或者刪除里面的數(shù)據(jù)時(shí)，其存儲(chǔ)空間不釋放蒂誉，僅僅是清空了里面的數(shù)據(jù)教藻。
std::vector的自增長(zhǎng)機(jī)制
當(dāng)已經(jīng)分配的空間不夠裝下數(shù)據(jù)時(shí)，分配雙倍于當(dāng)前容量的存儲(chǔ)區(qū)右锨，把當(dāng)前的值拷貝到新分配的內(nèi)存中括堤，并釋放原來的內(nèi)存。
說說std::list的底層（存儲(chǔ)）機(jī)制
以結(jié)點(diǎn)為單位存放數(shù)據(jù)绍移，結(jié)點(diǎn)的地址在內(nèi)存中不一定連續(xù)悄窃，每次插入或刪除一個(gè)元素，就配置或釋放一個(gè)元素空間
什么情況下用vector蹂窖，什么情況下用list
vector可以隨機(jī)存儲(chǔ)元素（即可以通過公式直接計(jì)算出元素地址轧抗，而不需要挨個(gè)查找），但在非尾部插入刪除數(shù)據(jù)時(shí)瞬测，效率很低横媚，適合對(duì)象簡(jiǎn)單，對(duì)象數(shù)量變化不大月趟，隨機(jī)訪問頻繁灯蝴。
list不支持隨機(jī)存儲(chǔ)，適用于對(duì)象大狮斗，對(duì)象數(shù)量變化頻繁绽乔，插入和刪除頻繁。
list自帶排序函數(shù)的排序原理
將前兩個(gè)元素合并碳褒，再將后兩個(gè)元素合并折砸，然后合并這兩個(gè)子序列成4個(gè)元素的子序列，重復(fù)這一過程沙峻，得到8個(gè)睦授，16個(gè)，...摔寨，子序列去枷，最后得到的就是排序后的序列。
時(shí)間復(fù)雜度：O(nlgn)

void List::sort()
{
    List carry;
    List counter[64];  //數(shù)組元素為鏈表
    int fill = 0;
    while (head->next != tail)
    {
        carry.transfer(carry.getHead()->next, head->next, head->next->next); //head是哨兵，不存放有效值
                                                                             //head->next元素被移走删顶，所以while循環(huán)不需要head=head->next;
        int i = 0;
        while (i < fill && counter[i].getHead()->next != counter[i].getHead())//counter[i]不是空
        {
            counter[i].merge(carry);
            carry.swap(counter[i++]);
        }
        carry.swap(counter[i]);
        if (i == fill) ++fill;
    }
    for (int i = 1; i < fill; i++)
        counter[i].merge(counter[i - 1]);   //通過這個(gè)實(shí)現(xiàn)排序（將有序的鏈表合成一個(gè)新的有序鏈表）
    swap(counter[fill - 1]);
}

說說std::deque的底層機(jī)制
deque動(dòng)態(tài)地以分段連續(xù)空間組合而成竖螃，隨時(shí)可以增加一段新的連續(xù)空間并鏈接起來。不提供空間保留功能逗余。
注意：除非必要特咆，我們盡可能選擇使用vector而非deque，因?yàn)閐eque的迭代器比vector迭代器復(fù)雜很多录粱。對(duì)deque排序腻格，為了提高效率，可先將deque復(fù)制到一個(gè)vector上排序啥繁，然后再?gòu)?fù)制回deque菜职。
deque采用一塊map（不是STL的map容器）作為主控，其為一小塊連續(xù)空間旗闽，其中每個(gè)元素都是指針酬核，指向另一段較大的連續(xù)空間（緩沖區(qū)）。
deque的迭代器包含4個(gè)內(nèi)容：
1）cur：迭代器當(dāng)前所指元素
2）first：此迭代器所指的緩沖區(qū)的頭适室。
3）last：緩沖區(qū)尾愁茁。
4）node：指向管控中心。
** deque與vector的區(qū)別**
1）vector是單向開口的連續(xù)線性空間亭病，deque是雙向開口的連續(xù)線性空間。（雙向開口是指可以在頭尾兩端分別做元素的插入和刪除操作）嘶居。
2）deque沒有提供空間保留功能罪帖，而vector則要提供空間保留功能。
3）deque也提供隨機(jī)訪問迭代器邮屁，但是其迭代器比vector迭代器復(fù)雜很多整袁。
不允許有遍歷行為的容器有哪些（不提供迭代器
1）queque，除了頭部外佑吝，沒有其他方法存取deque的其他元素坐昙。
2）stack（底層以deque實(shí)現(xiàn)），除了最頂端外芋忿，沒有任何其他方法可以存取stack的其他元素炸客。
3）heap，所有元素都必須遵循特別的排序規(guī)則戈钢，不提供遍歷功能痹仙。
vector插入刪除和list的區(qū)別
vector插入和刪除數(shù)據(jù)，需要對(duì)現(xiàn)有數(shù)據(jù)進(jìn)行復(fù)制移動(dòng)殉了，如果vector存儲(chǔ)的對(duì)象很大或者構(gòu)造函數(shù)很復(fù)雜开仰，則開銷較大，如果是簡(jiǎn)單的小數(shù)據(jù)，效率優(yōu)于list众弓。
list插入和刪除數(shù)據(jù)恩溅，需要對(duì)現(xiàn)有數(shù)據(jù)進(jìn)行遍歷，但在首部插入數(shù)據(jù)谓娃，效率很高脚乡。

舉例實(shí)現(xiàn)vector

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
void printf(vector<int> v);

int main()
{
    vector<int> vec;
    vec.push_back(23);
    vec.push_back(24);
    printf(vec);

    vector<int>::iterator p;
    p=vec.begin();
    *p=69;
    *(p+1)=74;
    *(p+2)=89;
    printf(vec);
    vec.pop_back();
    int i=0;
    while(i<vec.size())
        cout<<vec[i]<<" "<<endl;
    vec[3]=1000;
    while(i<vec.size())
        cout<<vec[i]<<" "<<endl;
    sort(vec.begin(),vec.end());
    return 0;
}

void printf(vector<int> v)
{
    cout<<"這個(gè)向量的大小為"<<v.size()<<endl;
    vector<int>::iterator p ;
    for(p = v.begin();p!=v.end();p++)
    {
        cout<<*p<<" "<<endl;
    }
    return;
}

擴(kuò)展當(dāng)vector的內(nèi)存用完了，它是如何動(dòng)態(tài)擴(kuò)展內(nèi)存的傻粘？它是怎么釋放內(nèi)存的每窖？用clear可以釋放掉內(nèi)存嗎？是不是線程安全的弦悉？

STL如何實(shí)現(xiàn)list

STL如何實(shí)現(xiàn)deque

關(guān)聯(lián)容器

標(biāo)準(zhǔn)關(guān)聯(lián)容器set, multiset, map, multimap內(nèi)部采用的一種非常高效的平衡檢索二叉樹:紅黑樹窒典，也稱為RB樹(Red-BlackTree)。RB樹的統(tǒng)計(jì)性能要好于一般的 平衡二叉樹
STL map和set的使用雖不復(fù)雜稽莉，但也有一些不易理解的地方
如:
map: type [pair] <constKey, T> 瀑志，很多不同的 constKey 對(duì)應(yīng)的 T 對(duì)象的一個(gè)集合，所有的記錄集中只要 const Key 不一樣就可以污秆， T 無關(guān)! set: type const Key. 只存單一的對(duì) const Key 劈猪，沒有 map 的 T 對(duì)像!可以看成 map 的一個(gè)特例
為何map和set的插入刪除效率比用其他序列容器高?
答:因?yàn)閷?duì)于關(guān)聯(lián)容器來說，不需要做內(nèi)存拷貝和內(nèi)存移動(dòng)良拼。map和set容器內(nèi)所有元素都是以節(jié)點(diǎn)的方式來存儲(chǔ)战得，其節(jié)點(diǎn)結(jié)構(gòu)和鏈表差不多，指向父節(jié)點(diǎn)和子節(jié)點(diǎn)
為何每次insert之后庸推，以前保存的iterator不會(huì)失效?
答:iterator這里就相當(dāng)于指向節(jié)點(diǎn)的指針常侦，內(nèi)存沒有變，指向內(nèi)存的指針怎么會(huì)失效呢(當(dāng)然被刪除的那個(gè)元素本身已經(jīng)失效了)贬媒。相對(duì)于vector來說聋亡，每一次刪除和插入，指針都有可能失效际乘，調(diào)用push_back在尾部插入也是如此坡倔。因?yàn)闉榱吮ＷC內(nèi)部數(shù)據(jù)的連續(xù)存放，iterator指向的那塊內(nèi)存在刪除和插入過程中可能已經(jīng)被其他內(nèi)存覆蓋或者內(nèi)存已經(jīng)被釋放了脖含。即使時(shí)push_back的時(shí)候罪塔，容器內(nèi)部空間可能不夠，需要一塊新的更大的內(nèi)存养葵，只有把以前的內(nèi)存釋放垢袱，申請(qǐng)新的更大的內(nèi)存，復(fù)制已有的數(shù)據(jù)元素到新的內(nèi)存港柜，最后把需要插入的元素放到最后请契，那么以前的內(nèi)存指針自然就不可用了咳榜。特別時(shí)在和find等算法在一起使用的時(shí)候，牢記這個(gè)原則:不要使用過期的iterator爽锥。
為何map和set不能像vector一樣有個(gè)reserve函數(shù)來預(yù)分配數(shù)據(jù)?
答:引起它的原因在于在map和set內(nèi)部存儲(chǔ)的已經(jīng)不是元素本身了涌韩，而是包含元素的節(jié)點(diǎn)。也就是說map內(nèi)部使用的Alloc并不是map<Key, Data, Compare, Alloc>聲明的時(shí)候從參數(shù)中傳入的Alloc氯夷。
set, multiset
set和multiset會(huì)根據(jù)特定的排序準(zhǔn)則自動(dòng)將元素排序臣樱，set中元素不允許重復(fù)，multiset可以重復(fù)腮考。
因?yàn)槭桥判虻墓秃粒詓et中的元素不能被修改，只能刪除后再添加踩蔚。
向set中添加的元素類型必須重載<操作符用來排序棚放。排序滿足以下準(zhǔn)則:
1、非對(duì)稱馅闽，若A<B為真飘蚯，則B<A為假。
2福也、可傳遞局骤，若A<B,B<C，則A<C暴凑。
3峦甩、A<A永遠(yuǎn)為假。
set中判斷元素是否相等:
if(!(A<B || B<A))现喳，當(dāng)A<B和B<A都為假時(shí)穴店，它們相等。
map拿穴，multimap
map和multimap將key和value組成的pair作為元素，根據(jù)key的排序準(zhǔn)則自動(dòng)將元素排序忧风，map中元素的key不允許重復(fù)默色，multimap可以重復(fù)。
map<key,value>
因?yàn)槭桥判虻氖ㄍ龋詍ap中元素的key不能被修改腿宰，只能刪除后再添加。key對(duì)應(yīng)的value可以修改缘厢。
向map中添加的元素的key類型必須重載<操作符用來排序吃度。排序與set規(guī)則一致。

map/set的實(shí)現(xiàn)

http://www.cnblogs.com/zlcxbb/p/5753906.html
紅黑樹的特性
https://blog.csdn.net/lf_2016/article/details/52974143

hash_map和map的區(qū)別

構(gòu)造函數(shù) hash_map需要hash函數(shù)贴硫，等于函數(shù);map只需要比較函數(shù)(小于函數(shù)).
存儲(chǔ)結(jié)構(gòu) hash_map采用hash表存儲(chǔ)椿每，map一般采用紅黑樹實(shí)現(xiàn)伊者。因此其memory數(shù)據(jù)結(jié)構(gòu)是不一樣的。
什么時(shí)候用hash_map,什么時(shí)候用map
權(quán)衡三個(gè)因素: 查找速度, 數(shù)據(jù)量, 內(nèi)存使用间护。
hash_map底層是散列的所以理論上操作的平均復(fù)雜度是常數(shù)時(shí)間亦渗，map底層是紅黑樹，理論上平均復(fù)雜度是O(logn)
下面是借鑒的網(wǎng)上的總結(jié)：
這里總結(jié)一下汁尺，選用map還是hash_map法精，關(guān)鍵是看關(guān)鍵字查詢操作次數(shù)，以及你所需要保證的是查詢總體時(shí)間還是單個(gè)查詢的時(shí)間痴突。如果是要很多次操作搂蜓，要求其整體效率，那么使用hash_map辽装，平均處理時(shí)間短帮碰。如果是少數(shù)次的操作，使用 hash_map可能造成不確定的O(N)如迟，那么使用平均處理時(shí)間相對(duì)較慢收毫、單次處理時(shí)間恒定的map，考慮整體穩(wěn)定性應(yīng)該要高于整體效率殷勘，因?yàn)榍疤嵩诓僮鞔螖?shù)較少此再。如果在一次流程中，使用hash_map的少數(shù)操作產(chǎn)生一個(gè)最壞情況O(N)玲销，那么hash_map的優(yōu)勢(shì)也因此喪盡了输拇。
http://www.cnblogs.com/lang5230/p/5556611.html