lantionzy

       標(biāo)準(zhǔn)庫(kù)定義了三種順序容器類(lèi)型：vector、list 和 deque（雙端隊(duì)列“double-ended queue”）。它們的差別在于訪(fǎng)問(wèn)元素的方式，以及添加或刪除元素相關(guān)操作的運(yùn)行代價(jià)。

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

       在容器中添加元素。

       在容器中刪除元素。

       設(shè)置容器大小。

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

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

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

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

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

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

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

    3、常用迭代器運(yùn)算

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

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

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

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

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