STL Notes

STL容器共性

STL容器所提供的都是值寓意，而非引用寓意，也就是说当我们向容器插入元素的时候，容器内部实施了拷贝动作，将我们要插入的元素再另行拷贝一份放入到容器中，也就是说我们提供的元素必须能够拷贝。

若有指针，需要写拷贝构造，重载等号

• 除了queue和stack之外，每个容器都提供可返回迭代器的函数，运用返回的迭代器就可以访问元素。
• 通常STL不会抛出异常，需要使用者传入正确参数。
• 每个容器都提供了一个默认的构造函数和默认的拷贝构造函数。
• 大小相关的构造方法：
  • size()返回容器中元素的个数
  • empty()判断元素是否为空

STL容器使用时机

	vector	deque	list	set	multiset	map	multimap
典型内存结构	单端数组	双端数组	双向链表	二叉树	二叉树	二叉树	二叉树
可随机存取	是	是	否	否	否	对key而言，是	否
元素搜寻速度	慢	慢	非常慢	快	快	对key而言，快	对key而言，快
元素安插移除	尾端	头尾两端	任何位置	-	-	-	-

使用场景

vector

软件历史操作数据的存储，经常查看历史记录，但不会删除记录。

deque

排队购票系统，排队者的存储可以采用deque，支持头部快速移除，尾端快速添加。如果采用vector，头部移除会移动大量数据，速度慢。

vector v.s. deque

• vector.at()比deque.at()效率高：vector.at(0)是固定的，deque的开始位置是不固定的
• 如果有大量释放操作时，vector花的时间更少
• deque支持头部的快速插入与移除

list

公交车乘客的存储，随时可能有乘客下车，支持频繁的不确定位置元素的移除和插入

set

对手机游戏的个人得分纪录的存储，存储要求从高分到低分的顺序排列

map

按ID号存储十万个用户，想要快速通过ID查找对应的用户。利用二叉树的查找效率。