容器containers解析
侯捷老师STL课程笔记
容器
容器的分类
1、Sequence Containers
===============================
Array:数组，定义多大的空间就只能用多大，无法扩充，超过就会越界。
Vector:
- 起点处不能动，后面可以扩充。
- 当空间不够时，会自动的扩充空间（利用分配器自动的执行扩充）。扩充空间时两倍增长。
Deque:
- 双向队列，前后两端可进可出。
- 此容器本身没有sort（）函数，如果排序使用全局的sort（deque.begin(), deque.end()）。
- 每次增加一个buffer的容量，每个buffer之间可以不连续。
deque可以分散出queue（队列）和stack（栈）
stack:没有iterator，因为会破坏它先进后出的特性。
queue：没有iterator。
List:
- 双向（环状）链表，用双向指针连起来的。
- 自身带有sort函数。不可以直接使用全局sort（）。
- 每次扩充一个结点，资源利用率高。
- 但是查找困难。
Forward-List:
- 单向链表，单向指针链接起来的，耗用的内存比list少。
- 只有push_front()
注：有时候直接使用::find()函数，要比经过排序后再查找要快（时间浪费到排序上）
2、Associative Containers
===============================
用于大量查找使用关系型容器，内部是红黑树（平衡）
Set:
- set表示存放的元素不能重复
- 如果存入随机数，size比元素多，不会存入重复的元素。
Multiset:
- 只有value。（set表示存放的元素不能重复，Multiset可以重复）
- 插入元素的函数是multiset.insert()，插入位置不是头也不是尾。
- 容器本身有find。查找很快。
Map:
- 红黑树
- 不重复
- Map表示存放key不能重复，Multimap可以重复。
- 可以使用[]，例：c[i] = string[buf]，Map表示存放key不能重复即i不重复。
Multimap:
- Map的每一个节点都有两个部分：key和value，利用key查找value。
- Map表示存放key不能重复，Multimap可以重复。
- multimap不可使用[ ]做insertion。
- 插入元素因为是由key和value组成，所以要用pair去组合。例：c.insert(pair< long, string >(i, buf))
- 容器有find().
- 不可以使用[]进行添加元素，只能用insert。
Unordered Containers: HashTable Separate Chaining
不是红黑树结构，使用哈希表的结构。
1、Unordered Set/Multiset
- insert插入
- bucket是比元素多，有的bucket是空的。
- 如果元素比bucket大，那么bucket两倍扩充。
- 容器自己的find比全局的find快很多很多
2、Unordered Map/Multimap
- multimap不可使用[ ]做insertion。
每个结点连接链表，链表不能够太长，也就是每个结点对应的数据不能太多，链表过长会影响查找速度。
http://www.cplusplus.com