Effective STL [1] | 仔细选择你的容器

迭代器

1. 输入迭代器

• 每个迭代位置只能被读1次的只读迭代器，通常表现为 istream_iterator

2. 输出迭代器

• 每个迭代位置只能被写1次的只写迭代器，通常表现为 ostream_iterator

3. 前向迭代器

• 有输入和输出迭代器的能力，可以反复读写1个位置，不支持 operator–，可以高效地向前移动任意次数

• 散列容器的一种设计可以产生前向迭代器；

• 单链表容器也提供前向迭代器

4. 双向迭代器

• 像前向迭代器一样，后退很容易。标准关联容器都提供双向迭代器，list也有

5. 随机访问迭代器

• 可以做双向迭代器一样的事情，但也提供“迭代器算术”，即迭代器有一步向前或向后跳的能力。

• vector、string 和 deque 都提供随机访问迭代器。

• 指针数组的指针可以作为数组的随机访问迭代器。

容器

STL有迭代器、算法和函数对象，但对于大多数C++程序员，容器是最突出的。

它们比数组更强大更灵活，可以动态增长（也常是缩减），可以管理属于它们自己的内存，可以跟踪它们拥有的对象数目，可以限制它们支持操作的算法复杂度等等。

分类

vector、list和deque提供给程序员不同的复杂度，因此应该这么用：

• vector是一种可以默认使用的序列类型
  
• 当很频繁地对序列中部进行插入和删除时应该用list
  
• 当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构
  

连续内存容器和基于节点的容器的区别

• 连续内存容器（也叫做基于数组的容器）

  • 在一个或多个（动态分配）的内存块中保存它们的元素。

  • 如果一个新元素被查入或者已存元素被删除，其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来被删除的元素所占的空间。

  • 这种移动影响了效率和异常安全。

  • 标准的连续内存容器是vector、string和deque。

  • 非标准的rope也是连续内存容器。

• 基于节点的容器

  • 在每个内存块（动态分配）中只保存一个元素。

  • 容器元素的插入或删除只影响指向节点的指针，而不是节点自己的内容。

  • 所以当有东西插入或删除时，元素值不需要移动。

  • 表现为链表的容器——比如list和slist——是基于节点的，所有的标准关联容器也是（它们的典型实现是平衡树）。

  • 非标准的散列容器使用不同的基于节点的实现。

如何选择容器?

1. 你需要“可以在容器的任意位置插入一个新元素”的能力吗？
   • 如果是，你需要序列容器，关联容器做不到。
     
2. 你关心元素在容器中的顺序吗？
   • 如果不，散列容器就是可行的选择。否则，你要避免使用散列容器。
     
3. 必须使用标准C++中的容器吗?
   • 如果是，就可以除去散列容器、slist和rope。
     
4. 你需要哪一类迭代器？
   • 如果必须是随机访问迭代器，在技术上你就只能限于vector、deque和string，但你也可能会考虑rope。
   • 如果需要双向迭代器，你就用不了slist 和散列容器的一般实现。
     
5. 当插入或者删除数据时，是否非常在意容器内现有元素的移动？
   • 如果是，你就必须放弃连续内存容器。
     
6. 容器中的数据的内存布局需要兼容C吗？
   • 如果是，你就只能用vector。
     
7. 查找速度很重要吗？
   • 如果是，你就应该看看散列容器，排序的vector和标准的关联容器——大概是这个顺序。
     
8. 你介意如果容器的底层使用了引用计数吗？
   • 如果是，你就得避开string，因为很多string的实现是用引用计数。
   • 你也不能用rope，因为权威的rope实现是基于引用计数的。
   • 于是你得重新审核你的string，你可以考虑使用vector
     
9. 你需要插入和删除的事务性语义吗？也就是说，你需要有可靠地回退插入和删除的能力吗？
   • 如果是，你就需要使用基于节点的容器。
   • 如果你需要多元素插入（比如，以范围的方式）的事务性语义，你就应该选择list，因为list是唯一提供多元素插入事务性语义的标准容器。
   • 事务性语义对于有兴趣写异常安全代码的程序员来说非常重要。（事务性语义也可以在连续内存容器上实现，但会有一个性能开销，而且代码不那么直观）
     
10. 你要把迭代器、指针和引用的失效次数减到最少吗？
    • 如果是，你就应该使用基于节点的容器，因为在这些容器上进行插入和删除不会使迭代器、指针和引用失效（除非它们指向你删除的元素）。
    • 一般来说，在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。
      
11. 你需要具有以下特性的序列容器吗：1） 可以使用随机访问迭代器；2） 只要没有删除而且插入只发生在容器结尾，指针和引用的数据就不会失效？
    • 这个一个非常特殊的情况，但如果你遇到这种情况，deque就是你梦想的容器。
    • 有趣的是，当插入只在容器结尾时，deque的迭代器也可能会失效，deque是**唯一一个“在迭代器失效时不会使它的指针和引用失效”**的标准STL容器。

结语

当面对容器时，STL给了你很多选项。如果你的视线超越了STL的范围，那就会有更多的选项。在选择一个容器前，要保证考虑了所有你的选项。