STL标準容器類學習筆記之(Vector/Deque/List)

STL标準容器類簡介

1.順序性容器

vector相當與數組，從後面快速的插入與删除，直接通路任何元素

deque雙隊列，從前面或後面快速的插入與删除，直接通路任何元素

list雙連結清單，從任何地方快速插入與删除

2.關聯容器

set快速查找，不允許重複值

multiset快速查找，允許重複值

map一對一映射，基于關鍵字快速查找，不允許重複值

multimap一對多映射，基于關鍵字快速查找，允許重複值

3.容器擴充卡

stack後進先出

queue先進先出

priority_queue最高優先級元素總是第一個出列

4.所有标準庫共有函數

預設構造函數      提供容器預設初始化的構造函數。

複制構造函數      将容器初始化為現有同類容器副本的構造函數

析構函數      不再需要容器時進行記憶體整理的析構函數

empty       容器中沒有元素時傳回true,否則傳回false

max_size      傳回容器中最大元素個數

size       傳回容器中目前元素個數

operator=      将一個容器賦給另一個容器

operator<      如果第一個容器小于第二個容器，傳回true，否則傳回false，

operator<=      如果第一個容器小于或等于第二個容器，傳回true，否則傳回false

operator>      如果第一個容器大于第二個容器，傳回true，否則傳回false

operator>=      如果第一個容器大于或等于第二個容器，傳回true，否則傳回false

operator==      如果第一個容器等于第二個容器，傳回true，否則傳回false

operator!=      如果第一個容器不等于第二個容器，傳回true，否則傳回false

swap       交換兩個容器的元素

其operator>,operator>=,operator<,operator<=,operator==,operator!=均不适用于priority_queue

5.順序容器和關聯容器共有函數

begin      該函數兩個版本傳回iterator或const_iterator，引用容器第一個元素

end      該函數兩個版本傳回iterator或const_iterator,引用容器最後一個元素後面一位

rbegin      該函數兩個版本傳回reverse_iterator或const_reverse_iterator,引用容器最後一個元素

rend      該函數兩個版本傳回reverse_iterator或const_reverse_iterator，引用容器第一個元素前面一位

erase      從容器中清除一個或幾個元素

clear      清除容器中所有元素

下表顯示了順序容器和關聯容器中常用的typedef，這些typedef常用于變量、參數和函數傳回值的一般性聲明。

value_type      容器中存放元素的類型

reference      容器中存放元素類型的引用

const_reference 容器中存放元素類型的常量引用，這種引用隻能讀取容器中的元素和進行const操作

pointer      容器中存放元素類型的指針

iterator      指向容器中存放元素類型的疊代器

const_iterator      指向容器中存放元素類型的常量疊代器，隻能讀取容器中的元素

reverse_iterator      指向容器中存放元素類型的逆向疊代器，這種疊代器在容器中逆向疊代

const_reverse_iterator      指向容器中存放元素類型的逆向疊代器，隻能讀取容器中的元素

difference_type      引用相同容器的兩個疊代器相減結果的類型（list和關聯容器沒有定義operator-）

size_type      用于計算容器中項目數和檢索順序容器的類型（不能對list檢索）

6.容器實作

6.1Vector是一個類模闆，而不是一種資料類型，使用時需要：

#include<vector>

using std::vector;

定義vector對象：

vector<類型> 變量名;

初始化對象：

vector<T> v1: vector儲存類型為T的對象，預設構造函數v1為空。

vector<T> v2(v1):v2是v1的一個副本。

vector<T> v3(n, i):v3包含n個值為i的元素。

vector<T> v4(n):v4含有值初始化的元素的n個副本，具體初始值由系統定義。

Vector對象的操作：

v.empty():如果v是空，傳回true，否則傳回false。

v.size():傳回v中元素的個數。

v.push_back(t):在v的末尾增加一個值為t的元素。

v[n]:傳回v中位置為n的元素，下标從0開始。

v1 = v2:将v2賦給v1;保持邏輯操作符的原有含義。

注：在C++中的for循環判斷中，習慣用!=而不是><來編寫循環的判斷條件，隻是為了安全的泛型程式設計。

vector對象元素的通路除了使用下标的方法以外，常用的方法是使用疊代器，疊代器是一種檢查容器中元素并周遊元素的資料類型，标準庫為每一種容器定義了一種疊代器類型。

容器的iterator類型分類：

1. vector<T>::iterator iter;

2. vector<T>::const_iterator iter;

容器的iterator的其他操作：

疊代器還可以用來進行比較運算和算術運算。

容器的iterator使用：

概述：疊代器相當于指向vector容器的指針。

疊代器最為常用的操作就是用已經存在的vector向量的begin和end對其進行指派。

2.vector<T>::const_iterator iter;

它與上面的差別是使用它所定義的iter隻能讀取容器内的元素，不能改變它的值。要注意的是可以使用++iter，他與const vector不同，若定義const vector<T>::iterator iter,則iter不能進行自加運算。

Vector元素删除：

在使用Vector的時候，不可避免的要對其中的一些元素進行删除操作，删除的時候使用的操作時vector.erase(疊代器)的結構，具體的例子如下所示：

6.2deque

C++ STL容器deque和vector很類似，也是采用動态數組來管理元素。deque和vector的不同之處：

1、兩端都能夠快速插入和删除元素。vector隻能在尾端進行。

2、deque的元素存取和疊代器操作會稍微慢一些。因為deque的内部結構會多一個間接過程。

3、疊代器是特殊的智能指針，而不是一般指針。它需要在不同的區塊之間跳轉。

4、deque可以包含更多的元素，其max_size可能更大。因為不止使用一塊記憶體。

5、不支援對容量和記憶體配置設定時機的控制。

注意：在除了首尾兩端的其他地方插入和删除元素，都将會導緻指向deque元素的任何pointers、references、iterators失效。不過，deque的記憶體重配置設定優于vector。因為其内部結構顯示不需要複制所有元素。

6、deque的記憶體區塊不再被使用時，會被釋放。deque的記憶體大小是可縮減的。不過，是不是這麼做以及怎麼做由實作版本定義。

deque和vector相似的特性：

1、在中間部分插入和删除元素相對較慢，因為所有元素都要被移動。

2、疊代器屬于随即存取疊代器。

最好采用deque的情形：

1、需要在兩端插入和删除元素。

2、無需引用容器内的元素。

3、要求容器釋放不再使用的元素。

使用deque之前需包含頭檔案：

#include <deque>

deque<Elem> c建立一個空的deque。

deque<Elem> c1(c2)複制一個deque。

Deque<Elem> c(n)建立一個deque，含有n個資料，資料均已預設構造産生。

Deque<Elem> c(n, elem)建立一個含有n個elem拷貝的deque。

Deque<Elem> c(beg,end)建立一個以[beg;end)區間的deque。

Deque成員函數

c.assign(beg,end)将[beg; end)區間中的資料指派給c。

c.assign(n,elem) 将n個elem的拷貝指派給c。 

c.at(idx) 傳回索引idx所指的資料，假如idx越界，抛出out_of_range。

c.back() 傳回最後一個資料，不檢查這個資料是否存在。

c.begin() 傳回疊代器重的可一個資料。 

c.clear() 移除容器中所有資料。 

c.~deque<Elem>() 銷毀所有資料，釋放記憶體。 

c.empty() 判定容器是否為空。

c.end() 指向疊代器中的最後一個資料位址。

c.erase(pos)删除pos位置的資料，傳回下一個資料的位置。

c.erase(beg,end) 删除[beg,end)區間的資料，傳回下一個資料的位置。

c.front() 傳回地一個資料。

get_allocator 使用構造函數傳回一個拷貝。

c.insert(pos,elem) 在pos位置插入一個elem拷貝，傳回新資料位置。

c.insert(pos,n,elem)在pos位置插入>n個elem資料。無傳回值。

c.insert(pos,beg,end)在pos位置插入在[beg,end)區間的資料。無傳回值。 

c.max_size() 傳回容器中最大資料的數量。

c.pop_back() 删除最後一個資料。

c.pop_front() 删除頭部資料。 

c.push_back(elem) 在尾部加入一個資料。

c.push_front(elem) 在頭部插入一個資料。

c.rbegin() 傳回一個逆向隊列的第一個資料。

c.rend() 傳回一個逆向隊列的最後一個資料的下一個位置。

c.resize(num) 重新指定隊列的長度。

c.size() 傳回容器中實際資料的個數。

C1.swap(c2) 将c1和c2元素互換。

Swap(c1,c2)同上操作。

使用deque示例：

6.3List容器以雙向連結清單的方式管理它的元素，list容器的内部結構跟vector和deque都差别巨大，是以list容器在行為特征上跟vector和deque有明顯差異：

1.list容器不提供随機元素通路。如果你想通路第五個元素，那麼必須先周遊前四個元素才能到達第五個元素。是以使用list容器通路任意元素是低效的。

2.在list容器的任何位置插入和删除元素的效率都是一樣的，都同樣高效，這基于list容器的内部結構，不需要移動其他元素，隻需要維護相應的指針即可。

3.插入和删除操作不會使其他元素的引用、指針和疊代器失效。

4.List容器對異常處理有着完美的支援，一個操作要麼成功完成，要麼對容器不産生任何影響。

跟vector和deque相比，在外部操作接口上list容器有下列差別：

1.list容器既沒有[]操作符，也沒有at()接口，因為list容器不支援随機元素通路。

2.list容器不提供對capacity和記憶體維護相關的接口，因為list容器中的每個元素配置設定自己的記憶體空間，當元素删除時，其對應的記憶體空間銷毀。

3.list容器額外提供了一些移動元素的接口，這些接口比相應的通用算法要高效，因為它們基于list容器的内部結構而設計，是以在需要時應該優先使用它們。

list容器的操作

list容器跟vector、deque容器都屬于序列容器(sequence containers), 是以大部分的操作接口還是類似的，像建立(create)、複制(copy)、銷毀(destroy)、大小(size)、比較(compare)、指派(assignment)、疊代器(iterator)等都基本類似。

Element Access

因為list容器不支援随機通路，是以元素通路接口隻保留了front()和back()，分别用來通路第一個和最後一個元素。同樣這兩個接口不會檢查容器是否為空，如果對一個空的list容器調用這兩個接口，結果未可知。

Iterator Functions

跟vector和deque容器類似，list容器也提供了四個擷取iterator的接口：begin(), end(), rbegin(), rend()。但是有一個細節上的不同就是vector和deque的疊代器是随機通路疊代器(random access iterator), 而list容器的疊代器是雙向疊代器(bidirectional iterator)。它們的差別就是随機通路疊代器可以進行一些算術運算(+, -)，而雙向疊代器隻可以進行遞增(++)、遞減(--)操作。而且一些通用算法也隻接受随機通路疊代器，使用時要注意。

Inserting and Removing Elements

對于插入和删除元素，list容器除了提供所有跟deque一樣的接口外，還額外增補了兩個删除元素的接口：remove(), remove_if()：

c.remove(val): 删除容器中所有值為val的元素。

c.remove_if(op): 删除容器中所有使op為true的元素。

這兩個函數因為根據list容器的内部結構而設計，是以比對應的通用算法要高效，是以在同等的條件下應該優先使用這兩個成員函數。

Splice Functions(拼接函數)

對比vector和deque容器，list容器在内部結構上采用了連結清單結構，這就使得在任意位置插入和删除元素都非常便利，是以list容器額外提供了一組拼接函數，你可以使用這些成員接口在一個容器内部或者兩個容器之間友善地移動元素，當然這兩個容器要具備相同的類型。

c.unique(): 删除容器中值相同位置相鄰的額外元素，隻保留一個元素。

c.unique(op): 删除容器中同時滿足op條件位置相鄰的額外元素，隻保留一個元素。

c1.splice(pos, c2): 把容器c2中的所有元素移動到容器c1的疊代器位置pos之前。

c1.splice(pos, c2, c2pos): 把容器c2中的c2pos位置的元素移動到容器c1的pos位置之前。（c1和c2可以是同一個容器）

c1.splice(pos, c2, c2beg, c2end): 把容器c2中的[c2beg, c2end)範圍内的所有元素移動到容器c1的pos位置之前。（c1和c2可以是同一個容器）

c.sort(): 以操作符<（升序）來排序容器中所有元素。

c.sort(op): 以運算子op來排序容器中所有元素。

c1.merge(c2): 假定容器c1和c2包含的元素都已經過排序(sorted with operation < ), 該接口把c2容器中的所有元素移動到c1中并且也按照排序規則排序。

c1.merge(c2, op): 假定容器c1和c2包含的元素都已經過排序(sorted with op), 該接口把c2容器中的所有元素移動到c1中并且也按照排序規則排序。

c.reverse(): 反序容器中的元素次序。

使用list容器的一個例子：

執行結果如下：