容器是面向对象的基础,所有面向对象的语言都有容器.
在C++中也就是标准模板库也就是常说的STL.
容器分为三类 顺序容器顺序容器是元素间有顺序关系的线性表,每个元素都有固定位置.不会提供特点进行排序,元素的顺序和插入的时间位置有关.
关联容器关联容器以键值的方式来保存数据
容器适配器这东西其实就是容器的容器,结果还是容器.如果容器时普通类型的模板,那么容器适配器就是容器的模板.
各容器特点 顺序容器vector 尾插尾删,可以直接访问任何元素
deque 尾(前)插尾(前)删,可以直接访问任何元素
list 在任意位置插入删除元素
关联容器set 查找元素,不能有重复元素
multiset 查找元素,可以有重复元素
map 一对多映射,基于key快速查找,不允许key重复
multimap 多对多映射,基于key快速查找,允许key重复
容器适配器stack 先进后出
queue 先进先出
priority_queue 优先级队列,优先级最高的元素最先出列
顺序容器选择vector是一段连续的内存块,而deque是多个连续的内存块,list是数据分开存储
vector查询性能最好,尾端增加数据性能也很好,可以高效的随机存取
list插入,删除性能最好,查询差,适合较多的插入删除操作并且不关心随机存取
deque两则结合,他是由链表和数组结合的产生的,他比list查询好,比vector插入删除好.当频繁的需要两端插入删除可以选择.
关联容器选择都是树形结构,内部是二叉树(红黑树)结构实现.
set和map保证了元素的唯一性,multiset和multimap扩展了这一特性.元素是有序的集合默认升序.
set内部还是链表的形式,插入快于vector,查找和尾插慢于vector
map和set一样内部还是链表的形式,由链表的优点,它提供键(key)-值(value)对应的关系
容器适配器选择priority_queue优先级队列适配器要求随机访问功能,所以只有vector,deque
stack先进后出,可以任意一种顺序容器,可以push_back,pop_back和back操作
queue先进先出,适配器要求pop_front,所以只有deque,list
