c++之stl底层数据结构 c++stl库详解教程

1.vector基于数组

a.新增元素:vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，再插入新增的元素。

b.对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。

c.初始时刻vector的capacity为0，塞入第一个元素后capacity增加为1

d.不同的编译器实现的扩容方式不一样，vs2015中以1.5倍扩容，gcc以2倍扩容

2.list基于双向链表

3.map,multimap基于红黑树

4.unordered_map,unordered_multimap基于哈希表

根据应用场景进行选择:

map/unordered_map 不允许重复元素

multimap/unordered_multimap 允许重复元素

map/multimap底层基于红黑树，元素自动有序，且插入，删除效率高

unordered_map/unordered_multimap底层基于哈希表，故元素无序，查找效率高