關(guān)聯(lián)容器和順序容器根本的不同：

關(guān)聯(lián)容器中的元素是按關(guān)鍵字保存和訪(fǎng)問(wèn)的澡匪；順序容器中的元素是按在容器中的位置順序保存和訪(fǎng)問(wèn)的钻弄。

關(guān)聯(lián)容器支持高效的關(guān)鍵字查找和訪(fǎng)問(wèn)乖坠。兩個(gè)主要的關(guān)聯(lián)容器（associative container）類(lèi)型是map和set矮台。map中的元素是一些關(guān)鍵字-值（ket-value）對(duì)：關(guān)鍵字起到索引作用，值表示與索引相關(guān)聯(lián)的數(shù)據(jù)漾月。

set中每個(gè)元素只包含一個(gè)關(guān)鍵字已日；set支持高校的關(guān)鍵字查詢(xún)操作：檢查一個(gè)給定關(guān)鍵字是否在set中。例如某些文本處理過(guò)程中可以用set保存要忽略的單詞栅屏。

字典是一個(gè)很好的使用map的例子：可以將單詞作為關(guān)鍵字，將單詞釋義作為值堂鲜。

標(biāo)準(zhǔn)庫(kù)提供8個(gè)關(guān)聯(lián)容器栈雳。這8個(gè)容器間的不同體現(xiàn)在3個(gè)維度上：每個(gè)容器：

1. 或者是一個(gè)set，或者是一個(gè)map缔莲；
2. 或者要求不重復(fù)的關(guān)鍵字哥纫，或者允許重復(fù)關(guān)鍵字
3. 按順序保存元素，或無(wú)序保存

允許重復(fù)關(guān)鍵字的容器的名字中都有multi痴奏；不保持關(guān)鍵字按順序存儲(chǔ)的容器名字都以unordered開(kāi)頭蛀骇。

例如：一個(gè)unordered_multi_set是一個(gè)允許重復(fù)關(guān)鍵字厌秒，元素?zé)o序保存的集合。一個(gè)set是一個(gè)不允許重復(fù)關(guān)鍵字擅憔，有序存儲(chǔ)的集合鸵闪。

無(wú)序容器使用哈希函數(shù)來(lái)組織元素。

類(lèi)型map和multimap定義在頭文件<map>中暑诸，set和multiset定義在頭文件<set>中蚌讼；無(wú)序容器則定義在unordered_map和unordered_set中。

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

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

map類(lèi)型通常稱(chēng)為：關(guān)聯(lián)數(shù)組（associative array）凰萨。關(guān)聯(lián)數(shù)組類(lèi)似正常數(shù)組，但其下標(biāo)不必是正數(shù)械馆，可以是一個(gè)關(guān)鍵字胖眷；set就是關(guān)鍵字的簡(jiǎn)單集合。

使用map

從文件讀取單詞并計(jì)數(shù)程序

int main(){
    std::map<std::string, size_t> word_count;
    std::string ifile = "words.txt";
    std::ifstream ifs(ifile, std::ios_base::in);
    std::istream_iterator<std::string> it(ifs), eof;
    std::vector<std::string> v(it, eof);
    for(auto i: v) ++word_count[i];
    for (const auto& w: word_count){
        std::cout<<w.first<<'\t'<<w.second<<std::endl;
    }
}

map也是一個(gè)模板狱杰，因此需要指定key和value的類(lèi)型瘦材，如本例中的string和size_t。其中string可以作為下標(biāo)仿畸。
當(dāng)從map中提取一個(gè)元素時(shí)會(huì)得到一個(gè)pair類(lèi)型的對(duì)象食棕。pair也是一個(gè)模板類(lèi)型，保存兩個(gè)數(shù)據(jù)成員first和second错沽。

使用set

使用set設(shè)置一個(gè)忽略關(guān)鍵詞的列表簿晓，并且在上面程序中進(jìn)行判斷，可以使用set自帶的find成員千埃，若返回尾后迭代器則代表未找到憔儿，未出現(xiàn)在排除列表中：

int main(){
    //設(shè)置除外列表
    std::set<std::string> exclude = {"and", "or", "the", "a", "with"};
    std::map<std::string, size_t> word_count;
    std::string ifile = "words.txt";
    std::ifstream ifs(ifile, std::ios_base::in);
    std::istream_iterator<std::string> it(ifs), eof;
    std::vector<std::string> v(it, eof);
    for(auto i: v) 
        if (exclude.find(i) == exclude.end()) //判斷是否不在除外列表中
            ++word_count[i];
    for (const auto& w: word_count){
        std::cout<<w.first<<'\t'<<w.second<<std::endl;
    }
}

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

關(guān)聯(lián)容器都支持普通的容器操作，但不支持順序容器的位置相關(guān)的操作放可，如push_back等谒臼。
同時(shí)，也不支持構(gòu)造函數(shù)或插入操作等接受一個(gè)元素值和一個(gè)數(shù)量值的操作耀里。
關(guān)聯(lián)容器支持一些順序容器不支持的操作蜈缤、類(lèi)型別名。
此外冯挎，無(wú)序容器還提供一些調(diào)整哈希性能的操作底哥。
關(guān)聯(lián)容器的迭代器都是雙向的。

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

定義一個(gè)map需要指明k和v的類(lèi)型，set只需要指名k的類(lèi)型趾徽⌒蹋可以默認(rèn)初始化為空容器，map也可以使用初始化列表進(jìn)行值初始化孵奶。

int main(){
    std::map<std::string, int> m1;
    std::set<std::string> s1 = {"a", "b", "c"};
    std::map<std::string, int> m2 = {{"a", 0}, {"b", 1}, {"c", 2}};
}

初始化multimap或multiset

可以使用一個(gè)順序容器的一對(duì)迭代器對(duì)一個(gè)set進(jìn)行初始化：

int main(){
    std::vector<int> v;
    auto it = std::back_inserter(v);
    for(int i = 0; i<10; i++) {it = i;  it = i;}

    for(auto j: v) std::cout<<j;  //00112233445566778899
    std::cout<<std::endl;

    std::set<int> s(v.begin(), v.end());
    std::multiset<int> ms(v.begin(), v.end());

    for(auto k: s) std::cout<<k;  //0123456789
    std::cout<<std::endl;          

    for(auto k: ms) std::cout<<k; //00112233445566778899
    std::cout<<std::endl;         
}

關(guān)鍵字類(lèi)型的要求

對(duì)于有序容器map疲酌、multimap、set拒课、multiset徐勃，關(guān)鍵字類(lèi)型必須定義元素比較的方法。默認(rèn)情況下是使用了關(guān)鍵字類(lèi)型的operator<進(jìn)行比較早像。
set類(lèi)型中僻肖，關(guān)鍵字類(lèi)型就是元素類(lèi)型；映射類(lèi)型中關(guān)鍵字類(lèi)型是元素第一部分(first)的類(lèi)型卢鹦。

有序容器的關(guān)鍵字類(lèi)型

可以向一個(gè)算法提供自己定義的比較操作臀脏，或者比較操作符。

所提供的操作必須在關(guān)鍵詞類(lèi)型上定義一個(gè)嚴(yán)格弱序（strict weak ordering）冀自，可將其視為“小于等于”揉稚。

定義的比較函數(shù)需要具備如下基本性質(zhì)：

• 兩關(guān)鍵字不能同時(shí)“小于等于”對(duì)方
• 小于等于必須具有傳遞性
• 若存在兩個(gè)關(guān)鍵字任何一個(gè)都不小于等于第三個(gè)，則這來(lái)給你個(gè)等價(jià)熬粗，視為相等搀玖。

使用關(guān)鍵字類(lèi)型的比較函數(shù)

用來(lái)組織一個(gè)容器中元素的操作的類(lèi)型也是該容器類(lèi)型的一部分。為了指定使用自定義的操作驻呐，必須在定義關(guān)聯(lián)容器類(lèi)型時(shí)提供此操作的類(lèi)型灌诅。如前所述，用尖括號(hào)指出要定義哪種類(lèi)型的容器含末，自定義的操作類(lèi)型必須在尖括號(hào)中緊跟元素類(lèi)型給出猜拾。

尖括號(hào)中出現(xiàn)的每個(gè)類(lèi)型僅僅是一個(gè)類(lèi)型。當(dāng)創(chuàng)建了一個(gè)容器對(duì)象時(shí)佣盒，才會(huì)以構(gòu)造函數(shù)參數(shù)的形式提供真正的比較操作挎袜。

為了使用自定義的操作，在定義multiset時(shí)必須提供兩個(gè)類(lèi)型：關(guān)鍵字類(lèi)型以及比較操作類(lèi)型（一種函數(shù)指針類(lèi)型）肥惭。

pair類(lèi)型

標(biāo)準(zhǔn)庫(kù)類(lèi)型pair定義在頭文件utility中盯仪。

一個(gè)pair保存兩個(gè)數(shù)據(jù)成員。類(lèi)似容器蜜葱，pair是一個(gè)用于生成特定類(lèi)型的模板磨总。創(chuàng)建一個(gè)pair時(shí)，必須提供兩個(gè)類(lèi)型名笼沥，pair的數(shù)據(jù)成員將具有對(duì)應(yīng)的類(lèi)型，兩個(gè)類(lèi)型可以不一樣。

using std::pair, std::string, std::vector;
pair<string, size_t> p1;
pair<string, string> p2;
pair<string, vector<string>> p3;

pair的默認(rèn)構(gòu)造函數(shù)會(huì)對(duì)數(shù)據(jù)成員進(jìn)行值初始化奔浅。也可以為每個(gè)成員提供初始化器馆纳。

pair<string, string> p4 = {"s1", "s2"};

pair的數(shù)據(jù)成員是public的。分別名為first和second汹桦，可以使用普通的成員訪(fǎng)問(wèn)符號(hào)進(jìn)行訪(fǎng)問(wèn)鲁驶。

創(chuàng)建pair對(duì)象的函數(shù)

將pair作為函數(shù)返回值脆霎，可以直接使用初始化列表進(jìn)行列表初始化：

std::pair<std::string, int> foo(std::vector<std::string> v, const int& cond){
    switch (cond) {
        defalult:
            //默認(rèn)初始化方式
            return std::pair<std::string, int>();
        case 1:    
            //make_pair方式
            return std::make_pair(v.front(), v.front().size()); 
        case 2:
            //初始化列表方式
            return {v.back(), v.back().size()};  
        case 3:
            //較早版本方式
            return std::pair<std::string, int>(v.back(), v.back().size());
    }
}

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

關(guān)聯(lián)容器還定義了以下類(lèi)型：

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

解引用一個(gè)關(guān)聯(lián)容器迭代器睛蛛，會(huì)得到一個(gè)類(lèi)型為容器value_type的值的引用。對(duì)map而言為一個(gè)pair胧谈，first保存const的關(guān)鍵字（無(wú)法修改）忆肾，second保存值；對(duì)set就是key_type本身菱肖。

int main(){
    std::map<std::string, size_t> mp = {{"A", 1},{"b", 2},{"C", 3},{"D", 4}};
    auto it = mp.begin();
    std::cout<<it->first<<std::endl;  //A
    std::cout<<it->second<<std::endl; //1

    ++(it->second);  //second成員值+1
    std::cout<<it->first<<std::endl;  //A
    std::cout<<it->second<<std::endl; //2

    ++it->second;  //等價(jià)于++(it->second)
    std::cout<<it->first<<std::endl;  //A
    std::cout<<it->second<<std::endl; //3

    (++it)->second; //未賦值客冈，僅后移迭代器
    std::cout<<it->first<<std::endl;  //B
    std::cout<<it->second<<std::endl; //2

    //it->first = "X"; //錯(cuò)誤：該值為const
}

set的迭代器是const的

只包含keys的迭代器，和map迭代器指向pair的first成員一樣稳强，是const的场仲。

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

map和set都支持begin和end操作，并使用迭代器遍歷內(nèi)容键袱。

關(guān)聯(lián)容器和算法

通常不對(duì)關(guān)聯(lián)容器使用泛型算法燎窘。原因是const特性使得一些會(huì)修改和重排容器的算法無(wú)法使用。

對(duì)于只讀類(lèi)型的算法如find等蹄咖，可以用在關(guān)聯(lián)容器上褐健，但是由于儲(chǔ)存和尋址方式不同，速度較慢澜汤。建議使用關(guān)聯(lián)容器自身的find成員進(jìn)行類(lèi)似操作蚜迅。

通常使用關(guān)聯(lián)容器的成員比使用類(lèi)似的泛型算法快得多

此外，可以使用泛型copy將關(guān)聯(lián)容器當(dāng)作一個(gè)源序列俊抵；或者使用inserter綁定一個(gè)關(guān)聯(lián)容器谁不，使用inserter將關(guān)聯(lián)容器作為插入的目的位置。

添加元素

可以使用關(guān)聯(lián)容器自身的insert成員進(jìn)行元素的添加徽诲。
map和set包含不重復(fù)的關(guān)鍵字刹帕，因此插入一個(gè)已存在的元素沒(méi)有任何影響吵血，也沒(méi)有任何作用。

int main(){
    std::map<std::string, size_t> mp = {{"A", 1},{"B", 2},{"C", 3},{"D", 4}};
    auto it = mp.begin();
    mp.insert({"A", 5});
    std::cout<<it->first<<std::endl;   //A
    std::cout<<it->second<<std::endl;  //1
}

向map添加元素

必須記住偷溺，向map添加的元素類(lèi)型是pair蹋辅。添加的四種方法(以及decltype)：

mp.insert({"A", 1});
mp.insert(std::make_pair("A", 1));
mp.insert(std::pair<std::string, size_t>("A", 1));
mp.insert(std::map<std::string, size_t>::value_type("A", 1));

insert的返回值

對(duì)于不包含重復(fù)關(guān)鍵字的容器侦另，添加單一元素的insert和emplace版本返回一個(gè)pair：

• first成員是一個(gè)迭代器，指向具有指定關(guān)鍵字的元素尉共；
• second成員是一個(gè)bool值褒傅，指出插入成功還是已在容器。

展開(kāi)遞增語(yǔ)句

若ret是insert的返回值袄友，則：

++ret.first->second

按優(yōu)先級(jí)寫(xiě)為：

++((ret.first)->second);

ret的first成員是一個(gè)迭代器殿托，其second值即指向插入后位置的value。該語(yǔ)句為將其遞增的操作杠河。

向multiset或multimap添加元素

由于插入總是成功碌尔，不必返回一個(gè)bool值，因此返回的不是pair而直接是指向新元素的迭代器券敌。

刪除元素

關(guān)聯(lián)容器定義了三個(gè)版本的erase唾戚。

• 可以傳遞一個(gè)或一對(duì)迭代器來(lái)刪除指定元素或范圍。和順序容器操作類(lèi)似待诅，指定的元素被刪除叹坦，返回void。
• 第三個(gè)版本接受一個(gè)key_type參數(shù)卑雁，刪除所有匹配給定關(guān)鍵字的元素募书，返回實(shí)際刪除元素的數(shù)量〔舛祝可以使用該版本在打印結(jié)果之前刪除特定key的pair莹捡。
• • 非multi容器，返回值總是0或1扣甲；為0表示要?jiǎng)h除的元素不在容器中篮赢。
• • 對(duì)于multi容器，返回值可能大于1：可能刪除多個(gè)元素琉挖。

map的下標(biāo)操作

非multi的map類(lèi)型存在下標(biāo)運(yùn)算符和對(duì)應(yīng)的at函數(shù)纱耻；set由于只有關(guān)鍵字而沒(méi)有相關(guān)值而不能進(jìn)行下標(biāo)操作芭梯。multi類(lèi)型由于一對(duì)多，同樣無(wú)法使用下標(biāo)操作膝迎。

下標(biāo)操作返回值

解引用迭代器返回的類(lèi)型和下標(biāo)運(yùn)算符返回的類(lèi)型通常一樣限次。

對(duì)于map則不同：下標(biāo)操作會(huì)獲得一個(gè)mapped_type對(duì)象；但解引用時(shí)柴灯，會(huì)得到一個(gè)value_type對(duì)象卖漫。（value_type包含mapped_type和key_type）

std::cout<<mp.begin()->second; //value_type
std::cout<<mp["A"];  //mapped_type

訪(fǎng)問(wèn)元素

是否在：find，返回迭代器
有幾個(gè)：count赠群，返回?cái)?shù)目

lower_bound和upper_bound不適用于無(wú)序容器

在map中用find代替下標(biāo)操作！

map中使用下標(biāo)若關(guān)鍵字不存在冬三，會(huì)插入一個(gè)被值初始化的未知值匀油，后續(xù)再插入可能出問(wèn)題，因此首先使用find判斷是更好的方法勾笆。

在multimap或multiset查找元素

如果一個(gè)multimap或multiset中有多個(gè)元素具有給定關(guān)鍵字敌蚜，則這些元素在容器中相鄰存儲(chǔ)。

要找到所有key等于特定值的元素窝爪，首先需要進(jìn)行count操作返回一個(gè)數(shù)目弛车，該數(shù)目就是find返回迭代器需要的前進(jìn)次數(shù)。

int main(){
    std::multimap<std::string, size_t> mp = {{"A", 1},{"A", 2},{"A", 3},{"B", 4}};
    auto cnt = mp.count("A");
    //利用了同關(guān)鍵字元素連續(xù)存儲(chǔ)的特性
    auto it = mp.find("A");
    std::vector<size_t> v;
    while (cnt){
        v.push_back(it++->second);
        cnt--;
    }
    for(auto i: v) std::cout<<i<<" ";
}

find只有接受一個(gè)參數(shù)的版本蒲每，因此不能指定開(kāi)始位置纷跛，無(wú)法使用多次find進(jìn)行循環(huán)，另一種方式是面向迭代器的方法：lower_bound, upper_bound, equal_range邀杏。

使用equal_range返回的兩個(gè)迭代器創(chuàng)建一個(gè)新的map：

int main(){
    std::multimap<std::string, size_t> mp = {{"A", 1},{"A", 2},{"A", 3},{"B", 4}};
    auto ir = mp.equal_range("A");
    decltype(mp) mp2(ir.first, ir.second); 
    //mp2: {{"A", 1},{"A", 2},{"A", 3}}
    for(auto i: mp2) std::cout<<i.first<<'\t'<<i.second<<'\n';
}

使用lower_bound和upper_bound:

int main(){
    std::multimap<std::string, size_t> mp = {{"A", 1},{"A", 2},{"A", 3},{"B", 4}};
    auto beg = mp.lower_bound("A");
    auto end = mp.upper_bound("A");
    for (; beg != end; beg++) 
        std::cout<<beg->first<<'\t'<<beg->second<<'\n';
}

實(shí)質(zhì)：

int main(){
    std::multimap<std::string, size_t> mp = {{"A", 1},{"A", 2},{"A", 3},{"B", 4}};
    auto beg = mp.lower_bound("A");
    auto end = mp.upper_bound("A");
    auto rng = mp.equal_range("A");
    std::cout<<(rng.first==beg);  //1
    std::cout<<(rng.second==end); //1
}

無(wú)序容器

4個(gè)無(wú)序關(guān)聯(lián)容器（unordered associative container）不是使用比較運(yùn)算符組織元素贫奠，而是使用哈希函數(shù)（hash function）和關(guān)鍵字類(lèi)型的==運(yùn)算符。

使用無(wú)序容器

除了哈希管理操作淮阐，無(wú)序容器還提供了與有序容器相同的操作(find叮阅、insert等)。即曾用于map和set的操作也能用于unordered_map和unordered_set泣特。無(wú)序容器也允許重復(fù)關(guān)鍵字的版本浩姥。

因此通常可以用一個(gè)無(wú)序容器替換對(duì)應(yīng)的有序容器状您，反之亦然。但是由于元素未按順序存儲(chǔ)隘击，使用無(wú)序容器程序的輸出通常與有序容器版本不同箩艺。

管理桶

無(wú)序容器在存儲(chǔ)組織上為一組桶，每個(gè)桶保存零個(gè)或者多個(gè)元素拌汇。無(wú)序容器使用一個(gè)哈希函數(shù)將元素映射到桶。

為了訪(fǎng)問(wèn)一個(gè)元素弊决，容器首先計(jì)算元素的哈希值噪舀，指出要搜索的桶。容器將具有一個(gè)特定哈希值的所有元素保存在相同的桶中飘诗。如果容器允許重復(fù)關(guān)鍵字与倡，所有具有相同關(guān)鍵字的元素也會(huì)在同一個(gè)桶中。

因此昆稿，無(wú)序容器的性能依賴(lài)于哈希函數(shù)的質(zhì)量和桶的數(shù)量和大小纺座。

對(duì)于相同的參數(shù)，哈希函數(shù)必須總是產(chǎn)生相同的結(jié)果溉潭。理想情況下哈希函數(shù)還能將每個(gè)特定的值映射到唯一的桶净响。但是，將不同關(guān)鍵字的元素映射到相同的桶也是允許的喳瓣。當(dāng)一個(gè)桶保存多個(gè)元素時(shí)馋贤，需要順序搜索這些元素來(lái)檢查我們想要的那個(gè)。計(jì)算一個(gè)元素的哈希值在桶中搜索通常很快夫椭。但是如果一個(gè)桶中保存了很多元素掸掸，那查找一個(gè)特定元素需要大量比較操作。

無(wú)序容器提供的一組管理桶的函數(shù)：

無(wú)序容器對(duì)關(guān)鍵字類(lèi)型的要求

默認(rèn)情況下扰付，無(wú)序容器使用關(guān)鍵字類(lèi)型的==運(yùn)算符比較元素。還使用一個(gè)hash<key_type>類(lèi)型的對(duì)象來(lái)生成每個(gè)元素的哈希值仁讨。

標(biāo)準(zhǔn)庫(kù)為內(nèi)置類(lèi)型提供了hash模板羽莺，還為string和智能指針等標(biāo)準(zhǔn)庫(kù)類(lèi)型定義了hash。因此洞豁，可以直接定義關(guān)鍵字是內(nèi)置類(lèi)型（含指針類(lèi)型）盐固、string還是智能指針類(lèi)型的無(wú)序容器。

但是不能直接定義關(guān)鍵字類(lèi)型為自定義類(lèi)類(lèi)型的無(wú)序容器丈挟。與容器不同刁卜，不能直接使用哈希模板，而必須提供自己的hash模板版本曙咽。