第十一章 泛型算法

1.      在大多数情况下,每个算法都需要使用(至少)两个迭代器来指出该算法操纵的元素范围,第一个迭代器指向第一个元素,而第二个迭代器则指向最后一个元素的下一个位置.第二个迭代器(有时也被称为超出末端迭代器)所指向的元素本身不是要操作的元素,而被用作终止遍历的哨兵.

2.      算法永不执行容器提供的操作;泛型算本身从不执行容器的操作,只是单独依赖迭代器和迭代器操作的实现

3.      泛型算法必须包含: #include

          标准库还定义了一种泛化的算术算法,其命名习惯与泛型算法相同.使用它们时,要包含如下头文件: #include <numeric>.

          除了少数算法外,所有算法都在一段范围内的元素上操作,我们将这段范围称为”输入范围”.(他们总是指向要处理的第一个元素和最后一个元素的下一个位置的迭代器),另外理解这些算法的最基本的方法是了解该算法是否读元素,写元素,或者对元素进行重新排序.

4.常见的泛型算法:

◆find(beg,end,val)//查找从beg到end中值为val的元素,如果找到,则返回该元素对应的迭代器,否则返回end

◆accumulate(beg,end,val)//将beg到end之间的元素相加,并加上val.返回累加的结果.( 用于指定累加起始值的第三个实参是必要的,因为accumulate对将要累加的元素类型一无所知.)

◆find_first_of(beg1,end1,beg,end)//查找beg1到end1之间的元素出现在beg到end的个数,查找成功,返回一个指向第一个匹配的元素的迭代器,否则返回第一个范围的end迭代器(这句根据我的理解是,返回需查找的元素本身的迭代器).在这里有中的例子为证:

      

vector<string>vect_string;

       vect_string.push_back("liming");

       vect_string.push_back("andy");

       vect_string.push_back("zhangxueyou");

       vect_string.push_back("guofucheng");



       string person_Name;

       vector<string>vect_other_string;

       while (cin>>person_Name)

       {

              vect_other_string.push_back(person_Name);

       }



       int count = 0;

       vector<string>::iterator iter = vect_string.begin();

       while ((iter = (find_first_of(iter,vect_string.end(),vect_other_string.begin(),vect_other_string.end()))) != vect_string.end())

       {

              iter++;

              count++;

       }

          cout<<"相同元素的个数为:"<<count<<endl;

假设输入为:

chenglong

andy

ctrl+z程序将会返回:相同元素的个数为:1

注意:这里需要重点说明的一点是:假若我们第一次输入的元素不在vect中则返回end,则循环结束.就没有必要继续对比.也就不会输出”相同元素个数为:1”,因此,如果我们把它理解为返回当前元素就可以得到结果.(这里只是我个人的理解,欢迎拍砖)

 

◆fill(beg,end,val)//初始化beg到end的元素为val

注意:对于指定数目的元素做写入运算,或者写到目标迭代器的算法,都不检查目标的大小是否足以存储要写入的元素

确保算法有足够的元素存储输出数据的一种方法是使用插入迭代器.插入迭代器是可以给基础容器添加元素的迭代器.

◆back_inserter(vec)//生成一个绑定在该容器上的插入迭代器.

◆sort(beg,end)//对beg到end的元素进行排序

◆unique(beg,end)//删除相邻的重复的元素,然后重新排列输入范围内的元素,并返回迭代器,表示无重复值范围的结束

注意:算法不直接改变容器的大小.如果需要添加或删除元素,则必须使用容器操作

◆stable_sort(beg,end,fun)://将 beg到end的元素按照fun函数约定的规则进行排序其中fun必须接受两个参数.

◆connt_if(beg,end,fun)//将beg到end的元素按照fun函数的约定进行排序,fun函数必须是具有单个元素类型的实参.返一个使得条件成立的个数

◆fill_n(back_insert(vec),10,0)//在vec的末尾添加10个值为0的元素

◆replace(beg,end,val1,val2)//将beg到end的区域中的val1的值替换为val2值

◆replace_copy(beg,end,back_insert(vec),val1,val2)//将beg到end区域值为val1的值替换为val2,并插入至vec中.

举例:

      

list<int>ilst;

       for (list<int>::size_type ix = 0; ix <= 9;ix++)

       {

              ilst.push_back(ix);

              ilst.push_back(ix);

       }



       vector<int>ivec;

       ivec.push_back(100);

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



       int i = 0;

       for (vector<int>::iterator iter = ivec.begin();iter != ivec.end(); iter++)

       {

              cout<<"该vector的第"<<i++<<"个元素的值为:"<<*iter<<endl;

        }

5.C++语言提供了三种迭代器,其差别在于插入元素的位置不同.

          ①.back_inserter,创建使用push_back实现插入的迭代器

          ②.front_inserter,使用push_front实现插入迭代器

   ③.inserter,使用insert实现插入操作,除了所关联的容器外,inserter还带有第二个实参,:指向插入起始位置的迭代器

注意:只有当容器提供push_front操作时,才能使用front_inserter,在vector或其他没有提供push_front操作的容器上使用时将会发生错误

front_inserter与inserter的本质区别:

listilst1,ilst2,ilst3;

for(list::size_type  i= 0;I != 4;++i)

{

          ilst1.push_front(i);

}

前者总是在容器的所有元素之前插入,而后者则是在前面插入一个与元素后,元素首位置改变了.

6.iostream迭代器

istream_iteratorin(strm)                     创建从输入流strm中读取T类型对象的istream_iterator对象

istream_iteratorin                       istream_iterator对象的超出末端的迭代器

ostream_iteratorin(strm)          创建将T类型的对象写到输出流strm的ostream_iterator对象

ostream_iteratorin(strm,delim) 创建将T类型的对象写到输出流strm的ostream_iterator对象,在写入过程中使用delim作为元素的分隔符.delim是以空字符结束的字符数组

注意:迭代器只提供了最基本的迭代器操作:自增,解引用和赋值.此外还可以比较两个istream迭代器是否相等(或不等).而ostream迭代器则不提供比较运算

举例:

       istream_iteratorin_iter(cin);

       istream_iteratorin;

       vectorvec;

 

       while (in_iter != in)

       {

              vec.push_back(*in_iter++);

}

7.ostream_iterator对象和istream_iterator对象的使用:

       ostream_iterator<string>out_iter(cout,"/n");

       istream_iterator<string>in_iter(cin),eof;

 

       while (in_iter != eof)

       {

              *out_iter++ = *in_iter++;

       }

8.流迭代器的限制:

1).不可能将ostream_iterator对象读入,也不可能写到istream_iterator对象中.

2).一旦给ostream_iterator对象赋了一个值,写入就提交了.赋值后,没有办法在改变这个值.此外,ostream_iterator对象中的每个值都正好只能输出一次

3).ostream_iterator没有->操作符.

9.反向迭代器:

 

vec.begin()

vec.end()

 

 

 

vec.rbegin()

vec.rend()

①     从一个即支持—也支持++的迭代器就可以定义反向迭代器.

②     流式迭代器由于不能使用反向迭代器

③     使用普通迭代器对反向迭代器进行初始化或赋值时,所得到的迭代器并不是指向原迭代器所指向的元素

10.五种迭代器:

①     输入迭代器:读,不能写;只能支持自增运算

②     输出迭代器:写,不能读;只能支持自增运算

④     前向迭代器:读和写,只能支持自增操作运算

⑤     双向迭代器:读和写,支持自增和自减运算

⑥     随机访问迭代器:读和写,支持完整的迭代器算术运算

标准库提供的 find 运算：

 vector::const_iterator result =  find(vec.begin(), vec.end(), search_value);

 

只要找到与给定值相等的元素，find 就会返回指向该元素的迭代器。如果没有匹配的元素，find 就返回它的第二个迭代器实参，表示查找失败。

由于 find 运算是基于迭代器的，因此可在任意容器中使用相同的 find 函数查找值。

 

类似地，由于指针的行为与作用在内置数组上的迭代器一样，因此也可以使用 find 来搜索数组：

int ia[6] = {27, 210, 12, 47, 109, 83};
int *result = find(ia, ia + 6, 12);

 

如果需要传递一个子区间，则传递指向这个子区间的第一个元素以及最后一个元素的下一位置的迭代器（或指针）。

 

元素值的比较，有两种解决方法。默认情况下，find 操作要元素类型定义了相等（==）操作符，算法使用这个操作符比较元素。如果元素类型不支持相等（==）操作符，或者打算用不同的测试方法来比较元素，则可使用第二个版本的 find 函数。这个版本需要一个额外的参数：实现元素比较的函数名字

  

accumulate 算法

 

该算法在 numeric 头文件中定义。假设 vec 是一个 int 型的 vector 对象，下面的代码：

     int sum = accumulate(vec.begin(), vec.end(), 42);
将 sum 设置为 vec 的元素之和再加上 42。第三个形参则是累加的初值。

  

用于指定累加起始值的第三个实参是必要的，因为 accumulate 对将要累加的元素类型一无所知

 

这个事实有两层含义。首先，调用该函数时必须传递一个起始值，否则，accumulate 将不知道使用什么起始值。其次，容器内的元素类型必须与第三个实参的类型匹配，或者可转换为第三个实参的类型。

 

考虑下面的例子，可以使用 accumulate 把 string 型的 vector 容器中的元素连接起来：   
string sum = accumulate(v.begin(), v.end(), string(""));

这个函数调用的效果是：从空字符串开始，把 vec 里的每个元素连接成一个字符串。注意：程序显式地创建了一个 string 对象，用作该函数调用的第三个实参。

传递一个字符串字面值，将会导致编译时错误。因为此时，累加和的类型将是 const char*，而 string 的加法操作符所使用的操作数则分别是 string 和 const char* 类型，加法的结果将产生一个 string 对象，而不是 const char* 指针。

  

find_first_of 函数。这个算法带有两对迭代器参数来标记两段元素范围，在第一段范围内查找与第二段范围中任意元素匹配的元素，然后返回一个迭代器，指向第一个匹配的元素。如果找不到元素，则返回第一个范围的 end 迭代器。

list::iterator it = find_first_of(roster1.begin(), roster1.end(),roster2.begin(), roster2.end());

roster1 和 roster2 的类型不必精确匹配：roster1 可以是 list 对象，而 roster2 则可以是 vector 对象，只要这两个序列的元素可使用相等（==）操作符进行比较即可。     

 

fill 函数

fill(vec.begin(), vec.end(), 0); // 将迭代器范围内元素值设置为0 

 

如果输入范围有效，则可安全写入。这个算法只会对输入范围内已存在的元素进行写入操作。

  

fill_n 函数

    带有的参数包括：一个迭代器、一个计数器以及一个值。该函数从迭代器指向的元素开始，将指定数量的元素设置为给定的值。fill_n 函数假定对指定数量的元素做写操作是安全的。

初学者常犯的错误的是：在没有元素的空容器上调用 fill_n 函数（或者类似的写元素算法）。

vector vec; // empty 
fill_n(vec.begin(), 10, 0);

这个 fill_n 函数的调用将带来灾难性的后果。我们指定要写入 10 个元素，但这些元素却不存在——vec 是空的。其结果未定义，很可能导致严重的运行时错误。

  

back_inserter 函数是迭代器适配器。

使用 back_inserter 可以生成一个指向 fill_n 写入目标的迭代器：

vector vec; // empty 

fill_n (back_inserter(vec), 10, 0);

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

 

copy 函数

    带有三个迭代器参数：头两个指定输入范围，第三个则指向目标序列的一个元素。传递给 copy 的目标序列必须至少要与输入范围一样大。假设 ilst 是一个存放 int 型数据的 list 对象，可如下将它 copy 给一个 vector 对象：

vector ivec; // empty 
copy (ilst.begin(), ilst.end(), back_inserter(ivec));

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

当然，这个例子的效率比较差：通常，如果要以一个已存在的容器为副本创建新容器，更好的方法是直接用输入范围作为新构造容器的初始化式：   
vector ivec(ilst.begin(), ilst.end());

  

replace 函数

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

这个调用将所有值为 0 的实例替换成 42。如果不想改变原来的序列

 

replace_copy。

这个算法接受第三个迭代器实参，指定保存调整后序列的目标位置。

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

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

  

对容器元素重新排序的算法（sort,unique ）

假设我们要分析一组儿童故事中所使用的单词。例如，可能想知道它们使用了多少个由六个或以上字母组成的单词。每个单词只统计一次，不考虑它出现的次数，也不考虑它是否在多个故事中出现。要求以长度的大小输出这些单词，对于同样长的单词，则以字典顺序输出。

1. 去除重复

     sort(words.begin(), words.end());
     vector::iterator end_unique = unique(words.begin(), words.end());
     words.erase(end_unique, words.end());
为了说清楚，使用下面这个简单的故事作为我们的输入：

the quick red fox jumps over the slow red turtle
对于这个输入，我们的程序应该产生如下输出：

1 word 6 characters or longer
- 1.1 调用 sort 后，此 vector 对象的元素按次序排列：(注意，单词 red 和 the 重复出现了。)

fox jumps over quick red red slow the the turtle

 

- 1.2 调用 unique 后，vector 中存储内容是：(end_unique 指向位置 9 的 "red")

fox jumps over quick red slow the turtle red the

 

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

 

- 1.3 调用 erase 后，这个函数调用从 end_unique 指向的元素开始删除，直到 words 的最后一个元素也删除掉为止。调用之后，words 存储输入的 8 个不相同的元素。

 

值得注意的是，对没有重复元素的 vector 对象，调用 erase 也是安全的。如果不存在重复的元素，unique 就会返回 words.end()，此时，调用 erase 的两个实参值相同，都是 words.end()。两个迭代器相等这个事实意味着 erase 函数要删除的范围是空的。删除一段空的范围没有任何作用，所以即使输入中没有重复的元素，我们的程序仍然正确。

 

2. 定义需要的实用函数

谓词是做某些检测的函数，返回用于条件判断的类型，指出条件是否成立。

我们需要的第一个谓词将用在基于大小的元素排序中,指出第一个字符串是否比第二个短：

     bool isShorter(const string &s1, const string &s2)    
    {
        return s1.size() < s2.size();
    }

 

另一个所需的谓词函数将判断给出的 string 对象的长度是否不小于 6：
bool GT6(const string &s)    
{
     return s.size() >= 6;
}

3. 排序算法  

stable_sort(words.begin(), words.end(), isShorter); 

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

fox red the over slow jumps quick turtle

 

4. 统计长度不小于 6 的单词 

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

vector::size_type wc = count_if(words.begin(), words.end(), GT6);
bool GT6(const string &s){return s.size() >= 6;} 

执行 count_if 时，首先读取它的头两个实参所标记的范围内的元素。每读出一个元素，就将它传递给第三个实参表示的谓词函数。此谓词函数。此谓词函数需要单个元素类型的实参，并返回一个可用作条件检测的值。count_if 算法返回使谓词函数返回条件成立的元素个数。在这个程序中，count_if 将每个单词传递给 GT6，而 GT6 返回一个 bool 值，如果单词长度不小于 6，则该 bool 值为 true。

insert iterators（插入迭代器）：这类迭代器与容器绑定在一起，实现在容器中插入元素的功能。 

iostream 迭代器：这类迭代器可与输入或输出流绑定在一起，用于迭代遍历所关联的 IO 流。

reverse iterator（反向迭代器）：所有容器类型都定义了自己的 reverse_iterator 类型，由rbegin 和 rend 成员函数返回。