STL容器简述（c++）

vector

• 向量，STL标准且安全的数组，只能push_back()
• 原理：连续的内存空间、数组、支持下标访问、随机访问的速度很快、头部插入很慢，尾部插入很快。（所以推出了deque，可以插头去头）
• 性能：查找删除与数组性能一样，增加元素引发扩容时时会有性能压力，一般为当前当钱大小的两倍，然后把原数组的内容拷贝过去，接着释放原来的空间

list

• 列表，游标一次只能移动一步，双向链表，每个节点有指向前驱和后继的两个指针
• 原理：双向链表、不支持下标访问、随机访问速度慢、插入快
• 性能：常量性能的增删，不支持随机访问

map，multimap

• 映射，包含了经过排序的二元组的集合，key值唯一（排序、搜索），可以通过ar[43]="overripe"或者ar[“banana”]="overripe"找到想要的数据。
• 原理：以key建立的红黑树、插入删除效率贼高
• 区别：multimap不存在at操作
  红黑树虽然本质上是一棵BST，但它在BST的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除、的时间复杂度最坏为O(logn)

set,multiset:

• 原理：红黑树
• 区别：Set和Vector的区别在于Set不包含重复的数据。Set和Map的区别在Set只含有Key，而Map有一个Key和Key所对应的Value两个元素

unordered_map:

• 所有无序容器的底层实现都是Hash Map
• 原理：序容器存储键值对时，会先申请一整块连续的存储空间，但此空间并不用来直接存储键值对，而是存储各个链表的头指针，我们称其为桶，各键值对真正的存储位置是各个链表的节点

deque、stack

deque双端队列，功能和vector相似，但是增加对容器头部的增删。pop_front(),push_front()

详细每个容器常用的api函数请看我另一篇博客c++常用容器简介