STL的概述
STL 概述
C++ STL 是一套功能強(qiáng)大的 C++ 模板類，提供了通用的模板類和函數(shù)，這些模板類和函數(shù)可以實(shí)現(xiàn)多種流行和常用的算法，關(guān)于 STL 呢，下面通過一個系統(tǒng)框圖來對其進(jìn)行一個總結(jié)：
image-20210812170610134
可以看到，其主要包含 6 大方面，分別是：
- 容器：一個容器就是一些特定類型對象的集合。STL容器分為兩大類：序列式容器和關(guān)聯(lián)式容器
- 序列式容器：為程序員提供了控制元素存儲和訪問順序的能力。這種順序不依賴于元素的值，而是與元素加入容器時的位置相對應(yīng)。
- 關(guān)聯(lián)式容器：關(guān)聯(lián)容器中的元素是按照關(guān)鍵字來保存和訪問的。關(guān)聯(lián)式容器支持高效的關(guān)鍵字查找和訪問，STL有兩個主要的關(guān)聯(lián)式容器：map 和 set。
- 算法：STL 通過函數(shù)模板提供了很多作用于容器的通用算法，例如查找、插入、刪除、排序等，這些算法均需要引入頭文件，所有的
STL算法都作用在由迭代器所標(biāo)識出來的區(qū)間上，可以分為兩類： - 質(zhì)變算法：運(yùn)算過程中會更改區(qū)間內(nèi) 迭代器所指向的內(nèi)容，如分割，刪除
- 非質(zhì)變算法：運(yùn)算過程中不會改變區(qū)間內(nèi)迭代器所指向的內(nèi)容，如匹配，計(jì)數(shù)等算法
- 迭代器：迭代器提供對一個容器中的對象的訪問方法，并且定義了容器中的對象的范圍。迭代器就如同一個指針。事實(shí)上，C++的指針也是一種迭代器。
- 仿函數(shù)：仿函數(shù)在 C++ 標(biāo)準(zhǔn)中采用的名稱是函數(shù)對象。仿函數(shù)主要用于 STL 中的算法中，雖然函數(shù)指針也可以做為算法的參數(shù)，但是函數(shù)指針不能滿足 STL 對于抽象的要求
- 配接器：配接器又被稱之為是適配器，通俗來講，適配器就是以序列式容器為底層數(shù)據(jù)結(jié)構(gòu)，進(jìn)一步封裝了的為適應(yīng)場景應(yīng)用的容器。STL中提供了三種適配器，分別為： stack ， queue ,priority_queue
- 配置器:以 STL 運(yùn)用的角度而言，空間配置器是最不需要介紹的，它總是藏在一切組件的背后，默默工作。整個 STL 的操作對象都存放在容器之中，而容器需要配置空間以放置資料，這就是空間配置器的作用。
在對 STL 標(biāo)準(zhǔn)庫做了一個總體的概述之后，進(jìn)一步詳細(xì)地對每個部分進(jìn)行敘述。
容器
在一份資料中看到，容器是這樣被形容的：
容器，置物之所也
對于容器來說，又分為序列式容器和關(guān)聯(lián)式容器，這里先從序列式容器開始說起
序列式容器
序列式容器：其中的元素都可序，但是未必有序。C++語言本身提供了一種序列式容器array，STL另外提供了 vector，list，deque，stack，queue，priority-queue等序列容器。其中stack、queue只是由deque改頭換面而成，技術(shù)上稱為一種配接器。
下面將對幾種序列式容器進(jìn)行闡述：
vector
vector 是一個擁有擴(kuò)展功能的數(shù)組，我們可以創(chuàng)建任何類型的 vector
比如說，我們可以通過如下的方式創(chuàng)建一個二一維數(shù)組：
vector A1 {1,2,3,4,5};
對于一維數(shù)組的初始化，也可以采用如下的方式進(jìn)行：
vector A1(10); /* 帶參數(shù)構(gòu)造，10個數(shù)據(jù)都是 0 */
vector A2(10,1); /* 帶參數(shù)構(gòu)造，10個數(shù)據(jù)全是 1 */
除了上述這種給出數(shù)據(jù)的初始化方式以外，也可以通過同類型來進(jìn)行初始化，比如下面這樣：
vector A3(12,1);
vector A4(A3); /* 通過 A3 來初始化 A4 */
也可以通過創(chuàng)建一個存儲 vector元素的 vector的形式來創(chuàng)建一個二維數(shù)組：
vector> Matrix {{1,2,3},{4,5,6},{7,8,9}};
也可以通過如下的方式來初始化二維數(shù)組：
vectorint>> Matrix(N,vector<int>(M,-1));
上述代碼的意思就是說，創(chuàng)建了一個 N*M 的矩陣，并且用 -1 填充所有位置上的值。
在創(chuàng)建了一個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(); /* 返回最后一個元素的下一個地址 */
cout << *(k2 - 1) << endl;
cout << A1.at(0) << endl;
上述代碼經(jīng)過運(yùn)行之后，輸出的結(jié)果如下所示：
1
2
5
1
緊接著，就是關(guān)于元素的插入，刪除，插入刪除可以使用下面方法：
A1.pop_back(); /* 刪除最后一個元素 */
A1.push_back(); /* 在末尾添加一個元素 */
當(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是一個具有擴(kuò)展功能的數(shù)組，也就是說 vector的容量是可以擴(kuò)充的，如下就有一個例子：
最后，來敘述一些 vector的遍歷方式：
for (int i = 0; i < A.size(); i++)
{
cout << A1[i] << endl
}
上述這種方式是和C語言中普通數(shù)組的遍歷方式一樣的，在C++ 中除了這種遍歷方式，還有其余的方式，比如：
for (vector<int>::iterator k = A1.begin(); k != A1.end(); k++)
{
cout << *k << endl;
}
除此之外，還有一種稍微簡便一點(diǎn)的方式，用 auto 來推導(dǎo)迭代：
for (auto iter = A1.begin(); iter != A1.end(); iter++)
{
cout << *iter << endl;
}
除此之外，還有更為簡潔的，如下所示：
for (auto i : A1)
{
cout << i << endl;
}
list
對比于 vector的連續(xù)線性空間，list顯得復(fù)雜許多，他的好處是每次插入或者刪除一個元素，就配置或者釋放一個元素空間。因此list對于空間的運(yùn)用有著絕對的精準(zhǔn)，一點(diǎn)也不浪費(fèi)。而且對于任何位置的元素插入或者元素移除，list永遠(yuǎn)是常數(shù)時間。下圖展示了 list雙向鏈表容器是如何存儲元素的：
image-20210815154103144
在使用 list 的時候，需要包含下面兩行代碼：
#include
using namespace std;
根據(jù)不同的使用場景，有如下幾種方式創(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方法，而且由于是雙鏈表的原因，也可以從頭部插入或者刪除數(shù)據(jù)：push_front，pop_front
#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
對比結(jié)果，和代碼就可以清除地知道具體地作用，在這里需要注意地就是：mylist.begin()和 mylist.end()返回的分別是：返回容器中第一個元素的雙向迭代器，返回指向容器中最后一個元素所在位置的下一個位置的雙向迭代器。
上述所敘述的基本是 list相對比與 vector相同的部分，那么兩者不同的部分呢，由于 list 數(shù)據(jù)結(jié)構(gòu)的特殊，也提供了一些 vector 沒有的操作，比如說：
- splice: 將某個連續(xù)范圍的元素從一個 list 遷移到另一個（或者同一個）list 的某個節(jié)點(diǎn)
- remove: 刪除list中指定值的元素，和 erase 不同，這里是根據(jù)值而不是位置去刪除。
- merge: 合并兩個有序鏈表并使之有序。
- sort: 針對 list 的特定排序算法，默認(rèn)的算法庫中的sort需要隨機(jī)訪問迭代器，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);
下面分別就這三種原型進(jìn)行敘述：
#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é)果為：
1
10
20
30
2
3
4
這里需要注意的是：此處的 it由于是指向的mylist1，經(jīng)過splice后，此迭代器依然存在于 mylist1中，所以沒有失效。
#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)在就無效了
*/
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 */
}
上述注釋對 splice三種原型進(jìn)行了常數(shù)，結(jié)合注釋也能夠清楚地知道具體地功能。
除了splice以外，還有remove函數(shù)以及 merge 和sort也是區(qū)別于vector的，所涉及的代碼如下所示：
#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，使用起來也很簡單，它的作用是將兩個有序序列進(jìn)行合并，注意，必須是有序序列，并且，兩種序列的排序方式是一致的，也就是說，要么都是升序，要么都是降序。下面是關(guān)于 merge的使用例子：
#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ù)時間內(nèi)對起頭端進(jìn)行元素的插入或移除操作
- deque 沒有所謂的容量（capacity）概念，因?yàn)樗莿討B(tài)地以分段連續(xù)空間組合而成，隨時可以增加一段新的空間并鏈接起來。
關(guān)于deque要指出的一點(diǎn)是，它的迭代并不是普通的指針，其復(fù)雜度要大的多，因此除非必要，應(yīng)該盡可能使用 vector 而非 deque。對 deque 進(jìn)行排序操作，為了提高效率，可以先將 deque 完整復(fù)制到一個 vector 中，將 vector 排序后（利用 STL sort），再復(fù)制回 deque。
下面是關(guān)于 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
適配器
在本文的最開頭給出了適配器的概念，再來回顧一下，就是：適配器就是以序列式容器為底層數(shù)據(jù)結(jié)構(gòu)，進(jìn)一步封裝了的為適應(yīng)場景應(yīng)用的容器。STL中提供了三種適配器，分別為： stack ， queue ,priority_queue
stack
Stack (堆棧) 是一個容器類的改編,為程序員提供了堆棧的全部功能,也就是說實(shí)現(xiàn)了一個先進(jìn)后出 (FILO)的數(shù)據(jù)結(jié)構(gòu)，其示意圖如下所示：
image-20210815225740108
它主要支持如下操作：
- empty: 判斷 棧是否為空
- size: 取得棧的大小
- top: 取得棧頂?shù)脑?/li>
- push：入棧操作
- pop: 出棧操作
stack 的所有元素都必須滿足先進(jìn)后出的機(jī)制，只有stack頂?shù)脑?，才有機(jī)會被外界取用，以此stack不提供迭代器，關(guān)于它的簡單的使用例子如下所示：
#includequeue
queue 是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，允許從最底部加入元素，同時取得最頂部元素。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)，但取出時一定是從優(yōu)先權(quán)最高的元素開始取。優(yōu)先隊(duì)列具有權(quán)值觀念，其內(nèi)的元素并非依照被推入的次序排列，而是自動依照元素的權(quán)值排列，權(quán)值最高者排在最前面。
優(yōu)先隊(duì)列完全以底部容器為根據(jù)，加上 heap 處理規(guī)則，具有修改某物接口，形成另一種風(fēng)貌的性質(zhì)，因此是配接器。優(yōu)先隊(duì)列中的所有元素，進(jìn)出都有一定的規(guī)則，只有queue頂部的元素（權(quán)值最高者），才有機(jī)會被外界取用。因此并不提供遍歷功能，也不提供迭代器。
優(yōu)先隊(duì)列的構(gòu)造函數(shù)和其他序列式容器的略有不同，因?yàn)樾枰付ǖ讓尤萜鞯念愋秃蛢?yōu)先級比較的仿函數(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++中的序列式容器做了一個總結(jié)，當(dāng)然 C++ 中的容器不止這些，還有其余內(nèi)容，這次就寫到這里啦，下次繼續(xù)。
-
函數(shù)
+關(guān)注
關(guān)注
3文章
4327瀏覽量
62569 -
C++
+關(guān)注
關(guān)注
22文章
2108瀏覽量
73618 -
STL
+關(guān)注
關(guān)注
0文章
86瀏覽量
18319
發(fā)布評論請先 登錄
相關(guān)推薦
STL130N6F7 MOS管現(xiàn)貨
X-CUBE-STL與ARM的STL的區(qū)別是什么？
effective stl中文版下載pdf
C++ STL的概念及舉例
STEP7 STL語句表編程使用手冊
STL算法在GIS中的應(yīng)用
數(shù)據(jù)結(jié)構(gòu)與STL
基于STL曲面網(wǎng)格重建算法
C++之STL庫中的容器
STL內(nèi)容介紹
工商網(wǎng)監(jiān)
評論