vector和list区别

1. 从底层实现来说，vector是通过数组实现的，存储空间上是一段连续的存储空间；list是通过双向链表实现的，把不连续的内存块通过链表的方式连接在一起。
2. 从插入删除时间复杂度来说，vector是随机访问的O(1)，但是插入和删除需要移动元素O(n)。 list不支持随机访问，需要遍历链表来查询O(n), 但是插入和删除效率就很高。
3. vector空间扩大，stl中的源码可以看看，增大的方式是首先找到一个两倍大的内存空间，然后将原有的元素通过复制的方式初始化新的空间，然后析构释放原空间，这样会有个问题就是原有的迭代器都是指向原空间的，现在就失效了。

map的实现原理

map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。内部的实现采用了红黑树，红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。

unorder_map实现原理

unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。

两者的优缺点

map：
优点 有序性，红黑树使得很多操作在lgn的时间复杂度下就可以实现。
缺点 空间占用率高，虽然提高了效率但是每个节点都要保存父节点 孩子节点以及红黑的性质信息。

unorder_map：
优点：查找速度比map更快
缺点：建立hashmap比较花时间，内存会比map高一些

若考虑有序，查询速度稳定，容器元素量少于1000,非频繁查询那么考虑使用map。
若非常高频查询(100个元素以上，unordered_map都会比map快)，内部元素可非有序，数据大超过1k甚至几十万上百万时候就要考虑使用unordered_map(元素上千万上亿时4GB的内存就要担心内存不足了,需要数据库存储过程挪动到磁盘中)。
hash_map相比unordered_map就是千万级别以上内存占用少15MB,上亿时候内存占用少300MB，百万以下都是unordered_map占用内存少，
且unordered_map插入删除相比hash_map都快一倍，查找效率相比hash_map差不多，或者只快了一点约1/50到1/100。
综合非有序或者要求稳定用map，都应该使用unordered_map,set类型也是类似的。
unordered_map 查找效率快五倍，插入更快，节省一定内存。如果没有必要排序的话，尽量使用 hash_map(unordered_map 就是 boost 里面的 hash_map 实现)。