STL容器之雙端隊列和表容器類

STL是C++的一個類庫。STL中的容器有隊列容器和關聯容器，容器適配器congtainer adapters：stack,queue，priority queue），位集bit_set），串包(string_package)等等。

在系列中，我將介紹list,vector，deque等隊列容器，和set和multisets,map和multimaps等關聯容器，一共7種基本容器類。

隊列容器順序容器）：隊列容器按照線性排列來存儲T類型值的集合，隊列的每個成員都有自己的特有的位置。順序容器有向量類型、雙端隊列類型、列表類型三種。

下面介紹雙端隊列容器類和表容器類。

雙端隊列deque容器類）：

deque讀音：deck，意即：double queue，#include<qeque>）容器類與vector類似，支持隨機訪問和快速插入刪除，它在容器中某一位置上的操作所花費的是線性時間。與vector不同的是，deque還支持從開始端插入數據：push_front()。

此外deque也不支持與vector的capacity()、reserve()類似的操作。

#include <iostream>  
#include <deque>  
using namespace std;  
typedef deque<int> INTDEQUE;//有些人很討厭這種定義法，呵呵  
//從前向後顯示deque隊列的全部元素  
void put_deque(INTDEQUE deque, char *name)  
{  
INTDEQUE::iterator pdeque;//仍然使用迭代器輸出  
cout << "The contents of " << name << " : ";  
for(pdeque = deque.begin(); pdeque != deque.end(); pdeque++)  
cout << *pdeque << " ";//注意有 "*"號哦，沒有"*"號的話會報錯  
cout<<endl;  
}  
//測試deqtor容器的功能  
int main()  
{  
//deq1對象初始為空  
INTDEQUE deq1;   
//deq2對象最初有10個值為6的元素   
INTDEQUE deq2(10,6);   
//聲明一個名為i的雙向迭代器變量  
INTDEQUE::iterator i;  
//從前向後顯示deq1中的數據  
put_deque(deq1,"deq1");  
//從前向後顯示deq2中的數據  
put_deque(deq2,"deq2");  
//從deq1序列後面添加兩個元素  
deq1.push_back(2);  
deq1.push_back(4);  
cout<<"deq1.push_back(2) and deq1.push_back(4):"<<endl;  
put_deque(deq1,"deq1");  
//從deq1序列前面添加兩個元素  
deq1.push_front(5);  
deq1.push_front(7);  
cout<<"deq1.push_front(5) and deq1.push_front(7):"<<endl;  
put_deque(deq1,"deq1");  
//在deq1序列中間插入數據  
deq1.insert(deq1.begin()+1,3,9);  
cout<<"deq1.insert(deq1.begin()+1,3,9):"<<endl;  
put_deque(deq1,"deq1");  
//測試引用類函數  
cout<<"deq1.at(4)="<<deq1.at(4)<<endl;  
cout<<"deq1[4]="<<deq1[4]<<endl;  
deq1.at(1)=10;  
deq1[2]=12;  
cout<<"deq1.at(1)=10 and deq1[2]=12 :"<<endl;  
put_deque(deq1,"deq1");  
//從deq1序列的前後各移去一個元素  
deq1.pop_front();  
deq1.pop_back();  
cout<<"deq1.pop_front() and deq1.pop_back():"<<endl;  
put_deque(deq1,"deq1");  
//清除deq1中的第2個元素  
deq1.erase(deq1.begin()+1);  
cout<<"deq1.erase(deq1.begin()+1):"<<endl;  
put_deque(deq1,"deq1");  
//對deq2賦值並顯示  
deq2.assign(8,1);  
cout<<"deq2.assign(8,1):"<<endl;  
put_deque(deq2,"deq2");  
} 

上面我們演示了deque如何進行插入刪除等操作，像erase(),assign()是大多數容器都有的操作。關於deque的其他操作請參閱其書籍。

表List容器類）

List#include<list>）又叫鏈表，是一種雙線性列表，只能順序訪問從前向後或者從後向前），圖2是list的數據組織形式。與前面兩種容器類有一個明顯的區別就是：它不支持隨機訪問。要訪問表中某個下標處的項需要從表頭或表尾處接近該下標的一端）開始循環。而且缺少下標預算符：operator[]。

同時，list仍然包涵了erase(),begin(),end(),insert(),push_back(),push_front()這些基本函數，下面我們來演示一下list的其他函數功能。

• merge()：合並兩個排序列表；
• splice()：拼接兩個列表；
• sort()：列表的排序

#include <iostream>  
#include <string>  
#include <list>  
using namespace std;  
void PrintIt(list<int> n)  
{  
for(list<int>::iterator iter=n.begin(); iter!=n.end(); ++iter)  
cout<<*iter<<" ";//用迭代器進行輸出循環   
}  
int main()  
{  
list<int> listn1,listn2; //給listn1,listn2初始化   
listn1.push_back(123);  
listn1.push_back(0);  
listn1.push_back(34);  
listn1.push_back(1123); //now listn1:123,0,34,1123   
listn2.push_back(100);  
listn2.push_back(12); //now listn2:12,100  
listn1.sort();  
listn2.sort(); //給listn1和listn2排序  
//now listn1:0,34,123,1123 listn2:12,100   
PrintIt(listn1);  
cout<<endl;  
PrintIt(listn2);  
listn1.merge(listn2); //合並兩個排序列表後,listn1:0，12，34，100，123，1123   
cout<<endl;  
PrintIt(listn1);  
} 

上面並沒有演示splice()函數的用法，這是一個拗口的函數。用起來有點麻煩。圖3所示是splice函數的功能。將一個列表插入到另一個列表當中。list容器類定義了splice()函數的3個版本：

splice(position,list_value);  
splice(position,list_value,ptr);  
splice(position,list_value,first,last); 

ist_value是一個已存在的列表，它將被插入到源列表中，position是一個迭代參數，他當前指向的是要進行拼接的列表中的特定位置。

listn1:123,0,34,1123 listn2:12,100

執行listn1.splice(find(listn1.begin(),listn1.end(),0),listn2);之後，listn1將變為：123，12，100，34，1123。即把listn2插入到listn1的0這個元素之前。其中，find()函數找到0這個元素在listn1中的位置。值得注意的是，在執行splice之後，list_value將不復存在了。這個例子中是listn2將不再存在。

第二個版本當中的ptr是一個迭代器參數，執行的結果是把ptr所指向的值直接插入到position當前指向的位置之前.這將只向源列表中插入一個元素。

第三個版本的first和last也是迭代器參數，並不等於list_value.begin(),list_value.end()。First指的是要插入的列的第一個元素，last指的是要插入的列的最後一個元素。

如果listn1:123,0,34,1123 listn2:12,43，87，100 執行完以下函數之後

listn1.splice(find(listn1.begin(),listn1.end(),0),++listn2.begin(),--listn2.end());

listn1:123,43,87,0,34,1123 listn2:12,100

以上，我們學習了deque,list兩種基本順序容器，其他的順序容器還有：slist,bit_vector等等。請繼續下一篇>>