STL 的基本组成部分

标准模板库（Standard Template Library）,本质上，就是一些数据结构和算法的模板的集合。

广义上，STL分为3类：Algorithm（算法）、Container（容器）和Iterator（迭代器），容器和算法通过迭代器可以进行无缝地连接。

STL六大组件：容器(Container)、算法（Algorithm）、 迭代器（Iterator）、仿函数（Function object）、适配器（Adaptor）、空间配制器（Allocator）

说明

• 容器（Container）

一种数据结构，访问容器中的数据，可以使用由容器类输出的迭代器。

• 算法（Algorithm）

是用来操作容器中的数据的模板函数。

例子：STL用sort()来对一 个vector中的数据进行排序，用find()来搜索一个list中的对象， 函数本身与他们操作的数据的结构和类型无关，因此他们可以用于从简单数组到高度复杂容器的任何数据结构上。

• 迭代器（Iterator）

提供了访问容器中对象的方法。

• 仿函数（Function object）

仿函数又称之为函数对象， 其实就是重载了操作符的struct。

• 适配器（Adaptor）

一种接口类，专门用来修改现有类的接口，提供一中新的接口；或调用现有的函数来实现所需要的功能。主要包括3中适配器Container Adaptor、Iterator Adaptor、Function Adaptor。

• 空间配制器（Allocator）

为STL提供空间配置的系统。其中主要工作分为：

（1）对象的创建与销毁。

（2）内存的获取与释放。

STL 中常见的容器，并介绍一下实现原理

容器可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是模板类，顺序容器，关联式容器，容器适配器。

• 顺序容器

（1）vector 头文件<vector>

动态数组。元素内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。

（2）deque 头文件<deque>

双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（仅次于vector）在两端增删元素具有较佳的性能（大部分情况下是常数时间）

（3）list 头文件<list>

双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

• 关联式容器

元素是排序的；插入任何元素，都按相应的排序规则来确定其位置；在查找时具有非常好的性能；通常以平衡二叉树的方式实现。

（1）set/multiset 头文件<set>

set 即集合。set没有相同元素，multiset允许有相同元素。

（2）map/multimap 头文件<map>

map中有且仅有两个成员，一个first，一个second，map根据first值对元素从小到大排序，可以快速根据first来检索元素。map与multimap的不同在于是否允许有相同的first值。

• 容器适配器

封装了一些基本的容器，使之具备了新的函数功能，比如把deque封装一下变为一个具有

stack功能的数据结构。这种新的到的数据结构称为容器适配器。容器适配器本质上还是容器

只不过此容器模板类的实现，利用了大量其它基础容器模板类中已经写好的成员函数。

（1）stack 头文件<stack>

栈中序列中被删除、检索、修改只能是栈顶项。先进后出。

（2）queue 头文件<queue>

队列。插入只可以在尾部进行，删除，检索，和修改操作只能从头部进行。

（3）priority_queue 头文件<queue>

优先队列。内部维持某种有序，确保优先级最高的元素总是位于头部。优先级最高的总是第一个出列。

STL 中 map hashtable deque list 的实现原理

• map实现原理

map内部实现一个红黑树（红黑树是非严格平衡的二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树有自动排序的功能，因此map内部所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉树（又名二叉查找树、二叉排序树）存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值。使用中序遍历可将键值按照从小到大遍历出来。

• hashtable（直译作哈希表）实现原理

hashtable采用了函数映射的思想记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。这决定了哈希表特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。

• deque实现原理

deque内部实现的是一个双向队列。元素在内存连续存放。随机存取任何元素都在常数时间完成（仅次于vector）。所有适用于vector的操作都适用于deque。在两端增删元素具有较佳的性能（大部分情况下是常数时间）。

• list实现原理

list内部实现的是一个双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。无成员函数，给定一个下标i，访问第i个元素的内容，只能从头部挨个遍历到第i个元素。

介绍一下 STL 的空间配置器（allocator）

一般情况下,一个程序包括数据结构和相应的算法，而数据结构作为存储数据的组织形式，与内存空间有着密切的联系。在C++ STL中，空间配置器便是用来实现内存空间(一般是内存，也可以是硬盘等空间)分配的工具，他与容器联系紧密，每一种容器的空间分配都是通过空间分配器alloctor实现的。

说明

• 两种C++类对象实例化方式的异同

一种是直接利用构造函数,直接构造类对象，如 Test test()；另一种是通过new来实例化一个类对象，如 Test *pTest = new Test；内存分配的三种方式：

（1）静态存储区分配：

内存在程序编译的时候已经分配好，这块内存在程序的整个运行空间内都存在。如全局变量,静态变量等。

（2）栈空间分配

程序在运行期间，函数内的局部变量通过栈空间来分配存储（函数调用栈），当函数执行完毕返回时，相对应的栈空间被立即回收。主要是局部变量。

（3）堆空间分配

程序在运行期间，通过在堆空间上为数据分配存储空间，通过malloc和new创建的对象都是从堆空间分配内存，这类空间需要程序员自己来管理，必须通过free()或者是delete()函数对堆空间进行释放，否则会造成内存溢出。

那么，从内存空间分配的角度来对这两种方式的区别，就比较容易区分:

（1）对于第一种方式来说，是直接通过调用Test类的构造函数来实例化Test类对象的,如果该实例化对象是一个局部变量，则其是在栈空间分配相应的存储空间。 （2）对于第二种方式来说,就显得比较复杂。这里主要以new类对象来说明一下。new一个类对象,其实是执行了两步操作：首先,调用new在堆空间分配内存,然后调用类的构造函数构造对象的内容；同样，使用delete释放时，也是经历了两个步骤：首先调用类的析构函数释放类对象，然后调用 delete释放堆空间。

• C++ STL空间配置器实现

很容易想象，为了实现空间配置器，完全可以利用new和delete函数并对其进行封装实现STL的空间配置器，的确可以这样。但是，为了最大化提升效率，SGI STL版本并没有简单的这样做，而是采取了一定的措施，实现了更加高效复杂的空间分配策略。由于以上的构造都分为两部分，所以，在SGI STL中，将对象的构造切分开来，分成空间配置和对象构造两部分。

内存配置操作: 通过alloc::allocate()实现 内存释放操作: 通过alloc::deallocate() 实现 对象构造操作: 通过::construct()实现 对象释放操作: 通过::destroy()实现

关于内存空间的配置与释放，SGI STL采用了两级配置器：一级配置器主要是考虑大块内存空间，利用malloc和free实现；二级配置器主要是考虑小块内存空间而设计的（为了最大化解决内存碎片问题，进而提升效率），采用链表free_list来维护内存池（memory pool）， free_list通过union结构实现，空闲的内存块互相挂接在一块，内存块一旦被使用，则被从链表中剔除，易于维护。

STL 常见容器用过哪些，查找的时间复杂度是多少，为什么？

STL常用的容器有vector、deque、list、map、set、multimap、multiset unordered_map、 unordered_set等。容器底层实现方式及时间复杂度分别如下：

• vector

采用一维数组实现，元素在内存连续存放，不同操作的时间复杂度为：

插入: O(N)

查看: O(1)

删除: O(N)

• deque

采用双向队列实现，元素在内存连续存放，不同操作的时间复杂度为：

插入: O(N)

查看: O(1)

删除: O(N)

• list

采用双向链表实现，元素存放在堆中，不同操作的时间复杂度为：

插入: O(1)

查看: O(N)

删除: O(1)

• map、set、multimap、multiset

上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:

插入: O(logN)

查看: O(logN)

删除: O(logN)

• unordered_map、unordered_set、unordered_multimap、 unordered_multiset

上述四种容器采用哈希表实现，不同操作的时间复杂度为： 插入: O(1)，最坏情况O(N)

查看: O(1)，最坏情况O(N)

删除: O(1)，最坏情况O(N)

注意：容器的时间复杂度取决于其底层实现方式。