【STL详解】STL标准模板库入门 | STL版本 | STL六大组件 | STL优点 | 常用STL容器vector、list和map | STL算法函数

我们在C++代码中常用的容器有vector、list、map等，它们基于模板实现的方式，方便我们存放各种类型的数据。有了这些容器，一般不再需要我们自己去实现一些数据结构了，这些容器基本能满足日常开发的需要，给我们带来了很大的便利，有效提高了编码的效率。除了容器之外，STL还提供了操作这些容器的算法函数，使用这些高效的算法函数，比直接遍历容器的效率要高很多，对于这一点，可以查看我之前根据项目中的使用实例与实际体验撰写的文章：

VC++调用STL算法函数有效提升STL列表的搜索速度（附源码）https://blog.csdn.net/chenlycly/article/details/123943134

有的人可能会认为STL只包含容器相关的内容，其实大家平常使用的字符串类string、输入输出iostream、unique_ptr等智能指针，都是STL标准模板库中的。STL模板库不仅仅包含容器和迭代器。

此外，说到STL，必须要说C++标准库；说到C++标准库，就要说到C++“准”标准库Boost库。所以这里简单地介绍一下C++标准库和Boost库。

1.1、C++ 标准库

C++标准库（C++ Standard Library）提供了丰富的类库及库函数资源，这些内容总共在50个标准头文件中定义，包括语言支持、输入输出、通用工具、字符串操作、容器、迭代器、算法函数、数值操作等。

C++标准库主要由C库、C++库和STL标准模板库构成，其中STL标准模板库在C++标准库中比重占了80%左右。在C++软件开发中，尽可能地利用C++标准库中的资源去完成。

1.2、Boost开源库

Boost开源库由C++标准委员会的部分成员所设立的Boost社区开发并维护，使用了许多现代C++编程技术，其内容涵盖字符串处理、正则表达式、容器与数据结构、并发编程、函数式编程、泛型编程、设计模式实现等许多领域，极大地丰富了C++的功能和表现力，能够使C++软件开发更加简捷、灵活和高效。

Boost库由C++标准委员会库工作组成员发起，即许多 Boost 库的作者本身就是 C++ 标准委员会成员，因此，Boost“天然”成了标准库的后备，负责向新标准输送组件，这也使得 Boost 获得了“准”标准库的美誉！

C++标准库从boost库中引入了大家熟知的正则表达式regex库，智能指针unique_ptr（对应boost库中的scoped_ptr）、shared_ptr和weak_ptr，函数适配bind库、函数对象容器function等。

2、STL 版本

自 1998 年 ANSI/ISO C++ 标准正式定案，C++ STL 规范版本正式通过以后，各个 C++ 编译器厂商在此标准的基础上，实现了满足自己需求的 C++ STL 泛型库版本，主要包括 HP STL、PJ STL、Rouge Wave STL、SGI STL等。即不同类型的IDE和编译器使用的STL版本可能是不同的，这些STL版本在实现细节上有着一定的差异。

2.1、HP 原始版本

HP STL 是 Alexandar Stepanov（STL 标准模板库之父）在惠普 Palo Alto 实验室工作时，与 Meng Lee 合作完成的。本着开源精神，他们声明允许任何人任意运用、拷贝、修改、传播、商业使用这些代码，无需付费。唯一要遵守的是，必修在文件中加上HP的版本声明和运用权限声明。

HP STL 是 C++ STL 的第一个实现版本，其它版本的 C++ STL 一般是以 HP STL 为蓝本实现出来的。不过，现在已经很少直接使用此版本的 STL 了。

2.2、P. J. 实现版本

由 P. J. Plauger 开发，继承自 HP 版本，该版本不开源，不能公开、修改或贩卖。该版本不开源也是合法的，因为HP没要求强迫要求其衍生产品必须开源。

该版本被微软 Visual C++ 采用，缺陷是，可读性比较低，符号命名也比较怪异。但我们在Visual Studio中阅读该版本的实现源码时，感觉还好，也没传说中那么难读。

其实 PJ STL 是 P.J.Plauger 公司的产品，尽管该公司当时只有 3 个人。

2.3、RW 实现版本

由 Rouge Wage 公司开发，继承自 HP 版本，被Borland公司的 C+ + Builder 采用。该版本也不是开源的，不能公开、修改或贩卖，这个版本的可读性还不错。

值得一提的是，尽管 Rouge Wave STL 的性能不是很好，但 C++ Builder 对 C++ 语言标准的支持还算不错，所以在一定程度上使 Rouge Wave STL 的表现得以改善。但遗憾的是，由于 Rouge Wave STL 长期没有更新且不完全符合标准，因此 Rouge Wave STL 在 6.0 版本时改用了 STLport 版本（之后的版本也都采用了 STLport），不过考虑到和之前版本的兼容，6.0 版本中依旧保留了 Rouge Wave STL。

Rouge Wave 公司在 C++ 程序库领域应该说是鼎鼎大名，对 C++ 标准化的过程出力甚多。不过 Rouge Wave STL 版本不仅更新频率慢，费用还高，基于这两个原因，Borland 在 6.0 版本决定弃用 Rouge Wave STL 而改用 STLport。

2.4、SGI 实现版本

由 Silicon Graphics Computer Systems，Inc 公司开发，继承自 HP 版本。该版本被 Linux GCC 采用，可移植性好，在 Linux 平台上的性能非常出色。该版本是开源的，可公开、修改甚至贩卖。

这个版本STL也是Alexander Stepanov主导开发的（HP版本就是他开发的），Alexander Stepanov 在离开 HP 之后，就加入到了 SGI 公司，并和 Matt Austern 等人开发了 SGI STL。

无论是符号命名，还是编程风格，这个版本的可读性非常高。如果大家要学习 STL源码，推荐大家看这个版本的源码实现。侯捷老师的经典书籍《STL源码剖析》，也是基于这个版本展开的。

2.5、STLport 实现版本

为了使 SGI STL 的基本代码都适用于 VC++ 和 C++ Builder 等多种编译器，俄国人 Boris Fomitchev 建立了一个 free 项目来开发 STLport，此版本 STL 是开放源码的。

由于 Rouge Wave STL 长期没有更新且不完全符合标准，因此 Rouge Wave STL 在 6.0 版本时改用了 STLport 版本，之后的版本也都采用了 STLport。

3、STL 的六大组件

STL标准模板库是C++标准库的重要组成部分，因此所有的C++编译器都支持STL，都选用各自的STL版本。STL 提供了六大组件，彼此组合套用协同工作。

3.1、STL 六大组件构成

这六大组件分别是：

容器（Containers）：各种数据结构，如 vector、list、deque、set、map 等。从实现的角度来看，容器是一种 class template。
算法（Algorithms）：各种常用算法，提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作，比如 sort、search、copy、erase。从实现的角度来看，STL 算法是一种 function template。
迭代器（Iterators）：迭代器用于遍历对象集合的元素，扮演容器与算法之间的胶合剂，是所谓的“泛型指针”，共有 5 种类型，以及其他衍生变化。从实现角度来看，迭代器是一种将 operator*、operator->、operator++、operator-- 等指针操作予以重载的 class template。所有的 STL 容器附带有自己专属的迭代器，因为只有容器设计者才知道如何遍历自己的元素。
仿函数（Functors）：也称为函数对象（Function object），行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了 operator() 的 class 或者 class template。
适配器（Adaptors）：一种用来修饰容器或者仿函数或迭代器接口的东西。例如 STL 提供的 queue 和 stack，就是一种空间配接器，因为它们的底部完全借助于 deque。
分配器（Allocators）：也称为空间配置器，负责空间的配置与管理。从实现的角度来看，配置器是一个实现了动态配置空间、空间管理、空间释放的 class template。

在这里，给大家重点推荐一下我的几个热门畅销专栏，欢迎订阅：（博客主页还有其他专栏，可以去查看）

专栏1：（该精品技术专栏的订阅量已达到530多个，专栏中包含大量项目实战分析案例，有很强的实战参考价值，广受好评！专栏文章持续更新中，预计更新到200篇以上！欢迎订阅！）

C++软件调试与异常排查从入门到精通系列文章汇总https://blog.csdn.net/chenlycly/article/details/125529931

本专栏根据多年C++软件异常排查的项目实践，系统地总结了引发C++软件异常的常见原因以及排查C++软件异常的常用思路与方法，详细讲述了C++软件的调试方法与手段，以图文并茂的方式给出具体的项目问题实战分析实例（很有实战参考价值），带领大家逐步掌握C++软件调试与异常排查的相关技术，适合基础进阶和想做技术提升的相关C++开发人员！

考察一个开发人员的水平，一是看其编码及设计能力，二是要看其软件调试能力！所以软件调试能力（排查软件异常的能力）很重要，必须重视起来！能解决一般人解决不了的问题，既能提升个人能力及价值，也能体现对团队及公司的贡献！

专栏中的文章都是通过项目实战总结出来的，包含大量项目问题实战分析案例，有很强的实战参考价值！专栏文章还在持续更新中，预计文章篇数能更新到200篇以上！

专栏2：（本专栏涵盖了C++多方面的内容，是当前重点打造的专栏，订阅量已达170多个，专栏文章已经更新到420多篇，持续更新中...）

C/C++实战进阶（专栏文章，持续更新中...）https://blog.csdn.net/chenlycly/category_11931267.html

以多年的开发实战为基础，总结并讲解一些的C/C++基础与项目实战进阶内容，以图文并茂的方式对相关知识点进行详细地展开与阐述！专栏涉及了C/C++领域多个方面的内容，包括C++基础及编程要点（模版泛型编程、STL容器及算法函数的使用等）、数据结构与算法、C++11及以上新特性（不仅看开源代码会用到，日常编码中也会用到部分新特性，面试时也会涉及到）、常用C++开源库的介绍与使用、代码分享（调用系统API、使用开源库）、常用编程技术（动态库、多线程、多进程、数据库及网络编程等）、软件UI编程（Win32/duilib/QT/MFC）、C++软件调试技术（排查软件异常的手段与方法、分析C++软件异常的基础知识、常用软件分析工具使用、实战问题分析案例等）、设计模式、网络基础知识与网络问题分析进阶内容等。

专栏3：

C++常用软件分析工具从入门到精通案例集锦汇总（专栏文章，持续更新中...）https://blog.csdn.net/chenlycly/article/details/131405795

常用的C++软件辅助分析工具有SPY++、PE工具、Dependency Walker、GDIView、Process Explorer、Process Monitor、API Monitor、Clumsy、Windbg、IDA Pro等，本专栏详细介绍如何使用这些工具去巧妙地分析和解决日常工作中遇到的问题，很有实战参考价值！

专栏4：

VC++常用功能开发汇总（专栏文章，持续更新中...）https://blog.csdn.net/chenlycly/article/details/124272585

将10多年C++开发实践中常用的功能，以高质量的代码展现出来。这些常用的高质量规范代码，可以直接拿到项目中使用，能有效地解决软件开发过程中遇到的问题。

专栏5：

C++ 软件开发从入门到精通（专栏文章，持续更新中...）https://blog.csdn.net/chenlycly/category_12695902.html

根据多年C++软件开发实践，详细地总结了C/C++软件开发相关技术实现细节，分享了大量的实战案例，很有实战参考价值。

3.2、六大组件的交互关系

六大组件的交互关系如下：

3.2.1、容器

一个容器就是一些特定类型对象的集合。STL 中容器分为两大类，序列式容器和关联式容器。

序列式容器（sequential container）为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

除了序列式容器外，标准库还定义了三个序列式容器适配器：stack、queue 和 priority_queue。适配器是标准库中的一个通用概念，容器、迭代器和函数都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。

和序列式容器对应的是关联式容器（associative-container），关联容器中的元素是按关键字来保存和访问的。关联容器支持高效的关键字查找和访问，STL 有两个主要的关联容器：map 和 set。

3.2.2、容器迭代器

迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。迭代器就如同一个指针。事实上，C++ 的指针也是一种迭代器。但是，迭代器不仅仅是指针，因此你不能认为他们一定具有地址值。例如，一个数组索引，也可以认为是一种迭代器。

迭代器有各种不同的创建方法。程序可能把迭代器作为一个变量创建。一个 STL 容器类可能为了使用一个特定类型的数据而创建一个迭代器。作为指针，必须能够使用 * 操作符类获取数据。还可以使用其他数学操作符如 ++ 操作符用来递增迭代器，以访问容器中的下一个对象。

如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成 past-the-end 值。使用一个 past-the-end 值得指针来访问对象是非法的，就好像使用 NULL 或为初始化的指针一样。

3.2.3、算法

STL 通过函数模板提供了很多作用于容器的通用算法，例如查找、插入、删除、排序等，这些算法均需要引入头文件 <algorithm>。

所有的 STL 算法都作用在由迭代器 [first, last) 所标示出来的区间上，可以分为两大类：

质变算法（mutating algorithms）：运算过程中会更改区间内迭代器所指的元素内容，如分割（partition）、删除（remove）等算法。
非质变算法（nonmutating algorithms）：运算过程中不会更改区间内迭代器所指的元素内容，如匹配（search），计数（count）等算法。

所有泛型算法的前两个参数都是一对迭代器，通常称为 first 和 last，用以标示算法的操作区间。注意，将无效的迭代器传给某个算法，虽然是一种错误，但不保证能够在编译期间被捕捉出来。

4、STL 优点

使用C++ STL（标准模板库，Standard Template Library）有多个显著的好处，这些优势使得STL成为C++编程中极为重要和常用的组成部分，在C++项目中得到了广泛的使用。以下是使用C++ STL的一些主要好处：

1）高效性
STL组件如容器、算法和迭代器都是经过精心设计的，很多实现都针对性能进行了优化。甚至在某些情况下通过编译器特定的优化还能表现得更好。
2）代码复用
STL提供了一套通用的、可重用的数据结构和算法，程序员不在需要自己设计链表等数据结构和算法逻辑，这减少了程序员重复造轮子的成本。
3）泛型编程
STL广泛采用了模板技术，支持泛型编程。这意味着你可以编写不依赖于特定类型的代码，提高了代码的灵活性和可重用性。比如，一个排序算法可以应用于多种数据类型，而无需为每种类型单独编写实现。
4）易读性和维护性
使用STL可以让代码更加简洁、清晰，易于理解和维护。标准的库函数和容器命名规范良好，减少了代码中的“魔法数字”和复杂的控制结构，使得其他开发者更容易理解代码意图。
5）标准化
STL是C++标准库的一部分，这意味着无论在哪种符合标准的C++编译器上，STL的行为都是一致的。这保证了代码的可移植性，降低了因平台差异引起的问题。
6）高稳定性
由于STL组件经过了广泛的测试和使用，它们的稳定性相对较高，能够减少由自定义实现引入的潜在错误。使用成熟且经过验证的库函数，可以提高软件的整体质量。
7）提升开发效率
借助STL，开发者可以更快地实现功能，因为不需要花费时间在基本的数据结构和算法实现上。这使得开发者可以将更多精力放在解决特定问题的逻辑上，加速开发进程。

综上所述，C++ STL通过提供高效、灵活且标准化的工具集，极大地提升了开发效率、代码质量和可维护性，是现代C++编程不可或缺的一部分。

5、STL 常用容器vector、list和map介绍

STL实现了很多常用的数据结构以及操作这些数据结构的算法函数，我们基本不需要自己再去重复造轮子，不用再去设计复杂的链表等数据结构，直接使用STL的容器就能满足我们的大部分需求，给日常开发带来了很大的便利，有效地提升了开发效率。

STL提供的容器有vector、list、map、set、deque、multimap和multiset等，其中vector、list和map在日常C++编码中使用的最多，所以此处我们详细介绍一下这三个容器。

5.1、vector

vector类似于数组，是在一段连续的内存上存放数据的，其数据存放及操作方式（使用数组下标访问容器中的元素）。与数组相比，两者的差别在于内存空间运用的灵活性上。数组是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，需要编码者自行处理，即首先配置一块新的内存空间，然后将旧空间的数据拷贝到新的内存空间中，然后再释放原来的内存空间。

vector使用的内存区域虽然是连续的，但其使用的内存是动态，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此，vector的使用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必担心空间不足而一开始就申请一大块的数组了，有新元素要加入到vector中时直接push进去就好了，vector内部会自动维护存放元素的内存。

vector的实现技术，关键在于其对占用内存空间大小的控制以及重新配置时的数据移动效率。一旦vector旧空间满了，如果每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为扩充空间时都会执行”配置新空间-数据移动-释放旧空间”操作，时间成本很高，要加入某种未雨绸缪的考虑，当内存不够时申请更大的一块连续内存区域，比如新的内存空间比之前的空间大一倍。

正是这种在内存不够用时触发的”配置新空间-数据移动-释放旧空间”操作，对容器的存储效率有较大的影响，特别是在存放大量的数据时影响更明显。再就是当容器中有元素删除时，会自动将删除元素后面的所有元素向前拷贝移动，这也会对效率产生不利的影响。还有一点需要注意，当从vector中删除元素后，vector不会自动释放删除元素占用的内存空间。即使对vector执行clear操作删除容器中所有元素时，不会释放vector占用的内存空间。

5.2、list

list内部是用链表实现的，存放的每个元素都是存放在链表节点上，所以存放元素的内存是不连续的。

链表是一种存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。

vector占用的内存是连续的，能够像数组那样使用下标去访问，效率相对高一些。但在存放大量数据时，无论是内存不够用时的重新申请内存操作，还是删除元素时右侧所有元素向前移动的操作，效率上都不如list。

5.3、map

map中存放的是key-value对（pair）数据，其中first字段（key）对应键值，second字段（value）对应的是实值。我们要保证插入元素的key是唯一的，不能重复，map中不允许两个元素有相同的key键值，后续也正是通过该唯一的key值到容器搜索元素的。如果在插入元素时，key值已经存在，则当前的元素会将已经存在的这个元素覆盖掉。

map在存放元素时会自动根据key值对元素自动进行hash排序，这样我们在使用key值到map中搜索元素时效率较高。

vector和list的使用比较简单，map的使用稍微有点讲究，此处给出一个使用map列表的实例。定义一个存放设备列表数据的map容器mapDevList，其中key字段为设备id，value字段为设备信息结构体TDeviceInfo，如下所示：

// 设备信息
struct TDeviceInfo 
{
    char achDeviceId[64];   // 设备id
    char achDeviceName[64]; // 设备名称
    int nDevType;            // 设备类型
};
 
map<char*，TDeviceInfo> mapDevList; // 存放设备信息的列表

向mapDevList中插入一个设备信息，如下：

char* lpszId；
TDeviceInfo tDevInfo;

// ... // 省略对上述变量lpszId和tDevInfo的赋值代码

mapDevList.insert( std::make_pair( lpszId, tDevInfo ) );

通过一个key值（lpszId），到mapDevList中搜索对应的元素：

map<char*, TDeviceInfo>::iterator it = mapDevList.find( lpszId );
if ( it != mapDevList.end() )
{
    // 通过lpszId找到对应的元素
}

6、使用 STL 算法函数，有效提升操作STL容器的效率（STL使用实战）

STL中提供了多个常用的算法函数，支持对STL容器执行一系列操作（算法函数均是基于模版实现，支持多个STL容器），包括对容器内容的初始化、排序、搜索和转换等操作，比如 sort、count、count_if、find、find_if、remove_copy、remove_copy_if。

STL提供的这些算法函数中算法，是经过了数学上的效能分析与证明的，其执行效率比我们直接写代码去遍历STL容器的效率要高很多（高出一定的数量级），特别是在处理大量的数据（容器中存放了大量的元素）时。这些STL算法函数的详细说明，可以参见《STL源码剖析》一书的第6章。

使用这些算法函数，可以有效的提高STL容器的搜索与遍历的效率，关于如何使用这些算法函数以及如何提升效率，可以查看我之前写的文章：
C++如何使用C++ STL标准模板库中的算法函数（附源码）https://blog.csdn.net/chenlycly/article/details/125486409 C++调用STL算法函数有效提升STL列表的搜索速度（附源码）https://blog.csdn.net/chenlycly/article/details/123943134

7、使用 STL 容器时发生异常的常见原因总结（STL使用实战）

我们在项目代码中会频繁地使用STL容器，在使用过程中可能会遇到一些问题。可能会因为编码不规范或者逻辑控制的有问题，导致访问STL容器出现异常，导致程序发生异常崩溃。

引发STL容器访问异常的原因有访问容器时越界、迭代器失效、多线程同时操作STL容器未加锁等，之前根据项目实战经历专门写了相关的总结文章，可以去查看文章：

C++程序使用 STL 容器发生异常的常见原因分析与总结https://blog.csdn.net/chenlycly/article/details/136991353

关于引发C++软件异常的常见原因与排查C++软件异常的常用手段和方法，之前做了详细且系统的总结，很有实战参考价值（总结来源于项目实战，服务于项目实战），可以查看对应的文章：

引发C++软件异常的常见原因分析与总结（实战经验分享）https://blog.csdn.net/chenlycly/article/details/124996473 排查C++软件异常的常见思路与方法（实战经验总结）https://blog.csdn.net/chenlycly/article/details/120629327

8、最后

本文详细介绍了STL版本、STL的六大组件、常用的STL容器vector、list和map、提升效率的STL算法函数、使用STL常见异常原因总结等内容。其中部分内容是基于项目实践总结出来的，有一定的实战参考价值。

标签：map,容器,STL,C++,算法,vector,版本
From： https://blog.csdn.net/chenlycly/article/details/142752672

【STL详解】STL标准模板库入门 | STL版本 | STL六大组件 | STL优点 | 常用STL容器vector、list和map | STL算法函数 | STL使用异常原因分析与总结

1、概述