STL 概述

C++ STL 是一套功能強(qiáng)大的 C++ 模板類，提供了通用的模板類和函數(shù)，這些模板類和函數(shù)可以實(shí)現(xiàn)多種流行和常用的算法，關(guān)于 STL 呢，下面通過一個(gè)系統(tǒng)框圖來對(duì)其進(jìn)行一個(gè)總結(jié)：

image-20210812170610134

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

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

在對(duì) STL 標(biāo)準(zhǔn)庫(kù)做了一個(gè)總體的概述之后，進(jìn)一步詳細(xì)地對(duì)每個(gè)部分進(jìn)行敘述。

容器

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

容器，置物之所也

對(duì)于容器來說，又分為序列式容器和關(guān)聯(lián)式容器，這里先從序列式容器開始說起

序列式容器

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

下面將對(duì)幾種序列式容器進(jìn)行闡述：

vector

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

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

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

對(duì)于一維數(shù)組的初始化，也可以采用如下的方式進(jìn)行：

vector A1(10);     /* 帶參數(shù)構(gòu)造，10個(gè)數(shù)據(jù)都是 0 */
vector A2(10,1);   /* 帶參數(shù)構(gòu)造，10個(gè)數(shù)據(jù)全是 1 */

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

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

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

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

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

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

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

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

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();    /* 返回最后一個(gè)元素的下一個(gè)地址 */
cout << *(k2 - 1) << endl;

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

上述代碼經(jīng)過運(yùn)行之后，輸出的結(jié)果如下所示：

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

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

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

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是一個(gè)具有擴(kuò)展功能的數(shù)組，也就是說 vector的容量是可以擴(kuò)充的，如下就有一個(gè)例子：

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

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

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

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

除此之外，還有一種稍微簡(jiǎn)便一點(diǎn)的方式，用 auto 來推導(dǎo)迭代：

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

除此之外，還有更為簡(jiǎn)潔的，如下所示：

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

list

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

image-20210815154103144

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

#include 
using namespace std;

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

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

可以看到上述的初始化的方法和vector一樣，都是有這么幾種方式，同樣的，和vector一樣，list也提供了push_back,pop_back方法，而且由于是雙鏈表的原因，也可以從頭部插入或者刪除數(shù)據(jù)：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;
    }
}

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

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

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

上述所敘述的基本是 list相對(duì)比與 vector相同的部分，那么兩者不同的部分呢，由于 list 數(shù)據(jù)結(jié)構(gòu)的特殊，也提供了一些 vector 沒有的操作，比如說：

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

先從 splice說起，對(duì)于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);

下面分別就這三種原型進(jìn)行敘述：

#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;
}

代碼輸出結(jié)果為：

這里需要注意的是：此處的 it由于是指向的mylist1，經(jīng)過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 現(xiàn)在就無(wú)效了
    */

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

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

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

上述注釋對(duì) splice三種原型進(jìn)行了常數(shù)，結(jié)合注釋也能夠清楚地知道具體地功能。

除了splice以外，還有remove函數(shù)以及 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;
}

最終輸出的結(jié)果為：

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;
}

關(guān)于 merge，使用起來也很簡(jiǎn)單，它的作用是將兩個(gè)有序序列進(jìn)行合并，注意，必須是有序序列，并且，兩種序列的排序方式是一致的，也就是說，要么都是升序，要么都是降序。下面是關(guān)于 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;
}

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

deque

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

deque 允許常數(shù)時(shí)間內(nèi)對(duì)起頭端進(jìn)行元素的插入或移除操作
deque 沒有所謂的容量（capacity）概念，因?yàn)樗莿?dòng)態(tài)地以分段連續(xù)空間組合而成，隨時(shí)可以增加一段新的空間并鏈接起來。

關(guān)于deque要指出的一點(diǎn)是，它的迭代并不是普通的指針，其復(fù)雜度要大的多，因此除非必要，應(yīng)該盡可能使用 vector 而非 deque。對(duì) deque 進(jìn)行排序操作，為了提高效率，可以先將 deque 完整復(fù)制到一個(gè) vector 中，將 vector 排序后（利用 STL sort），再?gòu)?fù)制回 deque。

下面是關(guān)于 deque的一個(gè)例子：

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

適配器

在本文的最開頭給出了適配器的概念，再來回顧一下，就是：適配器就是以序列式容器為底層數(shù)據(jù)結(jié)構(gòu)，進(jìn)一步封裝了的為適應(yīng)場(chǎng)景應(yīng)用的容器。STL中提供了三種適配器，分別為： stack ， queue ,priority_queue

stack

Stack (堆棧) 是一個(gè)容器類的改編,為程序員提供了堆棧的全部功能,也就是說實(shí)現(xiàn)了一個(gè)先進(jìn)后出 (FILO)的數(shù)據(jù)結(jié)構(gòu)，其示意圖如下所示：

image-20210815225740108

它主要支持如下操作：

empty: 判斷棧是否為空
size: 取得棧的大小
top: 取得棧頂?shù)脑?/li>
push：入棧操作
pop: 出棧操作

stack 的所有元素都必須滿足先進(jìn)后出的機(jī)制，只有stack頂?shù)脑?，才有機(jī)會(huì)被外界取用，以此stack不提供迭代器，關(guān)于它的簡(jiǎn)單的使用例子如下所示：

#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 是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，允許從最底部加入元素，同時(shí)取得最頂部元素。STL以 deque 作為缺省情況下的 queue 底部結(jié)構(gòu),下面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)先隊(duì)列（priority queue）允許用戶以任何次序?qū)⑷魏卧赝迫肴萜鲀?nèi)，但取出時(shí)一定是從優(yōu)先權(quán)最高的元素開始取。優(yōu)先隊(duì)列具有權(quán)值觀念，其內(nèi)的元素并非依照被推入的次序排列，而是自動(dòng)依照元素的權(quán)值排列，權(quán)值最高者排在最前面。

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

優(yōu)先隊(duì)列的構(gòu)造函數(shù)和其他序列式容器的略有不同，因?yàn)樾枰付ǖ讓尤萜鞯念愋秃蛢?yōu)先級(jí)比較的仿函數(shù)。C++11 中一共有5大種構(gòu)造函數(shù)，下面列出其中一種：

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

下面是具體的構(gòu)造示例：

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);

小結(jié)

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

聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請(qǐng)聯(lián)系本站處理。舉報(bào)投訴