程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> c++ STL容器總結之:vertor與list的應用

c++ STL容器總結之:vertor與list的應用

編輯:C語言基礎知識

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

1、容器(containers):各種數據結構,如vertor,list,deque,set,map.從實現的角度來看,STL容器是一種class template

2、算法(algorithms):各種算法如sort,search,copy,earse。STL算法是一種 function template。

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

4、仿函數(functors):行為類似函數,可以作為算法的某些策略。從實現的角度來看,仿函數是一種重載了operator()的class或class template。

5、配接器(adapters):一種用來修飾容器或仿函數或迭代器借口的東西。例如queue和stack

6、配置器(allocators):負責空間的配置與管理。配置器是一個實現了動態空間分配、空間管理、空間釋放的class template。

STL是建立在泛化之上的。數組泛化為容器,參數化了所包含的對象的類型。函數泛化為算法,參數化了所用的迭代器的類型。指針泛化為迭代器,參數化了所指向的對象的類型。

vector、string、deque和list被稱為標准序列容器,

set、multiset、map和multimap是標准關聯容器。

非標准序列容器slist和rope。slist是一個單向鏈表,rope本質上是一個重型字符串。

非標准關聯容器hash_set、hash_multiset、hash_map和hash_multimap。

標准非STL容器,包括數組、bitset、valarray、stack、queue和priority_queue。

迭代器被分成五個種類:

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

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

輸入和輸出迭代器被塑造為讀和寫輸入和輸出流(例如,文件)。

前向迭代器有輸入和輸出迭代器的能力,但是它們可以反復讀或寫一個位置。

雙向迭代器就像前向迭代器,除了它們的後退可以像前進一樣容易。標准關聯容器都提供雙向迭代器。list也有。

連續內存容器(也叫做基於數組的容器)在一個或多個(動態分配)的內存塊中保存它們的元素。如果一個新元素被查入或者已存元素被刪除,其他在同一個內存塊的元素就必須向上或者向下移動來為新元素提供空間或者填充原來被刪除的元素所占的空間。這種移動影響了效率和異常安全。標准的連續內存容器是vector、string和deque。非標准的rope也是連續內存容器。

基於節點的容器在每個內存塊(動態分配)中只保存一個元素。容器元素的插入或刪除只影響指向節點的指針,而不是節點自己的內容。所以當有東西插入或刪除時,元素值不需要移動。表現為鏈表的容器——比如list和slist——是基於節點的,所有的標准關聯容器也是(它們的典型實現是平衡樹)。非標准的散列容器使用不同的基於節點的實現。

1、vector

vector和數組類似,它擁有一段連續的內存空間,並且起始地址不變,因此它能非常好的支持隨機存取(即使用[]操作符訪問其中的元素),但由於它的內存空間是連續的,所以在中間進行插入和刪除會造成內存塊的拷貝(復雜度是O(n)),另外,當該數組後的內存空間不夠時,需要重新申請一塊足夠大的內存並進行內存的拷貝。這些都大大影響了vector的效率。

vector不是一種數據類型,而只是一個類模板,可用來定義任意多種數據類型。vector類型的每一種都指定了其保存元素的類型。因此,vector<int>和vector <string>都是數據類型。

vector對象的定義和初始化

vector<T>  v1;

vector保存類型為T的對象。默認構造函數v1為空。

vector<T> v2(v1);

v2是v1的一個副本。

vector<T> v3(n, i);

v3包含n個值為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中元素的個數。

v.push_back(t)

在v的末尾增加一個值為t的元素。

v[n]

返回v中位置為n的元素。

v1 = v2

把v1的元素替換為v2中元素的副本。

v1 == v2

如果v1與v2相等,則返回true。

!=, <, <=, >, >=

保持這些操作符慣有的含義。

向vector添加元素:
代碼如下:

string word;

vector<string> text;        // empty vector

while (cin >> word) {

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

}
  vector的下標操作:

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

    ivec[ix] = 0;

vector迭代器

每種容器都定義了一對命名為begin和end的函數,用於返回迭代器。如果容器中有元素的話,由begin返回的迭代器指向第一個元素:
代碼如下:

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

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

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的類型,該類型只能訪問容器內元素,但不能改變其值。
代碼如下:

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

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

2、list

list是由數據結構中的雙向鏈表實現的,因此它的內存空間可以是不連續的。因此只能通過指針來進行數據的訪問,這個特點使得它的隨機存取變的非常沒有效率,需要遍歷中間的元素,搜索復雜度O(n),因此它沒有提供[]操作符的重載。但由於鏈表的特點,它可以以很好的效率支持任意地方的刪除和插入。

list::iterator與vector::iterator的一些不同:
代碼如下:

#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;       //編譯錯誤,list沒有重載[]
        cout << (v.begin() < v.end()) << endl;
        //cout << (l.begin() < l.end()) << endl;   //編譯錯誤,list::iterator沒有重載<或>
        cout << *(v.begin() + 1) << endl;

        vector<int>::iterator itv = v.begin();
        list<int>::iterator itl = l.begin();
        itv = itv + 2;
        //itl = itl + 2;                  //編譯錯誤,list::iterator沒有重載+
        itl++;itl++;                    //list::iterator中重載了++,只能使用++進行迭代訪問。
        cout << *itv << endl;
        cout << *itl << endl;

        return 0;
}

由於vector擁有一段連續的內存空間,能非常好的支持隨機存取,因此vector<int>::iterator支持“+”、“+=”、“<”等操作符。

而list的內存空間可以是不連續,它不支持隨機訪問,因此list<int>::iterator則不支持“+”、“+=”、“<”等操作符運算,因此代碼20、26行會有編譯錯誤。只能使用“++”進行迭代,例如代碼27行,使用兩次itl++來移動itl。還有list也不支持[]運算符,因此代碼18行出現編譯錯誤。

總之,如果需要高效的隨即存取,而不在乎插入和刪除的效率,使用vector;如果需要大量的插入和刪除,而不關心隨即存取,則應使用list。

vector擁有一段連續的內存空間,因此支持隨機存取,如果需要高效的隨即存取,而不在乎插入和刪除的效率,使用vector。

list擁有一段不連續的內存空間,因此支持隨機存取,如果需要大量的插入和刪除,而不關心隨即存取,則應使用list。當大部分插入和刪除發生在序列的頭或尾時可以選擇deque這種數據結構。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved