大家好，今天来为大家解答C++标准模板库（STL）、基本组成及底层实现原理揭秘（一）这个问题的一些问题点，包括也一样很多人还不知道，因此呢，今天就来为大家分析分析，现在让我们一起来看看吧！如果解决了您的问题，还望您关注下本站哦，谢谢~

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

STL六大组件：容器（Container）、算法（Algorithm）、迭代器（Iterator）、函子（Function object）、适配器（Adaptor）、空间分配器（Allocator）

阐明

容器（Container）是一种数据结构。要访问容器中的数据，可以使用容器类输出的迭代器。

算法是一个模板函数，用来操作容器中的数据。

示例：STL 使用sort() 对向量中的数据进行排序，并使用find() 在列表中搜索对象。这些函数本身与它们所操作的数据的结构和类型无关，因此它们可用于从简单数组中提取数据。高度复杂容器的任何数据结构。

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

Functor（函数对象） Functor也称为函数对象。它实际上是一个带有重载运算符的结构。

Adapter是一个接口类，专门用于修改现有类的接口以提供新的接口；或者调用已有的函数来实现所需的功能。主要包括三个适配器：Container Adapter、Iterator Adapter、Function Adapter。

空间分配器（Allocator）为STL提供了空间配置的系统。主要工作分为：

(1)对象的创建和销毁。

(2)内存的获取和释放。

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

容器可用于存储各种类型数据（基本类型的变量、对象等）的数据结构，它们是模板类、顺序容器、关联容器和容器适配器。

顺序容器（一）向量头文件向量

动态数组。元素连续存储在内存中。对任意元素的随机访问可以在常数时间内完成。在末尾添加和删除元素具有更好的性能。

(2)deque头文件deque

双向队列。元素连续存储在内存中。对任意元素的随机访问可以在常数时间内完成（仅次于向量）。在两端添加和删除元素具有更好的性能（大多数情况下时间恒定）

(3)列出头文件列表

双向链表。元素不是连续存储在内存中的。任意位置添加或删除元素都可以在常数时间内完成。不支持随机访问。

关联容器元素已排序；任何插入的元素都会按照相应的排序规则进行定位；在搜索时具有非常好的性能；它通常以平衡二叉树的形式实现。

(1)set/multiset头文件集合

set是集合的意思。 Set 不可以有相同的元素，multiset 允许有相同的元素。

(2)map/multimap头文件map

地图上只有两名成员，一名第一名和一名第二名。 Map根据first值从小到大对元素进行排序，并且可以根据first快速检索元素。 map 和multimap 的区别在于是否允许相同的第一个值。

容器适配器封装了一些基本的容器，为它们提供新的功能，比如将deque封装成a

栈函数的数据结构。这种新的数据结构称为容器适配器。容器适配器本质上就是容器

只是这个容器模板类的实现利用了大量已经在其他基本容器模板类中编写的成员函数。

(1)栈头文件栈

只能按堆栈顺序删除、检索或修改堆栈顶部的项目。先入后出。

(2)队列头文件队列

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

(3)priority_queue头文件队列

优先队列。维护一些内部顺序以确保最高优先级元素始终位于头部。具有最高优先级的总是第一个从队列中出来的。

STL 中 map hashtable deque list 的实现原理

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

hashtable（直译为散列表）的实现原理hashtable利用函数映射的思想，将记录的存储位置与记录的关键字关联起来，这样就可以非常快速地进行查找。这就决定了哈希表特殊的数据结构，它与数组、链表、二叉排序树有明显的不同。它可以快速定位你想要查找的记录，而不是与表中已存在的记录进行比较。关键词与搜索进行比较。

Deque实现原理deque内部实现了一个双向队列。元素连续存储在内存中。对任意元素的随机访问都是在常数时间内完成的（仅次于向量）。适用于向量的所有操作都适用于双端队列。在两端添加和删除元素具有更好的性能（大多数情况下是恒定时间）。

List实现原理List在内部实现为双向链表。元素不是连续存储在内存中的。任意位置添加或删除元素都可以在常数时间内完成。不支持随机访问。没有成员函数。给定一个下标i，要访问第i个元素的内容，只能从头部逐个遍历到第i个元素。

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

一般情况下，程序包括数据结构和相应的算法，数据结构作为存储数据的组织形式，与内存空间密切相关。在C++ STL中，空间分配器是用来分配内存空间（通常是内存，也可以是硬盘等）的工具。它与容器密切相关。每个容器的空间分配是通过空间分配器进行的。由分配器实现。

阐明

两种实例化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实现；第二级配置器主要考虑大内存空间，使用malloc和free实现；第二级配置器主要是考虑小内存空间的情况（为了最大化解决内存碎片问题，提高效率），使用链表free_list来维护内存池。 free_list是通过union结构实现的。空闲内存块相互链接。一旦内存块被使用，它就会从内存池中删除。消除了链表，易于维护。