C++拾遺（四）——順序容器，拾遺順序容器

C++拾遺（四）——順序容器，拾遺順序容器

　　之前一篇博文（《初窺標准庫》）簡單了解了一種最常用的順序容器：vector類型。本文將對該文內容進行進一步的學習和完善，繼續討論標准庫提供的順序容器類型。所謂順序容器，即將單一類型的元素聚集起來成為容器，並根據位置來存儲和訪問這些元素。標准庫定義了三種順序容器類型：vector,list和deque(double-ended queue雙端隊列)。同時還提供了三種順序容器適配器（adaptor）：stack,queue,priority_queue。

順序容器的定義及迭代器

• 容器元素類型必須滿足兩個條件：元素支持賦值運算，元素對象可以復制。以上為容器要滿足的最低限度，關聯容器則需要滿足其他元素。注意到，引用不支持賦值運算，IO庫類型不支持賦值或復制，故兩者都不能作為容器的元素。
• 注意：容器定義時，必須用空格隔開兩個相鄰的>符號，否則系統會將>>當作右移操作符，導致編譯錯誤。

1 vector< vector<string> > liens; //ok
2 vector < vector<string>> lines; //error:>>treated as shift operator

• 標准庫為迭代器提供一些常用的運算，如解引用，自增自減等。
• 關系操作符只適用於vector和deque容器，因為它們提供快速隨機訪存，可以根據元素位置直接訪問容器元素。而list容器的迭代器既不支持算術運算，也不支持關系運算。
• 迭代器范圍為左閉合區間，即[first,last)，表示從first所指示的位置到last所指示的位置之前的所有元素。對迭代器的要求為：它們指向同一個容器中的元素或超出末端的下一位置；first反復做自增運算能夠到達last。
• 某些容器操作會修改容器的內在狀態或移動容器內的元素，這樣將會使部分迭代器失效，進而導致與懸垂指針同樣的問題。考慮如下兩段代碼，有何不同？為何？

   1 vector<int>::iterator mid = iv.begin() + iv.size()/2;
   2 vecor<int>::iterator iter = iv.begin();
   3 while (iter != mid)
   4     if (*iter == someVal)
   5         iv.insert(iter, 2*someVal);
   6 
   7 vector<int>::iterator iter = iv.begin();
   8 while (iter != iv.begin() + iv.size()/2)
   9 {
  10     if (*iter == someVal)
  11     {    
  12           iter = iv.insert(iter, 2*someVal);
  13           iter += 2;
  14     }        
  15     else
  16         ++iter;
  17 }

   

順序容器的操作

• 一些基本的操作，如begin和end成員，insert操作，resize操作，erase操作，assign操作，關系操作符等。

vector容器的自增長

• vector類提供了兩個成員函數：capacity和reserve，前者獲取在容器需要分配更多的存儲空間之前能夠存儲的元素總數，後者則告訴容器應該預留多少空間。注意，capacity不等於size。

容器的選用

• 若要隨機訪存元素，應使用vector或deque。
• 若要在容器的中間位置插入或刪除元素，應使用list。
• 若是在首尾部分插入或刪除，使用deque。
• 如果只需要在讀取輸入時在容器的中間位置插入元素，然後需要隨即訪問元素，則可將元素讀入list容器，接著對此容器重新排序，使之適合順序訪問，在復制到vector中。
• 選擇容器的核心取決於：隨機訪存list的代價與在vector/deque中插入刪除時復制元素的代價。