從零開始_學_資料結構（五）——STL（map、set、list、vector）

stl容器

前注：

stl（标準模闆庫）是一個c++的軟體庫，也是c++标準程式庫的一部分。

這些容器，應該都是stl裡面的一個類。

vector封裝數組、list封裝連結清單、map和set封裝二叉樹

一、list

在不懂的時候，list可以了解為雙向連結清單（很像，但事實上不是）。

（1）聲明一個list對象：

①包含頭檔案list：#include<list>

②聲明他：std::list<int> one;

//聲明一個list對象

③需要注意，list位于std名稱空間之中，是以如果使用using namespace std，可以省略std::

（2）使用

疊代器：

①疊代器，在不懂的時候，可以了解為指針，指向對象。但事實上，疊代器不是指針（例如，指針可以加一個int值，但疊代器是不可以的）。

②聲明一個list類疊代器：std::list<int>::iterator pr = one.begin();

//一個疊代器，用于指向one的第一個對象

③疊代器可以使用++和--

這樣的形式；

pr++;

pr--;

++pr;

--pr;

效果是：++（指向list對象内的下一項），--（指向上一個項）；

note：假如目前疊代器已經指向最後或最初，則不能超出界限，否則會出錯（例如最後時不能+，第一個時不能-）

④利用疊代器插入一個成員（有疑問）。

int a = 1;

one.insert(pr, a);

//注意，根據觀察，每添加一個對象，疊代器便會自動指向下一個位置。

⑤查詢目前容器裡有多少個項目：

cout << one.size();

⑥删除一個成員

更多的使用，參考連結：

http://www.cppblog.com/lee7/archive/2008/04/14/47036.html

· 疊代

(iterator)

· list.begin() 回傳指向第一個元素的

iterator。

· list.end() 回傳指向最末元素的下一個位置的

· list.rbegin() 回傳指向最末個元素的反向

· list.rend() 回傳指向第一個元素的前一個位置的反向

· capacity/size:

· list.empty() 若list内部為空，則回傳true值。

· list.size() 回傳list内實際的元素個數。

· list.resize() 重新分派list的長度。

· 存取元素的方法

· list.front() 存取第一個元素。

· list.back() 存取最末個元素。

· modify methods

· list.push_front() 增加一個新的元素在

list 的前端。

· list.pop_front() 删除

list 的第一個元素。

· list.push_back() 增加一個新的元素在

list 的尾端。

· list.pop_back() 删除

list 的最末個元素。

· list.insert() -

插入一個或多個元素至 list内的任意位置。

· list.erase() -

删除 list中一個或多個元素。

· list.clear() -

清空所有元素。

· 重新配置／重設長度

· list.reserve() -

如有必要，可改變 list的容量大小（配置更多的記憶體）。

· list.resize() -

改變 list目前持有的元素個數。

二、map

如代碼：

#include<map>

map<char*,

int> map;

//聲明一個map

map["first"] = 1;

//first是關鍵字key，1是值。值和key是成對出現的。可以把first了解為下标，隻不過和平常的int下标不同

map["second"] = 2;

map["qqq"] = 3;

int>::iterator pr = map.begin();

//疊代器指向開始（first）

//疊代器指向下一個

cout << pr->first

<< " : ";

//輸出key值，注意不要括号

cout << pr->second

<< endl;

//輸出值（在這裡就是int值）

map.erase(pr++);

//删除目前疊代器指向的元素，需要使用pr++，如果在這行之後使用的話，疊代器會無法使用（除非重新指派）

//此時疊代器指向的原本的第三個（目前的第二個）

//此時疊代器指向原本的第一個（目前第一個），原本第二個被删除了

map.insert(pr,{ "ww",4 });

//插入一個（插入位置是最後，第三個），當目前疊代器還指向的是第一個

//

三、vector

#include<vector>

vector<int>abc(10);

//類型為int，數量為10

abc[1] = 1;

//第二個元素指派為1

cout << abc[1] << endl;

//輸出第二個元素

vector<int>::iterator pr = abc.begin();

//疊代器指向第一個元素

cout << *pr

//輸出該元素的值

cout << abc.size()

<< endl; //數組元素數量

abc.front(); //數組第一個元素的引用

abc.back(); //數組最後一個元素的引用

其他用法：

<a target="_blank" href="https://zh.wikipedia.org/wiki/vector_(stl)">https://zh.wikipedia.org/wiki/vector_(stl)</a>

· 通路元素的方法

· vec[i] - 通路索引值為 i 的元素引用。 (索引值從零起算，故第一個元素是vec[0]。)

· vec.at(i) - 通路索引值為 i 的元素的引用，以 at() 通路會做數組邊界檢查，如果通路越界将會抛出一個例外，這是與operator[]的唯一差異。

· vec.front() - 回傳 vector 第一個元素的引用。

· vec.back() - 回傳 vector 最尾元素的引用。

· 新增或移除元素的方法

· vec.push_back() - 新增元素至 vector 的尾端，必要時會進行記憶體配置。

· vec.pop_back() - 删除 vector 最尾端的元素。

· vec.insert() - 插入一個或多個元素至 vector 内的任意位置。

· vec.erase() - 删除 vector 中一個或多個元素。

· vec.clear() - 清空所有元素。

· 擷取長度/容量

· vec.size() - 擷取 vector 目前持有的元素個數。

· vec.empty() - 如果 vector 内部為空，則傳回 true 值。

· vec.capacity() - 擷取 vector 目前可容納的最大元素個數。這個方法與記憶體的配置有關，它通常隻會增加，不會因為元素被删減而随之減少。

· 重新配置／重置長度

· vec.reserve() - 如有必要，可改變 vector 的容量大小（配置更多的記憶體）。在衆多的 stl 實做，容量隻能增加，不可以減少。

· vec.resize() - 改變 vector 目前持有的元素個數。

· 疊代 (iterator)

· vec.begin() - 回傳一個iterator，它指向 vector 第一個元素。

· vec.end() - 回傳一個iterator，它指向 vector 最尾端元素的下一個位置（請注意：它不是最末元素）。

· vec.rbegin() - 回傳一個反向iterator，它指向 vector 最尾端元素的。

· vec.rend() - 回傳一個iterator，它指向 vector 的第一個元素。

四、set

（1）set以結點的方式來存儲。

（2）插入和删除之後，iterator可能失效。

（3）set中使用二分查找法，效率是f(n)=log n;

（4）常用代碼：

#include&lt;set&gt;

set&lt;int&gt;abc;

//聲明一個set對象

abc.insert(1); //插入一個

abc.insert(100); //再插入一個

abc.insert(50); //插入第三個

set&lt;int&gt;::iterator pr = abc.begin();

//疊代器指向第一個

//指向下一個，注意，不是插入的第二個（100），而是值從小到大的第二個50

//輸出50

&lt;&lt; endl; //abc總共的元素個數

cout &lt;&lt; abc.count(50)

&lt;&lt; endl; //輸出值50在整個abc裡面出現的次數

cout &lt;&lt; abc.max_size()

&lt;&lt; endl; //abc的最大能容納的個數（很多很多），大概是int_max的1/10