STL预习总结

在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因，list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。

Deque（复杂的动态数组）的特点：

1.支持随机访问，即支持[]以及at()，但是性能没有vector好。

2.可以在内部进行插入和删除操作，但性能不及list。 deque是一种优化了的对序列两端元素进行添加和删除操作的基本序列容器。通常由一些独立的区块组成，第一区块朝某方向扩展，最后一个区块朝另一方向扩展。它允许较为快速地随机访问但它不像vector一样把所有对象保存在一个连续的内存块，而是多个

连续的内存块。并且在一个映射结构中保存对这些块以及顺序的跟踪。

deque和vector的不同之处：

1. 两端都能够快速插入和删除元素。vector只能在尾端进行。

2. deque的元素存取和迭代器操作会稍微慢一些。因为deque的内部结构会多一个间接过程。

3. 迭代器是特殊的智能指针，而不是一般指针。它需要在不同的区块之间跳转。

4. deque可以包含更多的元素，其max_size可能更大。因为不止使用一块内存。

5. 不支持对容量和内存分配时机的控制。

注意：在除了首尾两端的其他地方插入和删除元素，都将会导致指向deque元素的任何pointers、references、iterators失效。不过，deque的内存重分配优于vector。因为其内部结构显示不需要复制所有元素。

6. deque的内存区块不再被使用时，会被释放。deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实作版本定义。

deque和vector相似的特性：

1. 在中间部分插入和删除元素相对较慢，因为所有元素都要被移动。

2. 迭代器属于随即存取迭代器。

四 序列式容器总结

1. 如果需要高效的随即查找和存取，而不在乎插

入和删除的效率，使用vector。

2. 如果需要大量的插入和删除，而不在乎查找和

存取的效率，应使用list。

3. 如果又要考虑查找和存取，又要关心两端数据

的插入和删除，应使用deque(但单独性能没有list和vector优)。