C++学习笔记（九）模板与标准模板库（下）

1、基本序列式容器

我们以vector、deque和list为例介绍基本序列式容器。我们先来看一个关于vector的例子。

例1：

vector可以理解为可以在两端插入、删除数据的数组，它提供了丰富的成员函数，用于操作数据。在本例中我们加入了头文件vector，在使用vector时必须包含该头文件。

我们接着来看一下主函数。在主函数中我们定义了一个vector类的int型实例num，需要注意的是我们并没有指定实例的大小，因为vector是可以根据需求自动调整大小的，这一点跟数组不同。接下来我们调用函数push_back，该函数时在vector实例num的最后添加一个元素，因为一开始定义的时候为空，因此此时的num中只包含一个元素50。

之后我们再调用insert函数，该函数可以在指定位置插入元素。在insert参数中，我们分别调用了begin和end函数，这两个函数分别用来访问num实例的头部和尾部。begin()返回的是一个迭代器，如果容器不为空，则返回的迭代器指向容器的第一个元素；如果容器为空，则返回的迭代器指向容器尾部之后的位置。end()函数同样返回的是一个迭代器，该迭代器指向的是容器尾部之后的位置。当容器为空时，begin()函数和end()函数都指向同一个位置，当容器有一个元素的时候，begin()函数指向第一个元素的位置，end()函数则指向第一个元素之后的位置。调用insert函数时，如果不是在容器尾部插入元素，则需要将所插入位置以后的元素都向后移一位，然后再将需要插入的元素插入到当前位置。例如我们要在开头插入一个元素，则需要将容器现有的元素都向后移动一个位置，然后再将元素插入到第一个位置，因此vector在非尾部位置插入元素，其效率不高。在主函数中调用两次insert函数之后，此时的容器num中的元素有：10，50，20。

之后又调用了两个push_back函数，在容器尾部插入了两次数据。此时容器中的数据按顺序依次为：10，50，20，60，40。

之后调用size函数，返回容器的大小，因为此时容器中包含五个元素，因此返回值为5。接下来我们将容器中的元素一一打印出来，我们可以通过下标操作符访问容器中的元素，打印结果为：10，50，20，60，40。

接下来调用erase函数删除容器中的元素，删除位置是容器第一个元素，删除之后，该位置就会空出，此时后面的元素需要全部向前移动一个位置。此时容器中的元素按顺序一次为：50，20，60，40。

例2：

我们将例1中的vector换成deque，运行程序我们发现两个程序的运行结果完全相同。是不是vector和deque相同呢？其实不是的，vector说到底是个数组，在非尾部插入元素都需要移动其它元素，而deque则不同，它是一个可以操作数组头部和尾部的数组，因此在头部或尾部插入或删除数据，其处理效率都是一样的。当我们需要频繁在头部和尾部插入或删除数据，则deque优于vector。

例3：

在本例中我们定义了一个list容器string类型的实例str，之后我们先在容器中添加了6个string类型元素，为了遍历str容器，我们定义了一个迭代器iter。通常每定义一个容器，就会有一个与容器数据类型相关的迭代器，本例中定义了容器str，则它的对应的容器有：

如果我们不需要修改容器中的元素，仅仅只是进行访问的话，则可以定义为const_iterator。

为了从头到尾遍历容器，我们先将迭代器指向str.begin()，for循环的结束条件是str.end()，每次运行一遍循环体中的内容，迭代器自增一次，相当于指向下一个元素，我们之所以能够直接使用自增运算符，那是因为在容器的类中系统已经重载过了自增操作符。当我们需要获得当前迭代器所指的元素时，我们可以用取址操作符“*”来操作迭代器，“*iter”就为迭代器所指向的元素。在此程序中我们之所以没有按照vector和deque的方式，以下标进行访问容器中的元素，那是因为list并没有重载下标操作符，因而不能根据下标进行直接访问。

在主函数中我们调用了reverse函数，对容器中的元素进行翻转，然后再次打印容器中的元素。

list容器是一个双向链表，因此在容器中的任何位置插入元素，都不需要移动其它元素，因此执行效率是稳定的。

2、基本序列式容器效率比较

在前面介绍序列式的三种容器时，我们简单介绍了在容器各部位插入或删除元素时的处理效率，在此节我们做一个总结。

根据STL公布的容器各种操作效率，我们可以根据不同的需求来选择合适的容器。例如，我们需要频繁的在容器的任意位置插入或删除元素，则我们可以选择list，而非vector和deque。具体的总结见下表。

对于vector而言，它只是一个可以伸缩长度的数组，因此除了在尾部插入、删除数据外，在其它任何部位插入、删除数据都是线性的复杂度，容器长度越大，完成相应的操作也就越多。而访问元素则可以根据下标直接访问到，因此访问任何位置的元素，其效率都是恒定的。

对于deque而言，它是一个可以操作头部和尾部的并且可以伸缩长度的数组，因此它在头部和尾部插入、删除数据，效率是恒定的，但是在容器的中间插入元素，则它跟vector一样，同样是要移动其它元素的，因此在中部插入或删除元素效率是线性的。对于访问容器中的元素，它同样可以通过下标进行直接访问，因此效率也是恒定的。

对于list而言，它是一个双向链表，因此在任何位置插入或删除元素都不用移动其它元素，其效率始终是恒定的。对于访问元素，双向链表访问头尾元素都很方便，但是访问中间元素则需要逐一从头部或尾部一一遍历过去，因此访问容器中间的元素其效率是线性的。

在今后的程序设计过程中，如果需要使用容易，应该按照需求选择合适的容器，否则会大大降低程序的效率。如果我们只需要在容器尾部插入删除元素，则vector就够用了，如果还需要在头部也频繁的插入删除元素，则需要选择deque。

3、基本关联式容器

基本的关联式容器主要有：set、multiset、map和multimap，这四种容器可以分为两组：map和set。

set可以理解为我们数学中的集合，它可以包含0个或多个不重复、不排序的数据，这些数据被称为键值。map也是一种集合，它同样可以包含0个或多个不排序的元素对，每一个元素对有一个键值和一个与键值相关联的值，在map中键值是不允许重复的。而multiset则是允许重复的集合，multimap则是允许有重复键值的map，因为multiset和multimap可以看做是set和map的扩展，因此我们将主要介绍set和map。

例1：

本例是set的一个示例，在主函数中我们先创建了一个set容器整型的示例s，之后就开始向容器中添加数据。对于set容器，insert被重载过，其调用方式有两种，我们既可以向前面序列式容器那样调用：

也可以不指定插入位置，而直接插入元素：

但是无论以哪种方式进行调用，insert函数都能保证插入元素后set容器中不会出现重复的元素。

在插入一些元素之后，我们就定义了一个迭代器itor用于访问容器中的元素。访问的方法和序列式容器相同。

find函数可以用于查找set容器中是否包含指定的键值，如果存在，则返回指向该键值的迭代器，如果不存在，则返回与end()函数相同的结果。在例1中，我们分别查找了键值2和5是否存在于集合s中，因为s容器没有2元素，因此返回值等于s.end()，存在5元素，因此查找5元素时，函数返回结果不等于s.end()。

例2：

本例是一个map容器的示例程序，map是一种关联式的列表，即将一个键值与一个值一一对应起来。我们直接来看主函数，主函数一开始定义了一个map容器示例m，“map< char, int > m;”语句中char表示键值的数据类型，int表示与键值对应的值的数据类型。我们用字符来作为键值，键值在map中是不允许出现重复的，但是与键值对应的值value可以出现重复，如本例中m[ 'a' ]和m[ 'e' ]相同。但是如果键值出现相同，则以最后一次出现的作为结果，例如本例中一开始“m[ 'a' ] = 1;”，在后面又出现“m[ 'a' ] = 0;”，此时不会有语法错误，这两句可以理解为“m[ 'a' ] = 1;”是给“m[ 'a' ]”赋初值，其值为1，而“m[ 'a' ] = 0;”则可以理解为我们将“m[ 'a' ]”的值由1修改为0。

遍历map时同样是使用迭代器，在函数中我们定义了一个迭代器itor，由于map中是由元素对组成的，包含两个元素，因此遍历方法与前面所介绍的容器稍有不同，前面的容器用*itor就可以直接获得所需要的元素，而map容器则需要通过itor->first访问键值，并用itor->second访问与键值对应的值。

例2最终运行结果如下：
A –– 0
B –– 2
c –– 3
d –– 4
e –– 1
f –– 2
g –– 3
h –– 4

4、容器适配器

容器适配器是用基本容器实现的一些新容器，这些容器可以用于描述更高级的数据结构。容器适配器有三种：stack、queue和priority_queue。stack可以与数据结构中的栈对应，它具有先进后出的特性，而queue则可以理解为队列，它具有先进先出的特性，priority_queue则是带优先级的队列，其元素可以按照某种优先级顺序进行删除。

例1：

本例是一个stack的示例程序，我们在主函数中定义了一个stack容器实体s，之后我们定义了一个变量a，我们用一个while循环向容器s中添加数据。之后再利用一个while循环将元素都出栈并打印显示。对于stack，push为入栈操作即向栈中添加元素，pop为出栈操作即删除栈顶元素，top函数则为返回栈顶元素但是并不删除它，empty函数则用于判断栈是否为空，若为空则返回true，否则返回false。

默认情况下stack容器衍生自deque，当我们定义一个stack容器实例时：

如果我们想从vector衍生出stack容器则需要按照如下方式进行定义：

本例是queue容器的一个示例程序，对于queue容器而言，它同样默认是衍生自deque容器的。与stack容器相同，queue同样有push、pop函数用于插入和删除元素，只不过不同的是stack只能操作栈顶，而queue是在队列尾部插入元素，在队列头部删除元素。stack容器用top函数访问栈顶元素，而queue没有栈顶这么一说，因而也就没有top函数了，我们想访问队列头的元素可以使用front函数，该函数只是访问并不删除元素。empty函数同样可以用于判断队列queue是否为空。

本例是priority_queue容器的示例程序，使用priority_queue容器我们只需要包含头文件queue就可以了。同样priority_queue容器可以用push和pop函数来插入和删除元素，priority_queue容器提供了top函数用于访问下一个元素，访问但不删除。对于整型的优先队列而言，默认是按照数据从大到小的顺序删除元素的。程序运行情况如下：

1 89 23 43 54 32 65 0 8 18 67 +↙
89 67 65 54 43 32 23 18 8 1 0

5、STL算法

STL提供了大量操作容器的算法，这些算法大致可以分为：排序、搜索、集合运算、数值处理和拷贝等，这些算法的实现是采用函数模板来实现的，函数模板类似于类模板。对于STL算法而言，算法是一样的，只是所处理的容器不同，只要使用合适的迭代器，就可以直接用算法操作容器了。

例1：

如果我们需要使用STL算法，则需要在头文件中包含algorithm头文件，在本程序中使用了四种STL算法：generate、replace_if、sort和for_each。下面我们来一一了解这四种算法的功能。

generate函数前面两个参数均为迭代器，分别指向开头和结尾，通过这两个迭代器，我们可以为num的10个元素赋值。由于num是整型的vector实例，因此要求generate函数的第三个参数返回值也为整型，因此我们将库函数rand作为第三个参数，用于生成随机数，其返回值是整型。

调用完generate函数之后，num中就分别填充了一些随机数值。replace_if前面两个参数还是两个迭代器，通过这两个迭代器我们可以对num进行遍历，遍历过程中会逐一判断元素是否为奇数，如果为奇数，则将其换为0。Replace_if要求第三个参数为一个返回bool类型的函数，为此我们专门设计了一个odd函数，用于判断数值是否为奇数，如果为奇数则返回true，否则返回false。因为num为int型vector实例，因此要求用来替换的元素也必须为int型，故replace_if函数最后一个参数必须为int型，在本例中我们直接使用0。

接着我们对num进行排序，sort函数前面两个参数仍然是迭代器，第三个参数是可选的，默认情况下sort将会以升序进行排序。本例中使用了第三个参数，第三个参数为compare函数的函数名。因为num为整型实例，因此compare函数的两个参数为整型的引用。同时由于sort函数要求第三个参数为返回一个bool类型的函数，因此compare也必须返回bool类型。本例中我们希望num以降序的方式排列，因此我们compare函数返回“a > b”。当我们返回“a < b”或者根本就不提供第三个参数时，函数将会以升序的形式排列num。

最后为了打印num中的所有元素，我们使用了for_each函数，当然如果使用循环根据下标或使用迭代器都是可以打印num中的元素的，只不过我们是想介绍一下for_each函数而已。for_each函数前面两个参数仍然是两个迭代器，通过这两个迭代器，我们就可以遍历num中的元素。for_each函数第三个参数用来完成打印操作，我们定义了一个display函数用于完成此操作。

在整个程序中我们一直没有使用任何循环就完成了整个操作，这是因为这四个函数中分别定义了内建的迭代操作，而我们只需要指明迭代的起始和终止位置即可。

STL中还提供了很多其它的算法，在今后的学习过程中，大家如果有需要可以去查找C++的类库手册。