C++STL

STL

1.说说 STL 的基本组成部分

STL由6部分组成：容器(Container)、算法（Algorithm）、 迭代器（Iterator）、仿函数（Function object）、适配器（Adaptor）、空间配制器（Allocator）。

1. 容器(Container)
   是一种数据结构， 如list，vector，和deques，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器。

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

3. 迭代器（Iterator）
   提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++ 的指针也是一种迭代器。 但是，迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符方法的类对象。

4. 仿函数（Function object）
   仿函数又称之为函数对象，其实就是重载了操作符的struct，没有什么特别的地方。

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

6. 空间配制器（Allocator）
   为STL提供空间配置的系统。其中主要工作包括两部分：
   （1）对象的创建与销毁。
   （2）内存的获取与释放。

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

容器可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是模板类，分为顺序容器、关联式容器、容器适配器三种类型，三种类型容器特性分别如下：

顺序容器

​ 容器并非排序的，元素的插入位置同元素的值无关。包含vector、deque、list，具体实现原理如下：

（1）vector 头文件

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

（2）deque 头文件

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

（3）list 头文件

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

关联式容器

​元素是排序的；插入任何元素，都按相应的排序规则来确定其位置；在查找时具有非常好的性能；通常以平衡二叉树的方式实现。包含set、multiset、map、multimap，具体实现原理如下：

（1）set/multiset 头文件

​ set 即集合。set中不允许相同元素，multiset中允许存在相同元素。

（2）map/multimap 头文件

​ map与set的不同在于map中存放的元素有且仅有两个成员变，一个名为first,另一个名为second, map根据first值对元素从小到大排序，并可快速地根据first来检索元素。

​ 注意：map同multimap的不同在于是否允许相同first值的元素。

容器适配器

​封装了一些基本的容器，使之具备了新的函数功能，比如把deque封装一下变为一个具有stack功能的数据结构。这新得到的数据结构就叫适配器。包含stack，queue，priority_queue，具体实现原理如下：

（1）stack 头文件

​ 栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最进插入序列的项（栈顶的项）。后进先出。

（2）queue 头文件

​ 队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。

（3）priority_queue 头文件

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