STL、容器相关理论基础

1.STL是什么？有哪些版本？

STL全称 Standard template library ,译为标准模板库或者叫泛型库，其中包含了大量的模板类和模板函数，用户完成输入/输出、数学计算等功能。

STL 是一些 容器、算法和其他一些组件的集合。

HP STL（惠普实验室）1998年被定义为国际标准，为 STL标准模板库之父，是C++STL第一个实现版本，其他版本一般以HP STL为蓝本实现，开源的。SGI STL ，HP STL的继承版，开源，其源码可读性好，“民间版”并不是所有支持C++的编译器都支持该模板库，它在Linux平台上的性能很出色。STLport，为了使 SGI STL基本代码适用于VC++、C++ Builder等多种编译器，俄国人开发了STLport，开源。PJ STL ，可被Visual C++编译器采用，不开源。

2.什么是容器？容器的优势？

在数据存储上，有一种对象类型，它可以持有其它对象或指向其它对象的指针，这种对象类型就叫做容器。

容器 可以保存“其它对象”以及一系列处理“其它对象”的方法——容器类是一种对特定代码重用问题的良好的解决方案；容器 可以自行扩展，不像数组，容器可以不需要预先知道存储对象的个数，只需要创建对象并合理调用所提供的方法即可。它会自动申请内存或释放内存。

3.容器的分类

STL 对定义的通用容器分三类：顺序性容器、关联式容器、容器适配器。

顺序性容器：各元素之间由顺序关系的线性表，是一种线性结构的可序群集。

每个元素均有固定的位置，除非通过删除、插入等操作改变。

相对位置与逻辑次序一致。【元素插入容器时，指定在什么位置，元素就在什么位置，不会自动根据元素大小排序】

例如：

Array【数组容器：C++本身提供的一种容器，一旦确定，该容器长度固定不变，意味着不能增加或者删除元素，只能改变某个元素的值】Vector  【向量容器：长度可变的序列容器，存储空间不足时，会自动申请更多的内存。在尾部增加或者删除元素的效率最高，在其它位置插入或删除元素的效率较差，时间复杂度为O(n)】Deque  【双端队列容器：和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 】List        【“双”链表容器：是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。】Forward_List【正向链表容器：和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器】

关联式容器：非线性结构，各元素之间没有严格的物理上的顺序关系。关联式容器一个显著的特点是它是以键值的方式来保存数据，就是说它能把关键字和值关联起来保存，而顺序性容器只能保存一种（可以认为它只保存关键字，也可以认为它只保存值）。

底层实现为红黑树。按照链表方式存储，所以插入元素比vector快，但是查找和在末尾添加慢。

 容器适配器：C++的解释是：适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器是让一种已存在的容器类型采用另一种不同的抽象类型的工作方式来实现的一种机制。

【PS：容器适配器中的“适配器”，和生活中常见的电源适配器中“适配器”的含义非常接近。我们知道，无论是电脑、手机还是其它电器，充电时都无法直接使用 220V 的交流电，为了方便用户使用，各个电器厂商都会提供一个适用于自己产品的电源线，它可以将 220V 的交流电转换成适合电器使用的低压直流电。从用户的角度看，电源线扮演的角色就是将原本不适用的交流电变得适用，因此其又被称为电源适配器。】

 4.unordered_set、unordered_map等是什么类型容器？有什么特点？

无序关联容器，该容器是C++11标准才正式引入到STL标准库中。

底层实现原理是哈希表。

无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键，和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。

 【PS：有读者可能会问，既然无序容器和之前所学的关联式容器类似，那么在实际使用中应该选哪种容器呢？总的来说，实际场景中如果涉及大量遍历容器的操作，建议首选关联式容器；反之，如果更多的操作是通过键获取对应的值，则应首选无序容器】

参考连接：C++ STL无序容器（哈希容器）是什么？ (biancheng.net)

C++容器详解_一小闷棍666的博客-CSDN博客_c++容器