找工作 stl源码剖析 顺序容器1(总体)(2)

为此，forward_list提供了如下的插入接口：

接口描述

其他所有STL容器都是在指定位置之前插入元素（除了std::array，它不允许插入）。forward_list的这种特殊处理，还是出于效率的考虑。对于单链表我们应该很熟悉，为了在某个指定节点之前插入插入节点，我们必须改变插入位置的前一个节点的指向。换句话说，为了在指定节点之前插入新元素，我们必须要先获得插入位置前一个位置的节点，为了获取前面这个节点，需要线性的操作时间。

而如果我们是在指定位置之后插入新元素，则无需线性时间的查找操作，这样可实现常数时间的插入：

同样的，处于性能的考虑，forward_list没有提供在尾部进行操作的接口，包括push_back(),pop_back()和emplace_back(),这些操作对单列表来说都至少要花费O(n)来完成。

指向被删除元素的迭代器，在删除之后失效。

list同样是一个模板类，它底层数据结构为双向循环链表。因此，它支持任意位置常数时间的插入/删除操作，不支持快速随机访问。

list的迭代器具备前移、后移的能力，所以list提供的是Bidirectional iterator(双向迭代器)。由于采用的是双向迭代器，自然也很方便在指定元素之前插入新节点，所以list很正常地提供了insert()操作与push_back()/pop_back()操作。在C++11中，list新增了三个接口，以支持在指定位置构造对象后插入容器中:

接口（C++11新增）描述

list的空间配置策略，自然是像我们普通双向链表那样，有多少元素申请多少内存。它不像vactor那样需要预留空间供新元素的分配，也不会因找不到连续的空间而引起整个容器的内存迁移。

list 有一个重要性质：插入操作（insert）与接合操作（splice）都不会造成原有的list迭代器失效。这在vector是不成立的，因为vactor的插入可能引起空间的重新配置，导致原来的迭代器全部失效。list的迭代器失效，只会出现在删除的时候，指向删除元素的那个迭代器在删除后失效。

通常来说，forward_list在使用灵活度上比不上list，因为它只能单向迭代元素，且提供的接口没有list多。然而，在内存的使用上，它是比list占优势的。当对内存的要求占首要位置时，应该选择forward_list。

vector的底层数据结构是动态数组，因此，vector的数据安排以及操作方式与std::array十很相似，它们间的唯一差别在于对空间的运用灵活性上。array为静态数组，有着静态数组最大的缺点：每次只能分配一定大小的存储空间，当有新元素插入时，要经历 “找到更大的内存空间”->“把数据复制到新空间” ->“销毁旧空间” 三部曲， 对于std::array而言，这种空间管理的任务压在使用它的用户身上，用户必须把握好数据的数量，尽量在第一次分配时就给数据分配合理的空间（这有时很难做到），以防止“三部曲”带来的代价，而数据溢出也是静态数组使用者需要注意的问题。而vector用户不需要亲自处理空间运用问题。vector是动态空间，随着新元素的插入，旧存储空间不够用时，vector内部机制会自行扩充空间以容纳新元素，当然，这种空间扩充大部分情况下（几乎是）也逃脱不了“三部曲”，只是不需要用户自己处理，而且vector处理得更加安全高效。vector的实现技术关键就在于对其大小的控制以及重新配置时数据移动效率。

对于C_style数组，我们使用普通指针就可以对数组进行各种操作。vector维护的是一个连续线性空间，与数组一样，所以无论其元素型别为何，普通指针都可以作为vector的迭代器而满足所有必要的条件。vector所需要的迭代器操作，包括operator*,operator->,operator++,operator--,operator+=,operator-=等，普通指针都具有。因此，普通指针即可满足vector对迭代器的需求。所以，vector提供了Random Access Iterators。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-61869-2.html