C++ 標準模板庫(STL)

作者:AceTan,轉(zhuǎn)載請標明出處哼勇！

0x00 何為STL##

STL(Standard Template Library) 即標準模板庫肄满。它是一個具有工業(yè)強度摧找，高效的C++程序庫。它包含了諸多在計算機科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和算法。這些數(shù)據(jù)結(jié)構(gòu)可以與標準算法一起很好的工作，這為我們的軟件開發(fā)提供了良好的支持韵卤。如果你還不理解它的重要性，那我換個說法崇猫。這就好比你去打架沈条，你不會使用STL，那就手里的武器就相當(dāng)于彈弓诅炉。敵人熟練使用STL蜡歹，人家手里拿的是AK47，開著坦克涕烧。

從名字就可以知道月而，它的設(shè)計基石是模板技術(shù)。這樣的設(shè)計帶來了更好的重用機會议纯。STL共有以下六大組件父款。

• 迭代器(iterator)

• 容器(container)

• 算法(algorithm)

• 仿函數(shù)(function object)

• 適配器(Adaptor)

• 空間配制器(allocator)

仿函數(shù)和空間配制器不是很常用，我們主要討論一下迭代器，容器憨攒，算法和適配器世杀。其中，我們以容器的用法為重點肝集。

0x01 迭代器

迭代器在STL中起著粘合劑的作用瞻坝，它將算法和容器聯(lián)系起來，主要用來存取容器中的元素杏瞻。幾乎所有的算法都是通過迭代器存取元素進行工作的所刀。每一個容器也都定義了其本身所專有的迭代器，用以存取容器中的元素捞挥。想象一下浮创，你面前有一缸水(缸就好比容器)，你喝水需要要到瓢(咱是文明人砌函，不帶用雙手直接捧著喝的)斩披。這個瓢就相當(dāng)于迭代器，你可以用它來打水喝胸嘴，也可以用瓢來把水缸裝滿雏掠。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;        // 定義一個vector容器
    
    v.push_back(1);        // 向容器中添加3個元素
    v.push_back(2);
    v.push_back(3);

    // 遍歷向量的元素
    vector<int>::iterator b = v.begin();        // 指向容器的第一個元素
    vector<int>::iterator e = v.end();            // 指向容器尾元素的下一個位置

    // C++11新標準的寫法, auto關(guān)鍵字為類型推斷斩祭，由編譯器自動完成
    // auto b = v.begin();
    // auto e = v.end();

    for (vector<int>::iterator iter = b; iter != e; ++iter)
    {
        cout << *iter << endl;
    }

    return 0;
}

迭代器的使用劣像，上面給了一段簡單的代碼，我們來精析一下摧玫。

迭代器最常用到的就是begin和end成員耳奕。其中begin成員負責(zé)返回指向第一個元素。end成員則負責(zé)返回指向容器的“ 尾元素的下一個位置(one past the end) ”诬像。要特別注意end成員不是指向尾元素屋群，而是指向尾元素的下一個位置！ end成員返回的迭代器也叫尾后迭代器(off-the-end iterator)坏挠，簡稱尾迭代器芍躏。

如果容器為空呢？那么begin和end返回的是同一個迭代器降狠，都是尾后迭代器对竣。

這里要注意一下for循環(huán)的循環(huán)條件。

• 初始化語句：vector<int>::iterator iter = b; 如果你的環(huán)境支撐C++11標準榜配，那么強烈建議你寫成auto iter = b; 即使用類型自動推斷關(guān)鍵字auto否纬。使用auto使程序更為簡潔，也不會出錯蛋褥，由編譯器自動推斷临燃。

• 條件語句 iter != e; 一般的for循環(huán)里我們會用itet < e 這樣的形式，當(dāng)然，在vector里改成這樣也是可以的膜廊。但是乏沸，并非所有的容器都重載了 < 運算符，所有的容器都重載了== 和 != 運算符溃论。所以我們應(yīng)該習(xí)慣使用 == 和 != 運算符屎蜓。

• 表達式語句 ++iter。 建議使用前置++而非后置++钥勋。 在迭代器中炬转，前置++的效率高于后置++。實際上算灸，除非邏輯需要扼劈，一般都使用前置++ 進行向前迭代。關(guān)于前置++和后置++的本質(zhì)區(qū)別菲驴，看官可自行查看其它資料荐吵。

標準容器迭代器的運算符:

• *iter： 返回迭代器iter所指元素的引用

• iter->mem: 解引用iter并獲取該元素的名為mem的成員，等價于(*item).mem

• ++iter: 另iter指向容器的下一個元素

• --iter: 另iter指向元素的前一個元素

• iter1 == iter2：判斷兩個迭代器是否相等

• iter1 != iter2: 判斷兩個迭代器是否不相等

迭代器類型：

• iterator ：可讀可寫赊瞬。

• const_iterator ： 可讀不可寫先煎。使用迭代器帶c的版本來返回，尤其是使用auto關(guān)鍵字的時候巧涧。

迭代器的范圍:

迭代器范圍(iterator range) 由一對迭代器表示薯蝎，最常見的就是begin和end。begin和end所表示的范圍恰好是容器的全部元素谤绳。這是一個左閉合區(qū)間(left-inclusive interval),其標準的數(shù)學(xué)表達式為:

[begin,end)

其他迭代器:

除了為每個容器定義迭代器外占锯，標準庫在頭文件 iterator中還定義了額外幾種迭代器，這些迭代器包括以下幾種缩筛。

• 插入迭代器(insert iterator)： 這些迭代器被綁定到一個容器上消略，可用來向容器中插入元素。

• 流迭代器(stream iterator)： 這些迭代器被綁定到輸入或輸出流上瞎抛，可用來遍歷相關(guān)的IO流艺演。

• 反向迭代器(reverse iterator) 這些迭代器和正常的迭代器移動方向相反。例如++操作是指向前一個元素桐臊。除了forward_list之外的標準庫庫容器都有反向迭代器胎撤。即迭代器的r版本。

• 移動迭代器(move iterator) 這些專用的迭代器不是拷貝其中的元素豪硅，而是移動它們哩照。

迭代器類別:

算法所要求的迭代器可以分為5個迭代器類別(iterator category)。

• 輸入迭代器 : 只讀懒浮，不寫飘弧。單遍掃描识藤，只能遞增。

• 輸出迭代器 ： 只寫次伶，不讀痴昧。單遍掃描，只能遞增冠王。

• 前向迭代器 ： 可讀可寫赶撰。多遍掃描，只能遞增柱彻。

• 雙向迭代器 ： 可讀可寫豪娜。多遍掃描，可遞增遞減哟楷。

• 隨機訪問迭代器 ： 可讀可寫瘤载。多遍掃描，支持全部迭代器運算卖擅。

下面的例子演示一下迭代器的運算鸣奔，c版本的迭代器，r版本的迭代器惩阶。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;        // 定義一個vector容器
    
    v.push_back(1);        // 向容器中添加5個元素
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    // 使用c版本的迭代器
    auto b = v.cbegin();    // 帶c版本的迭代器表示const_iterator類型的迭代器
    auto e = v.cend();        // 指向容器尾元素的下一個位置

    for (auto iter = b; iter != e; ++iter)
    {
        // *iter *= 2;            // 報錯挎狸，試圖給常量賦值！
    }

    // 反向輸出容器中的元素断楷，使用r版本的迭代器
    auto rb = v.rbegin();        // 實際指向尾元素
    auto re = v.rend();            // 指向第一個元素的前一個位置

    for (auto iter = rb; iter != re; ++iter)
    {
        cout << *iter << endl;
    }

    // 進行迭代器的運算锨匆，輸出容器的中間元素
    auto mid = v.begin() + v.size() / 2;
    cout << "該容器的中間元素為:" << *mid << endl;

    return 0;
}

0x02 容器

容器的定義是：特定類型對象的集合。

在沒有使用容器之前脐嫂，我們可能會用數(shù)組解決一些問題统刮。使用數(shù)組解決問題紊遵，那么我們必須要知道或者估算出大約要存儲多少個對象账千，這樣我們會創(chuàng)建能夠容納這些對象的內(nèi)存空間大小。當(dāng)我們要處理一些完全不知道要存儲多少對象的問題時暗膜，數(shù)組顯的力不從心匀奏。我們可以使用容器來解決這個問題。容器具有很高的可擴展性学搜，我們不需要預(yù)先告訴它要存儲多少對象娃善，只要創(chuàng)建一個容器，并合理的調(diào)用它所提供的方法瑞佩，所有的處理細節(jié)由容器自身完成聚磺。

新標準庫的容器的性能幾乎肯定與最精心優(yōu)化過的同類數(shù)據(jù)結(jié)構(gòu)一樣好(通常會更好)。現(xiàn)代C++程序應(yīng)該使用標準容器庫炬丸，而不是更原始的數(shù)據(jù)結(jié)構(gòu)瘫寝，如內(nèi)置數(shù)組蜒蕾。

通用容器的分類

通用容器分為3類：順序容器、關(guān)聯(lián)容器焕阿、容器適配器咪啡。

順序容器

順序容器是一種元素之間有順序的線性表，是一種線性結(jié)構(gòu)的可序群集暮屡。這和我們數(shù)據(jù)結(jié)構(gòu)課程上所講的線性表是一樣的撤摸。順序容器中的每個元素位置是固定的，除非你使用了插入或者刪除操作改變了這個位置褒纲。順序容器不會根據(jù)元素的特點排序而是直接保存了元素操作時的邏輯順序准夷。比如我們一次性對一個順序容器追加三個元素，這三個元素在容器中的相對位置和追加時的邏輯次序是一致的莺掠。

順序容器都提供了快速順序訪問元素的能力冕象。但是，他們在以下方面都有不同的性能折中：

• 向容器中添加或者向容器中刪除元素的代價汁蝶。(不是末端)

• 非順序訪問容器中元素的代價渐扮。

順序容器的類型：

• vector : 可變大小數(shù)組，支持快速隨機訪問掖棉。在尾部之外的位置插入或者刪除元素可能很慢墓律。

• deque : 雙端隊列。支持快速隨機訪問幔亥。在頭尾位置插入耻讽、刪除速度很快。

• list : 雙向鏈表帕棉。只支持雙向順序訪問针肥。在list中任何位置進行插入、刪除操作速度都很快香伴。

• forward_list : 單向鏈表慰枕。只支持單向順序訪問。在鏈表的任何位置進行插入即纲、刪除操作都很快具帮。(C++11標準新加)

• array : 固定大小數(shù)組。支持快速隨機訪問低斋。不能添加或者刪除元素蜂厅。(C++11標準新加)

• string : 與vector相似的容器，但專門用于保存字符膊畴。隨機訪問快掘猿，在尾部插入刪除快。

如何選擇呢唇跨？是不是又犯了選擇困難癥稠通？ 我們一般對癥下藥礁遵，了解這些容器的特性，根據(jù)自己的編程需求選擇適合的容器采记。vector佣耐、deque和list這三者我們可以優(yōu)先考慮vector。vector容器適用于大量讀寫唧龄，而插入兼砖、刪除比較少的操作。list容器適用于少量讀寫既棺，大量插入讽挟，刪除的情況。deque折中了vector和deque丸冕， 如果你需要隨機存取又關(guān)心數(shù)據(jù)的插入和刪除耽梅，那么可以選擇deque。forward_list適用于符合它這種邏輯結(jié)構(gòu)的情況胖烛，array一般用來代替原生的數(shù)組眼姐。string用于和字符串操作有關(guān)的一些情況，也是實際開發(fā)中應(yīng)用最多的佩番。

關(guān)于各容器的操作众旗，實在是太多了，下面的示例程序列舉一些比較常見的操作和用法趟畏。

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <list>
#include <forward_list>
#include <array>

using namespace std;

int main()
{
    /*--------------------- vector容器的一些操作  ------------------*/
    vector<int> vect1;            // 定義一個vector容器
    vect1.push_back(1);            // push_back: 向容器的末尾添加元素
    vect1.push_back(2);
    vect1.push_back(3);
    vect1.pop_back();            // pop_back: 去除末尾的元素

    vect1.insert(vect1.begin() + 1, 8);    // 在某個位置插入一個元素,效率低贡歧，不適合大批操作
    vect1.at(0);                        // at:取某個位置的元素
    vect1.capacity();                    // capacity: 不分配新的內(nèi)存空間的前提下它最多能保存多少元素。這個和下面的size 是有區(qū)別的８承恪尖坤！
    vect1.size();                        // size: 已經(jīng)保存的元素的數(shù)目
    vect1.empty();                        // empty：判斷容器是否為空
    vect1.front();                        // front：取第一個元素
    vect1.back();                        // back：取最后一個元素
    vect1.erase(vect1.begin() + 1);        // erase：刪除指定位置的元素
    vector<int> vect2;
    vect2.assign(vect1.begin(), vect1.end()); // 賦值操作
    /*------------------------------------------------------------*/

    // 其他容器操作都和vector差不多劲蜻，以下列舉一些其他容器特有的操作


    /*--------------------- string容器一些操作  --------------------*/
    string str1 = "Hello Ace";            // string的幾種構(gòu)造方法
    string str2("Hello World");        
    string str3(str1, 6);                // 從str1下標6開始構(gòu)造在岂， str3 -> Ace
    
    string str4 = str2.substr(0, 5);    // 求子串： str4 -> Hello
    string str5 = str2.substr(6);        // 求子串： str5 -> World
    string str6 = str2.substr(6, 11);    // 求子串： str6 -> World
    // string str7 = str2.substr(12);    // 拋異常： out_of_range

    string str8 = str2.replace(6, 5, "Game");    // 替換：str8 -> Hello Game 從位置6開始锐锣，刪除5個字符，并替換成"Game"
    
    string str9 = str2.append(", Hello Beauty");// 追加字符串： str9 -> Hello World, Hello Beauty

    auto pos1 = str1.find("Ace");                // 查找字符串    : pos1 -> 6 ,返回第一次出現(xiàn)字符串的位置益眉，如果沒找著晌柬，則返回npos

    int res = str1.compare("Hello, Ace");        // 比較字符串： res -> -1, 根據(jù)str1是等于姥份、大于還是小于參數(shù)指定的字符串郭脂， 返回0、整數(shù)或者負數(shù)

    string str10 = "Pi = 3.14159";
    double pi = stod(str10.substr(str10.find_first_of("+-.0123456789")));    // 數(shù)值轉(zhuǎn)換： pi -> 3.14159
    /*------------------------------------------------------------*/


    /*--------------------- deque容器一些操作  --------------------*/
    deque<int> d1;
    d1.push_back(1);                            // 尾后壓入元素
    d1.push_back(2);
    d1.push_back(3);
    d1.push_front(4);                            // 隊頭壓入元素
    d1.push_front(5);
    d1.push_front(6);
    d1.pop_back();                                // 尾后彈出一個元素
    d1.pop_front();                                // 隊頭彈出一個元素

    d1.front();                                    // 取隊頭元素
    d1.back();                                    // 取隊尾元素
    /*------------------------------------------------------------*/


    /*--------------------- list容器一些操作  --------------------*/
    list<int> l;
    l.push_back(1);                                // 尾后壓入元素
    l.push_back(2);
    l.push_back(3);
    l.push_front(4);                            // 隊頭壓入元素
    l.push_front(5);
    l.push_front(6);
    l.pop_back();                                // 尾后彈出一個元素
    l.pop_front();                                // 隊頭彈出一個元素
    l.front();                                    // 取隊頭元素
    l.back();                                    // 取隊尾元素

    l.insert(l.begin(), 88);                    // 某個位置插入元素(性能好)
    l.remove(2);                                // 刪除某個元素(和所給值相同的都刪除)
    l.reverse();                                // 倒置所有元素
    l.erase(--l.end());                            // 刪除某個位置的元素(性能好)
    /*------------------------------------------------------------*/


    /*--------------------- forward_list容器一些操作  --------------*/
    forward_list<int> fl = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    fl.push_front(0);                // 壓入元素澈歉，該容器沒有push_back方法
    auto prev = fl.before_begin();    // 表示fl的"首前元素"
    auto curr = fl.begin();            // 表示fl的第一個元素

    // 循環(huán)遍歷
    while (curr != fl.end())        // 表示仍有元素要處理
    {
        if (*curr % 2)                // 若元素為奇數(shù)展鸡，則刪除
        {
            curr = fl.erase_after(prev);    // 刪除它并移動curr
        }
        else
        {
            prev = curr;            // 移動迭代器curr，指向下一個元素埃难，prev指向curr之前的元素
            ++curr;
        }
    }

    // 操作后： fl = {0, 2, 4, 6, 8}
    /*------------------------------------------------------------*/


    /*--------------------- array容器一些操作  --------------------*/
    array<int, 5> myArray1 = { 1, 2, 3, 4, 5 };    // 定義一個一維數(shù)組
    array<array<int, 2>, 3> myArray2 = {1, 2, 3, 4, 5, 6};    // 定義一個二維數(shù)組
    array<int, 5> myArray3 = {6, 7, 8, 9, 10};
    array<int, 5> myArray4;                // 此數(shù)組并未初始化

    // array.resize();        // array 不能有改變?nèi)萜鞔笮〉牟僮饔ū祝男时葀ector高
    myArray1.swap(myArray3);// 交換兩個數(shù)組的的元素
    myArray4 = myArray1;    // 支持直接這樣賦值涤久，原生的數(shù)組不可以這樣。它把值全部復(fù)制過去忍弛，而不是引用
    myArray1.assign(0);        // 把myArray1的元素全部置為0

    // 遍歷數(shù)組元素
    for (int i = 0; i < myArray1.size(); ++i)
    {
        cout << myArray1[i] << endl;
    }
    /*------------------------------------------------------------*/

    return 0;
}

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

關(guān)聯(lián)容器(associative-container)和順序容器有著根本的不同：關(guān)聯(lián)容器中元素定義是按關(guān)鍵字來保存和訪問的响迂。與之相對，順序容器中的元素是按他們在容器中的位置來順序保存和訪問的细疚。雖然關(guān)聯(lián)容器的很多行為和順序容器相同蔗彤，但其不同之處反映了關(guān)鍵字的作用。

關(guān)聯(lián)容器支持高效的關(guān)鍵字查詢和訪問疯兼。標準庫一共定義了8個關(guān)聯(lián)容器然遏，最主要的類型是map和set。8個容器中吧彪，每個容器：

• 是一個map或者是一個set待侵。map保存關(guān)鍵字-值對；set只保存關(guān)鍵字姨裸。

• 要求關(guān)鍵字唯一或者不要求秧倾。

• 保持關(guān)鍵字有序或者不保證有序。

關(guān)聯(lián)容器類型：

按關(guān)鍵字有序保存元素

• map : 關(guān)聯(lián)數(shù)組傀缩；保存關(guān)鍵字-值對

• set : 關(guān)鍵字即值中狂，即只保存關(guān)鍵字的容器

• multimap : 關(guān)鍵字可重復(fù)的map

• multiset ：關(guān)鍵字可重復(fù)的set

無序集合

• unordered_map ： 用哈希函數(shù)組織的map

• unordered_set : 用哈希函數(shù)組織的set

• unordered_multimap ： 哈希組織的map;關(guān)鍵字可以重復(fù)出現(xiàn)

• unordered_multiset : 哈希組織的set;關(guān)鍵字可以重復(fù)出現(xiàn)

從上面的容器名稱可以看出：允許重復(fù)關(guān)鍵字的容器名字都包含multi；而使用哈希技術(shù)的容器名字都以unordered開頭扑毡。

pair類型

使用關(guān)聯(lián)容器胃榕，繞不開pair類型。它定義在標準庫頭文件utility中瞄摊。一個pair保存兩個數(shù)據(jù)成員勋又。類似容器，pair是一個用來生成特定類型的模板换帜。當(dāng)創(chuàng)建pair時楔壤，我們必須提供兩個類型名，pair的成員將具有對應(yīng)的類型惯驼。與其他標準庫類型不同蹲嚣，pair的數(shù)據(jù)成員是public的。兩個成員分別命名為first和second祟牲。

pair<string, string> author{"Stanley", "C++ Prime"};    // 構(gòu)造一個pair

make_pair(v1, v2);                                        // 返回一個用v1和v2初始化的pair隙畜。pair的類型從v1和v2的類型推斷出來

map的使用

下面的程序是統(tǒng)計每個單詞在輸入中出現(xiàn)的次數(shù)：

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main()
{
    // 統(tǒng)計每個單詞在輸入中出現(xiàn)的次數(shù)
    map<string, size_t> word_count;        // string到map的空map
    string word;
    while (cin >> word)
    {
        ++word_count[word];                // 提取word的計數(shù)器并將其加1
    }

    for (const auto &w : word_count)    // 遍歷map的每個元素
    {
        cout << w.first << "出現(xiàn)的次數(shù)為: " << w.second << endl;
    }

    return 0;
}

set的使用

對上面那個統(tǒng)計單詞的程序做一個擴展，忽略常見單詞说贝。比如 the and or then等议惰。 我們使用set保存想要忽略的單詞，只對不在集合中的單詞進行統(tǒng)計乡恕。

#include <iostream>
#include <map>
#include <set>
#include <string>

using namespace std;

int main()
{
    // 統(tǒng)計每個單詞在輸入中出現(xiàn)的次數(shù)
    map<string, size_t> word_count;        // string到map的空map
    set<string> exclude = {"The", "But", "And", "Or", "An", "A", 
                            "the", "but", "and", "or", "an", "a"};
    string word;
    while (cin >> word)
    {
        // 只統(tǒng)計不在exclude中的單詞言询。find調(diào)用返回一個迭代器俯萎，如果在集合中，返回的迭代器指向其該關(guān)鍵中运杭。否則返回尾后迭代器
        if (exclude.find(word) == exclude.end())
        {
            ++word_count[word];                // 提取word的計數(shù)器并將其加1
        }
    }

    for (const auto &w : word_count)    // 遍歷map的每個元素
    {
        cout << w.first << "出現(xiàn)的次數(shù)為: " << w.second << endl;
    }

    return 0;
} 

0x03 容器適配器

除了順序容器外夫啊，標準庫還定義了三個順序容器適配器:stack、 queue和priority_queue辆憔。 適配器(adaptor)是標準庫的一個通用概念涮母。容器、迭代器和函數(shù)都有適配器躁愿。

本質(zhì)上叛本，一個適配器是一種機制，能使某種事物的行為看起來像另一種事物一樣彤钟。

所有容器適配器都支持的操作和類型

• size_type : 一種類型来候，足以保存當(dāng)前類型的最大對象的大小

• value_type : 元素類型

• container_type : 實現(xiàn)適配器的底層容器類型

• A a : 創(chuàng)建一個名為a的空適配器

• A a(c) : 創(chuàng)建一個名為a的適配器，帶有容器c的一個拷貝

• 關(guān)系運算符 : 每個適配器都支持所有關(guān)系運算符： ==逸雹、营搅！=、<梆砸、<=转质、>、和>=帖世。這些運算符返回底層容器的比較結(jié)果休蟹。

• a.empty() ： 若a包含任何元素，返回fasle日矫，反正返回true

• a.size() : 返回a中的元素數(shù)目

• swap(a, b) : 或?qū)懽鱝.swap(b)赂弓、b.swap(a)。交換a和b的內(nèi)容哪轿。a和b必須有相同的類型盈魁，包括底層容器類型也必須相同

棧適配器(stack)的額外操作

• s.pop() : 刪除棧頂元素，但不返回該元素值窃诉。

• s.push(item) : 創(chuàng)建一個新元素壓入棧頂

• s.emplace(args) ： 同push杨耙，其值由args構(gòu)造

• s.top() ： 返回棧頂元素，但不將元素彈出棧

queue和priority_queue的額外操作

• q.pop() : 返回queue的首元素或priority_queue的最高優(yōu)先級的元素飘痛，但不刪除此元素珊膜。

• q.front() : 返回首元素或者尾元素，但不刪除此元素

• q.back() : 只使用于queue

• q.top() : 返回最高優(yōu)先級元素敦冬，但不刪除此元素

• q.push(item) : 在queue末尾或者priority_queue中恰當(dāng)?shù)奈恢脛?chuàng)建一個元素辅搬，其值為item

• q.emplace(args) : 同push,其值由args構(gòu)造

棧默認基于deque實現(xiàn)。queue默認基于deque實現(xiàn)脖旱。priority_queue默認基于vector實現(xiàn)堪遂。

stack和queue的使用方法比較簡單，priority_queue在存儲自己定義的數(shù)據(jù)結(jié)構(gòu)時萌庆，必須重載 operator < 或者自己寫仿函數(shù)溶褪。下面給個簡單的例子：

#include <iostream>
#include <queue>

using namespace std;

struct Node
{
    int x;
    int y;
};

struct MyCmp
{
    // 自定義的比較函數(shù)
    bool operator ()(Node a, Node b)
    {
        if (a.x == b.x)
        {
            return a.y > b.y;
        }
        
        return a.x > b.x;
    }
};

int main()
{
    // priority_queue<Type, Container, Functional>
    // Type 為數(shù)據(jù)類型，Container 為保存數(shù)據(jù)的容器践险，F(xiàn)unctional 為元素比較方式
    priority_queue<Node, vector<Node>, MyCmp>  myQueue;

    // 添加一些元素
    for (int i = 1; i <= 10; ++i)
    {
        Node node;
        node.x = i;
        node.y = i * i;
        myQueue.push(node);
    }

    // 遍歷元素
    while (!myQueue.empty())
    {
        cout << myQueue.top().x << "," << myQueue.top().y << endl;
        myQueue.pop();            // 出隊
    }

    return 0;
}

0x04 泛型算法

雖然容器提供了眾多操作猿妈，但有些常見的操作，比如查找特定的元素巍虫，替換或者刪除某個特定值彭则，重新排序等，這些由一組泛型算法(generic algorithm)來實現(xiàn)占遥。

大多數(shù)的算法都定義在頭文件algorithm中俯抖，有些關(guān)于數(shù)值的泛型算法定義在numeric這個頭文件中。

標準庫提供了上百個算法瓦胎，幸運地是芬萍，它們的算法結(jié)構(gòu)基本上是一致的。這樣我們就不用死記硬背了搔啊。

算法的形參模式

大多數(shù)的算法具有如下4種形式之一：

• alg(beg, end, other args);

• alg(beg, end, dest, other args);

• alg(beg, end, beg2, other args);

• alg(beg, end, beg2, end2, other args);

其中alg是算法的名字,beg和end表示算法所操作的輸入范圍柬祠。dest表示指定目的位置,beg2和end2表示接受第二個范圍。

標準算法庫對迭代器而不是容器進行操作负芋。因此漫蛔，算法不能直接添加或者刪除元素(可以調(diào)用容器本身的操作來完成)。

find和sort是兩個比較常見的泛型算法旧蛾，我們以這兩個為例子惩猫，來演示一下泛型算法的使用。

find的簡單使用

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

using namespace std;

int main()
{
    int val = 5;
    int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    vector<int> vec = { 11, 22, 33, 44, 55, 66, 77, 88, 99 };
    
    // 查找元素的范圍是第2個元素到第8個元素蚜点，支持內(nèi)置數(shù)組
    // 如果找到想要的元素轧房，則返回結(jié)果指向它
    auto result = find(arr + 1, arr + 7, val);
    cout << *result << endl;    // 輸出結(jié)果為 5,如果沒找到返回7，想一下為什么

    int val2 = 100;
    // 沒有找到這個值绍绘，返回vec.cend()
    auto res = find(vec.begin(), vec.end(), val2);
    if (res == vec.cend())
    {
        cout << "沒找到元素!" << endl;
    }
    else
    {
        cout << *res << endl;
    }

    return 0;
}

簡述一下find的執(zhí)行步驟

1. 訪問序列中的元素
2. 比較此元素與我們要查找的值
3. 如果此元素與我們要查找的值匹配奶镶，find返回標示此元素的值。
4. 否則,find前進到下一個元素陪拘，重復(fù)執(zhí)行步驟2和3厂镇。
5. 如果到達序列尾,find停止。
6. 如果find到達序列末尾左刽，它應(yīng)該返回一個指出元素未找到的值捺信。此值和步驟3中返回的值必須具有相同的類型。

sort的簡單使用

參數(shù)形式為：sort(beg, end, cmp)

對于基本數(shù)據(jù)類型，第三個參數(shù)是可以省略的迄靠，有默認的實現(xiàn)秒咨。但對于自定義的數(shù)據(jù)類型，我們要提供第三個參數(shù)掌挚。第三個參數(shù)叫做謂詞(predicate)雨席。標準庫有一元謂詞(unary predicate)和二元謂詞(binary predicate)之分，分別表示只接受1個參數(shù)和只接受2個參數(shù)吠式。

下面實現(xiàn)一個小程序陡厘，有語文和數(shù)學(xué)兩門課的成績，按總分從大到小排序特占。如果總分相同糙置，數(shù)學(xué)成績高的排在前面。

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

using namespace std;

struct CoureSocre
{
    string name;    // 姓名
    int math;        // 數(shù)學(xué)成績
    int chinese;    // 語文成績
    int total;        // 總成績

    CoureSocre(string _name, int _math, int _chinese)
    {
        name = _name;
        math = _math;
        chinese = _chinese;
        total = math + chinese;
    }
};

bool myCmp(CoureSocre c1, CoureSocre c2)
{
    // 如果總成績相同
    if (c1.total == c2.total)
    {
        return c1.math >= c2.math;
    }

    return c1.total > c2.total;
}

int main()
{
    // 初始化5個學(xué)生的程序
    CoureSocre c1("Ace", 90, 95);
    CoureSocre c2("Shawna", 99, 100);
    CoureSocre c3("Kelly", 100, 99);
    CoureSocre c4("Jordan", 88, 90);
    CoureSocre c5("Kobe", 90, 88);

    // 加入容器
    vector<CoureSocre> vecScoreList = { c1, c2, c3, c4, c5 };

    // 調(diào)用sort算法進行排序
    sort(vecScoreList.begin(), vecScoreList.end(), myCmp);

    cout << "學(xué)生的成績排名為:" << endl;
    for each (CoureSocre c in vecScoreList)        // 使用for each 算法進行遍歷
    {
        cout << "姓名:" << c.name << "\t總成績:" << c.total << "\t數(shù)學(xué):" << c.math << "\t語文:" << c.chinese << endl;
    }

    return 0;
}

另外一個和sort相關(guān)的是stable_sort算法是目。這種穩(wěn)定排序算法維持相等元素的原有順序谤饭。

傳遞的謂詞只能接受1個或者2個參數(shù)，如果我們想傳入更多的參數(shù)怎么辦呢胖笛，這就超出了算法對謂詞的限制网持。這時候，我們就需要上lambda表達式了长踊。具體細節(jié)以后會介紹功舀。

0x05 結(jié)束語

C++ STL很好很強大，熟練使用它將使你如虎添翼身弊。補充一個新手常踩的坑辟汰，在使用for循環(huán)時，不要在里面使用改變迭代器的操作阱佛，比如insert和erase帖汞，這些操作會使迭代器失效，從而引發(fā)意想不到的bug凑术。

程序猿