C++ 9.1 順序容器-----vector、list、deque

簡介

• C++提供了使用抽象進行高效率程式設計的方式。标準庫就是一個很好的例子，标準庫定義了許多容器類以及一系列泛型算法，使得程式員可以更加簡潔、抽象和有效的編寫程式。
• 容器都是由标準庫定義的，我們可以将string類型看作僅包含字元的特殊容器，string類型提供大量的容器操作。（9章）
• 标準庫還提供了幾種關聯容器，關聯容器元素不是順序排列，而是按鍵（key）排序的。（10章）
• 泛型算法，這些算法通常作用于容器或序列中某一範圍的元素。算法庫提供了各種各樣經典算法的有效實作，像查找、排序及其他常見的算法任務–複制算法。（11章）
• 标準庫定義了三種順序容器類型：
  • vector
  • list
  • deque(是雙端隊列的簡寫)
• 他們的差别在于通路元素的方式，以及添加或删除元素相關操作的運作代價。
• 順序容器擴充卡包括：
  • stack
  • queue
  • priority_queue
• 為了定義一個容器類型的對象，必須先包含相關的頭檔案，即以下頭檔案之一：

//三種順序容器的頭檔案
#include<vector>
#include<list>
#include<deque>
           

===========================================================================================================

第二部分 标準庫定義的容器與算法 序

• C++提供了使用抽象進行高效率程式設計的方式。标準庫就是一個很好的例子，标準庫定義了許多容器類以及一系列泛型算法，使得程式員可以更加簡潔、抽象和有效的編寫程式。
• 容器都是由标準庫定義的，我們可以将string類型看作僅包含字元的特殊容器，string類型提供大量的容器操作。（9章）
• 标準庫還提供了幾種關聯容器，關聯容器元素不是順序排列，而是按鍵（key）排序的。（10章）
• 泛型算法，這些算法通常作用于容器或序列中某一範圍的元素。算法庫提供了各種各樣經典算法的有效實作，像查找、排序及其他常見的算法任務–複制算法。（11章）
• 為容器提供通用接口是設計庫的目的。如果兩種容器提供相似的操作，則為他們定義的這個操作應該完全相同。
• 容器提供的操作和算法是一緻定義的，這使得學習标準庫更加容易：隻需要了解一個操作如何工作，就能将該操作應用于其他的容器。

一、順序容器

1、順序容器、順序容器擴充卡

• 容器容納特定類型對象的集合。我們使用過一種容器類型：标準庫vector類型，這是一種順序容器。它将單一類型元素聚集起來稱為容器，然後根據位置來存儲和通路這些元素，這就是順序容器。
• 順序容器的元素排列次序與元素值無關，而是由元素添加到容器裡的次序決定。
• 标準庫定義了三種順序容器類型：
  • vector
  • list
  • deque(是雙端隊列的簡寫)
• 他們的差别在于通路元素的方式，以及添加或删除元素相關操作的運作代價。
• 标準庫還提供了三種容器擴充卡（adaptor）:擴充卡是根據原始的容器類型所提供的操作，通過定義新的操作接口，來适應基礎的容器類型。
• 順序容器擴充卡包括：
  • stack
  • queue
  • priority_queue

    

• 容器隻定義了少量（添加删除元素/指向第一個元素）操作。大多數額外操作則由算法庫（11章）提供。

2、容器類型的操作集合

• 标準庫為容器類型定義的操作強加了公共的接口。這些容器類型的差别在于它們提供哪些操作，但是如果兩個容器提供了相同的操作，則它們的接口（函數名稱和參數個數）應該相同。
• 容器類型的操作集合形成了以下層次結構：
  • 一些操作适用于所有容器類型；
  • 另外一些操作則隻适用于順序或關聯容器類型；
  • 還有一些操作隻适用于順序或關聯容器類型的一個子集。（關聯容器 10章）

3、順序容器定義

• 為了定義一個容器類型的對象，必須先包含相關的頭檔案，即以下頭檔案之一：

//三種順序容器的頭檔案
#include<vector>
#include<list>
#include<deque>
           

• 所有容器都是類模闆（不是一種資料類型，隻是一種類模闆，可以用來定義多種資料類型）

vector<string> svec;//空的vector容器，存放string資料類型
list<int>  ilist;//空的list容器，存放int資料類型
deque<Sale_item> items;//空的deque容器，存放Sale_item資料類型
           

• 所有的容器類型都定義了預設構造函數，用于建立指定類型的空容器對象。預設構造函數不帶參數。（最常用的）

4、容器元素的初始化

除了預設構造函數，容器類型還提供其他的構造函數，使程式員可以指定元素初值。

4.1 将一個容器初始化為另一個容器的副本———直接複制容器，類型必須完全比對！！！！

vector< int >  iivec(要複制的第一個元素的位置，要複制的最後一個元素的下一個位置);
           

• 當不使用預設構造函數，而是用其他構造函數初始化順序容器時，必須指出該容器有多少個元素，并提供這些元素的初值。同時指定元素個數和初值的一個方法是将新建立的容器初始化為一個同類型的已存在容器的副本：
• 将一個容器複制給另一個容器時，類型必須比對：容器類型和元素類型都必須相同！！

vector<int> ivec;
vector<int> ivec2(ivec);//可以
list<int>  ilist(ivec);//不可以！！！vector類型不同
vector<double>  dvec(ivec);//不可以！！！元素類型不同
           

4.2 初始化為一段元素的副本—-使用疊代器初始化，容器類型不一定要完全相同

• 盡管不能直接将一種容器内的元素複制給另一種容器，但系統允許通過傳遞一對疊代器間接實作該功能。
• 使用疊代器時，不要求容器類型相同，容器内的元素類型也可以不相同，隻要互相相容，能夠将要複制的元素轉換為所建構的新容器的元素類型，即可實作複制。
• 疊代器标記了要複制的元素範圍，這些元素用于初始化新容器的元素。疊代器标記出要複制的第一個元素和最後一個元素的下一個位置。采用這種初始化形式可複制不能直接複制的容器。更重要的是，可以實作複制其他容器的一個子序列

list<string> slist(svec.begin(),svec.end());//svec是vector<string>類型
vector<string>::iterator mid=svec.begin()+svec.end()/;//找到中間位置
deque<string> front(svec.begin(),mid);//初始化front，但是不包括 中間元素（*mid)
deque<string> back(mid,svec.end());
           

我們知道指針就是疊代器，是以允許通過使用内置數組中的一對指針初始化容器也就不奇怪 了

char *words[]={"stately","plump","buck","mulligan"};//定義一個數組
size_t words_size = sizeof(words)/sizeof(char *);//數組下标是size_t類型。
//這裡用了sizeof函數，看 5.8節sizeof操作
//sizeof（數組名）=數組内所有元素所占的記憶體空間
//char *words[] 表示的一個數組，裡邊放的是字元指針，看4.4節。
//要求數組裡面有多少元素，就使用sizeof(數組名)/sizeof(數組元素類型)
//因為數組元素類型是指針，是以sizeof(數組元素類型)=4

list<string> word2(words , words+word_size);//定義一個list類型容器，起始位置是數組名（指針）
           

這裡，使用sizeof計算數組的長度，将數組長度加到指向第一個元素的指針上就可以得到指向超出數組末端的下一位置的指針。其中第二個指針提供停止複制的條件，其所指向的位置上存放的元素并沒有複制。

4.3 配置設定和初始化指定數目的元素

• 建立順序容器時，可顯示指定容器大小和一個（可選的）元素初始化式。容器大小可以是常量或非常量表達式，元素初始化式則必須是可用于初始化其元素類型的對象的值：

const list<int>::size_type list_size =;//容器的下标是size_type類型
list<string>  slist(list_size,"eh?");//共有64個元素，每個都是 "eh?"字元串
           

• 建立容器時，除了指定元素個數，還可以選擇是否提供元素初始化式。我們也可以隻指定容器大小：

list<int> ilist(list_size);//預設初始化，為0
extren unsigned get_word_count(const string &file_name);
vector<string> svec(get_word_count("Chimera"));
           

• 不提供元素初始化式時，标準庫将為該容器實作值初始化。采用這種方式必須指定元素個數，預設會初始化,元素類型必須是内置或複合類型，或者是提供了預設構造函數的類類型。如果元素類型沒有預設構造函數，則必須顯示指定其元素初始化式
• 接受容器大小做形參的構造函數隻适用于順序容器，而關聯容器不支援這種初始化。