这周的课讲了将泛型算法。现在将泛型算法收集下,备用。

1.C++标准库的算法,是什么东西?

谓词(predicate)是做某些检测的函数,配合标准算法库使用。假设我们要统计一个
vector<int> 里有多少个元素大于 5,则要定义一个谓词函数
gt5:        vector<int>::difference_type cnt =
count_if(vec.begin(), vec.end(), gt5);
假设我们还要统计大于 8 的元素的数目,则还要定义一个
gt8。而如果还要统计大于
10、100、150……的元素的数目,则要定义更多的函数。这明显非常不便!使用模板可以解决这个问题:
        template <int N>
        inline bool gt(int n)
        {
            return n > N;
        }
这样,只需定义一个模板,就可以用于统计大于任意值的元素的数目。例如:
        vector<int>::difference_type cnt10  =
count_if(vec.begin(), vec.end(), gt<10>);
        vector<int>::difference_type cnt100 =
count_if(vec.begin(), vec.end(), gt<100>);
不过,如果需要统计大于
1、2、3、4、5……的元素的数目,使用模板作为谓词也会非常不便,因为需要单独写很多个
count_if。遇到这种情况,就应该使用函数对象,这样的话,就可通过在循环中调用
count_if 来解决问题。

(1)泛型算法用迭代器来解决第一个要求:遍历容器。所有迭代器都支持自增操作符,从一个元素定位下一个元素,并提供解引用操作符访问元素的值 

从语言的层面讲,STL的算法都长下面两个样子:

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

template

【 只读算法】 

Algorithm(Iterator itr1, Iterator itr2)

 (3)只读算法是 accumulate,该算法在 numeric 头文件中定义。  accumulate
带有三个形参。头两个形参指定要累加的元素范围。第三个形参则是累加的初值。
假设 vec 是一个 int 型的 vector 对象,下面的代码:      

{

// sum the elements in vec starting the summation with the value 42   
  

  //…

int sum = accumulate(vec.begin(), vec.end(), 42);

}

 将 sum 设置为 vec 的元素之和再加上 42。
首先,调用该函数时必须传递一个起始值,否则,accumulate
将不知道使用什么起始值。 其次,容器内的Section 11.2.  A First Look at
the
Algorithms元素类型必须与第三个实参的类型匹配,或者可转换为第三个实参的类型。 

template

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

Algorithm(Iterator itr1, Iterator itr2, Cmp comp)

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())            {        

上面这两个东西是Function
template(函数模板),一般情况算法都有两个版本,一个是两个参数的,一个是有三个参数的版本。
前面两个参数是两个迭代器,用来让算法知道需要操作的对象的范围,第三个参数是为了增加算法的弹性,用户可以在其中加上自己的准则,比如:sort函数,默认是从小到大排序,如果加上第三个参数(指定从大到小),
那么sort就会将数据按照指定的方式操作。

        ++cnt;        

算法是看不见容器的,对其一无所知,一切信息都是从iterator中得到。
iterator就是算法和容器之间的桥梁。

 // we got  a match, increment it to look in the rest of roster1

1.1各种容器的iterators的iterator_category

        ++it;

STL中有五中iterator_category分别是:

      }

struct input_iterator_tag{};

      cout << “Found ” << cnt<< ” names on both
rosters” << endl;

struct output_iterator_tag{};

   
注意:find_first_of,带有两对迭代器参数。每对迭代器中,两个实参的类型必须精确匹配,但不要求两对之间的类型匹配。特别是,元素可存储在不同类型序列中,只要这两序列的元素可以比较即可。 

struct forward_iterator_tag: public input_iterator_tag{};

 【
写容器元素的算法】********************************************************** 

struct bidirectional_iterator_tag: public forward_iterator_tag{};

 (5) fill 函数,写入到输入序列的算法    fill
带有一对迭代器形参,用于指定要写入的范围,而所写的值是它的第三个形参的副本。执行时,将该范围内的每个元素都设为给定的值。如果输入范围有效,则可安全写
入。这个算法只会对输入范围内已存在的元素进行写入操作。

struct random_access_iterator_tag: public
bidirectional_iterator_tag{};

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

Array,Vector,Deque这三种容器支持随机访问,是连续空间(deque模仿出连续的假象),使用的是random_access_iterator_tag

// set  subsequence of the range to 10

list,
set,map,multiset,multimap,都是关联性容器,不支持随机访问,使用的是bidirectional_iterator_tag

      fill(vec.begin(), vec.begin() + vec.size()/2, 10); 

forward_list,unordered_set,
unordered_map,unordered_multiset,unordered_multimap是单向连续性空间,不支持随机访问,使用的是forward_iterator_tag

(6) fill_n函数,不检查写入操作的算法    fill_n
函数带有的参数包括:一个迭代器、一个计数器以及一个值。该函数从迭代器指向的元素开始,将指定数量的元素设置为给定的值。fill_n
函数假定对指定数量的元 素做写操作是安全的。   
注意:初学者常犯的错误的是:在没有元素的空容器上调用 fill_n
函数(或者类似的写元素算法):      

istream ,ostream分别使用的是input_iterator_tag,output_inerator_tag

*****************************************************

注:typeid(iter).name(),可以直接得到对象的类型名称

      vectorvec; // empty vector

1.2iterator_category对算法的影响

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

使用distance函数求得一个容器begin和end之间的距离

      fill_n(vec.begin(), 10, 0);

template

      //vec 是空的,其结果未定义,很可能导致严重的运行时错误。     
*****************************************************

inline iterator_traits::difference_type

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

distance(InputIterator first, InputIterator last)

    vectorivec; // empty vector

{

    // copy elements from ilst into ivec

  typedef typename iterator_traits::iterator_category category;

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

  return __distance(first, last, category);

 (8)算法的 _copy 版本 
有些算法提供所谓的“复制(copying)”版本。这些算法对输入序列的元素做出处理,但不修改原来的元素,而是创建一个新序列存储元素的处理结果。但不修改原来的元素,
而是创建一个新序列存储元素的处理结果。

}

 (9)replace 算法,对输入序列做读写操作,将序列中特定的值替换为新的值 
该算法带有四个形参:一对指定输入范围的迭代器和两个值。每一个等于
第一值的元素替换成第二个值。

当传入vector.begin()和vector.end()函数,通过萃取机iterator_traits得到他的iterator_category类型,然后去调用:

      // replace any element  with value of 0 by 42

template

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

inline iterator_traits::difference_type

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

__distance(RandomAccessIterator first, RandomAccessIterator last,
input_iterator_tag)

      // create empty vector to hold the replacement     
vector<i>ivec;

{

      // use back_inserter to grow destination as needed

  return last – first;

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

}

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

因为连续空间的容器,所以直接首尾相减,就能得到距离,速度非常快


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

当传入的是list.begin()和list.end()函数,通过萃取机iterator_traits得到他的iterator_category类型,然后去调用:

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

template

 (12)unique
算法,该算法删除相邻的重复元素,然后重新排列输入范围内的元素,并且返回一个迭代器,表示无重复的值范围的结束。 
  它带有两个指定元素范围的迭代器参数。    注:调用
unique“删除”了相邻的重复值。给“删除”加上引号是因为 unique
实际上并没有删除任何元素,而是将无重复的元素复制到序列的前端,从而覆盖相邻的重复元素。unique
返回的迭代器指向超出无重复的元素范围末端的下一位置。(想真正删除元素要与erase函数连用)

inline iterator_traits::difference_type

 (13)stable_sort 算法,有着相同长度的元素还能以字典次序的不同而区分   
stable_sort
算法有第三个形参:比较元素所使用的谓词函数的名字。这个谓词函数必须接受两个实参,实参的类型必须与元素类型相同,并返回一个可用作条件检测的值。

__distance(InputIterator first, InputIterator last,
input_iterator_tag)

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

{

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

  iterator_traits::difference_type n = 0;

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

    while(first != last)

      {

    {

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

      ++first;

      }

      ++n;

 (14)count_if 算法,统计个数    执行 count_if
时,首先读取它的头两个实参所标记的范围内的元素。每读出一个元素,就将它传递给第三个实参表示的谓词函数。此谓词函数。此谓词函数需要单个元素类型
的实参,并返回一个可用作条件检测的值。count_if
算法返回使谓词函数返回条件成立的元素个数。      vector::size_type wc
=count_if(words.begin(), words.end(), GT6);

    }

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

  return n;

      bool GT6(const string &s)

}

      { 

因为是非连续空间容器,所以只能通过迭代的方式,一个一个向后偏移得到距离。
速度很慢。

         return s.size() >= 6;

由此可以想象,不同的iterator_category对算法的影响是非常大的。
在算法中,会做非常多的检查,让算法使用正确的最快的迭代器分类去操作容器,使用STL其实是一件非常幸福的事情(想想c程序员。。。

      }

2.仿函数

  【
再谈迭代器】**************************************************************** 

仿函数其实是一个类重载了()运算符,在STL中如下:

 (15)插入迭代器(insert
iterators):这类迭代器与容器绑定在一起,实现在容器中插入元素的功能。 
插入器是一种迭代器适配器,带有一个容器参数,并生成一个迭代器,用于在指定容器中插入元素。通过插入迭代器赋值时,迭代器将会插入一个新的元素。C++
语言提供了三种插入器,其差别在于插入元素的位置不同:

template

 (a)back_inserter,创建使用 push_back 实现插入的迭代器。

struct plus: public binary_function

 (b)front_inserter,使用 push_front 实现插入。

{

  (c)inserter,使用 insert 实现插入操作。除了所关联的容器外,inserter
还带有第二实参:

  T operator () (const T& x, const T& y)

      指向插入起始位置的迭代器。

  {

 注:front_inserter 需要使用 push_front,只有当容器提供 push_front
操作时,才能使用 front_inserter。在 vector 或其他没有 push_front
运算的容器上使用front_inserter,将产生错下载文档到电脑,查找使用更方便1下载券 
131人已下载下载还剩2页未读,继续阅读误。

    return x+y;

      listilst, ilst2, ilst3;

  }

    // empty lists

}

      // after this loop ilst contains: 3 2 1 0

在使用STL的算法时,可以使用函数来指定第三参数,也可以用仿函数指定,例如:

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

// 使用函数指定

          ilst.push_front(i);

bool myfunc(int i, int j)

      // after copy ilst2 contains: 0 1 2 3

{

      copy (ilst.begin(), ilst.end(), front_inserter(ilst2)); 

  return i < j;

     // after copy, ilst3 contains: 3 2 1 0

}

      copy (ilst.begin(), ilst.end(),

sort(myvec.begin(), myvec.end(), myfunc);

      inserter (ilst3, ilst3.begin()));

// 使用仿函数指定

 在复制并创建 ilst2 的过程中,元素总是在这个 list
对象的所有元素之前插入。而在复制创建 ilst3 的过程中,元素则在 ilst3
中的固定位置插入。刚开始时,这个插入 位置是此 list
对象的头部,但插入一个元素后,就不再是首元素了。

template

  (16) iostream 迭代器

struct less: public binary_function

    【注】流迭代器都是类模板:任何已定义输入操作符(>>
操作符)的类型都可以定义
istream_iterator。类似地,任何已定义输出操作符(<<
操作符)的类型也可定义ostream_iterator。

{

      istream_iteratorcin_it(cin);    // reads ints1 from cin

  bool operator () (const T& x, const T& y) const

      istream_iteratorend_of_stream;  // end iterator value

  {

      // writes Sales_items from the ofstream named outfile

    return x < y;

      // each element  is followed by a space      ofstream outfile; 

  }

在创建 istream_iterator
时,可直接将它绑定到一个流上。另一种方法是在创建时不提供实参,则该迭代器指向超出末端位置。ostream_iterator
不提供超出末端迭代器。 在创建 ostream_iterator
对象时,可提供第二个(可选的)实参,指定将元素写入输出流时使用的分隔符。分隔符必须是
C 风格字符串。因为它是 C
风格字符串,所以必须以空字符结束;否则,其行为将是未定义的。

}

    【注】流迭代器的限制:

sort(myvec.begin(), myvec.end(), less());

 (a)不可能从 ostream_iterator 对象读入,也不可能写到 istream_iterator
对象中。

less()是一个临时对象,将其传入sort之后,sort会自动调用class
less里头的operator
(),就像调用函数一样(仿函数比函数更有弹性),因为仿函数可以被适配器修改。

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

如果我们自己写了一个仿函数,需要继承STL的两个类:

 (c)ostream_iterator 没有 -> 操作符。

      istream_iteratorcin_it(cin);    // reads ints from cin

// 一个操作数继承

      istream_iteratorend_of_stream;  // end iterator value

unary_functiontemplate < class Arg, class Result>

      // initialize vec from the standard input:

struct unary_function

      vectorvec(cin_it, end_of_stream);

{

      sort(vec.begin(), vec.end());

typedef Arg argument_type;

      // writes ints to cout using ” ” as the delimiter

typedef Result result_type;

      ostream_iterator<int>output(cout, ” “);

};

// write only the unique elements in vec to the standard output

// 两个操作数继承

     unique_copy(vec.begin(), vec.end(), output);

binary_functiontemplate

输入是: 23 109 45 89 6 34 12 90 34 23 56 23 8 89 23 输出是: 6 8 12 23 34 45 56 89 90 109

struct binary_ function

{

typedef Arg1 fist_argument_type;

typedef Arg2 second_argument_type;

typedef Result result_type;

};

STL规定每一个Adaptable Function都要挑选适当的来继承,因为Function
Adapter将会提问问题,例如:

template

class binder2nd: public unary_function

{

protected: Operation op;

// 这里就是function adapter在问问题

typename Operation::second_argument_type value;

public:

// ….

};

typename Operation::second_argument_type value;

这一句就是在问仿函数问题,你的第二个参数类型是什么,如果这一句可以编译通过,那么函数适配器就得到了仿函数的第二个参数类型,仿函数就可以被改造。

一个仿函数想要能被STL中的适配器改造,就需要继承适当的类融入STL。

  1. Adapter

STL的算法可以让用户提供第三参数,用于给用户自定义算法处理数据的方式,上面讲述了可以使用仿函数作为第三参数,仿函数可以被适配器改造,下面就来看一下适配器是如何改造仿函数的。

3.1 bind2nd

以泛型算法count_if为例:

模板 < 类 InputIterator, 类谓词 > 类型 iterator_traits <
InputIterator >::d ifference_type count_if (InputIterator 第一,
InputIterator 最后, 谓词 pred) {类型

iterator_traits < InputIterator >::d ifference_type n = 0;for (;
首先是最后一个; + + 第一个) {if (pred (* 第一)) {+ n;}

} 返回 n;

} 在使用count_if时如下:

count_if (vi. 开始 (), vi. 结束 (), bind2nd (较少 < int > (),
40));bind2nd就是一个适配器,用于将仿函数less的第二参数绑定为40.

bind2nd源码如下:

模板 < 类操作, 类 T > 内联 binder2nd < 操作 > bind2nd (const
操作 & op, 常量 T & x) {typedef 类型操作:: second_argument_type
arg2_type; 返回

binder2nd < 操作 > (op, arg2_type (x));}

在bind2nd中返回的是一个binder2nd类型的临时对象,bind2nd函数其实是一个中间层,因为binder2nd类模板不可以自动推导类型参数,只有模板函数可以,所以使用中间层给类模板指定模板参数Operation。

class binder2nd源码如下:

模板 < 类操作 > 类 binder2nd: 公共 unary_function < 类型操作::
first_argument_type, 类型操作:: result_type > {保护:

操作 op;类型操作:: second_argument_type 值;

public: binder2nd (const 操作 & x, 常量类型操作:: second_argument_type
& y): op (x), 值 (y) {} 类型操作:: result_type 运算符 () (const

类型操作:: first_argument_type & x) 常量 {返回 op (x, 值);}

} 当在count_if中传入第三参数bind2nd (较少 < int > (), 40) 后,
先会调用bind2nd函数, 函数确定Operation 和 T的类型函数变成如下:

内嵌 binder2nd < 更少 < int > > bind2nd (恒少 < 国际 >
& op, const int & x) {typedef 更少的 < int >::
second_argument_type arg2_type; 返回 binder2nd < 少 < 国际 >
> (op, arg2 _

类型 (x));} 然后先让class binder2nd确定模板参数

类 binder2nd: 公共 unary_function < 较少 < int >::
fist_argument_type, 更少 < 国际 >:: result_type > {保护:
更少的 < 国际 > op; 更少的 < 国际 >:: second_argument_

类型值;公共: binder2nd (常量较少 < int > & x, 常量较少 < int
>:: second_argument_type & y): op (x)、值 (y) {} 更少 < int
>:: result_type 运算符 () (不小于 < int >:

: first_argument_type & x) 常量 {返回 op (x, 值);}

}

再在函数内部调用class
binder2nd的构造函数,实例化一个binder2nd类型的临时对象,将less()和40分别记录在op和value里头。

最后count_if的第三个参数就得到一个binder2nd类型的临时对象,其中包涵了less和40,count_if函数变成如下:

加上vi是容器list的实例化 ptrdiff_t count_if (列表 < int >::
迭代器第一, 列表 < int >:: 迭代最后, binder2nd pred) {ptrdiff_t n
= 0; for (; 首先! = 尾页; + + 第一个) {if (pred (*

第一)) {+ + n;}

} 返回 n;

}

在count_if中调用pred这个仿函数时(pred就是binder2nd类型的临时对象的别名),会触发class
binder2nd中的 operator(),在operator()中

op(x, 40);

40就被绑定到less()的第二参数上

这就是仿函数适配器的工作原理(真的非常的巧妙)。

3.2 inserter

当我们想用copy函数进行容器间的拷贝动作时,一种是提前将空间预留

int myints[] = {10, 20, 30, 40, 50, 60, 70};

vector myvec(7);

copy(myints, myints+7, myvec.begin());

提前预留空间是因为copy函数只是单纯的移动迭代器,向迭代器所指的地方插入数据,源码如下:

模板 < 类 InputIterator, 类 OutputIterator > OutputIterator 复制
(InputIterator 首先, InputIterator 最后, OutputIterator 结果) {而
(第一个! 最后一个) {结果 = * 第一;

++ 结果;首先为 ++;

} 返回结果;

}

假设我们的容器其中本来就有数据,没有预留空间,那么直接使用copy函数会造成一颗定时炸弹(越界访问),在这种时候就需要使用适配器来改造拷贝动作。

将copy的第三参数改写成迭代适配器:

copy(myints, myints+7, inserter(myvec, iter));
//iter为迭代器,指向容器内任意地方

inserter源码如下:

模板 < 类容器, 类迭代器 > 内联 insert_iterator < 容器 >
插入 (容器 & x, 迭代器 i) {类型容器: 迭代器 iter; 返回 insert_

迭代器 < 容器 > (x, iter (i));}
inserter与bind2nd一样,也是一个辅助函数,帮助class
insert_iterator确定模板参数.

类 insert_iterator源码如下:

模板 < 类容器 > 类 insert_iterator {保护: 容器 * 容器;
类型容器:: 迭代器 iter; public: typedef output_iterator_tag

iterator_category;

insert_iterator(Container& x, typename Container::iterator i)

    :container(&x), iter(i)

{ }

insert_iterator&

operator = (const typename Container::value_type& value)

{

    iter = container->insert(iter, value);

    return *this;

}

typename Container::iterator& operator ++ ()

{

    return ++iter;

}

};

inserter函数返回一个insert_iterator类型的临时对象,在这个临时对象中,容器myvec被记录到了容器指针container中,myvec的迭代器iter被记录到了临时对象中的的iter里,当copy函数在执行:

result = *first;

++result;

以上两个操作的时候,会触发class insert_iterator里的两个操作符重载函数。

这样copy函数从原来一个傻傻的,只会一个一个拷贝的底层函数,摇身一变成了一个智能的插入拷贝函数(C++技术相当奇妙,这就是操作符重载的好处)。

  1. iostream iterator

标准库定义有提供给输入输出使用的 iostream
iterator,称为istream_iterator 和
ostream_iterator,他们分别支持单个元素的读取和写入。

使用这两个迭代器需要包涵#include

4.1 ostream_iterator

ostream_iterator的使用方法如下:

将out_it绑定到cout输出设备 ostream_iterator < int > out_it
(cout);

//将out_it绑定到cout输出设备, 并且在输出元素后加上一个字符串
ostream_iterator < int > out_it (cout, “,”);

包括 < iostream >

包括 < 向量 >

包括 < 算法 >

包括 < 迭代器 >

使用命名空间性病;

int main () {向量 < int > vec; (int i = 0; 我 < 10; + + i)
{vec. push_back (i);}

ostream_iterator < int > outit (cout, “,”);

复制 (vec, 开始 (), vec. end (), outit);

返回 0;

}

4.2 istream_iterator

使用方法如下:

// 定义一个指向输入流结束位置的迭代器

istream_iterator eos;

// 定义一个指向标准输入的迭代器

istream_iterator iit(cin)

当 iit =
eos时,说明流中的数据已经全部读取结束,操作iit让其加一,可以让迭代器指向下一个流中的数据

包括 < iostream >

包括 < 迭代器 >

using namespace std;

int main()

{

double value1, value2;

cout << “please insert two value: “;

istream_iterator eos;

istream_iterator iit(cin);

if(iit != eos)

{

    value1 = *iit;

}

++iit;

if(iit != eos)

{

    value2 = *iit;

}

cout << value1 << ‘ ‘ << value2 << endl;

return 0;

}

这里值得注意的是,当我们把

cout << “please insert two value: “;

写到

istream_iterator iit(cin);

后面

在执行程序的时候,我们发现,当输入第一个数字之后,cout这句输出才会被打印出来,造成这样的原因是,当定义了iit之后,其构造函数已经对iit加一,读取已经开始,所以cout的输出被放在后面。

注:

ifstream infile(“./test/01.cpp”);

istream_iterator eos;

istream_iterator iit(infile);

ofstream outfile(“./2.cpp”);

ostream_iterator out_it(outfile, ” “)