STL 概述

C++ STL 是一套功能強大的 C++ 模板類，提供了通用的模板類和函數，這些模板類和函數可以實現多種流行和常用的算法，關于 STL 呢，下面通過一個系統框圖來對其進行一個總結：

image-20210812170610134

可以看到，其主要包含 6 大方面，分別是：

• 容器：一個容器就是一些特定類型對象的集合。STL容器分為兩大類：序列式容器和關聯式容器
• 序列式容器：為程序員提供了控制元素存儲和訪問順序的能力。這種順序不依賴于元素的值，而是與元素加入容器時的位置相對應。
• 關聯式容器：關聯容器中的元素是按照關鍵字來保存和訪問的。關聯式容器支持高效的關鍵字查找和訪問，STL有兩個主要的關聯式容器：map 和 set。
• 算法：STL 通過函數模板提供了很多作用于容器的通用算法，例如查找、插入、刪除、排序等，這些算法均需要引入頭文件，所有的 STL算法都作用在由迭代器所標識出來的區(qū)間上，可以分為兩類：
• 質變算法：運算過程中會更改區(qū)間內 迭代器所指向的內容，如分割，刪除
• 非質變算法：運算過程中不會改變區(qū)間內迭代器所指向的內容，如匹配，計數等算法
• 迭代器：迭代器提供對一個容器中的對象的訪問方法，并且定義了容器中的對象的范圍。迭代器就如同一個指針。事實上，C++的指針也是一種迭代器。
• 仿函數：仿函數在 C++ 標準中采用的名稱是函數對象。仿函數主要用于 STL 中的算法中，雖然函數指針也可以做為算法的參數，但是函數指針不能滿足 STL 對于抽象的要求
• 配接器：配接器又被稱之為是適配器，通俗來講，適配器就是以序列式容器為底層數據結構，進一步封裝了的為適應場景應用的容器。STL中提供了三種適配器，分別為： stack ， queue ,priority_queue
• 配置器:以 STL 運用的角度而言，空間配置器是最不需要介紹的，它總是藏在一切組件的背后，默默工作。整個 STL 的操作對象都存放在容器之中，而容器需要配置空間以放置資料，這就是空間配置器的作用。

在對 STL 標準庫做了一個總體的概述之后，進一步詳細地對每個部分進行敘述。

容器

在一份資料中看到，容器是這樣被形容的：

容器，置物之所也

對于容器來說，又分為序列式容器和關聯式容器，這里先從序列式容器開始說起

序列式容器

序列式容器：其中的元素都可序，但是未必有序。C++語言本身提供了一種序列式容器array，STL另外提供了 vector，list，deque，stack，queue，priority-queue等序列容器。其中stack、queue只是由deque改頭換面而成，技術上稱為一種配接器。

下面將對幾種序列式容器進行闡述：

vector

vector 是一個擁有擴展功能的數組，我們可以創(chuàng)建任何類型的 vector

比如說，我們可以通過如下的方式創(chuàng)建一個二一維數組：

vector A1 {1,2,3,4,5};

對于一維數組的初始化，也可以采用如下的方式進行：

vector A1(10);     /* 帶參數構造，10個數據都是 0 */
vector A2(10,1);   /* 帶參數構造，10個數據全是 1 */

除了上述這種給出數據的初始化方式以外，也可以通過同類型來進行初始化，比如下面這樣：

vector  A3(12,1);
vector  A4(A3);          /* 通過 A3 來初始化 A4 */

也可以通過創(chuàng)建一個存儲 vector元素的 vector的形式來創(chuàng)建一個二維數組：

vector> Matrix {{1,2,3},{4,5,6},{7,8,9}};

也可以通過如下的方式來初始化二維數組：

vectorint>> Matrix(N,vector<int>(M,-1));

上述代碼的意思就是說，創(chuàng)建了一個 N*M 的矩陣，并且用 -1 填充所有位置上的值。

在創(chuàng)建了一個vector之后，又該如何訪問內部的數據成員呢？有如下幾種方式：

vector<int> A1 = {1,2,3,4,5};
vector<int>::iterator k1 = A1.begin();
cout << *k1 << endl;
cout << *(k1 + 1) << endl;

vector<int>::iterator k2 = A1.end();    /* 返回最后一個元素的下一個地址 */
cout << *(k2 - 1) << endl;

cout << A1.at(0) << endl;

上述代碼經過運行之后，輸出的結果如下所示：

1
2
5
1

緊接著，就是關于元素的插入，刪除，插入刪除可以使用下面方法：

A1.pop_back();               /* 刪除最后一個元素 */
A1.push_back();              /* 在末尾添加一個元素 */

當然，也可以在特定位置插入元素，如下所示：

vector A1 = {1,2,3,4,5};
vector::iterator k = A1.begin();
A1.insert(k + 1, 9);

插入元素之后，A1里的元素變?yōu)椋?/p>

1,9,2,3,4,5

在敘述 vector的開頭，就說了vector是一個具有擴展功能的數組，也就是說 vector的容量是可以擴充的，如下就有一個例子：

最后，來敘述一些 vector的遍歷方式：

for (int i = 0; i < A.size(); i++)
{
    cout << A1[i] << endl
}

上述這種方式是和C語言中普通數組的遍歷方式一樣的，在C++ 中除了這種遍歷方式，還有其余的方式，比如：

for (vector<int>::iterator k = A1.begin(); k != A1.end(); k++)
{
    cout << *k << endl;
}

除此之外，還有一種稍微簡便一點的方式，用 auto 來推導迭代：

for (auto iter = A1.begin(); iter != A1.end(); iter++)
{
    cout << *iter << endl;
}

除此之外，還有更為簡潔的，如下所示：

for (auto i : A1)
{
    cout << i << endl;
}

list

對比于 vector的連續(xù)線性空間，list顯得復雜許多，他的好處是每次插入或者刪除一個元素，就配置或者釋放一個元素空間。因此list對于空間的運用有著絕對的精準，一點也不浪費。而且對于任何位置的元素插入或者元素移除，list永遠是常數時間。下圖展示了 list雙向鏈表容器是如何存儲元素的：

image-20210815154103144

在使用 list 的時候，需要包含下面兩行代碼：

#include 
using namespace std;

根據不同的使用場景，有如下幾種方式創(chuàng)建 list 容器：

list<int> values;        /* 空的 list 容器 */
list<int> values(10);    /* 創(chuàng)建一個包含 n 個元素的 list 容器 */
list<int> values(10,5);  /* 創(chuàng)建了一個包含 10 個元素且值都為 5 的容器 */
list<int> values2(values);

可以看到上述的初始化的方法和vector一樣，都是有這么幾種方式，同樣的，和vector一樣，list也提供了push_back,pop_back方法，而且由于是雙鏈表的原因，也可以從頭部插入或者刪除數據：push_front，pop_front

#include 
#include 
#include 

using namespace std;

int main(int argc, char **argv)
{
    list<int> mylist;

    mylist.push_back(33);
    mylist.push_back(22);
    mylist.push_front(11);

    for (auto n: mylist)
    {
        cout << n << endl;
    }

    mylist.front() -= mylist.back();
    mylist.insert(mylist.begin(),0);

    cout << "^^^^^^^^^^^^^^^^^^^^^^^^^" << endl;
    for (auto n : mylist)
    {
        cout << n << endl;
    }
    cout << "========================" << endl;
    mylist.erase(--mylist.end());

    for (auto n : mylist)
    {
        cout << n << endl;
    }
}

上述代碼最終的輸出結果如下所示：

11
33
22
^^^^^^^^^^^^^^^^^^^^^^^^^
0
-11
33
22
========================
0
-11
33

對比結果，和代碼就可以清除地知道具體地作用，在這里需要注意地就是：mylist.begin()和 mylist.end()返回的分別是：返回容器中第一個元素的雙向迭代器，返回指向容器中最后一個元素所在位置的下一個位置的雙向迭代器。

上述所敘述的基本是 list相對比與 vector相同的部分，那么兩者不同的部分呢，由于 list 數據結構的特殊，也提供了一些 vector 沒有的操作，比如說：

• splice: 將某個連續(xù)范圍的元素從一個 list 遷移到另一個（或者同一個）list 的某個節(jié)點
• remove: 刪除list中指定值的元素，和 erase 不同，這里是根據值而不是位置去刪除。
• merge: 合并兩個有序鏈表并使之有序。
• sort: 針對 list 的特定排序算法，默認的算法庫中的sort需要隨機訪問迭代器，list并不能提供

先從 splice說起，對于splice來說，其主要有如下三種原型：

void splice(iterator position, list  &x);
void splice(iterator position, list  &x, iterator it);
void splice(iterator position, list  &x, iterator first, iterator last);

下面分別就這三種原型進行敘述：

#include 
#include 
#include 

using namespace std;

int main(int argc, char** argv)
{
    list<int> mylist1, mylist2;
    list<int>::iterator it;

    for (int i = 0; i <= 4; i++)
        mylist1.push_back(i);

    for (int i = 0; i <= 3; i++)
        mylist2.push_back(i*10);

    it = mylist1.begin();
    it++;

    mylist1.splice(it,mylist2);

    for (auto n : mylist1)
        cout << n << endl;
}

代碼輸出結果為：

1
10
20
30
2
3
4

這里需要注意的是：此處的 it由于是指向的mylist1，經過splice后，此迭代器依然存在于 mylist1中，所以沒有失效。

#include 
#include 
#include 

using namespace std;

int main(int argc, char** argv)
{
    list<int> mylist1, mylist2;
    list<int>::iterator it;

    for (int i = 0; i <= 4; i++)
        mylist1.push_back(i);

    for (int i = 0; i <= 3; i++)
        mylist2.push_back(i*10);

    it = mylist1.begin();
    it++;

    mylist1.splice(it,mylist2);

    for (auto n : mylist1)
        cout << n << endl;
    cout << "^^^^^^^^^^^^^^^^^^^^^" << endl;

    mylist2.splice(mylist2.begin(), mylist1, it);

    /* mylist1: 1, 10, 20, 30, 3, 4
    *  mylist2: 2
    *  it 現在就無效了
    */

    cout << "====================" << endl;

    it = mylist1.begin(); /* 現在 it 指向的是 1 */
    advance(it, 3);       /* 現在 it 就指向的是 30 */

    mylist1.splice(mylist.begin(), mylist1, it, mylist.end());
    /* 經過上述這么操作之后 */
    /* mylist1 就變成了：30 3 4 1 10 20 */
}

上述注釋對 splice三種原型進行了常數，結合注釋也能夠清楚地知道具體地功能。

除了splice以外，還有remove函數以及 merge 和sort也是區(qū)別于vector的，所涉及的代碼如下所示：

#include 
#include 
#include 

using namespace std;

int main(int argc, char** argv)
{
    list  mylist;
    mylist.push_back('A');
    mylist.push_back('B');
    mylist.push_back('C');
    mylist.remove("B");

    mylist.sort();

    for (auto n : mylist)
           cout << n << endl;  

    return 0;
}

最終輸出的結果為：

int main(int argc, char** argv)
{
    list  mylist;
    mylist.push_back("one");
    mylist.push_back("two");
    mylist.push_back("three");
    mylist.remove("two");

    mylist.sort();

    for (auto n : mylist)
           cout << n << endl;  

    return 0;
}

關于 merge，使用起來也很簡單，它的作用是將兩個有序序列進行合并，注意，必須是有序序列，并且，兩種序列的排序方式是一致的，也就是說，要么都是升序，要么都是降序。下面是關于 merge的使用例子：

#include
#include

int main(){
    // declaring the lists
    // initially sorted, use sort() if unsorted
    std::list<int> list1 = { 10, 20, 30 };
    std::list<int> list2 = { 40, 50, 60 };

    // merge operation
    list2.merge(list1);

    std::cout << "List:  ";

    for (auto it = list2.begin(); it != list2.end(); ++it)
        std::cout << *it << " ";

    return 0;
}

代碼輸出的結果是：10，20，30，40，50，60

deque

vector 是單向開口的連續(xù)線性空間，deque 則是一種雙向開口的連續(xù)線性空間。所謂雙向開口，意思是可以在頭尾兩端分別做元素的插入和刪除工作,deque 和 vector 的差異在于：

• deque 允許常數時間內對起頭端進行元素的插入或移除操作
• deque 沒有所謂的容量（capacity）概念，因為它是動態(tài)地以分段連續(xù)空間組合而成，隨時可以增加一段新的空間并鏈接起來。

關于deque要指出的一點是，它的迭代并不是普通的指針，其復雜度要大的多，因此除非必要，應該盡可能使用 vector 而非 deque。對 deque 進行排序操作，為了提高效率，可以先將 deque 完整復制到一個 vector 中，將 vector 排序后（利用 STL sort），再復制回 deque。

下面是關于 deque的一個例子：

std::deque<int> mydeque;

// set some initial values:
for (int i=1; i<6; i++) mydeque.push_back(i);   // 1 2 3 4 5
std::deque<int>::iterator it = mydeque.begin();
++it;
it = mydeque.insert (it,10);
mydeque.erase(--mydeque.end());
for(auto n: mydeque) std::cout << n << " ";     // 1 10 2 3 4

適配器

在本文的最開頭給出了適配器的概念，再來回顧一下，就是：適配器就是以序列式容器為底層數據結構，進一步封裝了的為適應場景應用的容器。STL中提供了三種適配器，分別為： stack ， queue ,priority_queue

stack

Stack (堆棧) 是一個容器類的改編,為程序員提供了堆棧的全部功能,也就是說實現了一個先進后出 (FILO)的數據結構，其示意圖如下所示：

image-20210815225740108

它主要支持如下操作：

• empty: 判斷 棧是否為空
• size: 取得棧的大小
• top: 取得棧頂的元素
• push：入棧操作
• pop: 出棧操作

stack 的所有元素都必須滿足先進后出的機制，只有stack頂的元素，才有機會被外界取用，以此stack不提供迭代器，關于它的簡單的使用例子如下所示：

#include
#include

using namespace std;

int main(int argc, char **argv)
{
    stack<int> mystack;

    for (int i = 0; i < 4; i++)
        mystack.push(i);

    cout << "pop out element..." << endl;

    while (!mystack.empty())
    {
        cout << mystack.top();
    }

    cout << "\\n" << endl;
    return 0;
}
輸出：
// Popping out elements... 4 3 2 1 0

queue

queue 是一種先進先出（FIFO）的數據結構，允許從最底部加入元素，同時取得最頂部元素。STL以 deque 作為缺省情況下的 queue 底部結構,下面queue的示意圖：

image-20210815230959996

代碼如下所示：

std::queue<int> myqueue;
for (int i=0; i<5; ++i) myqueue.push(i);
std::cout << "Popping out elements...";
while (!myqueue.empty())
{
   std::cout << ' ' << myqueue.front();
   myqueue.pop();
}
std::cout << '\\n';
// Popping out elements... 0 1 2 3 4
return 0;

priority queue

優(yōu)先隊列（priority queue）允許用戶以任何次序將任何元素推入容器內，但取出時一定是從優(yōu)先權最高的元素開始取。優(yōu)先隊列具有權值觀念，其內的元素并非依照被推入的次序排列，而是自動依照元素的權值排列，權值最高者排在最前面。

優(yōu)先隊列完全以底部容器為根據，加上 heap 處理規(guī)則，具有修改某物接口，形成另一種風貌的性質，因此是配接器。優(yōu)先隊列中的所有元素，進出都有一定的規(guī)則，只有queue頂部的元素（權值最高者），才有機會被外界取用。因此并不提供遍歷功能，也不提供迭代器。

優(yōu)先隊列的構造函數和其他序列式容器的略有不同，因為需要指定底層容器的類型和優(yōu)先級比較的仿函數。C++11 中一共有5大種構造函數，下面列出其中一種：

template <class InputIterator>
priority_queue (InputIterator first, InputIterator last,
                const Compare& comp, const Container& ctnr);

下面是具體的構造示例：

int myints[]= {10,60,50,20};

std::priority_queue<int> first;
std::priority_queue<int> second (myints,myints+4);
std::priority_queue<int, std::vector<int>, std::greater<int>> third (myints,myints+4);

小結

本次就是關于C++中的序列式容器做了一個總結，當然 C++ 中的容器不止這些，還有其余內容，這次就寫到這里啦，下次繼續(xù)。