浅谈STL中各种容器

目录

浅谈STL中各种容器

1、STL六大部件

2、容器分类

3、各种容器介绍

vector

deque

list

set/map

unordered_map/unordered_set

1、STL六大部件

容器、分配器、算法、迭代器、适配器、仿函数

2、容器分类

• Sequence Containers
• Associative Containers：set/map 红黑树，用于查找速度快
• Unordered Containers：哈希表

3、各种容器介绍

vector

     底层就是一段连续的数组，成长空间以两倍增长，当内存不够时，会另外找一片空间，进行搬移，即先拷贝数据，再释放原先空间，但并没有销毁原先内存空间，只是清除了原先内存中的数据。会有空间浪费，支持随机访问。由于本身就是一段连续空间，所以iterator就是一个单纯的指针而已。

deque

    分段有序，每次扩充是以一个buffer进行扩充。 

对于deque中的iterator，由于deque实质上并不是连续的空间，所以不能仅仅只是一个指针，而是一个class类，在class中，有四个指针，cur(buffer中的当前位置)、first(buffer的头)、last(buffer的尾)、node(buffer在map中的位置)，至于关于iterator的++等操作，就是进行操作符的函数重载而已，使整个过程看似是一个连续的过程。

insert时，需要比较和前端近还是和后端比较近，则是搬移前端还是搬移后端。 

list

    G4.9：本身是一个指针，每个节点有两个指针（指向自己的指针）。双向环状，最后一个加一个空白节点，为了符合STL的前闭后开原则。

 关于链表的节点，最好的结构就是嵌入式指针结构，用数据域前多少个字节充当指针用于串联起整个链表。同样地，iterator也不只是单纯的指针，而是一个class类，里面也有大量的运算符重载。

不支持随机访问。

 set/map

     底层均以红黑树实现，具有排序功能，对于set，key就是value，直接以value进行排序，而map，既有key，也有value，对于key是不能修改的，所以设置成const，排序也是根据key进行排序的。

     特点：1）插入速度较快，因为没有数据拷贝和移动，2）当insert数据后，之前保存的iterator不会失效，因为插入操作只是节点换来换去，节点内存没有改变，而iterator就像指向内存的指针，内存没变，指向内存的指针自然不会变。3）map/set的查找速度也较快，是基于二分查找的。

unordered_map/unordered_set

    底层是哈希表结构，查找基本上是常数级别。