STL

Word count: 170 | Reading time≈ 1 min

容器结构分类

sequence containers
- 按照放进去的顺序拜访元素
- 包括
  - array
    - 定长
  - vector
    - 尾部可扩张
  - deque
    - 双向可扩张
  - list
    - 双向链表
  - forward-list
    - 单向链表
associative containers
- 包括
  - 红黑树（没有规定一定红黑树，但红黑树效果好所以都用它）
    - Set/Multiset
    - Map/multimap
unordered containers
- 其实unordered其实就是associative的一种
- 包括
  - unordered Set/Multiset
  - unordered Map/multimap

	Vector	Deque	List	Set	MultiSet	Map	MultiMap
内部结构	dynamic array	array of arrays	double linked list	binary tree	binary tree	binary tree	binary tree
随机存取	Yes	Yes	No	No	No	Yes(key)	No
搜索速度	慢	慢	很慢	快	快	快	快
快速插入移除	尾部	首尾	任何位置	–	–	–	–