C++碎碎念STL（vector、deque、list、map、set）

vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放掉之前的内存，然后再插入新增的元素。插入新的数据分在最好插入push_back和通过迭代器在任何位置插入，通过迭代器与第一个元素的距离就可以知道插入的位置，即int index=iter-begin()，这个元素后面的所有元素都要向后移动一个位置，在空出来的位置上存入新增的元素。

2、删除元素

删除和新增差不多，也分两种，删除最后一个元素pop_back和通过迭代器删除任意一个元素erase(iter)。通过迭代器删除首先要找到删除元素的位置，即int index=iter-begin();这个位置后的每个元素都向前移动一个元素的位置。同时erase不释放内存只初始化默认值。
删除全部元素clear，只是循环遍历了erase，所以删除了全部元素的时候不释放内存。内存是在析构的时候释放的。

四、vector和list容器的比较

1、vector：一维数组

（1）特点：元素在内存连续存放，动态数组，在堆中分配内存，元素连续存放，有保留内存，如果减少大小后内存也不会释放；
（2）优点：和数组类似开辟一段连续的空间，并且支持随机访问，所以他的查找效率高其时间复杂度O(1)
（3）缺点：由于开辟一段连续的空间，所以插入和删除需要对数据进行移动，因此时间复杂度为O(N)，另外当空间不足时还需要扩容。
扩容方式：
a、开辟三倍的内存；
b、旧的数据开辟到新的内存；
c、释放旧的内存；
d、指向新的内存。

2、list:双向链表

（1）特点：元素在堆中存放，每个元素都是存放在一块内存中，他的内存空间可以不是连续的，通过指针来进行数据的访问；
（2）优点：底层实现是循环双链表，当对大量数据进行插入或删除时，其时间复杂度为O(1)；
（3）缺点：底层没有连续的空间，只能通过指针来访问，所以查找数据需要遍历其时间复杂度O(N)。

3、应用场景

vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随机访问，而不在乎插入和删除的效率，使用vector。
list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。

五、vector和list在删除末尾元素后其指针和迭代器如何变化，若删除的是中间元素呢？

1、迭代器和指针的区别

迭代器不是指针，是类模板，表现得像指针，他只是模拟了指针的一些功能，重载了指针的一些操作，--> 、++、 --等。迭代器封装了指针，是一个可遍历的STL容器内全部或部分元素的对象，本质是封装了原生指针，是指针概念的一种提升，提供；饿比指针更高级的行为，相当于一种智能指针，他可以根据不同的数据结构来实现不同的++、--等操作。
迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。

2、vector增删元素

删除某个元素以后，该元素后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。

3、list增删元素

删除某个元素，只有“指向被删除元素”的那个迭代器失效，其他迭代器不受影响。

六、STL中的map实现原理

map是关联式容器，他们的底层容器都是红黑树。map的所有元素都是pair，同时拥有键值（key）和实值（value）。pair的第一元素被视为键值，第二元素视为实值。所有元素都会根据元素的键值自动被排序。不允许键值重复。

1、map的特性如下：

1、map是以红黑树为底层容器；

2、所有元素都是（键+值）存在；

3、不允许键值重复；

4、所有元素都是通过键进行自动排序；

5、map的键是不能修改的，但是其键对应的值是可以修改的。

2、set的特性如下：

1、set是以红黑树为底层容器；

2、所得元素只有key没有value，value就是key；

3、不允许出现键值重复；

4、所有元素都会自动排序；

5、不能通过迭代器来改变set的值，因为set的值就是键，set的迭代器是const.