标签：容器 set 迭代 deque vector multiset 指针
- vector 容器的增长是当容量不够时，就找到一块二倍大的空间，将原来的内容复制到新空间。每一次复制伴有大量的拷贝构造和析构函数的调用，开销大。vector 里面有 begin end end_of_storge 三个迭代器（指针）。
- list本质是一个双向链表，list类模版里面含有迭代器，list的迭代器里含有一根指针。
- deque双端队列的实现是 多段式存储 ，模拟连续存储。deque有一个vector控制中心，控制中心里含有指向各个buffer的指针，deque含有首尾两个迭代器。控制中心的增长同 vector。deque的iterator含四根指针，一根指向控制中心该元素的位置的节点，指向该buffer的first，last，和指向当前buffer当前位置的cur指针。 deque的插入：插入的位置靠近尾部，就将尾部的位置后移，靠近首部，就将首部的位置前移。
-
- queue 和 stack 中内含一个deque，用deque做底层支持，对queue和stack的动作就是对queue做动作。stack和 queue没有迭代器。
- 容器rb_tree 类（红黑树）。红黑树提供了迭代器和遍历操作。rb_tree 为set和map做底层支持。
- set/multiset 以红黑树为底层结构，set/multiset 元素的value和key合一。set/multiset 禁止用iterator修改元素值。multiset允许重复key。map/multimap 以红黑树做底层结构。map/multimap 可以改变value。multimap 允许key重复。
- hash_table，类似于vector<list>，当数据个数超过bucket的个数时，就需要rehash，rehash的代价是巨大的，需要扩容vector，重新放置元素(成长的代价是痛苦的)。hash函数有很多特化版本。hash_table的iterator有指向vector的指针和指向当前bucket的指针两根指针。
- unorder_set unorder_multiset unorder_map unorder_multimap 以hash_table为底层结构。 l
标签：容器,
set,
迭代,
deque,
vector,
multiset,
指针
From： https://www.cnblogs.com/wuyun--wy/p/17202497.html