首页 > 代码库 > C++primer第十一章 泛型算法
C++primer第十一章 泛型算法
标准库容器定义的操作非常少。标准库没有给容器添加大量的功能函数,而是选择提供一组算法,这些算法大都不依赖特定的容器类型,是“泛型”的,可作用在不同类型的容器和不同类型的元素上。
因为它们实现共同的操作,所以称之为“算法”;而“泛型”指的是它们可以操作在多种容器类型上——不但可作用于 vector 或 list 这些标准库类型,还可用在内置数组类型、甚至其他类型的序列上。
11.1. 概述
假设有一个 int 的 vector 对象,名为 vec,我们想知道其中包含某个特定值。解决这个问题最简单的方法是使用标准库提供的 find 运算:
// value we‘ll look forint search_value = http://www.mamicode.com/42;// call find to see if that value is presentvector<int>::const_iterator result = find(vec.begin(), vec.end(), search_value); // report the resultcout << "The value " << search_value << (result == vec.end() ? " is not present" : " is present") << endl;
由于 find 运算是基于迭代器的,因此可在任意容器中使用相同的 find 函数查找值。
// call find to look through elements in a listlist<int>::const_iterator result = find(lst.begin(), lst.end(), search_value);cout << "The value " << search_value << (result == lst.end() ? " is not present" : " is present") << endl;
类似地,由于指针的行为与作用在内置数组上的迭代器一样,因此也可以使用 find 来搜索数组:
int ia[6] = {27, 210, 12, 47, 109, 83};int search_value = http://www.mamicode.com/83;int *result = find(ia, ia + 6, search_value);cout << "The value " << search_value << (result == ia + 6 ? " is not present" : " is present") << endl;
算法如何工作
find 必须包含以下步骤:
1. 顺序检查每个元素。
2. 如果当前元素等于要查找的值,那么返回指向该元素的迭代器。
3. 否则,检查下一个元素,重复步骤 2,直到找到这个值,或者检查完所有的元素为止。
4. 如果已经到达集合末尾,而且还未找到该值,则返回某个值,指明要查找的值在这个集合中不存在
标准算法固有地独立于类型
算法的明确要求如下:
1. 需要某种遍历集合的方式:能够从一个元素向前移到下一个元素。
2. 必须能够知道是否到达了集合的末尾。
3. 必须能够对容器中的每一个元素与被查找的元素进行比较。
4. 需要一个类型指出元素在容器中的位置,或者表示找不到该元素。
迭代器将算法和容器绑定起来
泛型算法用迭代器来解决第一个要求:遍历容器。
11.2. 初窥算法
使用泛型算法必须包含 algorithm 头文件:
#include <algorithm>
标准库还定义了一组泛化的算术算法(generalized numeric algorithm),其命名习惯与泛型算法相同。
#include <numeric>
11.2.1. 只读算法
许多算法只会读取其输入范围内的元素,而不会写这些元素。
find 就是一个这样的算法。另一个简单的只读算法是 accumulate,该算法在 numeric 头文件中定义。
// sum the elements in vec starting the summation with the value 42int sum = accumulate(vec.begin(), vec.end(), 42);
将 sum 设置为 vec 的元素之和再加上 42。
题目:将0~1234存储到vector中,并计算其总和。
find_first_of 的使用
这个算法带有两对迭代器参数来标记两段元素范围,在第一段范围内查找与第二段范围中任意元素匹配的元素,然后返回一个迭代器,指向第一个匹配的元素。如果找不到元素,则返回第一个范围的 end 迭代器。
// program for illustration purposes only:// there are much faster ways to solve this problemsize_t cnt = 0;list<string>::iterator it = roster1.begin();// look in roster1 for any name also in roster2while ((it = find_first_of(it, roster1.end(), roster2.begin(), roster2.end()))!= roster1.end()) { ++cnt; // we got a match, increment it to look in the rest of roster1 ++it;}cout << "Found " << cnt << " names on both rosters" << endl;
11.2.2. 写容器元素的算法
一些算法写入元素值。在使用这些算法写元素时要当心,必须确保算法所写的序列至少足以存储要写入的元素。
写入输入序列的元素
写入到输入序列的算法本质上是安全的——只会写入与指定输入范围数量相同的元素。
fill(vec.begin(), vec.end(), 0); // reset each element to 0// set subsequence of the range to 10fill(vec.begin(), vec.begin() + vec.size()/2, 10);
不检查写入操作的算法
fill_n 函数带有的参数包括:一个迭代器、一个计数器以及一个值。
fill_n 函数假定对指定数量的元素做写操作是安全的。
vector<int> vec; // empty vector// disaster: attempts to write to 10 (nonexistent) elements in vecfill_n(vec.begin(), 10, 0);
这个 fill_n 函数的调用将带来灾难性的后果。我们指定要写入 10 个元素,但这些元素却不存在——vec 是空的。
引入 back_inserter
确保算法有足够的元素存储输出数据的一种方法是使用插入迭代器。插入迭代器是可以给基础容器添加元素的迭代器。
back_inserter 的程序必须包含 iterator 头文件。
back_inserter 生成一个绑定在该容器上的插入迭代器。
vector<int> vec; // empty vector// ok: back_inserter creates an insert iterator that adds elements to vecfill_n (back_inserter(vec), 10, 0); // appends 10 elements to vec
写入到目标迭代器的算法
第三类算法向目标迭代器写入未知个数的元素。
这类算法中最简单的是 copy 函数。copy 带有三个迭代器参数:头两个指定输入范围,第三个则指向目标序列的一个元素。
vector<int> ivec; // empty vector// copy elements from ilst into iveccopy (ilst.begin(), ilst.end(), back_inserter(ivec));
通常,如果要以一个已存在的容器为副本创建新容器,更好的方法是直接用输入范围作为新构造容器的初始化式:
// better way to copy elements from ilstvector<int> ivec(ilst.begin(), ilst.end());
算法的 _copy 版本
有些算法提供所谓的“复制(copying)”版本。这些算法对输入序列的元素做出处理,但不修改原来的元素,而是创建一个新序列存储元素的处理结果。
replace 算法就是一个很好的例子。该算法对输入序列做读写操作,将序列中特定的值替换为新的值。该算法带有四个形参:一对指定输入范围的迭代器和两个值。每一个等于第一值的元素替换成第二个值。
// replace any element with value of 0 by 42replace(ilst.begin(), ilst.end(), 0, 42);
这个调用将所有值为 0 的实例替换成 42。如果不想改变原来的序列,则调用 replace_copy。这个算法接受第三个迭代器实参,指定保存调整后序列的目标位置。
// create empty vector to hold the replacementvector<int> ivec;// use back_inserter to grow destination as neededreplace_copy (ilst.begin(), ilst.end(), back_inserter(ivec), 0, 42);
11.2.3. 对容器元素重新排序的算法
假设我们要分析一组儿童故事中所使用的单词。例如,可能想知道它们使用了多少个由六个或以上字母组成的单词。每个单词只统计一次,不考虑它出现的次数,也不考虑它是否在多个故事中出现。要求以长度的大小输出这些单词,对于同样长的单词,则以字典顺序输出。
1. 去掉所有重复的单词。
2. 按单词的长度排序。
3. 统计长度等于或超过 6 个字符的单词个数。
去除重复
// sort words alphabetically so we can find the duplicatessort(words.begin(), words.end());/* eliminate duplicate words:* unique reorders words so that each word appears once in the* front portion of words and returns an iterator one past theunique range;* erase uses a vector operation to remove the nonunique elements*/vector<string>::iterator end_unique = unique(words.begin(), words.end());words.erase(end_unique, words.end());
vector 对象包含每个故事中使用的所有单词。首先对此 vector 对象排序。sort 算法带有两个迭代器实参,指出要排序的元素范围。这个算法使用小于(<)操作符比较元素。
unique 的使用
注意,words 的大小并没有改变,依然保存着 10 个元素;只是这些元素的顺序改变了。调用 unique“删除”了相邻的重复值。给“删除”加上引号是因为 unique 实际上并没有删除任何元素,而是将无重复的元素复制到序列的前端,从而覆盖相邻的重复元素。unique 返回的迭代器指向超出无重复的元素范围末端的下一位置。
使用容器操作删除元素
如果要删除重复的项,必须使用容器操作,在本例中调用 erase 实现该功能。这个函数调用从 end_unique 指向的元素开始删除,直到 words 的最后一个元素也删除掉为止。调用之后,words 存储输入的 8 个不相同的元素。
定义需要的实用函数
下一个子问题统计长度不小于 6 的单词个数。为了解决这个问题,需要用到另外两个泛型算法:stable_sort 和 count_if。使用这些算法,还需要一个配套的实用函数,称为谓词。谓词是做某些检测的函数,返回用于条件判断的类型,指出条件是否成立。
// comparison function to be used to sort by word lengthbool isShorter(const string &s1, const string &s2){ return s1.size() < s2.size();}
// determine whether a length of a given word is 6 or morebool GT6(const string &s){ return s.size() >= 6;}
排序算法
上面只使用了最简单的 sort 算法,使 words 按字典次序排列。除了 sort 之外,标准库还定义了 stable_sort 算法,stable_sort 保留相等元素的原始相对位置。
// sort words by size, but maintain alphabetic order for words of the same sizestable_sort(words.begin(), words.end(), isShorter);
统计长度不小于 6 的单词
vector<string>::size_type wc = count_if(words.begin(), words.end(), GT6);
将全部程序段放在一起
11.3. 再谈迭代器
C++ 语言还提供了另外三种迭代器:
• 插入迭代器:这类迭代器与容器绑定在一起,实现在容器中插入元素的功能。
• iostream 迭代器:这类迭代器可与输入或输出流绑定在一起,用于迭代遍历所关联的 IO 流。
• 反向迭代器:这类迭代器实现向后遍历,而不是向前遍历。所有容器类型都定义了自己的 reverse_iterator 类型,由 rbegin 和 rend 成员函数返回。
11.3.1. 插入迭代器
• back_inserter,创建使用 push_back 实现插入的迭代器。
• front_inserter,使用 push_front 实现插入。
• inserter,使用 insert 实现插入操作。除了所关联的容器外,inserter还带有第二实参:指向插入起始位置的迭代器。
front_inserter 需要使用 push_front
front_inserter 的操作类似于 back_inserter:该函数将创建一个迭代器,调用它所关联的基础容器的 push_front 成员函数代替赋值操作。
inserter 将产生在指定位置实现插入的迭代器
inserter 适配器提供更普通的插入形式。这种适配器带有两个实参:所关联的容器和指示起始插入位置的迭代器。
// position an iterator into ilstlist<int>::iterator it = find (ilst.begin(), ilst.end(), 42);// insert replaced copies of ivec at that point in ilstreplace_copy (ivec.begin(), ivec.end(),inserter (ilst, it), 100, 0);
11.3.2. iostream 迭代器
流迭代器的定义
任何已定义输入操作符(>> 操作符)的类型都可以定义 istream_iterator。类似地,任何已定义输出操作符(<< 操作符)的类型也可定义 ostream_iterator。
istream_iterator<int> cin_it(cin); // reads ints1 from cinistream_iterator<int> end_of_stream; // end iterator value// writes Sales_items from the ofstream named outfile// each element is followed by a spaceofstream outfile;ostream_iterator<Sales_item> output(outfile, " ");
istream_iterator 对象上的操作
istream_iterator<int> in_iter(cin); // read ints from cinistream_iterator<int> eof; // istream "end" iterator// read until end of file, storing what was read in vecwhile (in_iter != eof)// increment advances the stream to the next value// dereference reads next value from the istream vec.push_back(*in_iter++);
ostream_iterator 对象和 ostream_iterator 对象的使用
// write one string per line to the standard outputostream_iterator<string> out_iter(cout, "\n");// read strings from standard input and the end iteratoristream_iterator<string> in_iter(cin), eof;// read until eof and write what was read to the standard outputwhile (in_iter != eof)// write value of in_iter to standard output// and then increment the iterator to get the next value from cin *out_iter++ = *in_iter++;
流迭代器的限制
• 不可能从 ostream_iterator 对象读入,也不可能写到istream_iterator 对象中。
• 一旦给 ostream_iterator 对象赋了一个值,写入就提交了。赋值后,没有办法再改变这个值。此外,ostream_iterator 对象中每个不同的值都只能正好输出一次。
• ostream_iterator 没有 -> 操作符。
与算法一起使用流迭代器
istream_iterator<int> cin_it(cin); // reads ints from cinistream_iterator<int> end_of_stream; // end iterator value// initialize vec from the standard input:vector<int> vec(cin_it, end_of_stream);sort(vec.begin(), vec.end());// writes ints to cout using " " as the delimiterostream_iterator<int> output(cout, " ");// write only the unique elements in vec to the standard outputunique_copy(vec.begin(), vec.end(), output);
11.3.3. 反向迭代器
假设有一个 vector 容器对象,存储 0-9 这 10 个以升序排列的数字:
vector<int> vec;for (vector<int>::size_type i = 0; i != 10; ++i) vec.push_back(i); // elements are 0,1,2,...9
下面的 for 循环将以逆序输出这些元素:
// reverse iterator of vector from back to frontvector<int>::reverse_iterator r_iter;for (r_iter = vec.rbegin(); // binds r_iter to last element r_iter != vec.rend(); // rend refers 1 before 1st element ++r_iter) // decrements iterator one element cout << *r_iter << endl; // prints 9,8,7,...0
11.4. 泛型算法的结构
11.4.1. 算法的形参模式
alg (beg, end, other parms);
alg (beg, end, dest, other parms);
alg (beg, end, beg2, other parms);
alg (beg, end, beg2, end2, other parms);
11.4.2. 算法的命名规范
区别带有一个值或一个谓词函数参数的算法版本
这些算法通常要用到标准关系操作符:== 或 <。其中的大部分算法会提供第二个版本的函数,允许程序员提供比较或测试函数取代操作符的使用。
sort (beg, end); // use < operator to sort the elementssort (beg, end, comp); // use function named comp to sort the elements
区别是否实现复制的算法版本
此版本的算法在名字中添加了_copy 后缀:
reverse(beg, end);reverse_copy(beg, end, dest);
11.5. 容器特有的算法
list 容器上的迭代器是双向的,而不是随机访问类型。由于 list 容器不支持随机访问,因此,在此容器上不能使用需要随机访问迭代器的算法。
lst.merge(lst2) lst.merge(lst2, comp) | |
将 lst2 的元素合并到 lst 中。这两个 list 容器对象都必 须排序。lst2 中的元素将被删除。合并后,lst2 为空。返 回 void 类型。第一个版本使用 < 操作符,而第二个版本则 使用 comp 指定的比较运算 | |
lst.remove(val) lst.remove_if(unaryPred) | |
调用 lst.erase 删除所有等于指定值或使指定的谓词函数 返回非零值的元素。返回 void 类型 | |
lst.reverse() | 反向排列 lst 中的元素 |
lst.sort | 对 lst 中的元素排序 |
lst.splice(iter, lst2) | |
lst.splice(iter, lst2, iter2) | |
lst.splice(iter, beg, end) | |
将 lst2 的元素移到 lst 中迭代器 iter 指向的元素前面。 在 lst2 中删除移出的元素。第一个版本将 lst2 的所有元 素移到 lst 中;合并后,lst2 为空。lst 和 lst2 不能是 同一个 list 对象。第二个版本只移动 iter2 所指向的元 素,这个元素必须是 lst2 中的元素。在这种情况中,lst 和 lst2 可以是同一个 list 对象。也就是说,可在一个 list 对象中使用 splice 运算移动一个元素。第三个版本移动迭 代器 beg 和 end 标记的范围内的元素。beg 和 end 照例必 须指定一个有效的范围。这两个迭代器可标记任意 list 对 象内的范围,包括 lst。当它们指定 lst 的一段范围时,如 果 iter 也指向这个范围的一个元素,则该运算未定义。 | |
lst.unique() lst.unique(binaryPred) | |
调用 erase 删除同一个值的团结副本。第一个版本使用 == 操作符判断元素是否相等;第二个版本则使用指定的谓词函 数实现判断 |
C++primer第十一章 泛型算法