C++ STL(2)

from my csdn blog

顺序性容器

• 向量 vector

  • 动态数组，创建后会在内存中分配一段连续的内存空间。
  • 初始空间大小可以预先指定，当数据超过空间时会重新分配一块内存，将原数据拷贝到新的内存块中，然后销毁原内存块中的对象（调用析构函数），最后释放原内存。
  • 所以尽量不要导致重复申请内存，只有预先知道大小的情况下vector性能最优，大多数情况下vector不是满存的。
  • 注意：内部插入删除效率非常低，头部也不能插入删除，最好创建时指定空间大小，只能在末尾进行push,pop。

• 双向链表 list

  • 线性链表，若干节点构成（信息块+前驱后继指针），无需分配内存大小且可任意伸缩，存储在非连续的内存空间中。
  • 随即检索性能差，目标元素越靠后，时间越长。 < vector
  • 可迅速在任何节点进行插入删除，也可以在两端进行push,pop。 >vector
  • 相对vector，内存占用更多。

• 双端队列 deque

  • 优化的，对序列两端元素进行添加删除的序列容器，采用多个连续的存储块，并且在一个映射结构中保存对这些块和顺序的跟踪。
  • 较为快速的随机访问 < vector > list
  • 两端添加元素开销小，无需重新分配内存 > vector
  • 可以在内部进行插入和删除，性能不如 list
  • 感觉这玩意挺不错的，在需求多情况下，如果不追求效率可以用

关联容器

• set, multiset, map, multimap

  • 非线性结构，使用一种高效特殊的平衡检索二叉树——红黑树（我学过AVL和splay）

• 集合 set

  • 一组元素的组合，包含的元素值唯一，按一定顺序排列
  • 内部通过链表的方式组织，插入时比vector块，查找和末尾添加比vector慢

• 多重集合 multiset

  • 与set不同是元素可以不唯一

• 字典 map

  • 提供 键-值 关系一对一的数据存储，键不可重复，且按照一定顺序排列，默认升序排列
  • multimap允许键不唯一

区别

• 关联容器链式存储，vector顺序存储，插入删除操作更快。但是比list要慢，list为线性结构，而关联容器每次插入删选需要重新排序。

• 关联容器元素检索比vector慢，比list快很多，当容器越大时，相对于list的优越性更加明显。

• 在使用上set 区别于vector,deque,list 的最大特点就是set 是内部排序的，这在查询上虽然逊色于vector ，但是却大大的强于list 。（有点不大懂）

• map的功能不可取代，其他容器无法做到。

容器适配器

• 容器适配器

  • 栈stack
  • 队列queue
  • 优先队列priority_queue

• 不懂的地方，粘过来的

  • 适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。
  • STL 中提供的三种适配器可以由某一种顺序容器去实现。默认下stack 和queue 基于deque 容器实现，priority_queue 则基于vector 容器实现。
  • 当然在创建一个适配器时也可以指定具体的实现容器，创建适配器时在第二个参数上指定具体的顺序容器可以覆盖适配器的默认实现。
  • 由于适配器的特点，一个适配器不是可以由任一个顺序容器都可以实现的。

• 注意事项

  • 栈stack 的特点是后进先出，所以它关联的基本容器可以是任意一种顺序容器，因为这些容器类型结构都可以提供栈的操作有求，它们都提供了push_back,pop_back和back操作
  • 队列queue 的特点是先进先出，适配器要求其关联的基础容器必须提供pop_front操作，因此其不能建立在vector容器上
  • 优先级队列priority_queue 适配器要求提供随机访问功能，因此不能建立在list容器上。