lantionzy

       標準庫定義了三種順序容器類型：vector、list 和 deque（雙端隊列“double-ended queue”）。它們的差別在于訪問元素的方式，以及添加或刪除元素相關(guān)操作的運行代價。

    1、每種順序容器都提供了一組有用的類型定義以及以下操作：

       在容器中添加元素。

       在容器中刪除元素。

       設(shè)置容器大小。

      （如果有的話）獲取容器內(nèi)的第一個和最后一個元素。

    2、一些關(guān)鍵概念和難點：

       vector 對象動態(tài)增長：vector 對象（以及其他標準庫容器對象）的重要屬性就在于可以在運行時高效地添加元素。因為 vector 增長的效率高，在元素值已知的情況下，最好是動態(tài)地添加元素。雖然可以對給定元素個數(shù)的 vector 對象預(yù)先分配內(nèi)存，但更有效的方法是先初始化一個空 vector 對象，然后再動態(tài)地增加元素（我們隨后將學(xué)習(xí)如何進行這樣的操作）。
      
       容器元素都是副本：在容器中添加元素時，系統(tǒng)是將元素值復(fù)制到容器里。類似地，使用一段元素初始化新容器時，新容器存放的是原始元素的副本。被復(fù)制的原始值與新容器中的元素各不相關(guān)，此后，容器內(nèi)元素值發(fā)生變化時，被復(fù)制的原值不會受到影響，反之亦然。
      
       list 容器表示不連續(xù)的內(nèi)存區(qū)域，允許向前和向后逐個遍歷元素。在任何位置都可高效地 insert 或 erase 一個元素。插入或刪除 list 容器中的一個元素不需要移動任何其他元素。另一方面，list 容器不支持隨機訪問，訪問某個元素要求遍歷涉及的其他元素。

       對于 vector 容器，除了容器尾部外，其他任何位置上的插入（或刪除）操作都要求移動被插入（或刪除）元素右邊所有的元素。例如，假設(shè)有一個擁有 50 個元素的 vector 容器，我們希望刪除其中的第 23 號元素，則 23 號元素后面的所有元素都必須向前移動一個位置。否則， vector 容器上將會留下一個空位（hole），而 vector 容器的元素就不再是連續(xù)存放的了。

       deque 容器擁有更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。從 deque 隊列的兩端插入和刪除元素都非常快。在容器中間插入或刪除付出的代價將更高。 deque 容器同時提供了 list 和 vector 的一些性質(zhì)：與 vector 容器一樣，在 deque 容器的中間 insert 或 erase 元素效率比較低；不同于 vector 容器，deque 容器提供高效地在其首部實現(xiàn) insert 和 erase 的操作，就像在容器尾部的一樣；與 vector 容器一樣而不同于 list 容器的是， deque 容器支持對所有元素的隨機訪問。

       在 deque 容器首部或尾部插入元素不會使任何迭代器失效，而首部或尾部刪除元素則只會使指向被刪除元素的迭代器失效。在 deque 容器的任何其他位置的插入和刪除操作將使指向該容器元素的所有迭代器都失效。

       vector 和 deque 容器都支持對其元素實現(xiàn)高效的隨機訪問。也就是說，我們可以高效地先訪問 5 號元素，然后訪問 15 號元素，接著訪問 7 號元素，等等。 由于 vector 容器的每次訪問都是距離其起點的固定偏移，因此其隨機訪問非常有效率。在 list 容器中，上述跳躍訪問會變得慢很多。在 list 容器的元素之間移動的唯一方法是順序跟隨指針。從 5 號元素移動到 15 號元素必須遍歷它們之間所有的元素。

    3、常用迭代器運算

         *iter           返回迭代器 iter 所指向的元素的引用
         iter->mem       對 iter 進行解引用，獲取指定元素中名為 mem 的成員。等效于 (*iter).mem
         ++iter iter++   給 iter 加 1，使其指向容器里的下一個元素
         --iter iter--   給 iter 減 1，使其指向容器里的前一個元素
         iter1 == iter2
         iter1 != iter2  比較兩個迭代器是否相等（或不等）。當(dāng)兩個迭代器指向同一容器中的同一個元素，或者當(dāng)它們都指向同一個容器的超出末端的下一位置時，兩個迭代器相等。
      
       只適用于 vector 和 deque 容器的操作

         iter + n
         iter - n        在迭代器上加（減）整數(shù)值 n，將產(chǎn)生指向容器中前面（后面）第 n 個元素的迭代器。新計算出來的迭代器必須指向容器中的元素或超出容器末端的下一位置
         iter1 += iter2
         iter1 -= iter2  這里迭代器加減法的復(fù)合賦值運算：將 iter1 加上或減去 iter2 的運算結(jié)果賦給 iter1
         iter1 - iter2   兩個迭代器的減法，其運算結(jié)果加上右邊的迭代器即得左邊的迭代器。這兩個迭代器必須指向同一個容器中的元素或超出容器末端的下一位置
         >, >=, <, <=    迭代器的關(guān)系操作符。當(dāng)一個迭代器指向的元素在容器中位于另一個迭代器指向的元素之前，則前一個迭代器小于后一個迭代器。關(guān)系操作符的兩個迭代器必須指向同一個容器中的元素或超出容器末端的下一位置
 
    4、選擇容器類型的法則
        

       如果程序要求隨機訪問元素，則應(yīng)使用 vector 或 deque 容器。

       如果程序必須在容器的中間位置插入或刪除元素，則應(yīng)采用 list 容器。
      
       如果程序不是在容器的中間位置，而是在容器首部或尾部插入或刪除元素，則應(yīng)采用 deque 容器。

       如果只需在讀取輸入時在容器的中間位置插入元素，然后需要隨機訪問元素，則可考慮在輸入時將元素讀入到一個 list 容器，接著對此容器重新排序，使其適合順序訪問，然后將排序后的 list 容器復(fù)制到一個 vector 容器。