本篇文章给大家谈谈C++｜浅谈STL的细节和内部原理，以及对应的知识点，文章可能有点长，但是希望大家可以阅读完，增长自己的知识，最重要的是希望对各位有所帮助，可以解决了您的问题，不要忘了收藏本站喔。

随后，在包括Bjarne Stroustrup 在内的所有人的帮助下，Stepanove 改进了STL。同时增加了一个封装内存模式信息的抽象模块，也就是现在STL中的分配器。它使得大多数STL的实现独立于特定的内存模式，从而独立于特定的平台。在同年夏天的滑铁卢会议上，委员会成员以80%的赞成票、20%的反对票，最终通过了提案，决定将STL正式纳入C++标准化进程。 STL随后被纳入会议工作文件。从此，STL终于成为C++家族的重要成员。

此后，随着C++标准的不断完善，STL也随之不断发展。直到1998年，ANSI/ISO C标准正式定稿，STL一直是C标准不可或缺的组成部分。

我们知道，程序的核心通常包括数据描述、定义和数据操作（函数）（一个完整的程序通常还包括输入、输出或UI部分），或者数据结构和算法（一些常见的函数模板（库）），对于封装数据成员和成员函数的类类型也是如此。

STL封装了一些常用的数据结构和算法。程序员不需要在STL中重新构建现有的数据结构和算法。毕竟库中实现的数据结构和算法都是顶级程序员完成的。具有最大程度的优化和安全测试。 STL力求尽可能实现这些数据结构和算法的通用性和通用化（面向对象强调数据和操作的封装，通用编译GP强调将一些通用算法（函数模板）与通用数据结构分离）。

实现数据结构（容器）通用性：通过类模板泛化数据类型；

STL是容器（数据结构部分、类模板（类型泛化）、可变长度（容器元素数量自增，通过分配器实现，并动态地将数据存储在堆内存上，让程序员避免复杂的内存管理操作））提供一致的外部接口（成员函数或方法）。这些接口包括少量的操作（如构造、添加、删除等与数据结构紧密结合的操作）和大量的附加操作（算法部分、函数模板（如排序、搜索、替换）等）由于操作接口的一致性，使得STL更容易使用。当然，也有特殊的数据结构和算法单独实现更高效的情况，例如链式存储的列表和forward_list内部配对查找。 () 和sort()，以及相关容器内部配对的find() 函数的实现。

容器是一堆常用数据结构的实现。它们主要被用户用来存储和读取数据。它们屏蔽了底层的内存分配和释放问题，因此用户可以更方便、更高效地使用它们。

实现算法（函数模板库）通用性：独立于具体容器类型（包括窗口元素的数据类型）和具体功能的定制，通过迭代器+函数对象实现；比如排序算法，可以是不同的Container也可以实现降序或者升序。前者是通过迭代器实现的，后者是通过函数对象实现的（有些函数是可以自定义的，并不是硬编码在算法内部，即可以通过传入函数对象来实现。当然，它们也可以实现为函数指针或lambda 表达式）。

一般形式为：

类型算法名称（迭代器开始，迭代器结束）；类型算法名称（迭代器开始，迭代器结束，proc op）；类型算法名称（迭代器开始，迭代器结束，UnaryPredicate op）；类型算法名称（迭代器开始，迭代器结束，const % value）；类型算法名称（迭代器开始，迭代器结束，）；模板类t1，类t2 类型算法名称（t1 第一个，t2 最后一个，）；在STL中，算法和容器是分开设计的，这与面向对象（OO）有些不一致。在面向对象中，我们一般将数据和方法封装在类中，而在STL中，与容器密切相关的操作被封装在类模板中，一些常用的操作则以函数模板的形式封装。算法库。

函数对象是一种编程对象，允许将其作为普通函数进行调用。与函数指针相比，函数对象有两个优点：第一，编译器可以内联执行对函数对象的调用（例如升序或降序排序，这是一行代码的区别）；其次，函数对象可以在内部维护状态。

迭代器如何让函数模板独立于容器？ Iterator首先是一个模板类，也是容器的内部类。因为是内部类，所以可以使用同一个名字：iterator，然后通过不同的容器类字段来区分，比如vectorint:iterator it；

另外，迭代器内部包含一个指向容器对象的指针，并实现了*、-、++、–、+n、-n等运算符的重载，根据重载的运算符区分不同的运算符。访问方式（读、写、顺序、随机访问），形成不同的迭代器。这样，STL的算法库通常可以使用一对指定容器元素范围作为参数的迭代器来访问容器元素：

我通过迭代器获取输入数据；

II 通过函数对象处理数据；

III 通过迭代器输出结果；

如果对容器、迭代器、函数对象的一些通用操作进行限制（或者重新定义或封装），就可以形成接口，这就是适配器的概念。

STL的上述六大组件（Containers、Allocator、Adapter、Algorithms算法库、Iterators、Functor函数对象）之间的关系可以表达如下：

下面是一个使用STL的六个主要组件的小例子：

六大组件中，除了算法库是函数模板外，其他都是类模板。

1 容器（container）和分配器（allocator）

向量int,分配器vi(ia,ia+6);

Vector是一种容器类型。

int 是容器中元素的类型，也可以有分配器参数或基本数据类型的参数（某些参数有默认值）。

Allocator是指定的分配器类型，也是一个模板。你需要告诉容器每次分配什么类型。这里指定了Int。容器构造函数提供了一个默认分配器。

模板类T，类Alloc=allocatorT类向量；模板类的构造函数具有重载，可以将数组的元素作为向量容器的元素。

(1) 空容器构造函数（默认构造函数）(2) 填充构造函数(3) 范围构造函数(4) 复制构造函数1.1 顺序容器

顺序容器通过元素在容器中的位置来存储和访问元素。

Deque是双向队列，可以前后扩展。我们知道，如果内存需要扩展，它是无法就地扩展的。例如，如果一个向量在尾部扩展，则需要找到另一个两倍大的空间并将其整体移动。而deque又是如何实现双向扩展的呢？如下图：

双端队列由一个控制中心和多个内存块缓冲区组成。控制中心是一个向量，它按顺序存储每个内存块的地址。这些地址连接起来形成整个双端队列空间。而呈现给用户的是类似于连续空间的表示。

map指向控制中心中的向量，其类型为T**，T是模板参数，表示deque中数据的类型，如int。 Map中存储的是指向内存块的指针，例如int*类型。那么map是一个指向向量的指针，而向量存储的是int*，所以map就是int**，也就是T**。

Map存储每个缓冲区的指针，一个缓冲区可以存储多个元素。当从末尾插入一个元素并且最后一个缓冲区空间不足时，稍后将申请另一个缓冲区，并将新缓冲区的头指针存储在映射的最后一个单元格中。从前面插入也是如此。

deque如何实现空间连续性的错觉？主要是通过运算符的重载来实现。当我们使用“++”或“–”等指针进行操作时，内部实现应该能够自动切换不同的内存块，形成连续内存地址的假象。

1.2 关联容器

关联容器通过键（例如映射）存储和读取元素的值。对于集合，它们的元素既是键又是值。

无序关联容器：

总结一下各个容器的特点：

2 算法（algorithm）、迭代器（iterator）、函数对象（function object, 也称为仿函数functor）

如上所述，大多数STL算法库（函数模板）通常可以使用一对指定容器范围作为参数的迭代器来访问容器的元素。

迭代器底层是一个对象指针，封装了一个容器，并重载了指针的一些操作符。根据读、写和重载操作符的不同，分为五种替代类型。算法选择哪个迭代器？算法和迭代器之间还有一个中间层，称为iterator_traits。五个替代者之间形成了一个层次结构：

输入迭代器（input iterator）：读，不能写，仅支持自增操作；

Output iterator（输出迭代器）：可写，不可读，仅支持自增操作；

Forward iterator（前向迭代器）：读写，仅支持自增操作；

双向迭代器：读写，支持自增和自减操作；

随机访问迭代器：可读写，支持完整的迭代器算术运算；

count_if() 函数模板原型：

模板类InputIterator，类UnaryPredicate typename iterator_traitsInputIterator:difference_type count_if（InputIterator first，InputIterator last，UnaryPredicate pred）{ typename iterator_traitsInputIterator:difference_type ret=0; while (first!=last) { if (pred(*first)) ++ret; ++首先； } return ret;} 参数pred 是一个一元函数对象或指针，它接受范围内的元素作为参数，并返回一个可以转换为bool 的值。返回的值指示该函数是否计算元素。

返回类型(iterator_traitsInputIterator:difference_type) 是有符号整型。

例子：

//count_if 示例#include iostream //std:cout#include 算法//std:count_if#include 矢量//std:vectorbool IsOdd (int i) { return ((i%2)==1); } } int main () { std:vectorint myvector; for (int i=1; i10; i++) myvector.push_back(i); //myvector: 1 2 3 4 5 6 7 8 9 int mycount=count_if (myvector.begin(), myvector.end(), IsOdd); std:cout ‘myvector 包含’ mycount ‘奇数值。\n’; return 0;}//Output: myvector 包含5 个奇数值。一些常见的算法：

for_each()

寻找（）

查找如果（）

数数（）

计数如果（）

代替（）

替换_if()

复制（）

唯一的_副本（）

种类（）

equal_range()

合并（）

对于某些容器，可能不适合使用全局算法。例如，列表容器无法使用全局排序进行排序。这是为什么呢？因为全局排序方法必须正确使用，所以它对迭代器有一定的要求。迭代器必须是随机访问迭代器（Random Access Iterator），但链表的节点是离散分布在内存中的（用指针链接）。因此，它的迭代器不满足随机访问的要求，所以列表本身提供了成员方法sort()。如果我们想对列表进行排序，我们必须使用它自己的sort()。可以使用全局：sort()的容器包括数组、双端队列、向量等内存连续分配的容器。

针对不同的需求，算法库中的同名函数模板也提供了不同的重载，例如max函数。标准库提供了两个版本：

第一个版本是使用类的运算符重载来完成大小比较。但是，如果比较是语言本身提供的类型，则可能只提供默认的比较方法。例如，默认情况下，字符串是逐个字符进行比较的。可能无法满足我们的个性化需求。

除了提供要比较的数据之外，第二个版本的参数还可以提供一种方法，通过该方法我们可以自定义如何比较数据。例如，我们可以比较字符串的长度。

3 谓词（predicate）

Predicate是一个函数，做一些检测，返回用于条件判断的类型，并指示条件是否为真。

一元函数对象是指接受一个参数的函数对象，例如operator()(x)。如果一元函数对象的返回值为bool 值，则该函数称为谓词；二元函数对象是指接受两个参数的函数，例如operator()(x,y)。如果二元函数对象的返回值为bool 值，则该函数对象称为二元谓词；

4 适配器（adaptor）

适配器在STL中起到转换器的作用。它本质上是一种设计模式，用于将一个接口转换为另一个接口（或连接不同的接口），从而使原本不兼容的接口能够很好地协同工作。比如我们有一个接口void fun(CString a)，它只接受字符串类型变量，但是提供的数据只有一个整型变量int a。这种情况下就需要一个适配器来将int a转换为CString a；

根据目标接口的类型，适配器可以分为以下三类：

4.1 改变容器的接口称为容器适配器

STL提供了串行容器，同时也提供了串行容器的容器适配器，可以在不同的场景中使用。一般来说，容器适配器以串行容器作为底层数据结构，进一步封装适应场景应用的容器。 STL中提供了三种适配器，分别是stack、queue和priority_queue。

4.1.1 Queue队列

4.1.2 堆栈

4.2 改变迭代器的接口，称为迭代器适配器

对于迭代器适配器来说，输入流和输出流都不支持迭代器，STL算法是通过操作迭代器来实现的。如果需要使用STL算法来处理流中输入的数据，请使用std:istream_iterator。这是一个Adapter，它为输入迭代器提供接口，是使用istream实现的。迭代器适配器包括：

4.2.1 三个反向适配器，如rbegin()、rend()等

4.2.2 insert迭代器，带有容器参数，包括back_inserter(容器)、front_inserter(容器)、inserter(容器、位置)。

4.2.3 流适配器：如ostream_iterator、istream_iterator。

4.3 改变函子的接口称为函子适配器

函数对象的适配器用于专门化和扩展一元或二元函数对象。它们主要分为两类：

4.3.1 否定者

否定谓词函数对象结果。包括not1和not2。 not1是构造一个与谓词结果相反的一元函数对象，not2是构造一个与谓词结果相反的二元函数对象。

模板类Predicate unary_negatePredicate not1 (const Predicate pred);例子：

//not1 example#include iostream //std:cout#include 函数式//std:not1#include 算法//std:count_ifstruct IsOdd { bool operator() (const int x) const {return x%2==1;} typedef int argument_type;}; int main () { int value[]={1,2,3,4,5}; int cx=std:count_if (值，值+5, std:not1(IsOdd())); std:cout ‘存在具有偶数值的’cx’元素。\n’; return 0;}输出：有2个值为偶数的元素。not2示例：

//not2 example#include iostream //std:cout#include 函数//std:not2, std:equal_to#include 算法//std:mismatch#include 实用程序//std:pairint main () { int foo[]={10,20,30,40 ,50} ; int bar[]={0,15,30,45,60}; std:pairint*,int* 第一个匹配，第一个不匹配；首先不匹配=std:mismatch (foo, foo+5, bar, std:equal_toint());第一个匹配=std:mismatch (foo, foo+5, bar, std:not2(std:equal_toint())); std:cout ‘条中的第一个不匹配是’ *firstmismatch.second ‘\n’; std:cout ‘bar 中的第一个匹配项是’ *firstmatch.second ‘\n’; return 0 ;}/* 输出bar 中的第一个不匹配是0 bar 中的第一个匹配是30*/4.3.2 binder (活页夹)

将二元函数对象的实际参数绑定到特殊值（常量），将其转换为一元函数对象。包括bind1st和bind2nd。 bind1st 将值绑定到二元函数对象的第一个参数； bind2nd 将值绑定到第二个参数。

bind1st和bind2nd函数用于将二元函数对象（二元函子，bf）转换为一元函数对象（一元函子，uf）。为了实现这一点，它们需要两个参数：要转换的bf 和一个值(v)。

例如： bool less:operator()(const %x, const T y) const

返回值为(xy)。 bind2nd的简单理解就是用y作为比较表达式的第二个参数，即(xv)。如果使用bind1st，则对应的表达式为(vy)，即v作为比较表达式的第一个参数。

f=std:bind1st（函子，v）； f(x) 等价于函子( v, x)

f=std:bind2nd(函子， v); f(x) 等价于函子( x, v)

绑定1st 和绑定2nd 示例：

int a[]={1, 2, 100, 200};std:vector int arr(a, a + 4);//删除所有小于100的元素arr.erase( std:remove_if( arr.begin(), arr.end ( ), std:bind2nd( std:less int(), 100)), arr.end());这里的比较表达式相当于arr.value 100。

如果使用bind1st，则含义正好相反：

//删除所有大于100的元素arr.erase( std:remove_if( arr.begin(), arr.end(),std:bind1st( std:less int(), 100)), arr.end());这里的表达式相当于100 arr.value。

要删除大于100 的元素，您还可以使用bind2nd 和：greater int()：

//删除所有大于100的元素arr.erase( std:remove_if( arr.begin(), arr.end(),std:bind2nd( std:greater int(), 100)), arr.end());如何实现x=k 那么，std提供了另一个好东西not1，我们可以说！ (x k) 和x=k 是等价的，那么我们看下面的表达式：

//删除所有小于等于100的元素arr.erase( std:remove_if( arr.begin(), arr.end(),std:not1(std:bind2nd( std:greater int(), 100))), arr.end()); 010 -1010 不同的数据结构有自己专属的迭代器，不同的迭代器也有不同的特性。由于算法的接口是统一的，通过迭代器的不同属性，算法自动选择正确的执行流程并完成任务。同时，也尽可能地提高了算法的执行效率。算法如何知道迭代器的属性？这项光荣的任务是靠特质来完成的。在STL实现中，广泛使用了特征编程技术。它利用“嵌入式类型”编程技术和C++的模板参数推导功能来弥补C++类型识别的缺点。通过traits，算法可以真实地提取迭代器的属性，帮助算法正确高效地运行。

通过模板参数派生、嵌入类型和模板部分特化来“提取”迭代器的特征：

5.1 提取容器元素类型的解决方案：模板参数推导

特征需要能够区分类迭代器和非类迭代器。

当算法想要询问value_type 时，会通过iterator_traits 进行中继。

如果算法要求的是迭代器，它将传递iterator_traits 的广义定义（如下图1，进一步确定迭代器的类型）。

如果算法要求的是一个指针，它将通过iterator_traits 的范围特化来定义（如下图2）。

如果算法想要询问的是常量指针，它将通过iterator_traits 的范围特化来定义（如下图3）。注意这里的返回

的是T而不是const T，见图中右边黄色框的解释。

6 STL的优势和劣势

6.1 STL标推模板库的优势

STL提供了丰富的数据结构与算法功能。

在许多不同平台上也有尚算健壮的实现。

几乎所有C++编译器都带有STL。

6.2 STL也有许多缺点

陡峭的学习曲线。虽然文档质里不错，但大部分平台的STL头文件都晦涩难惟。

相比为某问题而打造的数据结构，STL通常会较慢。

相比自行设计的数据结构，STL几乎总会占用更多内存。

STL会进行许多动态内存分配，对于高性能、内存受限的游戏机游戏来说，控制STL的内存食欲是富有挑战性的工作。

STL的实现和行为在各编译器上有微小差异，增加了多平台引擎上应用STL的难度。

附小实例代码：

#include <vector>#include <algorithm>#include <functional>#include <iostream>using namespace std;int main(){int ia[7] = {26,210,12,47,109,83};vector<int,allocator<int> > vi(ia,ia+6);// 分配器也是一个模板，需要告诉它每次分配的是什么东西cout<<count_if(vi.begin(), vi.end(), not1(bind2nd(less<int>(),40)));// 统计不小于40的元素数量return 0;}ref：

The C++ Resources Network http://www.cplusplus.com/reference/algorithm/count_if/?kw=count_if

C++ STL 体系结构与内核分析[侯捷] https://www.bilibili.com/video/BV1db411q7B8