首页 > 代码库 > 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第十一章 泛型算法