一、deque 双端队列容器
#include
是下标顺序容器，它允许在首尾两端快速的插入、删除数据
deque的元素不是全部相邻存储的:采用单独分配的固定大小数组的序列存储数据，以及额外的登记表(中控数组)，
该表中记录了所有序列的地址，这表示通过下标访问元素时必须经过两次指针解引用，vector只需要一次
deque支持随机访问，效率依然是O(1)
deque的存储也可以按需自动扩展、收缩，并且deque的扩展比vector更优，因为不设计到原内存复制，销毁环节
1、vector扩容，先申请一块更大的新内存，把原内存数据拷贝，释放原内存
2、deque扩容，只需要申请一块新的固定大小的序列，记录到中控数组即可
deque比vector多push_front\pop_front操作，并且效率也能O(1)
vector比deque多个reserve预分配内存，因为deque不需要预分配内存来节约时间
deque的优点：
1、与vector相比，头部的插入和删除时，不需要搬运后序的元素，效率特别高(O(1));
在扩容时，也不需要移动、释放原内存，只需要操作中控数组即可
2、与list相比，底层依然是连续空间，空间利用率更高，支持随机访问O(1)
deque的缺点：
1、没有vector和list那么极致，随机访问的速度要比vector慢，因为vector
是真正的连续空间；中间位置的插入和删除没有list快，list根本不需要扩容
2、不适合遍历，因为在遍历时deque的迭代器需要频繁的检查是否移动到了某个
序列的末尾，并且需要解两次引用，效率低
3、因此当需要线性容器时，大多数情况下优先考虑vector、list、deque的应用不多(stack\queue)
二、stack 栈容器(适配器)
底层由deque实现的
不支持运算符，没有迭代器，只有无参构造、拷贝构造
empty、push、pop、top、size
三、queue 队列容器(适配器)
底层由deque实现的
不支持运算符，没有迭代器，只有无参构造、拷贝构造
empty、push、pop、front、back、size
四、prioroty_queue 优先队列容器（适配器）
#include
底层采用vector实现,当数据入队时，会对数据进行调整成堆结构，默认
是大顶堆，元素越大，优先级越高，越先出队，不允许相同
注意:存储的元素必须支持 < 运算符
注意：只能查看top。所以，可以使用top和pop查看各个元素
如何调整优先队列的优先级:(小顶堆)
1、元素取反存入，取出去反
2、类类型数据重载 < 运算符，调整 < 运算符的比较过程
3、固定语法
priority_queue<类型，vector<类型>,greater<类型> > 队列名；
//升序
priority_queue<类型，vector<类型>,less<类型> > 队列名；
//降序
五、关联性容器(有序)
关联性容器可以实现快速查找（O(logn)）的容器
线性容器中array、vector、list、deque都可以使用全局的find进行顺序查找(O(n)),
必须支持operator==比较
底层实现：红黑树
六、set 集合容器
#include
集合容器，底层采用红黑树实现，特点：元素不能重复，会自动对数据进行排序，它存储的元素
必须支持 < 运算符，只能使用迭代器遍历
默认下是按照 operator< 运算符进行比较，为什么不是使用 operatior== 来比较
1、因为二叉排序树的规则：左小于根、根小于右，如果相等插入失败， ==无法判断大小
2、a == b 可以使用 !(a<b || b>a)来替代
构造函数:只有无参、拷贝构造
支持的运算符:与list一致，不支持随机访问
常用的成员函数：
iterator insert( iterator i, const TYPE& val );
功能：向set中添加val，i位置意义不大（因为它会排序）
void insert( input_iterator start, input_iterator end );
功能：向set添加一组[start,end)数据
pair<iterator,bool> insert( const TYPE& val );
功能：向set添加val
返回值：返回键值对，pair<添加的位置，是否添加成功>
class pair{
iterator first;
bool second;
}
size_type count( const key_type& key );
功能：查看key在set中有几个，要么是0要么是1，也就是存不存在
iterator find( const key_type& key );
功能：查找set中key对元素的位置，并返回该位置的迭代器
如果找不到key，返回end()位置的迭代器
pair<iterator, iterator> equal_range( const key_type& key );
功能：查看key在set中的范围，并返回该范围组成的键值对，在set中意义不大
void erase( iterator pos );
void erase( iterator start, iterator end );
size_type erase( const key_type& key );
功能：删除值为key的元素，成功返回1，失败返回0
key_compare key_comp() const;
功能：返回一个用于比较set中元素的函数对象，该对象属于set
例如：
set<int>::key_compare cmp = s.key_comp();
cmp(int,int) 第一个"小"，则为真
value_compare value_comp() const;
功能：在set中等同于 key_comp
iterator lower_bound( const key_type& key );
功能：返回一个大于或者等于key的最小的元素的迭代器
iterator upper_bound( const key_type& key );
功能：返回一个大于key的最小元素的迭代器
七、multiset 多重集合容器
#include
元素可以重复，也会对元素自动进行排序，元素必须支持 < 运算符，只能用迭代器遍历
size_type count( const key_type& key );
功能：计算能有几个key
pair<iterator, iterator> equal_range( const key_type& key );
功能：返回值为key的元素的范围
八、map 映射容器
#include
一般map中存储一些经常需要查找的数据，因为map的查找速度极快，set速度也不慢，但是
比set多一个value来进行描述。
redis内存数据库中使用键值对存储数据
key和value一一对应，可以根据key来访问value，底层采用红黑树根据key来进行组织、管理，
查找效率很高
构造函数：
map();
map( const map& m );
map( iterator start, iterator end );
功能：使用一组数据(pair类型)构造
map( iterator start, iterator end, const key_compare& cmp );
功能：使用一组数据(pair类型)构造，并提供key的比较函数
map( const key_compare& cmp );
功能：提供key的比较函数构造
支持的运算符：
[] 支持通过key作为下标访问元素的value
既可以用于访问，当key不存在时，也可以用于插入数据<key，value>，
如果key存在，则修改value
m[key] = value; //添加、修改
m[key]; //key不存在，添加key-value value使用无参构造或者默认值为0
m[key]; //key存在，访问对应的value
成员函数 at(key) 也可以用于访问、修改key的value，但是当key不存在时
会抛出异常 out_of_range
常用成员函数：
iterator insert( iterator i, const TYPE& pair );
void insert( input_iterator start, input_iterator end );
pair<iterator,bool> insert( const TYPE& pair );
九、multimap 多重映射容器
#include
通过迭代器删除元素需要注意的问题：
1、对于关联性容器(set\multiset\map\nultimap ),删除当前iterator会仅仅使得
当前iterator失效，其余位置没有变化，因此在erase时只需要递增iterator即可依次删除，
因为底层是红黑树，某个节点删除不会影响其他节点的位置
map.erase(it++);
2、对于线性容器(vector\deque),删除当前iterator
后，后序所有的iterator失去原来意义，因为使用的是连续内存，删除一个，后面所有元素都
重新移动，iterator不能递增删除，只能通过重新接收erase的返回值，获取新的当前iterator
继续删除
it = vector.erase(it);
3、list两种方式都可以
十、bitset 位集合容器
#include
是一种封装了各种位操作的类类型数据结构
!=, ==, &=, ^=, |=, ~, <<=, >>=, []
成员函数：
bool any();
功能：有任意一位是1，返回真
size_type count();
功能：统计二进制位是1的位数有几位
flip 所有二进制位取反\指定的二进制位取反
none 全部位没有一个是1，返回真
reset 全部二进制位置0\指定二进制位置0
set 全部二进制位置1\指定二进制位置val=1
size 获取位数
test 访问指定的二进制位的值
to_string 把所有二进制位转string类型
to_ulong 把所有二进制位转unsigned long类型
C++不常用，但是对于嵌入式软件编程会比较方便去设置二进制位
常考的面试问题：
1、vector与list的区别
顺序结构、链式结构的区别
容器区别：支持运算符、算法、迭代器等
2、指针与迭代器的区别
1、迭代器实际是为了遍历、操作容器而进行了封装的类模版，重载了指针操作的相关运算符，
使用起来像指针一样，更像智能指针
2、迭代器使用后会释放失效，不能继续直接使用，正常使用指针是可以继续使用
3、指针可以指向函数，迭代器只能指向容器
4、指针是迭代器的一种，只能用于某些特定类型的容器；迭代器是指针的一种泛化类型，
可以用于任意类型的容器，所以，指针满足迭代器的一切要求。
迭代器的设计模式：提供一种方法，不需要暴露其容器中的内部数据类型情况下，也能够正常操作、遍历该容器的每个
元素，这种设计模式在STL中广泛使用。
3、STL中哪些容器底层采用红黑树，为什么
set\multiset\map\multimap
(1)、数据需要频繁查找，也需要进行插入、删除操作，普通链式结构、顺序结构性能不高
(2)、选择二分查找
(3)、基于以上两点的话，就可以选择有序二叉树、不够均匀、接近单支状、效率低
(4)、所以可以选择平衡二叉树AVL，查找效率高，创建、插入、删除效率低
(5)、红黑树，伪平衡、查找速度很接近AVL、创建、插入、删除效率比AVL树高的多，综合性能最优