C++ STL 学习总结

看完《C++ premier》的第二部分，容器和算法，算是对C++中的STL有了一定的了解。总结起来，这里面涉及的主要概念有：容器、迭代器、适配器以及算法。

一、容器

容器容纳特定类型的对象的集合，例如一组整数，一组自定义类SalesItem。有些容器元素按照插入的顺序存放，读取元素时，可以利用存放顺序查找到它，这总容器称为顺序容器；有些容器元素在插入到容器中时，会给一个便于索引的键值，读取元素时，可以通过与元素关联的键值找到它，这种容器称为关联容器。

标准库定义了三种顺序容器，分别为vector、deque、list，它们在内存中不同的存储方式导致了他们具有不同的性能优势。Vector存放在一片连续的内存块中，因此它只能向后增长，如果需要在vector的中间插入新元素，则会导致插入位置起后面的所有元素都要往后迁移；另一方面由于它连续存储，因此随机访问元素很方便，支持下标操作和vec.at(n)操作（at比下标操作更安全一些，因为它会检查越界行为）。如果说vector是封装过的数组，那么list就是我们常说的链表，元素与元素之间通过指针相互连在一起，因此如果找准了位置，插入一个新元素（不论在list的什么位置）都只是敲断该位置原先的连接，然后把新元素跟这两段连接起来就好，而不必像vector那样劳师动众。但是，元素可能散落于内存的不同地方，所以元素并不存在所谓的“下标”，读取元素时只能通过遍历寻到。Deque（double-ended-queue）可以算得上是vector和list的中和了。它是由一小片一小片连续的内存连接起来的，每片连续的内存存放一定数量的元素，不够用的时候会添加新的内存块，因此deque在前面、后面添加元素都很方便。另外，deque也支持下标操作和at操作，但是效率比vector要慢很多。我们可以从添加、删除元素，访问元素、容器增长收缩这几个方面来比较这三种顺序容器。

1.       添加、删除元素

标准库提供了多种添加元素的方法，如前插入（push_front）、后插入（push_back）以及任意插入（insert）。由vector本身的存储特性决定了vector不提供push_front操作，而deque和list则提供，同时，三种顺序容器都提供push_back操作。Insert操作有三种，它们都必须首先提供插入的位置，表现为一个迭代器，元素将插入到该迭代器指向的位置前，插入的值有三种，一种是一个单值，一种是n个相同的值，最后一种由两个迭代器指定另一容器中的元素的范围。

同样的，标准库还提供了多种删除元素的方法，如前删除（pop_front）、后删除（pop_back）以及任意删除（erase），还有就是清空clear。同样，vector不提供pop_front操作，而deque和list则提供，它们都提供pop_back操作。Erase有两种，一种是删除单个元素，此时必须提供指向该元素的迭代器，一种是删除一段范围内的元素，该范围由两个迭代器表示。

2.       访问元素

Front和back函数分别返回容器的首个元素和末尾元素，list容器有关访问元素的操作就只有这两个了。而deque和vector还提供了下标操作和at操作，但是效率有所不同。由于deque是由多个内存块连接起来的，因此访问时必须跨内存访问，因此比vector要慢得多。

3.       容器的增长与收缩

有关容器大小的操作，三种顺序容器都提供了size()来返回容器中元素的数量，以及resize()来增长或减少容器的元素。Resize要求提供resize后的大小n，此时如果n小于原来的size()，超出的部分会被删除，如果n大于原来的size()，则新添加的元素有两种方式初始化：如果使用resize时还提供了另外一个初始值，新添加的元素被赋予该初始值；如果没有，则新添加的元素以该类型的默认值进行初始化。容器随着push和insert自增长，或者通过resize提供一个更大的值来扩充容量。在扩充容器容量方面，deque比vector要高效得多。当deque需要扩充容量时，它只须申请一小块新内存，然后把新申请的块与其他deque块连接起来，vector则必须申请一块比原先内存块更大的内存块，然后把原vector里面的数据复制到新内存块中，再销毁原来的内存块。Vector不支持把容器容量调小，删除元素或resize提供一个小一些的值，vector的内存块并不会自动收缩，相反的，由于deque是由很多小块组成的，当有空闲时，会销毁空闲的内存块，所以deque是自收缩的。Vector比deque多提供了两个操作，capacity()和reserve()，capacity返回当前vector的容量，而reserve()则通过提供一个值，指定vector应该开辟的内存块的大小。

这三种容器提供的操作总结如下：
 

关联容器有两种，一种是map，一种是set。map中元素是以<key, value>对的方式加入到map中来的，在map中，通过key找到value。set中只有key，每个key只出现一次（map也一样）。关联容器的元素根据键的次序排列，在迭代遍历关联容器时，我们可以确保按键的顺序访问元素，而与元素在容器中的存放位置、插入时间无关。关联容器不提供顺序容器中的push_back、push_front、pop_back、pop_front、back、front操作。

有一种专门的数据类型pair用于表示<key, value>对。可以通过make_pair( t1, t2)直接生成pair，或通过构造函数初始化一个pair。pair中有两个公开成员first和second，分别表示他的两个成员。

Map中的元素正是pair数据类型，它及其成员在map中有另外一种定义，如下：

 

其提供的插入、删除、查找并读取元素的方法如下：

 

另外值得一提的是map提供的下标操作（通过key索引），如下例子：

 

map<string, int> word_count; word_count["anna"] = 1;

 

 

以上语句 将发生以下事情：

（1）在word_count中查找键为"anna"的元素，没有找到（word_count目前是个空map）；

（2）生成一个新的键-值对，它的键是const string类型的对象，保存anna，而它的值 则采用值初始化，即int的值初始化为0；

（3）将这个新的键-值对插入到word_count中；

（4）读取新插入的元素，并将它的值赋为1。

下标操作实际上相当于结合了find和insert的动作，在某些情况下，使用下标操作会使代码显得非常的简洁，但是它有一个副作用：如果该键不在map中，那么下标操作会插入一个具有该键的新元素并自动初始化，有些时候这并非我们所希望的。

set类型只是单纯的键的集合，当我们只想知道一个值是否存在时，用set容器是最适合的。在set中，每个键只能出现一次。它提供map操作总结表中的所有操作。

如果希望map中一个键对应多个值，就如一个作者对应多篇论文那样，则需要使用multimap。multimap跟map的操作基本相同，除了查找键对应的元素现在可能变成多个值了，因此有必要考虑如何找出所有与key对应的value值。总共有三种：
策略1：使用find和count操作(假设contactor是一个以人名为键，电话号码为值的map） string search_item( "eva siu" ); typedef multimap<string, string>::size_type sz_type; sz_type entries = contactors.count(search_item); multimap<string, string>::iterator iter = contactors.find(search_item); for( sz_type cnt = 0; cnt!=entries; ++cnt, ++iter ) cout<<iter->second<<endl;

 

策略2、3：使用返回迭代器的关联容器操作

 也就是说，可以使用lower_bound(k)各upper_bound(k)来确定包含健k的范围，或者直接使用equal_range(k)。

 

 

 

二、迭代器

迭代器是一种检查容器内元素并遍历元素的数据类型，所有的标准库容器都定义了相应的迭代器类型，例如装了int元素的vector的迭代器iter，声明如下：

vector<int>::iterator iter;

获取容器的迭代器方法如下： vector<int> vec(10); vector<int>::iterator vec_begin = vec.begin(); vector<int>::iterator vec_end = vec.end(); vector<int>::iterator vec_last = vec.rend(); vector<int>::iterator vec_front = vec.rbegin();

 

一般的迭代器都提供自增（iter++, ++iter）、自减（iter--, --iter）、解引用（*iter, iter->mem）、比较相等与否（iter1==iter2, iter1 != iter2）的操作。而vector、deque由于其连续内存的优势，其迭代器还能像下标那样加减一个整数值、加减一个迭代器以及比较大小。

 

 

我们通常使用一对迭代器来标识一个范围，这个范围是一个左闭合区间，即[begin, end)区间。

迭代器常常被用于作为算法（STL的另一个重要部分）的输入，通常用于标识范围或指定位置，但有时候算法需要对容器作出修改（写容器算法），C++中定义了另外三种迭代器：

1.       插入迭代器：这类迭代器与容器绑定在一起，实现在容器中插入元素的功能

2.       iostream迭代器：与IO流绑定在一起，用于迭代遍历所关联的IO流

3.       反向迭代器：实现从后向前遍历。

插入迭代器又有三种，分别是front_inserter，要求关联的容器必须提供push_front的操作，该函数创建一个迭代器，调用它所关联的基础容器的push_front成员函数代替赋值操作；back_inserter函数创建一个迭代器，调用它所关联的基础容器的push_back成员函数代替赋值操作；inserter将产生在指定位置实现插入的迭代器。插入迭代器更多的是作为算法的输入参数，例如将算法的计算结果（修改了的容器内容）插入到插入迭代器中。

iostream迭代器分为istream_iterator和ostream_iterator，由于它是与流绑定在一起的，因此不存在逆方向，流过去了就没了。istream_iterator和ostream_iterator分别有两种声明方式，分别是

 

istream_iterator<T> in_iter(cin); //与某输入流绑定 istream_iterator<T> eof; // istream_iterator对象的超出末端迭代器 ostream_iterator<T> out_iter( cout ); //与某输出流绑定 ostream_iterator<T> out(cout, delim); //输出的时候写时用delim分隔一个个T

 

反向迭代器以容器的最后一个元素为起点，以容器第一个元素的前端元素为终点，自增相当于正常迭代器的自减，其范围可以这样表示[end-1, begin-1)。

 

三、适配器

适配器是标准库中通用的概念，包括容器适配器，迭代器适配器，函数适配器。本质上，适配器是使一事物的行为类似于另一事物的行为的一种机制。

容器适配器让一种已存在的容器类型采用另外一种不同的抽象类型的工作方式实现，但是该抽象工作方式的实现依赖于原容器类型所能提供的操作。

顺序容器适配器有stack、queue、priority_queue。

Stack是一种后进行出的数据结构，提供的操作只有pop(), push(), top(), empty()等操作，只在栈的顶端进行，因此三种顺序容器的操作均能支持，但它默认基于deque实现。Queue是一种先进先出的数据结构，提供的操作有pop要求能够push_back，又要能够pop_front，因此vector不适合作为queue的基础容器。Priority_queue在插入元素的时候会考虑其优先级，通常优先级由该类型默认的<来体现。

插入迭代器是一种迭代器适配器，它带有一个容器参数，并生成迭代器，用于指定在容器中插入元素。

至于函数适配器，目前还没有遇到过，这里记个空。

 

四、泛型算法

标准容器定义了很少的操作，基本上只涉及添加删除元素、访问元素、获取容器大小、重设容器大小，以及获取指向容器第一个元素后最后一个元素的下一位置的迭代器。但是除了这些操作，我们往往还需要更多的操作，例如查找某个特定的元素，给顺序容器排序，替代具有某种特性的元素的值等等。标准库并没有为每种容器定义实现这些操作的成员函数，而是定义了一组泛型算法：因为它们实现共同的操作，因此称之为算法；而“泛型”指的是它们可以作用在多种容器类型上——不但可以作用于vector或者list这种标准库容器，还可以用在内置数组类型甚至其他类型的序列上，这些算法均在头文件<algorithm>中定义。

算法一般不直接接受某个容器作为输入参数，而是通过迭代器指定容器的某个位置或范围与某个容器关联起来，其中迭代器的范围仍是遵循左闭合区间的约定。

根据算法对容器的使用修改情况，可以将算法分为：

1.       只读算法

只读算法只读取其输入范围内的元素，而不会修改其值，例如像find（查找某一特定元素），count_if（计算符合某一要求的元素的个数）等。此时传递给算法的迭代器可以是const的。

2.       写容器元素算法

写容器算法可能会修改容器中元素的值，如unique，unique函数将无重复的元素往前复制，从而覆盖相邻的重复元素，最后返回一个迭代器，表示无重复的值范围的结束，这种类型的算法不改变容器的大小，只修改容器中元素的值；又如fill，用一个值替换输入范围内的元素的值。另一种写容器元素算法可能会往容器中添加新元素，如fill的另一版本fill_n，要求从某个位置起连续加入n个元素，此时传递给算法的迭代器必须是插入迭代器。

3.       对容器元素重新排序的算法

对容器元素重新排序的算法不修改容器的大小，但是修改容器范围内的元素的值，例如前面的unique算法，或者如sort对容器范围内的元素进行重新排序等，此时传递给算法的迭代器不能是const的。

可以看到，不同算法对传递给他的迭代器有要求各有不同，find只要求其迭代器具有读的功能，而sort则要求其迭代器有读、写和随机访问的能力，根据算法要求可以将迭代器分成5个类别。

1.       输入迭代器：读，不能写；只支持自增运算，其解引用只能作为右操作数。

输入迭代器可用于读取容器中的元素，但不能保证能支持容器的写入操作，而且，输入迭代器只能顺序使用，一旦输入迭代器自增了，就无法再用它检查之前的元素。istream_iterator就是这样一种迭代器。

2.       输出迭代器：写，不能读；只支持自增运算，其解引用只能作为左操作数。

输出迭代器可用于向容器写入元素，但是不保证能支持读取容器内容。输出迭代器一般用做算法的第三个形参，标记起始写入的位置。例如copy（_copy类的）算法使用一个输出迭代器作为它的第三个实参，将元素复制到输入迭代器指定的目标位置。ostream_iterator是一种输出迭代器。

3.       前向迭代器：读和写，只支持自增运算。

前向迭代器支持输入迭代器和输出迭代器提供的所有操作，除此之外，还支持对同一元素的多次读写。可以通过复制向前迭代器来记录序列中的一个位置，以便将来返回此处。

4.       双向迭代器：读和写，支持自增、自减运算

比前向迭代器多了—运算。

5.       随机访问迭代器：读和写；支持完整的迭代器算术运算。

除了自增自减运算外，还提供加减一个整数获得指向新位置的迭代器，两个迭代器相减获得位置差等。

可以看到，迭代器的分类与其关联的容器类型相关。Vector、deque、string迭代器是随机访问迭代器，而list、map、set关联的迭代器是双向迭代器。

算法的形参一般有以下几种模式：

Alg( beg, end, … ) [beg, end)标记算法接收的容器的范围

Alg( beg, end, dest, … ) dest指定存储输出数据的目标对象

Alg( beg, end, beg2, … ) beg2标记算法的第二个接收范围的起始位置

Alg( beg, end, beg2, end2, … ) [beg2, end2) 标记算法的第二个接收范围。

算法可能还会接收一些函数作为其参数，以实现自定义的一些比较、筛选工具。

另外，需要注意的是，由于list的实现机理有别于vector和deque，为了充分利用它的结构特征以提高算法的效率，list中提供了<algorithm>中提供的一些操作，这些操作针对list的结构特征而设计，一般情况下优先选择list自己提供的函数。

《c++ premier》第二部分总结起来基本上就是这样了。至于<algorithm>中提供的一些算法我也没有完全了解透，可能需要在应用中慢慢熟悉起来。还有就是有关提供给算法的函数参数，有些是Predicat，有些是BinPred、UnaryPred，有些是Comp，有些是StrickWeakOrdering，这些内容不知道在哪里可以看到更多的介绍呢？