C++ 学习笔记第十一章（泛型算法）

基本概念：

泛型算法本身从不执行容器操作，只是单独依赖迭代器和迭代器操作实现。

算法也许会改变存储在容器中的元素的值，也许会在容器中移动元素，但是，算法从不直接添加或删除元素。

头文件：

#include

#include

1、只读算法

//把string类型的vector容器中的元素连接起来。

string sum = accumulate(v.begin(), v.end(), string(""));

//把int型的vector容器中元素累加

int sum = accumulate(v.begin(), v.end(), 100); //100为起点累加元素

这类的第三个元素是指定的元素类型，必须要有，前两个是迭代器范围。

find_first_of算法

这个算法带有两对迭代器参数来标记两段元素范围，在第一段范围内查找与

第二段范围中任意元素匹配的元素，然后返回一个迭代器，指向第一个匹配的元

素。如果找不到元素，则返回第一个范围的 end 迭代器。假

设 roster1 和 roster2 是两个存放名字的 list 对象，可使

用 find_first_of 统计有多少个名字同时出现在这两个列表中：

 // program for illustration purposes only: 

     // there are much faster ways to solve this problem 

     size_t cnt = 0; 

     list::iterator it = roster1.begin(); 

     // look in roster1 for any name also in roster2 

     while   ((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; 

在 while 的第一次循环中，

遍历整个 roster1 范围。第二次以及后续的循环迭代则只考虑 roster1 中尚未

匹配的部分。 

循环条件检查 find_first_of 的返回值，判断是否找到匹配的名字。如果

找到一个匹配，则使计数器加 1,同时给 it 加 1，使它指向 roster1 中的下一

个元素。很明显可知，当不再有任何匹配时，find_first_of 返

回 roster1.end()，完成统计。

2、写算法

写入输入序列的元素

写入到输入序列的一个简单算法是 fill 函数，考虑如下例子：

fill(vec.begin(), vec.end(), 0); // reset each element to 0 

 // set subsequence of the range to 10 

 fill(vec.begin(), vec.begin() + vec.size()/2, 10); 不检查写入操作的算法

vector vec; // empty vector 

 // disaster: attempts to write to 10 (nonexistent) elements in vec 

 fill_n(vec.begin(), 10, 0); 该操作很危险，vector可能没有10个元素

back_inserter 函数是迭代器适配器。与容器适配器（）一样，迭代器适配器使用一个对象作为实参，并生成一个适应其实参行为的新对象。在本例中，传递给 back_inserter 的实参是一个容器的引用。back_inserter 生成一个绑定在该容器上的插入迭代器。在试图通过这个迭代器给元素赋值时，赋值运算将调用 push_back 在容器中添加一个具有指定值的元素。使用 back_inserter 可以生成一个指向 fill_n 写入目标的迭代器：

vector vec; // empty vector 

 // ok: back_inserter creates an insert iterator that adds elements to vec 

fill_n (back_inserter(vec), 10, 0); // appends 10 elements to vec

现在，fill_n 函数每写入一个值，都会通过 back_inserter 生成的插入迭代器实现。效果相当于在 vec 上调用 push_back，在 vec 末尾添加 10 个元素，每个元素的值都是 0。

写入到目标迭代器的算法

vector ivec; // empty vector 

// copy elements from ilst into ivec 

copy (ilst.begin(), ilst.end(), back_inserter(ivec));

copy 从输入范围中读取元素，然后将它们复制给目标 ivec。

算法的 _copy 版本

replace 算法就是一个很好的例子。该算法对输入序列做读写操作，将序列中特定的值替换为新的值。该算法带有四个形参：一对指定输入范围的迭代器和两个值。每一个等于第一值的元素替换成第二个值。

// replace any element with value of 0 by 42 

 replace(ilst.begin(), ilst.end(), 0, 42);

 这个调用将所有值为 0 的实例替换成 42。如果不想改变原来的序列，则调 用 replace_copy。这个算法接受第三个迭代器实参，指定保存调整后序列的目 标位置。

 // create empty vector to hold the replacement 

 vector ivec; 

 // use back_inserter to grow destination as needed 

replace_copy (ilst.begin(), ilst.end(), back_inserter(ivec), 0, 42); 

调用该函数后，ilst 没有改变，ivec 存储 ilst 一份副本，而 ilst 内所 有的 0 在 ivec 中都变成了 42。

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

unique 的使用

单词按次序排列后，现在的问题是：让故事中所用到的每个单词都只保留一个副本。unique 算法很适合用于解决这个问题，它带有两个指定元素范围的迭代器参数。该算法删除相邻的重复元素，然后重新排列输入范围内的元素，并且返回一个迭代器，表示无重复的值范围的结束。

调用 unique 后，vector 中存储内容是：

注意，words 的大小并没有改变，依然保存着 10 个元素；只是这些元素的顺序改变了。调用 unique“删除”了相邻的重复值。给“删除”加上引号是因为 unique 实际上并没有删除任何元素，而是将无重复的元素复制到序列的前端，从而覆盖相邻的重复元素。unique 返回的迭代器指向超出无重复的元素范围末端的下一位置。

如果要删除重复的项，必须使用容器操作，在本例中调用 erase 实现该功能。这个函数调用从 end_unique 指向的元素开始删除，直到 words 的最后一个元素也删除掉为止。调用之后，words 存储输入的 8 个不相同的元素。

排序算法

标准库定义了四种不同的排序算法，上面只使用了最简单的 sort 算法，使 words 按字典次序排列。除了 sort 之外，标准库还定义了 stable_sort 算法，stable_sort 保留相等元素的原始相对位置。通常，对于已排序的序列，我们并不关心其相等元素的相对位置，毕竟，这些元素是相等的。但是，在这个应用中，我们将“相等”定义为“相同的长度”，有着相同长度的元素还能以字典次序的不同而区分。调用 stable_sort 后，对于长度相同的元素，将保留其字典顺序。

// sort words by size, but maintain alphabetic order for words of the same size stable_sort(words.begin(), words.end(), isShorter);

调用后，words 中的元素按长度大小排序，而长度相同的单词则仍然保持字典顺序：

现在此 vector 对象已经按单词长度排序，剩下的问题就是统计长度不小于 6 的单词个数。使用 count_if 算法处理这个问题：

vector::size_type wc = count_if(words.begin(), words.end(), GT6);

了解程序的细节之后，下面是完整的程序：

// comparison function to be used to sort by word length 

 bool isShorter(const string &s1, const string &s2) 

 {

          return s1.size() < s2.size(); 

 }

 // determine whether a length of a given word is 6 or more 

 bool GT6(const string &s)

 {

 return s.size() >= 6;

 }

 int main() {

 vector words; 

 // copy contents of each book into a single vector string next_word;

 while (cin >> next_word) 

{ 

  // insert next book's contents at end of words 

 words.push_back(next_word); 

 } 

 // sort words alphabetically so we can find the duplicates 

 sort (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 the unique range; * erase uses a vector operation to remove the nonunique elements */

 vector::iterator end_unique = unique(words.begin(), words.end()); words.erase(end_unique, words.end()); 

 // sort words by size, but maintain alphabetic order for words of the same size stable_sort(words.begin(), words.end(), isShorter); 

 vector::size_type wc = count_if (words.begin(), words.end(), GT6); 

 cout << wc << " " << make_plural(wc, "word", "s") << " 6 characters or longer" << endl;

 

 return 0; 

 }