C++提高程式設計（三）—— STL常用容器(11) ：容器總結

C++系列内容的學習目錄 → \rightarrow →C++學習系列内容彙總。

1. 順序容器

2. 容器擴充卡

3. 關聯容器

  一個容器就是一些特定類型對象的集合。順序容器(sequential container)為程式員提供了控制元素存儲和通路順序的能力。這種順序不依賴于元素的值，而是與元素加入容器時的位置相對應。

  下表列出了标準庫中的順序容器，所有容器都提供了快速順序通路元素的能力，但是這些容器在兩個方面都有不同的性能折中。第一個方面是，向容器中添加或從容器中删除元素的代價；第二個方面是，非順序通路容器中元素的代價。

容器類型

簡介

部落格連結

vector

可變大小數組。支援快速随機通路。在尾部之外的位置插入或删除元素可能很慢。

C++提高程式設計（三）—— STL常用容器(2) ：vector容器

deque

雙端隊列。支援快速随機通路。在頭尾位置插入/删除速度很快。

C++提高程式設計（三）—— STL常用容器(3) ：deque容器

list

雙向連結清單。隻支援雙向順序通路。在list中任何位置進行插入/删除操作速度都很快。

C++提高程式設計（三）—— STL常用容器(7) ：list容器

forward_list

單向連結清單。隻支援單向順序通路。在連結清單任何位置進行插入/删除操作速度都很快。

array

固定大小數組。支援快速随機通路。不能添加或删除元素。

string

與vector相似的容器，但專門用于儲存字元。随機通路快。在尾部位置插入/删除操作速度都很快。

C++提高程式設計（三）—— STL常用容器(1) ：string容器

  除了固定大小的array外，其他容器都提供高效、靈活的記憶體管理。我們可以添加和删除元素，擴張和收縮容器的大小。容器儲存元素的政策對容器操作的效率有着固有的、甚至是重大的影響。在某些情況下，存儲政策還會影響特定容器是否支援特定操作。

  例如，string和vector将元素儲存在連續的記憶體空間中。由于元素是連續存儲的，由元素的下标來計算其位址是非常快速的。但是，在這兩種容器的中間位置添加或者删除元素就會非常耗時。因為在一次插入或删除操作後，需要移動插入或删除位置之後的所有元素來保持連續存儲。而且，添加一個元素有時可能還需要配置設定額外的存儲空間。在這種情況下，每個元素都必須移動到新的存儲空間中。

  list和forward_list兩個容器的設計目的是令容器任何位置的添加或删除操作都很快速。作為代價，這兩個容器不支援元素的随機通路。為了通路一個元素，我們隻能周遊整個容器。而且，與vector、deque和array相比，這兩個容器的額外記憶體開銷也很大。

  deque是一個更為複雜的資料結構。與string和vector類似，deque支援快速的随機通路。與string和vector一樣，在deque的中間位置添加或删除元素的代價（可能）很高。但是，在deque的兩端添加或删除元素都是很快的，與list或forward_list添加删除元素的速度相當。

  forward_list和array是新C++标準增加的類型。與内置數組相比，array是一種更安全、更容易使用的數組類型。與内置數組類似，array對象的大小是固定的。是以，array不支援添加和删除元素以及改變容器大小的操作。forward_list的設計目标是達到與最好的手寫的單向連結清單資料結構相當的性能。是以，forward_list沒有size操作，因為儲存或計算其大小就會比手寫連結清單多出額外的開銷。對其他容器而言，size保證是一個快速的常量時間的操作。

  确定使用哪種順序容器的基本原則：

通常，使用vector是最好的選擇，除非有很好的理由選擇其他容器；

如果程式有很多小的元素，而且空間的額外開銷很重要，則不要使用list或forward_list；

如果程式要求随機通路元素，應使用vector或deque；

如果程式要求在容器的中間插入或删除元素，應使用list或forward_list；

如果程式需要在頭尾位置插入或删除元素，但不會在中間位置進行插入或删除操作，則使用deque；

如果程式隻有在讀取輸入時才需要在容器中間位置插入元素，随後需要随機通路元素，則

  首先，确定是否真的需要在容器中間位置添加元素。當處理輸入資料時，通常可以很容易地向vector追加資料，然後再調用标準庫的sort函數來重排容器中的元素，進而避免在中間位置添加元素；

  如果必須在中間位置插入元素，考慮在輸入階段使用list，一旦輸入完成，将list中的内容拷貝到一個vector中。

  如果程式既需要随機通路元素，又需要在容器中間位置插入元素，那該怎麼辦?答案取決于在list或forward_list中通路元素與vector或deque中插入/删除元素的相對性能。一般來說，應用中占主導地位的操作（執行的通路操作更多還是插入删除更多）決定了容器類型的選擇，在此情況下，對兩種容器分别測試應用的性能可能就是必要的了。

  如果不确定應該使用哪種容器，那麼可以在程式中隻使用vector和list公共的操作：使用選代器，不使用下标操作，避免随機通路。這樣，在必要時選擇使用vector或list都很友善。

  除了順序容器之外，标準庫還定義了三個順序容器适器：stack（棧）、queue（隊列）和priority_queue（優先隊列）。擴充卡(adaptor)是标準庫中的一個通用概念，容器、疊代器和函數都有擴充卡。本質上，一個擴充卡是一種機制，能使某種事物的行為看起來像另外一種事物一樣。一個容器擴充卡接受一種已有的容器類型，使其行為看起來像一種不同的類型。例如，stack擴充卡接受一個順序容器(除array或forward_list外)，并使其操作起來像一個stack一樣。

  下表列出了一些容器擴充卡。

容器擴充卡類型

stack

一種先進後出(FILO)的資料結構，隻有一個出口。

C++提高程式設計（三）—— STL常用容器(5) ：stack容器

queue

一種先進先出(FIFO)的資料結構，有兩個出口。

C++提高程式設計（三）—— STL常用容器(6) ：queue容器

 priority_queue 

每次從隊列中取出具有最高優先級的元素。

  預設情況下，stack和queue是基于deque實作的，priority_queue是基于vector之上實作的。

  關聯容器和順序容器有着根本的不同：關聯容器中的元素是按關鍵字來儲存和通路的。與之相對，順序容器中的元素是按它們在容器中的位置順序來儲存和通路的。

  關聯容器支援高效的關鍵字查找和通路，兩個主要的關聯容器(associative-container)類型是map和set，map中的元素是一些關鍵字 - 值(key-value)對：關鍵字起到索引的作用，值則表示與索引相關聯的資料，set中每個元素隻包含一個關鍵字。set支援高效的關鍵字查詢操作——檢查一個給定關鍵字是否在set中，例如，在某些文本處理過程中，可以用一個set來儲存想要忽略的單詞。字典則是一個很好的使用map的例子：可以将單詞作為關鍵字，将單詞釋義作為值。

  下表列出了一些關聯容器。

set

關鍵字即值，即隻儲存關鍵字的容器

C++提高程式設計（三）—— STL常用容器(8) ：set / multiset容器

map

關聯數組；儲存關鍵字 - 值對

C++提高程式設計（三）—— STL常用容器(9) ：map / multimap容器

multiset

關鍵字可重複出現的set

multimap

關鍵字可重複出現的map