C++｜漫谈STL细节及内部原理

欢迎大家来到IT世界,在知识的湖畔探索吧!

1988年，Alexander Stepanov开始进入惠普的Palo Alto实验室工作，在随后的4年中，他从事的是有关磁盘驱动器方面的工作。直到1992年，由于参加并主持了实验室主任Bill Worley所建立的一个有关算法的研究项目，才使他重新回到了泛型化算法的研究工作上来。项目自建立之后，参与者从最初的8人逐渐减少，最后只剩下两个人–Stepanove本人和Meng Lee。经过长时间的努力，最终，信念与汗水所换来的是一个包含有大量数据结构和算法部件的庞大运行库。这便是现在的STL的雏形（同时也是STL的一个实现版本–HP STL）。

　　1993年，当时在贝尔实验室的Andrew Koenig看到了Stepanove的研究成果，很是兴奋。在他的鼓励与帮助下，Stepanov于是年9月的圣何塞为ANSI/ISO C 标准委员会做了一个相关演讲（题为”The Science of C Programming”），向委员们讲述了其观念。然后又于次年3月，在圣迭戈会议上，向委员会提交了一份建议书，以期使STL成为C++ 标准库的一部分。尽管这一建议十分庞大，以至于降低了被通过的可能性，但由于其所包含的新思想，投票结果以压倒多数的意见认为推迟对该建议的决定。

　　随后，在众人的帮助之下，包括Bjarne Stroustrup在内，Stepanove又对STL进行了改进。同时加入了一个封装内存模式信息的抽象模块，也就是现在STL中的allocator，它使STL的大部分实现都可以独立于具体的内存模式，从而独立于具体平台。在同年夏季的滑铁卢会议上，委员们以80%赞成，20%反对，最终通过了提案，决定将STL正式纳入C++标准化进程之中，随后STL便被放进了会议的工作文件中。自此，STL终于成为了C++ 家族中的重要一员。

　　此后，随着C++ 标准的不断改进，STL也在不断地作着相应的演化。直至1998年，ANSI/ISO C 标准正式定案，STL始终是C 标准中不可或缺的一大部件。

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

STL封装了一些常用的数据结构和算法，程序员没必要重新去构造STL中已有的数据结构和算法，毕竟，库中实现的数据结构与算法是由顶尖的程序员完成的，有了最大程度的优化和安全性的检验。STL尽可能实现了这些数据结构和算法的通用性和泛化（面向对象强调数据与操作的封装，泛型编译GP强调一些通用的算法（函数模板）与一般的数据结构的分离）。

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

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

容器是一堆常用数据结构的实现，主要用户存放和读取数据，屏蔽了底层的内存分配和释放的问题，所以能够让用户更方便和高效的使用。

算法（函数模板库）通用性的实现：独立于具体的容器类型（包括窗口元素的数据类型）并实现特定功能的定制，通过迭代器+函数对象来实现；如一个排序算法，可以是不同的容器，也可以实现降序或升序，前者通过迭代器来实现，后者通过函数对象来实现（其中有些功能可定制，不是写死在算法内部，也就是通过传入函数对象来实现，当然也可以是函数指针或lambda表达式）。

一般的形式就是：

type algorithmName(Iterator begin, Iterator end); type algorithmName(Iterator begin, Iterator end, proc op); type algorithmName(Iterator begin, Iterator end,UnaryPredicate op); type algorithmName(Iterator begin, Iterator end, const %& value); type algorithmName(Iterator begin, Iterator end, …); template<class t1, class t2> type algorithmName(t1 first, t2 last, …);

欢迎大家来到IT世界,在知识的湖畔探索吧!

在STL中，算法和容器是分开设计的，这和面向对象（OO）有点不符，在面向对象中，我们一般将数据和方法封装在一个类中，而在STL中，将与容器联系较紧密的操作封装在类模板中，而一些通用的操作，则采用函数模板的形式封装在算法库。

函数对象（function object）是一个程序设计的对象允许被当作普通函数来调用。函数对象与函数指针相比，有两个优点：第一是编译器可以内联执行函数对象的调用（如排序的升序还是降序，也就是一行代码的不同）；第二是函数对象内部可以保持状态。

迭代器是怎样让函数模板独立于容器的呢？迭代器首先也是一个模板类，并且是容器的内部类，因为是内部类，所以可以使用一个相同的名称：iterator，再通过不同的容器类域加以区别，如vector<int>::iterator it;

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

I 通过迭代器获得输入数据；

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

III 通过迭代器将结果输出；

如果对容器、迭代器、函数对象的一些一般性操作加以限制（或重定义、封装），便可形成接口，也就是适配器的概念。

以上STL六大部件（Containers容器、Allocator分配器、Adaptor适配器、Algorithms算法库、Iterators迭代器、Functor函数对象）的关系可以表示如下：

以下是一个有使用到STL六大部件的小实例：

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

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

vector<int,allocator<int> > vi(ia,ia+6);

vector是一种容器类型。

int是容器内元素的类型，在<>还可以有分配器实参或基本数据类型的实参（一些参数有缺省值）。

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

欢迎大家来到IT世界,在知识的湖畔探索吧!template < class T, class Alloc = allocator<T> > class vector;

模板类的构造函数有重载，可以使用数组的元素做为vector容器的元素。

(1) empty container constructor (default constructor) (2) fill constructor (3) range constructor (4) copy constructor

1.1 序列式容器

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

deque是双向队列，前后都可以扩充。我们知道一个内存要扩充，是没办法在原地扩充的，像vector在尾巴上扩充，也是另外找一个2倍大的空间，整体移动过去。而deque是怎么做到双向扩充的呢？如下图所示：

deque由一个控制中心和多个内存块buffer组成，控制中心是一个vector，里面按顺序存放每个内存块的地址。由这些地址串联起来形成整个deque的空间。并且面向用户展现的是类似连续空间的表征。

map指向控制中心的vector，他的类型是T，T是模板参数，表示deque中数据的类型，比如int。map中存放的是指向内存块的指针，如int*类型。然后map又是指向vector的指针，vector中存放的是int*，所以map就是int，也就是T。

map中保存每个buffer的指针，一个buffer可以存放多个元素。当从最后插入元素，刚好遇到最后那个buffer的空间用完，则会在后面另外申请一个buffer，新的buffer的头指针存放在map的最后一格中。从前面插入也是同样的道理。

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

1.2 关联式容器

关联容器通过键(key)存储和读取元素的value，如map，对于set，其元素即是key也是value。

Unordered associative containers:

总结一下各容器特性：

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

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

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

Input iterator（输入迭代器）：读，不能写，只支持自增运算；

Output iterator（输出迭代器）：写，不能读，只支持自增运算；

Forward iterator（前向迭代器）：读和写，只支持自增运算；

Bidirectional iterator（双向迭代器）：读和写，支持自增和自减运算；

Random access iterator（随机访问迭代器）：读和写，支持完整的迭代器算术运算；

count_if()函数模板原型：

欢迎大家来到IT世界,在知识的湖畔探索吧!template <class InputIterator, class UnaryPredicate> typename iterator_traits<InputIterator>::difference_type count_if (InputIterator first, InputIterator last, UnaryPredicate pred) { typename iterator_traits<InputIterator>::difference_type ret = 0; while (first!=last) { if (pred(*first)) ++ret; ++first; } return ret; }

参数pred是一元函数对象或指针，接受范围内的元素作为参数，并返回可转换为bool的值。返回的值指示此函数是否计算元素。

返回类型 (iterator_traits<InputIterator>::difference_type) 是一个signed integral类型。

实例：

// count_if example #include <iostream> // std::cout #include <algorithm> // std::count_if #include <vector> // std::vector bool IsOdd (int i) { return ((i%2)==1); } int main () { std::vector<int> myvector; for (int i=1; i<10; 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 contains " << mycount << " odd values.\n"; return 0; } // Output: myvector contains 5 odd values.

一些常用算法：

for_each()

find()

find_if()

count()

count_if()

replace()

replace_if()

copy()

unique_copy()

sort()

equal_range()

merge()

对于某些容器，可能并不适合使用全局算法，例如list容器不能采用全局的sort来进行排序，这是为什么？因为全局的sort方法要正确使用，对迭代器有一定的要求，必须要求迭代器是随机访问迭代器（Random Access Iterator），但是list的node在内存中是离散分布的（用指针链接起来），所以他的迭代器不满足随机访问这个需求，所以list自己提供了成员方法sort()，那么我们要对list排序，就要使用它自己的sort()。能够使用全局::sort()的容器有array、deque、vector等内存是连续分配的容器。

因应不同的需要，算法库中的同一名称的函数模板也提供了不同的重载，如max函数，标准库提供了两种版本：

第一种版本是利用类的操作符重载来完成大小的比对，但如果比对的是语言本身带的类型，可能只提供了一个默认的比较方式，例如string默认是按字符一个一个比对的，可能不能满足我们的个性化需求。

第二种版本的参数除了提供要比对的数据，还可以提供一个方法，这个方法我们可以自定义如何比对数据，例如我们可以比对string的长度。

3 谓词（predicate）

谓词（predicate）是返回布尔值（或者可以隐式转换为布尔值）的函数对象。用于STL中的algorithm时，谓词应该是无状态的（ stateless）函数对象，即谓词的结果不依赖于内部的数据成员。这是因为STL中的algorithm不保证内部实现时对传入的谓词要复制多少次。

谓词是做某些检测的函数，返回用于条件判断的类型，指出条件是否成立。

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 栈stack

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

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

4.2.1 三种reverse（逆向）适配器，如rbegin(),rend()等。

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

4.2.3 stream适配器：如ostream_iterator,istream_iterator。

4.3 改变仿函数的接口，称为仿函数适配器

函数对象的适配器，用于特化和扩展一元或者二元函数对象，主要分为两类：

4.3.1 取反器(negator)

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

template <class Predicate> unary_negate<Predicate> not1 (const Predicate& pred);

实例：

// not1 example #include <iostream> // std::cout #include <functional> // std::not1 #include <algorithm> // std::count_if struct IsOdd { bool operator() (const int& x) const {return x%2==1;} typedef int argument_type; }; int main () { int values[] = {1,2,3,4,5}; int cx = std::count_if (values, values+5, std::not1(IsOdd())); std::cout << "There are " << cx << " elements with even values.\n"; return 0; } Output: There are 2 elements with even values.

not2 example：

// not2 example #include <iostream> // std::cout #include <functional> // std::not2, std::equal_to #include <algorithm> // std::mismatch #include <utility> // std::pair int main () { int foo[] = {10,20,30,40,50}; int bar[] = {0,15,30,45,60}; std::pair<int*,int*> firstmatch,firstmismatch; firstmismatch = std::mismatch (foo, foo+5, bar, std::equal_to<int>()); firstmatch = std::mismatch (foo, foo+5, bar, std::not2(std::equal_to<int>())); std::cout << "First mismatch in bar is " << *firstmismatch.second << '\n'; std::cout << "First match in bar is " << *firstmatch.second << '\n'; return 0; } /* output First mismatch in bar is 0 First match in bar is 30 */

4.3.2 绑定器(binder)

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

bind1st和bind2nd函数用于将一个二元函数对象（binary functor，bf）转换成一元函数对象（unary functor，uf）。为了达到这个目的，它们需要两个参数：要转换的bf和一个值（v）。

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

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

f = std::bind1st( functor, v); f(x)等价于functor( v, x)

f = std::bind2nd( functor, v); f(x)等价于functor( x, v)

bind1st和bind2nd例子：

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());

5 Iterator Traits 迭代器特性萃取机

不同的数据结构都有自己专属的迭代器，不同的迭代器也有不同的特性，由于算法的接口是统一的，通过迭代器的不同属性，算法自动选择正确的执行流程，在完成任务的同时，也尽可能提高算法的执行效率。那算法如何获知迭代器的属性呢？这一光荣的任务就是traits完成的。在STL实现中，traits编程技术得到大量的运用，它利用了“内嵌类型”的编程技巧与C++的template参数推导功能，弥补了C++类型识别方面的不足。通过traits，算法可以原汁原味的将迭代器的属性萃取出来，帮助算法正确高效的运行。

通过template参数推导、内嵌型别、模板偏特化来”萃取“迭代器的特性：

5.1 提取容器元素类型的解决办法：template参数推导

在算法函数中，我们必须知道容器的元素类型，这关系到函数返回值。既然迭代器设计中不能暴露容器的实现细节，那么我们在算法中是不可能知道容器元素的类型，因此，必须设计出一个机制，能够提取出容器中元素的类型：

#include <stdio.h> #include <iostream> using namespace std; // 此函数中并不知道iter所指的元素型别，而是通过模板T来获取的 template <class I, class T1 ,class T> T sum_impl(I iter ,T1 n , T t) { T sum = 0;// 通过模板的特性，可以获取I所指之物的型别,此处为int // 这里做func应该做的工作 for(int i = 0 ; i < n ;i++){ sum+=*iter++; } return sum; } template <class I , class T1> inline T1 sum(I iter , T1 n) {// 此处暴露了template参数推导机制的缺陷，在型别用于返回值时便束手无策 return sum_impl(iter , n ,*iter); } int main() { int a[5] = {1,2,3,4,5}; int sum1 = sum(a , 5); cout<<sum1<<endl; // 15 } 

5.2 以迭代器所指对象的类型声明返回类型的解决办法：内嵌型别

迭代器所指之物的型别并非只是”迭代器所指对象的型别“，最常用的迭代器型别有五种，并非任何情况下任何一种都可利用上述的template参数推导机制来获取，而且对于返回值类型，template参数推导机制也束手无策，因此，Traits技法的内嵌型别就应运而生：

#include <iostream> using namespace std; template <class T> struct MyIter{ typedef T value_type; // 内嵌型别声明 T* ptr; MyIter(T* p =0):ptr(p){} T& operator*() const {return *ptr;} }; template <class I> typename I::value_type // func返回值型别 func(I iter){ return *iter; } int main(){ MyIter<int> iter(new int(8)); cout<<func(iter)<<endl; // 8 } 

5.3 原生指针用作迭代器的解决办法：模板偏特化

针对原生指针这类特殊情况，我们很容易想到利用模板偏特化的机制来实现特殊声明，在泛化设计中提供一个特化版本。偏特化的定义是：针对任何template参数更进一步的条件限制所设计出来的一个特化版本。这里，针对上面的MyIter设计出一个适合原生指针的特化版本，如下：

template <class T> struct MyIter <T*>{ //T*代表T为原生指针，这便是T为任意型别的一个更进一步的条件限制 typedef T value_type; // 内嵌型别声明 T* ptr; MyIter(T* p =0):ptr(p){} T& operator*() const {return *ptr;} };

STL根据经验，定义了迭代器最常用到的五种类型：value_type、difference_type、pointer、reference、iterator_category，任何开发者如果想将自己开发的容器与STL结合在一起，就一定要为自己开发的容器的迭代器定义这五种类型，这样都可以通过统一接口iterator_traits萃取出相应的类型，下面列出STL中iterator_traits的完整定义：

template<typename Category, typename T, typename Distance = ptrdiff_t, typename Pointer = T*, typename Reference = T&> struct iterator { typedef Category iterator_category; typedef T value_type; typedef Distance difference_type; typedef Pointer pointer; typedef Reference reference; } tempalte<typename I> struct iterator_traits { typedef typename I::iterator_category iterator_category; typedef typename I::value_type value_type; typedef typeanme I:difference_type difference_type; typedef typename I::pointer pointer; typedef typename I::reference reference; };

如typedef typename I::value_type value_type;

Traits要能够区分class iterators和non-class iterators。

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

如果算法要问的东西是一个迭代器，那么会通过iterator_traits的泛化定义（下图①，更进一步，要确定迭代器的类型）。

如果算法要问的东西是一个指针，那么会通过iterator_traits的范围特化定义（下图②）。

如果算法要问的东西是一个常量指针，那么会通过iterator_traits的范围特化定义（下图③），注意这里返回的是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

https://www.cnblogs.com/leokale-zz/p/11100566.html

https://www.cnblogs.com/leokale-zz/p/11107807.html

－End－