C++ primer第二次阅读学习笔记(第11章:泛型算法)

长平狐 发布于 2012/10/08 15:17
阅读 77
收藏 1

第十一章:泛型算法

 标准库容器定义的算法很少,而是选择提供一组算法.。泛型是指这些算法不依赖特定的容器类型,可作用在不同类型的容器和不同类型的元素上。不但可以作用在listvector上还可以作用在内置数组上。

   迭代器将算法和容器绑定起来。大多数算法是通过遍历有两个迭代器标记的一段元素来实现其功能。

find函数,接受两个迭代器和一个值作为参数,它检查两个迭代器实参标记范围内的每一个元素,只要找到与给定值相等的元素,就会返回指向该元素的迭代器,如果没有匹配元素,find就返回它的第二个迭代器实参,表示查找失败。

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

标准算法固有的独立于类型,它与容器的类型无关,但是算法只在一点上隐式的依赖于元素类型:必须能够对元素做比较运算。泛型算法用迭代器遍历容器,所有迭代器都支持自增操作符,从一个元素定位到下一个元素,并提供解引用操作符访问元素的值。大多数情况下,每个算法都需要(至少)两个迭代器来指出该算法操纵的元素范围,第一个迭代器指向第一个元素,第二个迭代器指向最后一个元素的下一个位置,它是被用作终止遍历的哨兵。它也被用作返回值,表示没有找到要查找的元素。默认情况下,find函数要求元素类型定义了相等操作符,算法使用这个操作符来比较元素,如果元素不支持相等操作符,或者打算用不同的方法来比较元素,可以使用第二个版本的find函数,它需要一个额外的参数:比较函数名。

标准库提供超过100中算法,它们都有一致的结构。

泛型算法是基于迭代器及其操作实现,而并非基于容器操作。使用普通的迭代器时,算法不修改容器的大小,它也许会改变存储在容器中元素的值,也许会在容器内移动元素,但是它从不直接添加或删除元素。

使用算法标准库要包含algorithm头文件。

findaccumulate算法为只读算法。它只会读取一段范围的元素,而不会修改这些元素。accumulate带有三个形参,头两个指定要累加的范围,第三个则是累加的初值,函数返回计算结果。accumulate对要累加的类型一无所知,因此该函数必须传递一个起始值,否则accumulate将不知道使用什么起始值,其次,容器内的元素类型必须与第三个实参的类型匹配,或者可转换为第三个实参的类型。

使用find_first_of时,两对迭代器类型可以不必相同,如第一对时list容器的迭代器,第二对是vector类型的迭代器。但只要它们指向的元素可以比较就可以。

一些算法会将数据写入输入序列。必须要保证迭代器所标记的范围至少足以存储要写入的元素。

fill函数,带有一对迭代器用于指定写入的范围,第三个形参为要写入的值。而fill_n参数为:一个迭代器,一个计数器,一个值。此时应注意,不要使迭代器越界访问。

back_inserter,插入迭代器用于给基础容器添加元素的迭代器,通常用普通迭代器时,被赋的值是迭代器所值相等的元素,而使用插入迭代器赋值时,则会在容器添加一个元素。

back_inserter是迭代器适配器,与容器适配器一样,迭代器适配器是用一个对象作为实参,并生成一个适应其实参行为的新迭代器。如

vector<int> vec;

back_inserter(vec);//插入迭代器将生成一个绑定到vec对象的插入迭代器,试图使用这个迭代器赋值时,赋值运算将调用push_back在容器中添加一个具有指定值的元素。

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

copy函数向目标迭代器写入一定数量的元素。copy带有三个迭代器参数,头两个指定输入的范围,第三个指向目标序列的一个元素,传递给copy的目标序列必须至少要与输入的范围一样大。

replace算法,带有四个形参:一对迭代器指定输入范围的迭代器和两个值。每一个等于第一个值得元素将被替换为第二个值。

sort算法带有两个迭代器形参,指出要排序的范围,这个算法使用<操作符比较元素。

unique算法,带有两个指定元素范围的迭代器参数,该算法“删除”相邻的重复的元素,然后重新排列。之所以加引号是因为,它是将无重复的元素复制到序列的前段,覆盖了相邻的重复元素,它的返回值为迭代器,它指向超出无重复的元素范围末端的下一位置。

标准库定义了四种不同的排序算法,除了sort外还有stable_sort,稳定排序保留了相等元素的相对位置。sortstable_sort都有两个版本,另一个版本带有第三个形参:比较所使用的函数的名字。这个函数必须接受两个实参,实参的类型必须与元素类型相同,并返回一个用作条件检测的值。具体可以参考附录A:标准库。

前面已经简要的介绍了迭代器,其实C++语言还提供了另外三种迭代器:

1:插入迭代器:迭代器适配器,与容器绑定在一起,产生与该容器绑定的插入迭代器,用于实现在容器中插入元素。

2iostream迭代器:与输入或输出流绑定到一起,用于遍历所关联的IO流。

3:反向迭代器:用于实现从后向前遍历,所有容器类型都有定义了自己的反向迭代器类型。由rbeginrend返回。

插入迭代器,创建一个迭代器,用来给容器添加元素,它是一种迭代器适配器,带有一个容器参数,并生成一个迭代器,用于在容器中插入元素。通过插入迭代器赋值时,迭代器将会插入一个新的元素。

C++提供三种插入器,其差别在于插入的元素位置不同。

back_inserter:创建使用push_back实现插入的迭代器。

front_inserter:使用push_front实现插入。

inserter:使用insert实现插入,它还带有第二个参数:要插入的位置迭代器。

front_inserter的操作类似于back_inserter,该函数创建一个迭代器,调用它所关联的基础容器的push_front成员函数代替赋值操作。因此只有当容器提供push_front时,才能使用front_inserter。所以vector是不可以使用的。

inserter将产生在指定位置实现插入的迭代器。inserter函数总是在它的迭代器实参所标明的位置之前插入元素。

iostream虽然不是容器,但是标准库同样提供了在iostream对象上使用的迭代器。istream_iterator用于读取输入流,ostream_iterator用于写入到输出流。使用流迭代器时,可以使用泛型算法从流对象中读取数据。

1istream_iterator in(strm);//创建从输入流strm中读取T类型对象的istream_iterator对象。

2istream_iterator<T> in;//istream_iterator对象的超出末端迭代器。

3ostream_iterator<T> in(strm);//创建将T类型的对象写到输出流strmostream_iterator对象。

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

流迭代器只定义了最基本的迭代器操作:自增、解引用和赋值。可以比较两个istream_iterator,但是ostream迭代器则不提供比较运算。

流迭代器都是类模板:任何已定义的操作符的类型都可以定义istream_iterator。类似的任何已定义输出操作符的类型也可以定义ostream_iterator

istream_iterator<int> cin_it(cin);//cin读取int类型的对象。

ostream_iterator对象必须与特定的流绑定在一起。在创建istream_iterator时,可直接绑定到一个流上。另一种方法是在创建时不提供实参,该迭代器指向超出末端位置。

如:istream_iterator<in>end_of_stream

但是ostream_iterator不提供超出末端迭代器。

构造与流绑定在一起的istream_iterator对象时,将对迭代器定位,以便第一次对该迭代器进行解引用时即可从流中读取第一个值。

如:

istream_iterator<int> in_iter(cin);

istream_iterator<int>eof;

while(in_iter!=eof)

   vec.push_back(*in_iter++);

该程序也可以这样写:

istream_iterator<int>in_iter(cin);

istream_iterator<int>eof;

vector<int>vec(in_iter,eof);

可以使用ostream_iterator对象将一个值写入到写入流中。其操作过程与使用迭代器将一组值赋给容器的元素相同。

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

istream_iterator<string> in_iter(cin),eof;

while(in_iter!=eof)

*out_iter++=*in_iter++;

反向迭代器是一种反向遍历容器的迭代器。它从最后一个元素向第一个元素遍历容器,它还将自增(减)的含义反过来:对于反向迭代器,++运算将访问前一个元素,而--运算将访问下一个元素。

容器定义了rbeginrend,分别返回指向容器尾元素和首元素前一位置的反向迭代器。反向迭代器也有常量和非常量。

例如为了降序排列vector可以向sort传递一对反向迭代器。

流迭代器不能创建反向迭代器。

反向迭代器调用成员函数base()将获得与反向迭代器指向相同元素的正向迭代器。

算法要求用于指定范围的两个迭代器具有完全一样的类型。调用m.end()返回的类型,依赖于m的类型。如果mconst对象则返回const_iterator类型,否则返回普通的迭代器。

算法要求的迭代器分为五个类别,分别为:

1:输入迭代器,读,不能写,只支持自增运算。只能顺序使用,一旦自增就不能检查之前的元素。

2:输出迭代器。写,不能读,只支持自增运算。对于指定的迭代器应该使用一次*运算,而且只能使用一次。

3:前向迭代器,读和写,只支持自增运算。用于读写指定的容器,这个迭代器只会以一个方向遍历序列。它支持对一个元素的多次读写。

4:双向迭代器,读和写,支持自增和自减运算。从两个方向读写容器。所有标准库提供的迭代器都至少达到双向迭代器的要求。

5:随机访问迭代器。读和写,支持完整的迭代器算术运算。提供在常量的时间内访问容器任意位置的功能。需要随机访问迭代器的泛型算法包括sort算法,vectordeque,string迭代器都是随机访问迭代器。用作访问数组元素的指针也是随机访问迭代器。

除了输出迭代器外,其他类别的迭代器形成了一个层次结构:需要低级类别迭代器的地方,可以使用任意一种更高级的迭代器。对于需要输入迭代器的算法,可传递向前、双向或随机访问迭代器。而需要随机访问迭代器时,必须传递随机访问迭代器。

map,setlist类型提供双向迭代器。而stringvectordeque容器上定义的迭代器是随机访问迭代器,用作内置数组元素的指针也是随机访问迭代器。istream_iterator是输入迭代器,ostream_iterator为输出迭代器。

注意:尽管map,set类型提供双向迭代器,但关联容器只能使用算法的一个子集,这是因为:关联容器的键是const对象。因此关联容器不能使用任何写序列元素的算法。


原文链接:http://blog.csdn.net/ithzhang/article/details/7592331
加载中
返回顶部
顶部