STL--V7.30

标准模板库：Algorithm（算法）、Container（容器）和Iterator（迭代器），容器和算法通过迭代器可以进行无缝地连接。

1. 顺序容器 ：
容器并非排序的，元素的插入位置同元素的值无关。包含vector、deque、list，具体实现原理如下：
（1）vector 头文件   动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
（2）deque 头文件  双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（仅次于vector）。在两端增删元素具有较佳的性能（大部分情况下是常数时间）。
（3）list 头文件   双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。
2. 关联式容器
元素是排序的；插入任何元素，都按相应的排序规则来确定其位置；在查找时具有非常好的性能；通常以平衡二叉树的方式实现。包含set、multiset、map、multimap，具体实现原理如下：
（1）set/multiset 头文件  set 即集合。set中不允许相同元素，multiset中允许存在相同元素。
（2）map/multimap 头文件   map与set的不同在于map中存放的元素有且仅有两个成员变，一个名为first,另一个名为second, map根据first值对元素从小到大排序，并可快速地根据first来检索元素。
3. 容器适配器
封装了一些基本的容器，使之具备了新的函数功能，比如把deque封装一下变为一个具有stack功能的数据结构。这新得到的数据结构就叫适配器。包含stack,queue,priority_queue，具体实现原理如下：
（1）stack 头文件  栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最进插入序列的项（栈顶的项）。后进先出。
（2）queue 头文件  队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。
（3）priority_queue 头文件  优先级队列。内部维持某种有序，然后确保优先级最高的元素总是位于头部。最高优先级元素总是第一个出列。

复杂度：

1. vector采用一维数组实现，元素在内存连续存放，不同操作的时间复杂度为：插入: O(N)、查看: O(1)、删除: O(N)
2. deque采用双向队列实现，元素在内存连续存放，不同操作的时间复杂度为：插入: O(N)、查看: O(1)、删除: O(N)
3. list采用双向链表实现，元素存放在堆中，不同操作的时间复杂度为：插入: O(1)、查看: O(N)、删除: O(1)
4. map、set、multimap、multiset上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:插入: O(logN)、查看: O(logN)、删除: O(logN)
5. unordered_map、unordered_set、unordered_multimap、 unordered_multiset上述四种容器采用哈希表实现，不同操作的时间复杂度为：插入: O(1)，最坏情况O(N)；查看: O(1)，最坏情况O(N) ；删除: O(1)，最坏情况O(N)

------------------map和unordered_map的区别在于他们的实现基理不同？？
1. map实现机理： map内部实现了一个红黑树（红黑树是非严格平衡的二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树有自动排序的功能，因此map内部所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉树（又名二叉查找树、二叉排序树）存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值。使用中序遍历可将键值按照从小到大遍历出来。
2. unordered_map实现机理：unordered_map内部实现了一个哈希表（也叫散列表），通过把关键码值映射到Hash表中一个位置来访问记录，查找时间复杂度可达O（1），其中在海量数据处理中有着广泛应用。因此，元素的排列顺序是无序的。
-----------------vector对象的增长？？？

vector将元素连续存储，创建时会生成更大的内存空间。其中size()是指实际元素的大小，capacity()是指容器创建的总容量。当增长到capacity时，需要对容器进行扩容，重新扩容时会分配原容量的2~3倍容量，根据具体的底层规则实现。

扩容后，将原数据拷贝到新的地址，指针指向新的数据地址，释放原地址内存。

迭代器：

-------------------迭代器用过吗？什么时候会失效？ ？？

向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针、引用、迭代器失效。

在向容器添加元素后:

• 如果容器是vector 或string,且存储空间被重新分配，则指向容器的选代器指针和引用都会失效。如果存储空间未重新分配,指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的选代器、指针和引用将会失效。
• 对于 deque, 插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，选代器会失效，但指向存在的元素的引用和指针不会失效。
• 对于list和 forward_ list,指向容器的迭代器(包括尾后迭代器和首前迭代器)、指针和引用仍有效。

当我们从一个容器中删除元素后, 指向被删除元素的迭代器、 指针和引用会失效，不会令人惊讶。毕竞, 这些元素都已经被销毁了。当我们删除一个元素后:

• ·对于list和 forward_ list, 指向容器其他位置的迭代器(包括尾后迭代器禾首前选代器)、引用和指针仍有效。
• ·对于 deque,如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的选代器、 引用或指针也会失效。如果是删除deque的尾元素， 则尾后选代器也会失效，但其他迭代器、引用和指针不受影响:如果是删除首元素，这些也不会受影响。
• ·对于vector和 string, 指向被删元素之前元素的迭代器、引用和指针仍有效。注意:当我们删除元素时，尾后迭代器总是会失效。

2. 对于关联容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。

 ---------------------------说一下STL中迭代器的作用，有指针为何还要迭代器？？？？

1. 迭代器的作用
（1）用于指向顺序容器和关联容器中的元素
（2）通过迭代器可以读取它指向的元素
（3）通过非const迭代器还可以修改其指向的元素
2. 迭代器和指针的区别
 迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，重载了指针的一些操作符，-->、++、--等。迭代器封装了指针，是一个”可遍历STL（ Standard Template Library）容器内全部或部分元素”的对象，本质是封装了原生指针，是指针概念的一种提升，提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，--等操作。 迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。
3. 迭代器产生的原因： Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。