本文是《C++ Primer Plus（第6版）中文版》的笔记。

标准模板库 STL

STL提供了一组表示容器、迭代器、函数对象和算法的模板，容器是一个与数组类似的单元，可以存储若干个值。STL容器是同质的，即存储的值的类型相同；算法是完成特定任务（如对数组进行排序或在链表中查找特定值）的处方；迭代器能够用来遍历容器的对象，与能够遍历数组的指针类似，是广义指针；函数对象是类似于函数的对象，可以是类对象或函数指针（包括函数名，因为函数名被用作指针），STL使得能够构造各种容器（包括数组、队列和链表）和执行各种操作（包括搜索、排序和随机排列）。

泛型编程

C++中的STL就是一种泛型编程，面向对象编程关注的是编程的数据方面，而泛型编程关注的是算法。泛型编程旨在编写独立于数据类型的代码，模板就是C++中编写通用程序的工具。

为何使用迭代器

模板使得算法独立于存储的数据类型，而在STL中迭代器（iterator）使算法独立于使用的容器类型。

为达到上述目的，必须对迭代器和容器进行设计，如迭代器需要重载*，++等运算符，容器中增加了可用end()获取的超尾元素等。

迭代器类型

为满足不同算法的要求，STL中定义了5中类型的迭代器，并根据所需的迭代器类型对算法进行描述。5种迭代器为输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机访问迭代器。5种迭代器有一些共同点，如都可以执行解除引用操作，即都定义了*运算符，也都可以使用==或!=比较相等或不等（但可能被重载）。5种迭代器详细说明如下：

输入迭代器

这里“输入”是从程序的角度说的，即来自容器的信息被视为输入。

输入迭代器的解引用操作可以读取容器中的值，但不一定能让程序修改其值。需要输入迭代器的算法将不会修改容器中的值。输入迭代器支持前缀和后缀的++运算符，以能够遍历容器中的所有值。输入迭代器是单向迭代器，可以递增，不能倒退。

输出迭代器

“输出”也是从程序的角度说的，程序的输出即是容器的输入。其解除引用操作可以写但不能读。如果是单通行只写算法，则可以使用输出迭代器。

正向迭代器

正向迭代器只使用++运算符来遍历容器。与输入和输出迭代器不同的是，它总是按照相同的顺序遍历一系列值。将正向迭代器递增后，仍然可以对前边的迭代器解除引用（如果保存了它），并可以得到相同的值。因此正向迭代器可用于多次通行算法。正向迭代器可读可写，如果用const修饰则使得只能读取。

双向迭代器

双向迭代器支持所有正向迭代器的特性，并且还支持前缀和后缀的--运算。

随机访问迭代器

随机访问迭代器具有双向迭代器的所有特性，同时添加了支持随机访问的操作（如指针增加运算）和用于对元素进行排序的关系运算符。

迭代器层次结构

迭代器的类型形成了一个层次结构。如正向迭代器具有输入迭代器和输出迭代器的全部功能，同时还有自己的功能；双向迭代器具有正向迭代器的全部功能，同时还有自己的功能；随机访问迭代器具有正向迭代器的全部功能，同时还有自己的功能等。

下表总结了5种迭代器的功能，其中i表示迭代器，n表示整数：

在编写算法时，应尽可能使用要求最低的迭代器，并让其适用于容器的最大区间。

概念、改进和模型

• 概念（concept）：用于描述算法对于迭代器实现的一系列要求，如输入迭代器概念、正向迭代器概念等等
• 改进（refinement）：用于表示概念之间的继承关系，如双向迭代器是对正向迭代器概念的一种改进
• 模型（model）：概念的具体实现被称为模型，如指向int的常规指针是一个随机访问迭代器模型，也是一个正向迭代器模型，因为它满足该概念的所有要求

将指针用作迭代器

迭代器是广义的指针，指针满足所有迭代器要求。迭代器是STL算法的接口，而指针是迭代器，因此STL算法可以使用指针来对基于指针的非STL容器进行操作。

概念、改进和模型

例如可以对数组调用STL的排序算法：

1
2
3
4

const int SIZE = 100;
double arr[SIZE];
// ...
sort(arr , arr + SIZE);

又例如，STL的copy()操作也可以将一个数组复制到一个矢量中：

1
2
3

int cast[10] = {1,2,3,4,5,6,7,8,9,0};
vector<int> dice(10);
copy(casts , casts+10 , dice.begin());

STL中有ostream_iterator迭代器模板，它是输出迭代器概念的一个模型， 也是一个适配器，可以将一些其他接口转换为STL使用的接口，创建方法如下：

1
2

#include <iterator>
ostream_iterator<int,char> out_iter(cout," ");

上述定义的输出流迭代器中，两个迭代器参数中，第一个int表示发送给输出流的数据类型，char表示输出流使用的字符类型（另一个可能的值为wchar_t）。构造函数的第一个参数cout指定了要使用的输出流（也可以是用于文件的输出流），第二个参数字符串是发送给输出流的每个数据项后显示的分隔符。

1

*out_iter++ = 15;

表示将15和空格发送给cout管理的输出流中，并且为下一个输出操作做好准备。所以也可以有以下的用法：

1

copy(dice.begin(), dice.end(), out_iter); //将矢量dice中的内容发送至输出流

与ostream_iterator类似，STL中还有istream_iterator，是一个输入迭代器概念的模型。

其他有用的迭代器

反向迭代器reverse_iterator，对reverse_iterator执行递加操作将会导致其递减，这是为了简化对已有函数的使用。

插入迭代器back_insert_iterator、front_insert_iterator和insert_iterator也是为了提高STL算法通用性而设计，back_insert_iterator将元素插入到容器的尾部，而front_insert_iterator将元素插入到容器的前端。insert_iterator将元素插入到其构造时构造参数指定的位置前边。插入迭代器的使用有一些限制，如back_insert_iterator可用于vector这样的允许在尾部增加元素的容器，但front_insert_iterator却不可以。front_insert_iterator可用于queue，允许在前段插入。insert_iterator不受插入位置的限制，可以用在vector中在最前端插入。这些迭代器在声明时需要将容器作为模板参数，将实际的容器标识符作为构造函数的参数，例如：

1

back_insert_iterator<vector<int> > back_iter(dice);

front_insert_iterator的声明方式与上边类似。在声明insert_iterator时需要额外指定插入位置作为构造参数：

1

insert_iterator<vector<int> > insert_iter(dice, dice.begin());

容器

容器种类

STL中有容器概念和容器类型，概念是具有名称（如容器、序列容器、关联容器等）的通用类别；容器类型是可用于创建具体容器对象的模板。

容器概念

容器概念指定了所有STL容器类都必须满足的一系列要求：

• 容器是存储其它对象的对象，被存储的对象必须是同一类型的（可以是对象或内置类型值）；

• 当容器过期时（销毁），存储在其中的数据也会过期（如果存储的是指针，则其指向的数据不一定过期）；

• 只有可复制构造和可赋值的类型才可以存储在容器中（C++11中又增加了复制插入CopyInsertable和移动插入MoveInsertable）；

• 下表是所有的容器都提供的特征和操作：

（表中X表示容器类型，T表示存储的对象类型，a和b表示类型为X的值，r表示类型为X&的值，u表示类型为X标识符。）

C++11新增的容器要求

C++11中增加了右值引用的概念，及移动构造、移动赋值操作，也增加了对通用容器的要求：

（表中rv表示类型为X的非常量右值，X::iterator需要满足正向迭代器的要求。）

序列

序列（sequence）是对通用容器概念的一种重要改进。STL中有7种序列：deque、forward_list（C++11）、list、queue、priority_queue、stack和vector。序列概念要求迭代器至少是正向迭代器，以保证元素按照特定顺序排列，不会在两次迭代之间发生变化。array也被归类到序列容器，虽然它并不满足序列的所有要求。

序列要求其元素按照严格的线形顺序排列。数组和链表都是序列，但分支结构不是。序列中的元素可以执行诸如将值插入到特定位置、删除特定区间等操作，参见下表：

（表中X表示容器类型，a表示类型为X的值，t表示存储的对象类型T的值，n表示整数，p、q、i和j表示迭代器。）

序列概念的模型deque，list，queue，priority_queue，stack和vector支持上表中的所有操作。除此之外，还有一些其他操作，见下表，下表中的所有操作的时间复杂度均为固定时间：

在上表中，a[n]和a.at(n)的差异在于当n查出容器有效区间时，a.at(n)会检查边界并抛出异常 out_of_range；vector不支持push_front()和pop_front()是因为在vector的头部插入或删除新元素会引发复杂度为线性时间而非固定时间的操作。

具体说明几种序列容器类型：

vector

vector是数组的一种类表示，可以自动内存管理，动态改变vector对象的长度。可对元素随机访问，在尾部添加或删除元素为固定时间复杂度，但在头部添加或删除元素是线性时间复杂度。

vector还是可反转容器（reversible container）概念的模型，可使用反向迭代器逆序迭代：

1

for_each(dice.rbegin(), dice.rend(), Show);  // display in reversed order

deque

deque是双端队列（double-ended queue），在STL中其实现类似于vector，主要区别在于deque对象在其头部插入和删除元素的时间是固定的。为实现这一目的，deque对象设计比vector对象更为复杂，因此在对元素的随机访问和在序列中部执行限行时间的插入和删除操作，vector容器的执行速度会更快些。

list

list模板类表示双向链表，除了第一个和最后一个元素外，每个元素都与前后的元素相链接。list在链表中任意位置插入和删除元素都是固定时间的复杂度，但不支持随机访问。在list中插入或删除元素后链表迭代器指向的元素不变。list也是可反转容器。

除序列和可反转容器的函数外，list还有一些链表专用成员函数，见下表（Alloc参数通常有默认值）：

补充：

方法insert()和splice()的区别在于，前者将原始区间的副本插入到目标地址，而后者会将原始区间移到目标地址。list只能使用其成员函数sort()，而非成员函数sort()不能作用于list。

sort()、merge()和unique()还有各自拥有接受另一个参数的版本，该参数用于指定用来比较元素的函数。remove()也有一个接受另一个参数的版本，该参数用于指定一个用来确定是否删除元素的函数。

forward_list

C++11中的容器，实现了单链表。这种链表中每个节点都只链接到下一个节点，而没有链接到前一个节点。因此forward_list只需要正向迭代器。forward_list是不可反转容器，比list更简单、更紧凑，但功能更少。

queue

queue模板是一个适配器类，让底层类展示典型的队列接口。queue不仅不允许随机访问元素，甚至不允许遍历队列。可以进行队列的操作如在队尾添加元素、从队首删除元素、查看队首和队尾的值、检查元素数目和测试队列是否为空等：

priority_queue

priority_queue模板类是一个适配器类，与queue支持的操作相同。但在priority_queue中最大的元素总是被移到队首，其默认的底层类是vector。有两种构造函数，在构造时可以指定用于确定哪个元素放到队首的比较方式：

1
2

priority_queue<int> pq1;  // default version
priority_queue<int> pq2(greater<int>);  // use greater<int> to order

stack

与队列相似，stack是一个适配器类，给底层的类（默认是vector）提供了典型的栈接口。stack不允许随机访问栈元素，甚至不允许遍历栈。可以将元素推到栈顶、从栈顶弹出元素、查看栈顶的值、检查元素数目和测试栈是否为空：

array

C++11的array并非STL容器，因为其长度是固定的。array没有可以调整大小的操作如push_back()和insert()， 但有operator[]()和at()。STL中的很多标准算法如copy()和for_each()等可用于array对象。

关联容器

关联容器（associative containers） 是对容器概念的另一个改进。关联容器将值与键关联在一起，并使用键来查找值。对于容器X，表达式X::value_type通常指出了存储在容器中的值类型，在关联容器中，表达式X::key_type指出了键的类型。

关联容器的优点在于对元素的快速访问，允许插入新元素但不能指定元素的插入位置，关联容器的底层通常有用于确定数据存放位置的算法，以便能够快速检索信息，关联容器通常使用树来实现。

STL中有4中关联容器：set、multiset、map和multimap。set是最简单的关联容器，对于set来说，值的类型与键相同（值就是键），键是唯一的，所以集合中不会有多个相同的键。multiset与set相似，只是可能有多个值的键相同。

map中值与键的类型不同，键是唯一的，每个键只对应一个值。multimap中一个键可以与多个值相关联。

关联容器的成员变量和方法详见下边的两个表格：

通常，比较对象不要求键相同时值是相同的，等价键（equivalent key）意味着两个值（相同或不同）的键相同。上表中X是容器类，a是类型为X的对象。如果X使用唯一键（即set或map）则a_uniq将是类型为X的对象。如果X允许一键多值（multiset或multimap）则a_eq是类型为X的对象。i和j是指向value_type元素的输入迭代器，[i,j]是一个有效的区间，p和q2是指向a的迭代器，q和q1是指向a的可解除引用的迭代器，[q1,q2]是有效区间，t是X::value_type值，k是X::key_type值，il是initializer<value_type>对象。

无序关联容器

无序关联容器是对容器概念的另一种改进。与关联容器一样，无序关联容器也将值与键关联起来，并用键来查找值。但底层的差别在于，关联容器是基于树结构的，而无序关联容器是基于数据结构哈希表，旨在提高添加和删除元素的速度以及提高查找算法的效率。STL中的四种无序关联容器是unordered_set、unordered_multiset、 unordered_map 和unordered_multimap。

哈希函数（hash function）将键转换为索引值。哈希函数中有桶（bucket）的概念，不同的key得到不同的索引值（如使用数字编码等）后，将这些索引值根据桶的个数求余，求余得到的是与桶的数量相同的一组不同索引值，根据索引值将key放于桶中。如需在容器中搜索键，则对键执行哈希函数，进而只在索引对应的桶中搜索，理想情况下应有足够多的桶，每个桶只包含为数不多的key。C++11库中提供了模板hash<key>，无序关联容器默认使用该模板，为各种整型、浮点型、指针及一些模板类（如string）定义了改模板的具体化。

无序关联容器的成员变量及方法见下边的表格：

无序关联列表的方法与关联列表相似，所以上边关联容器列表的大多数方法也适用于无序关联列表，例外是：无序关联列表不存在lower_bound(k)、upper_bound(k)以及构造函数X(i,j,c)等涉及到排序或比较大小关系的方法。关联列表中有“大于”或“小于”的概念，但是在无序关联列表中只有“等于”和“不等于”。

表中X是无序关联容器，a是类型为X的对象，b可能是类型为X的常量对象，hf是类型为hasher的值，eq是类型为key_equal的值，n是类型为size_type的值，z是类型为float的值。i和j是指向value_type元素的输入迭代器，[i,j]是一个有效的区间，p和q2是指向a的迭代器，q和q1是指向a的可解除引用的迭代器，[q1,q2]是有效区间，t是X::value_type值，k是X::key_type值，il是initializer<value_type>对象。

REFERENCE

C++ Primer Plus（第6版）中文版