lantionzy

       标准库定义了三种顺序容器类型：vector、list 和 deque（双端队列“double-ended queue”）。它们的差别在于访问元素的方式，以及添加或删除元素相关操作的运行代价。

    1、每种顺序容器都提供了一组有用的类型定义以及以下操作：

       在容器中添加元素。

       在容器中删除元素。

       设置容器大小。

      （如果有的话）获取容器内的第一个和最后一个元素。

    2、一些关键概念和难点：

       vector 对象动态增长：vector 对象（以及其他标准库容器对象）的重要属性就在于可以在运行时高效地添加元素。因为 vector 增长的效率高，在元素值已知的情况下，最好是动态地添加元素。虽然可以对给定元素个数的 vector 对象预先分配内存，但更有效的方法是先初始化一个空 vector 对象，然后再动态地增加元素（我们随后将学习如何进行这样的操作）。
      
       容器元素都是副本：在容器中添加元素时，系统是将元素值复制到容器里。类似地，使用一段元素初始化新容器时，新容器存放的是原始元素的副本。被复制的原始值与新容器中的元素各不相关，此后，容器内元素值发生变化时，被复制的原值不会受到影响，反之亦然。
      
       list 容器表示不连续的内存区域，允许向前和向后逐个遍历元素。在任何位置都可高效地 insert 或 erase 一个元素。插入或删除 list 容器中的一个元素不需要移动任何其他元素。另一方面，list 容器不支持随机访问，访问某个元素要求遍历涉及的其他元素。

       对于 vector 容器，除了容器尾部外，其他任何位置上的插入（或删除）操作都要求移动被插入（或删除）元素右边所有的元素。例如，假设有一个拥有 50 个元素的 vector 容器，我们希望删除其中的第 23 号元素，则 23 号元素后面的所有元素都必须向前移动一个位置。否则， vector 容器上将会留下一个空位（hole），而 vector 容器的元素就不再是连续存放的了。

       deque 容器拥有更加复杂的数据结构。从 deque 队列的两端插入和删除元素都非常快。在容器中间插入或删除付出的代价将更高。 deque 容器同时提供了 list 和 vector 的一些性质：与 vector 容器一样，在 deque 容器的中间 insert 或 erase 元素效率比较低；不同于 vector 容器，deque 容器提供高效地在其首部实现 insert 和 erase 的操作，就像在容器尾部的一样；与 vector 容器一样而不同于 list 容器的是， deque 容器支持对所有元素的随机访问。

       在 deque 容器首部或尾部插入元素不会使任何迭代器失效，而首部或尾部删除元素则只会使指向被删除元素的迭代器失效。在 deque 容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器都失效。

       vector 和 deque 容器都支持对其元素实现高效的随机访问。也就是说，我们可以高效地先访问 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  比较两个迭代器是否相等（或不等）。当两个迭代器指向同一容器中的同一个元素，或者当它们都指向同一个容器的超出末端的下一位置时，两个迭代器相等。
      
       只适用于 vector 和 deque 容器的操作

         iter + n
         iter - n        在迭代器上加（减）整数值 n，将产生指向容器中前面（后面）第 n 个元素的迭代器。新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一位置
         iter1 += iter2
         iter1 -= iter2  这里迭代器加减法的复合赋值运算：将 iter1 加上或减去 iter2 的运算结果赋给 iter1
         iter1 - iter2   两个迭代器的减法，其运算结果加上右边的迭代器即得左边的迭代器。这两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置
         >, >=, <, <=    迭代器的关系操作符。当一个迭代器指向的元素在容器中位于另一个迭代器指向的元素之前，则前一个迭代器小于后一个迭代器。关系操作符的两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置
 
    4、选择容器类型的法则
        

       如果程序要求随机访问元素，则应使用 vector 或 deque 容器。

       如果程序必须在容器的中间位置插入或删除元素，则应采用 list 容器。
      
       如果程序不是在容器的中间位置，而是在容器首部或尾部插入或删除元素，则应采用 deque 容器。

       如果只需在读取输入时在容器的中间位置插入元素，然后需要随机访问元素，则可考虑在输入时将元素读入到一个 list 容器，接着对此容器重新排序，使其适合顺序访问，然后将排序后的 list 容器复制到一个 vector 容器。