C++容器的分类

一.sequence containers

1.array：数组封装类

2.vector: 单向生长

3.deque: 双向生长

4.list: 双向链表，通过指针链接相邻的两个元素

5.forward-list:单向链表，比list更省内存

二.associative containers

set/multiset: value是key，mutil表示value的值可以重复

map/multimap: value和key值分开，通过key值得到value的值

unordered_set/unordered_map/unordered_multiset/unordered_multimap: 采用separate chaining原理，背后是hashtable，hashtable下面挂了很多像篮子一样的指针，这些指针存放在vector的容器内，篮子内的元素可以是单向列表也可以是双向列表，元素的总数不超过篮子的总数，当等于篮子数量的时候，篮子的数量会成长为之前数量的两倍，这个过程叫做rehashing，篮子内的元素会通过hash function计算出来的hash code重新选择放入哪个篮子中。

三.容器的定义

template<typename _Tp, typename _alloc = std::allocator<_Tp>>

class vector : protected _Vector_base<_Tp, _alloc>

template<typename _Tp, typename _alloc = std::allocator<_Tp>>

class list : protected _List_base<_Tp, _alloc>

template<Typename _Key, typename _Compare = std::less<_Key>, typename _alloc= std::allocator<_Key>>

class set

template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, typename _alloc = std::allocator<std::pair<const _Key, _Tp>>>

class map

template<class _Value, calss _Hash = hash<_Value>, class _Pred=std::equal_to<_Value>, calss _alloc = std::allocator<_Value>>

class unordered_set

template<class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred =std::equal_to<_Key>, class _alloc = std::allocator<std::pair<const _Key, _Tp>>>

class unordered_map