STL——順序容器的總結

（注：本文轉載自http://blog.csdn.net/hackbuteer1/article/details/6791260）

本文主要讨論C++标準庫中的順序容器及相應的容器擴充卡，這些内容主要涉及順序容器類型：vector、list、deque，順序容器擴充卡類型：stack、queue、priority_queue。

标準庫中的容器分為順序容器和關聯容器。順序容器(sequential container)内的元素按其位置存儲和通路，顧名思義，這些内部元素是順序存放的；順序容器内的元素排列次序與元素值無關，而是由元素添加到容器裡的次序決定。而關聯容器的元素按鍵(key)排序。         容器類共享部分公共接口。标準庫定義的三種順序容器類型：vector、list、deque（double-ended queue的縮寫，發音為“deck”），它們的差别僅在通路元素的方式，以及添加或删除元素相關操作的代價。順序容器擴充卡包括：stack、queue和priority_queue。容器隻定義了少量操作，大多數操作由算法庫提供。如果兩個容器提供了相同的操作，則它們的接口（函數名和參數個數）應該相同。 

标準容器類	說明
順序性容器
vector	從後面快速的插入與删除，直接通路任何元素
deque	從前面或後面快速的插入與删除，直接通路任何元素
list	雙連結清單，從任何地方快速插入與删除
關聯容器
set	快速查找，不允許重複值
multiset	快速查找，允許重複值
map	一對多映射，基于關鍵字快速查找，不允許重複值
multimap	一對多映射，基于關鍵字快速查找，允許重複值
容器擴充卡
stack	後進先出
queue	先進先出
priority_queue	最高優先級元素總是第一個出列

      容器類型

vector	容器，支援快速随機通路（連續存儲）
list	連結清單，支援快速插入/删除
deque	雙端隊列，支援随機通路（連續存儲），兩端能快速插入和删除
stack	棧
queue	隊列
priority_queue	優先級隊列

  順序容器的定義 順序容器的構造和初始化 下表為疊代器為所有容器類型所提供的運算：

*iter	傳回類型iter所指向的元素的引用
iter->mem	對iter進行解引用，并取得指定成員
++iter	給iter加1，使其指向容器中下一個元素
iter++
--iter	給iter減1，使其指向容器中前一個元素
iter--
iter1 == iter2	當兩個疊代器指向同一個容器中的同一進制素，或者當它們都指向
iter1 != iter2	同一個容器的超出末端的下一個位置時，兩個疊代器相等。

     vector和deque容器的疊代器提供了額外的運算：疊代器的算術運算和另一些關系運算，如下表所示：  

iter + n	在疊代器上加（減）整數值，将産生指向容器中前面（後面）第n個元素的疊代器；
iter - n	新計算出來的疊代器必須指向容器中的元素或超出容器末端的下一位置。
iter1 += iter2	複合運算：先加（減），再指派
iter1 -= iter2
iter1 - iter2	隻适用于vector和deque
>, >=, <, <=	比較疊代器的位置關系；隻适用于vector和deque

     關系操作符隻适用于vector和deque容器，這是因為隻有這兩種容器為其元素提供快速、随機的通路。它們確定可根據元素位置直接有效地通路指定的容器元素。這兩種容器都支援通過元素位置實作的随機通路，是以它們的疊代器可以有效地實作算術和關系運算。 疊代器範圍：[first, last)是一個左閉合區間，表示範圍從first開始，到last結束，但不包括last。注意：如果first不等于last，則對first反複做自增運算必須能夠到達last；否則，即last位于first之前，則将發生未定義行為。    疊代器範圍使用左閉合的意義：因為這樣可以統一表示空集，就無需特别處理。    另外，使用疊代器時，要特别留意疊代器的可能的失效問題。 通路元素  

back()	傳回容器的最後一個元素的引用。如果容器為空，則該操作未定義
front()	傳回容器的第一個元素的引用。如果容器為空，則該操作未定義
c[n]	傳回下标為n的元素的引用；如果n<0 or n>=size()，則該操作未定義  （注：隻适用于vector和deque容器）
at[n]	傳回下标為n的元素的引用；如果下标無效，則抛出異常out_of_range異常  （注：隻适用于vector和deque容器）

  删除元素    

erase(p)	删除疊代器p所指向的元素。傳回一個疊代器，它指向被删除的元素後面的元素。如果p指向容器内最後一個元素，則傳回的疊代器指向容器的超出末端的下一個位置；如果p本身就是指向超出末端的下一個位置的疊代器，則該函數未定義
erase(b, e)	删除[b, e)内的所有元素。傳回一個疊代器，它指向被删除元素段後面的元素。如果e本身就是指向超出末端的下一個位置的疊代器，則傳回的疊代器也指向超出末端的下一個位置。
clear()	删除容器内的所有元素，傳回void
pop_back()	删除容器内的最後一個元素，傳回void。如果容器為空，則該操作未定義。
pop_front()	删除容器内的第一個元素，傳回void。如果c為空容器，則該操作未定義  （注：隻适用于list和deque容器）

  指派與swap  

c1 = c2	删除容器c1的所有元素，然後将c2的元素複制給c1。c1和c2的類型必須相同。
c1.swap(c2)	交換内容：調用該函數後，c1中存放的是c2原來的元素，c2中存放的是c1原來的元素。c1和c2的類型必須相同。該函數的執行速度通常要比将c2的元素複制到c1的操作快。
c.assign(b, e)	重新設定c的元素：将疊代器b和e标記的範圍内所有的元素複制到c中。b和e必須不是指向c中元素的疊代器。
c.assign(n, t)	将容器c重新設定為存儲n個值為t的元素。

  注意：assign操作首先删除容器内所有的元素，再将參數所指定的新元素插入到容器中。       swap操作不會删除或插入任何元素，而且保證在常量時間内實作交換。由于容器内沒有移動任何元素，是以疊代器不會失效。但要注意這些疊代器指向了另一個容器中的元素。 容器的選用： vector和deque容器提供了對元素的快速通路，但付出的代價是，在容器的任意位置插入或删除元素，比在容器尾部插入和删除的開銷更大，因為要保證其連續存儲，需要移動元素；list類型在任何位置都能快速插入和删除，因為不需要保證連續存儲，但付出的代價是元素的随機通路開銷較大。特征如下：    1）與vector容器一樣，在deque容器的中間insert或erase元素效率比較低；    2）不同于vector容器，deque容器提供高效地在其首部實作insert和erase的操作，就像在尾部一樣；    3）與vector容器一樣而不同于list容器的是，deque容器支援對所有元素的随機通路。    4）在deque容器首部或尾部删除元素則隻會使指向被删除元素的疊代器失效。在deque容器的任何其他位置的插入和删除操作将使指向該容器元素的所有疊代器都失效。   容器的比較：

vector （連續的空間存儲,可以使用[]操作符）快速的通路随機的元素，快速的在末尾插入元素，但是在序列中間歲間的插入，删除元素要慢，而且如果一開始配置設定的空間不夠的話，有一個重新配置設定更大空間，然後拷貝的性能開銷。

deque （小片的連續，小片間用連結清單相連，實際上内部有一個map的指針，因為知道類型，是以還是可以使用[]，隻是速度沒有vector快）快速的通路随機的元素，快速的在開始和末尾插入元素，随機的插入，删除元素要慢，空間的重新配置設定要比vector快,重新配置設定空間後，原有的元素不需要拷貝。對deque的排序操作，可将deque先複制到vector，排序後在複制回deque。

list （每個元素間用連結清單相連）通路随機元素不如vector快，随機的插入元素比vector快，對每個元素配置設定空間，是以不存在空間不夠，重新配置設定的情況。

set：内部元素唯一，用一棵平衡樹結構來存儲，是以周遊的時候就排序了，查找也比較快的哦。

map ：一對一的映射的結合，key不能重複。

stack ：擴充卡，必須結合其他的容器使用，stl中預設的内部容器是deque。先進後出，隻有一個出口，不允許周遊。

queue： 是受限制的deque，内部容器一般使用list較簡單。先進先出，不允許周遊。

vector<bool> 與bitset<> ,前面的可以動态改變長度。

priority_queue： 插入的元素就有優先級順序，top出來的就是優先級最高的了

valarray 專門進行數值計算的，增加特殊的數學函數。

   一些容器選用法則：    1） 如果程式要求随機通路元素，則應使用vector或deque容器；    2） 如果程式必須在容器的中間位置插入或删除元素，則應采用list容器；    3）如果程式不是在容器的中間位置，而是在容器首部或尾部插入或删除元素，則應采用deque容器；    4）如果隻需要在讀取輸入時在容器的中間位置插入元素，然後需要随機通路元素，則可以在輸入時将元素讀入到一個list容器中，然後對容器排序，再将排序後的list容器複制到vector容器中。    5）如果程式既需要随機通路，又需要在容器的中間位置插入或删除元素，此時應當權衡哪種操作的影響較大，進而決定選擇list容器還是vector或deque容器。注：此時若選擇使用vector或deque容器，可以考慮隻使用它們和list容器所共有的操作，比如使用疊代器而不是下标，避免随機通路元素等，這樣在必要時，可以很友善地将程式改寫為使用list容器。 容器擴充卡      擴充卡（adaptor）是标準庫中通用的概念，包括容器擴充卡、疊代器擴充卡和函數擴充卡。本質上，擴充卡是使一事物的行為類似于另一事物的行為的一種機制。容器擴充卡讓一種已存在的容器類型采用另一種不同的抽象類型的工作方式實作，隻是發生了接口轉換而已。      标準庫提供了三種順序容器擴充卡：queue, priority_queue和stack。      所有擴充卡都定義了兩個構造函數：預設構造函數用于建立空對象，而帶一個容器參數的構造函數将參數容器的副本作為其基礎值。      預設的stack和queue都基于deque容器實作，而priority_queue則在vector容器上實作。在建立擴充卡時，通過将一個順序容器指定為擴充卡的第二個類型參數，可覆寫其關聯的基礎容器類型。例如：     stack<int, vector<int> > int_stack;  // 此時，int-stack棧是基于vector實作     對于給定的擴充卡，其關聯的容器必須滿足一定的限制條件。stack擴充卡所關聯的基本容器可以是任意一種順序容器類型，因為這些容器類型都提供了push_back、pop_back和back操作；queue擴充卡要求其關聯的基礎容器必須提供pop_front操作，是以其不能建立在vector容器上；priority_queue擴充卡要求提供随機通路功能，是以不能建立在list容器上。      兩個相同類型的擴充卡可以做==, !=, <, >, <=, >=這些關系運算，隻要其基本元素類型支援==和<兩個操作即可。這與容器大小比較原則一緻。 這與容器大小比較原則一緻。 棧

s.empty()	如果棧為這人，則true；否則傳回false
s.size()	傳回棧中元素的個數
s.pop()	删除棧頂元素，但不傳回其值
s.top()	傳回棧頂元素的值，但不删除該元素
s.push(item)	在棧項壓入新元素

  隊列和優先級隊列    标準庫隊列使用了先進先出（FIFO）的存儲和檢索政策，進入隊列的元素被放置在尾部，下一個被取出的元素則取自隊列的首部。    priority_queue預設使用元素類型的 < 操作符來确定它們之間的優先級關系，使用者也可以定義自己的優先級關系。在優先級隊列中，新元素被放置在比它優先級低的元素的前面。  

q.empty()	如果隊列為空，則傳回true；否則傳回false
q.size()	傳回隊列中元素的個數
q.pop()	删除隊首元素，但不傳回其值
q.front()	傳回隊首元素的值，但不删除該元素  （注：該操作隻适用于隊列）
q.back()	傳回隊尾元素的值，但不删除該元素  （注：該操作隻适用于隊列）
q.top()	傳回具有最高優先級的元素值，但不删除該元素  （注：該操作隻适用于優先級隊列。MSDN也為queue提供了該操作）
q.push(item)	對于queue，在隊尾壓入一個新元素；  對于priority_queue，在基于優先級的适當位置插入新元素