腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

c++ STL容器總結(jié)之:vertor與list的應(yīng)用

更新時(shí)間：2013年05月12日 13:07:36 作者：

本篇文章對(duì)c++中STL容器中的vertor與list的應(yīng)用進(jìn)行了詳細(xì)的分析解釋。需要的朋友參考下

STL提供六大組件，彼此可以組合套用

1、容器（containers）：各種數(shù)據(jù)結(jié)構(gòu)，如vertor，list，deque，set，map.從實(shí)現(xiàn)的角度來(lái)看，STL容器是一種class template

2、算法（algorithms）：各種算法如sort，search，copy，earse。STL算法是一種 function template。

3、迭代器（iterators）：扮演容器與算法之間的膠合劑，是所謂的“泛型指針”。所有STL容器都有自己的專屬的迭代器。

4、仿函數(shù)（functors）：行為類似函數(shù)，可以作為算法的某些策略。從實(shí)現(xiàn)的角度來(lái)看，仿函數(shù)是一種重載了operator()的class或class template。

5、配接器（adapters）：一種用來(lái)修飾容器或仿函數(shù)或迭代器借口的東西。例如queue和stack

6、配置器（allocators）：負(fù)責(zé)空間的配置與管理。配置器是一個(gè)實(shí)現(xiàn)了動(dòng)態(tài)空間分配、空間管理、空間釋放的class template。

STL是建立在泛化之上的。數(shù)組泛化為容器，參數(shù)化了所包含的對(duì)象的類型。函數(shù)泛化為算法，參數(shù)化了所用的迭代器的類型。指針?lè)夯癁榈?，參?shù)化了所指向的對(duì)象的類型。

vector、string、deque和list被稱為標(biāo)準(zhǔn)序列容器，

set、multiset、map和multimap是標(biāo)準(zhǔn)關(guān)聯(lián)容器。

非標(biāo)準(zhǔn)序列容器slist和rope。slist是一個(gè)單向鏈表，rope本質(zhì)上是一個(gè)重型字符串。

非標(biāo)準(zhǔn)關(guān)聯(lián)容器hash_set、hash_multiset、hash_map和hash_multimap。

標(biāo)準(zhǔn)非STL容器，包括數(shù)組、bitset、valarray、stack、queue和priority_queue。

迭代器被分成五個(gè)種類：

輸入迭代器是每個(gè)迭代位置只能被讀一次的只讀迭代器。

輸出迭代器是每個(gè)迭代位置只能被寫一次的只寫迭代器。

輸入和輸出迭代器被塑造為讀和寫輸入和輸出流（例如，文件）。

前向迭代器有輸入和輸出迭代器的能力，但是它們可以反復(fù)讀或?qū)懸粋€(gè)位置。

雙向迭代器就像前向迭代器，除了它們的后退可以像前進(jìn)一樣容易。標(biāo)準(zhǔn)關(guān)聯(lián)容器都提供雙向迭代器。list也有。

連續(xù)內(nèi)存容器（也叫做基于數(shù)組的容器）在一個(gè)或多個(gè)（動(dòng)態(tài)分配）的內(nèi)存塊中保存它們的元素。如果一個(gè)新元素被查入或者已存元素被刪除，其他在同一個(gè)內(nèi)存塊的元素就必須向上或者向下移動(dòng)來(lái)為新元素提供空間或者填充原來(lái)被刪除的元素所占的空間。這種移動(dòng)影響了效率和異常安全。標(biāo)準(zhǔn)的連續(xù)內(nèi)存容器是vector、string和deque。非標(biāo)準(zhǔn)的rope也是連續(xù)內(nèi)存容器。

基于節(jié)點(diǎn)的容器在每個(gè)內(nèi)存塊（動(dòng)態(tài)分配）中只保存一個(gè)元素。容器元素的插入或刪除只影響指向節(jié)點(diǎn)的指針，而不是節(jié)點(diǎn)自己的內(nèi)容。所以當(dāng)有東西插入或刪除時(shí)，元素值不需要移動(dòng)。表現(xiàn)為鏈表的容器——比如list和slist——是基于節(jié)點(diǎn)的，所有的標(biāo)準(zhǔn)關(guān)聯(lián)容器也是（它們的典型實(shí)現(xiàn)是平衡樹）。非標(biāo)準(zhǔn)的散列容器使用不同的基于節(jié)點(diǎn)的實(shí)現(xiàn)。

1、vector

vector和數(shù)組類似，它擁有一段連續(xù)的內(nèi)存空間，并且起始地址不變，因此它能非常好的支持隨機(jī)存?。词褂肹]操作符訪問(wèn)其中的元素），但由于它的內(nèi)存空間是連續(xù)的，所以在中間進(jìn)行插入和刪除會(huì)造成內(nèi)存塊的拷貝（復(fù)雜度是O(n)），另外，當(dāng)該數(shù)組后的內(nèi)存空間不夠時(shí)，需要重新申請(qǐng)一塊足夠大的內(nèi)存并進(jìn)行內(nèi)存的拷貝。這些都大大影響了vector的效率。

vector不是一種數(shù)據(jù)類型，而只是一個(gè)類模板，可用來(lái)定義任意多種數(shù)據(jù)類型。vector類型的每一種都指定了其保存元素的類型。因此，vector<int>和vector <string>都是數(shù)據(jù)類型。

vector對(duì)象的定義和初始化

vector<T> v1;	vector保存類型為T的對(duì)象。默認(rèn)構(gòu)造函數(shù)v1為空。
vector<T> v2(v1);	v2是v1的一個(gè)副本。
vector<T> v3(n, i);	v3包含n個(gè)值為i的元素。

vector<int> ivec4(10, -1); // 10 elements, each initialized to -1

vector<string> svec(10, "hi!"); // 10 strings, each initialized to "hi!"

vector的操作

v.empty()	如果v為空，則返回true,否則返回false。
v.size()	返回v中元素的個(gè)數(shù)。
v.push_back(t)	在v的末尾增加一個(gè)值為t的元素。
v[n]	返回v中位置為n的元素。
v1 = v2	把v1的元素替換為v2中元素的副本。
v1 == v2	如果v1與v2相等，則返回true。
!=, <, <=, >, >=	保持這些操作符慣有的含義。

向vector添加元素:

復(fù)制代碼代碼如下:

string word;

vector<string> text; // empty vector

while (cin >> word) {

text.push_back(word); // append word to text

}
　　vector的下標(biāo)操作:

for (vector<int>::size_type ix = 0; ix != ivec.size(); ++ix)

ivec[ix] = 0;

vector迭代器

每種容器都定義了一對(duì)命名為begin和end的函數(shù)，用于返回迭代器。如果容器中有元素的話，由begin返回的迭代器指向第一個(gè)元素：

復(fù)制代碼代碼如下:

vector<int>::iterator iter = ivec.begin();

由end操作返回的迭代器指向vector的“末端元素的下一個(gè)”。通常稱為超出末端迭代器(off-the-end iterator)，表明它指向了一個(gè)不存在的元素。如果vector為空，begin返回的迭代器與end返回的迭代器相同。

復(fù)制代碼代碼如下:

for (vector<int>::iterator iter = ivec.begin(); iter != ivec.end(); ++iter) 

    *iter = 0;  // set element to which iter refers to 0 

const_iterator

前面的程序用vector::iterator改變vector中的元素值。每種容器類型還定義了一種名為const_iterator的類型，該類型只能訪問(wèn)容器內(nèi)元素，但不能改變其值。

復(fù)制代碼代碼如下:

for (vector<string>::const_iterator iter = text.begin();  iter != text.end(); ++ iter) 

    *iter = " ";     // error: *iter is const 

2、list

list是由數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表實(shí)現(xiàn)的，因此它的內(nèi)存空間可以是不連續(xù)的。因此只能通過(guò)指針來(lái)進(jìn)行數(shù)據(jù)的訪問(wèn)，這個(gè)特點(diǎn)使得它的隨機(jī)存取變的非常沒(méi)有效率，需要遍歷中間的元素，搜索復(fù)雜度O(n)，因此它沒(méi)有提供[]操作符的重載。但由于鏈表的特點(diǎn)，它可以以很好的效率支持任意地方的刪除和插入。

list::iterator與vector::iterator的一些不同：

復(fù)制代碼代碼如下:

#include <iostream> 
#include <vector> 
#include <list> 
using namespace std; 

int main( void ) 
{ 
        vector<int> v;  
        list<int> l; 

        for (int i=0; i<8; i++)     //往v和l中分別添加元素 
        { 
                v.push_back(i); 
                l.push_back(i); 
        } 

        cout << "v[2] = " << v[2] << endl; 
        //cout << "l[2] = " << l[2] << endl;       //編譯錯(cuò)誤,list沒(méi)有重載[] 
        cout << (v.begin() < v.end()) << endl; 
        //cout << (l.begin() < l.end()) << endl;   //編譯錯(cuò)誤,list::iterator沒(méi)有重載<或> 
        cout << *(v.begin() + 1) << endl; 

        vector<int>::iterator itv = v.begin(); 
        list<int>::iterator itl = l.begin(); 
        itv = itv + 2; 
        //itl = itl + 2;                  //編譯錯(cuò)誤,list::iterator沒(méi)有重載+ 
        itl++;itl++;                    //list::iterator中重載了++，只能使用++進(jìn)行迭代訪問(wèn)。 
        cout << *itv << endl; 
        cout << *itl << endl; 

        return 0; 
}

由于vector擁有一段連續(xù)的內(nèi)存空間，能非常好的支持隨機(jī)存取，因此vector<int>::iterator支持“+”、“+=”、“<”等操作符。

而list的內(nèi)存空間可以是不連續(xù)，它不支持隨機(jī)訪問(wèn)，因此list<int>::iterator則不支持“+”、“+=”、“<”等操作符運(yùn)算，因此代碼20、26行會(huì)有編譯錯(cuò)誤。只能使用“++”進(jìn)行迭代，例如代碼27行，使用兩次itl++來(lái)移動(dòng)itl。還有l(wèi)ist也不支持[]運(yùn)算符，因此代碼18行出現(xiàn)編譯錯(cuò)誤。

總之，如果需要高效的隨即存取，而不在乎插入和刪除的效率，使用vector；如果需要大量的插入和刪除，而不關(guān)心隨即存取，則應(yīng)使用list。

vector擁有一段連續(xù)的內(nèi)存空間，因此支持隨機(jī)存取，如果需要高效的隨即存取，而不在乎插入和刪除的效率，使用vector。

list擁有一段不連續(xù)的內(nèi)存空間，因此支持隨機(jī)存取，如果需要大量的插入和刪除，而不關(guān)心隨即存取，則應(yīng)使用list。當(dāng)大部分插入和刪除發(fā)生在序列的頭或尾時(shí)可以選擇deque這種數(shù)據(jù)結(jié)構(gòu)。

您可能感興趣的文章: