算法和函数对象（函数符）

函数对象就是一个类，但它和回调函数一样可以被回调。

1．   可以与()联合使用的形式有：函数名、指向函数的指针和重载了()操作符的对象。

2．   for_each()  的原型为：

         template<class InputIterator, class Function>

         Function for_each(InputIterator, InputIterator last, Function f);

         对于应用中的函数f可申明为:    void ShowView(const Review &);//即将(void *)(const Review&)赋值给模板参数Function 的类型。

         Function参数可表示具有重载的()操作符的类类型。

3．   函数符的概念：

         生成器：不用参数就可以调用的函数符。

         一元函数：有一个参数可以调用。二元函数同理。

         断言：返回bool值的一元函数。

         二元断言：返回bool值的二元函数。

         将断言作为参数举例：

                   bool tooBig(int n){return n>100;}

                   list<int> scores;            scores.remove_if(tooBig);

                   将函数对象作为remove_if()的参数：

                   template<class T>

                   class TooBig{

                   private:       T cutoff;

                   public:        TooBig(const T &t):cutoff(t){}

                                      bool operator(const T & v){return v>cutoff;}

                   };

                   void main(){

                            TooBig<int> f100(100);

list<int> ya;

int val[10]={20,50,100,…};

ya.insert(ya.begin(), val, val+10);

ya.remove_if(f100);

ya.remove_if(TooBig<int>(200));

}

4.      模板类函数对象：

         用法如：

         plus<double> add;        double y=add(2.2, 3.2);

         transform(gr.begin(), gr.end(), m.begin(), out, plus<double>());

         操作符和相应的函数符：                              

操作符	相应的函数	操作符	相应的函数
+	plus	>	greater
-	minus	<	less
*	multiplies	>=	greater_equal
/	divides	<=	less_equal
%	modulus	&&	logical_and
-	negate	||	logical_or
==	equal_to	!	logical_not
!=	not_equal_to

5.          自适应函数符和函数适配器：

         绑定函数：

         绑定器函数对象(被绑定函数对象必须为双目函数)

STL 中的帮定器有：

         bind1st() 创建一个函数对象，该函数对象将值V作为第一个参数A。

         bind2nd()创建一个函数对象，该函数对象将值V作为第二个参数B。

         用法举例：

         count_if(aList.begin(), aList.end(),bind1st(greater<int>(), 8), k);//计算所有小于或等于8的对象的数目，k为个数的应用，如果没有该参数，则返回在值为个数。

         否定函数对象：就是它从另一个函数对象创建而来，如果原先的函数返回真，则否定函数对象返回假。

         自适应函数：携带了参数类型和返回值类型的typedef成员，这些成员分别是result_type、   first_argument_type和second_augument_type.

将二元函数变成一元函数的方法（binder1st和binder2nd的用法）：

binder1st的对象将自适应函数的第一个参数的特定值相关联；binder2nd的对象将自适应函数的第二个参数的特定值相关联。

令f2()是一个带两个参数的自适应函数

binder1st(f2, val) f1; 返回的值与将val作为第一个参数、将f1()的参数作为第二个参数的f2()相同,即f(x)等价于f2(val, x);

STL提供bind1st以简化binder1st类的使用:

bind1st(multiplies<double>(), 2.5);          binder2nd和bind2nd用法同理。

7.      否定函数对象：就是它从另一个函数对象创建而来，如果原先的函数返回真，则否定函数对象返回假。       有两个否定函数对象：not1()和not2()。not1()接受单目函数对象，not2()接受双目函数对象。否定函数对象通常和绑定器一起使用。

         用法如：

         start = find_if(aList.begin(), aList.end(), not1(bind1nd(greater<int>(), 8)));//计算q>8，必须使用not1，因为bind1nd返回单目函数。

二     算法

(1)     算法组：

         1)      非修改式序列操作(头文件algorithm，前algo.h)

                            对区间中的每个元素进行操作，不改变容器的内容。

         2)      修改式序列操作(头文件algorithm，前algo.h)

可以修改容器中的内容，可以修改值，也可以修改值的排列顺序，如transform()、random_shuffle()和copy()。

         3)      排序和相关操作(头文件algorithm，前algo.h)

                           包括多个排序函数（如sort()）和其他各种函数，如集合操作。

         4)      通用数字运算(头文件numeric，前algol.h)

(2)     常用算法:

         1)      transform：将迭代区间中的值改变后存入另一个迭代器中。其有两种形式：

                  1.1 transform()接受四个参数：

         前两个参数是指定容器区间的迭代器，第三个参数是接受复制结果的迭代器，最后一个参数是一个一元函数符()，被用于区间中的每个元素，生成结果中的新元素。用法如：

               cout int LIM=5;

               double arr[LIM]={25,23,55,23,64};

               vector<double> gr(arr, arr+LIM);

               ostream_iterator<double, char> out (cout, “”);

               transform(gr.begin(), gr..end(), out, sqrt);

                   1.2    transform()接受五个参数的函数，并将该函数用于两个区间中元素，用第三个参数标识两个参数的起始位置。用法如：

                   令m是一个vector<double>的对象，mean(double, double)返回两个值的平均值。

                   transform(gr.begin(), gr.end(), m.begin(), out, mean);

                   set<string> wordset;

                   transform(words.begin(), words.end(),   

                            insert_itereator<set<string>>(wordset, wordset.begin()), ToLower))

（2）copy：将一个迭代区间中的值赋值给另一个迭代区间

         函数原型：

         template<class InputIterator, class OutputIterator>

         OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);

         用法如：

ostream_itereator<string, char>out(cout, “ ”);//有的编译器为ostream_iterator<int> out(cout, “ ”);

         copy(c.begin(), c.end(), out); //将元素拷贝到输出流

(3)     replace：在迭代区间中，用新值代替旧值。用两种形式：

         3.1    replace的就地版本原型(四个参数)：结果被存放在原始数据的位置。

                  template<class ForwardIterator, Class T>

                  void replace(ForwardIterator first, ForwardIterator last, const T& old_value,

                           const T&    new_value);

         3.2    replace的复制版本原型(五个参数)：结果被发送到另一个位置。

         template<class InputIterator, class OutputIterator, Class T>

void replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value,     const T& new_value);

用法举例：

                    vector<int> V;

                    V.push_back(1);

                    V.push_back(2);

                    V.push_back(3);

                    V.push_back(1);

                    replace(V.begin(), V.end(), 1, 99);

(4)       replace_if：从区间中移除断言为真的元素。

         函数原形为：

void replace_if(ForwardIterator fist, ForwardIterator last, Predicate pred);

(5)    for_each()：对于区间中的每个元素都进行f操作。

                   Function for_each(InputIterator, InputIterator last, Function f);

                   对于应用中的函数f可申明为:    void ShowView(const Review &);//即将(void *)(const Review&)赋             值给模板参数Function 的类型。Function参数可表示具有重载的()操作符的类类型。

(6)    accumulate() 算法(#include <numeric>):计算容器中所有值的总和。

         这样的值不一定是简单的类型，通过重载operator+()，也可以是类对象。

         两种函数原形：

         6.1    T accumulate(InputIterator first, InputIterator last, T init);// result = result + *i

         6.2    T accumulate(InputIterator first, InputIterator last, T init,

             BinaryFunction binary_op);// result = binary_op(result, *i)

         用法举例：

         vector<long> v(MAX);

         for (int i = 0; i < MAX; i++)

             v[i] = i + 1;

         long sum =accumulate(v.begin(), v.end(), 0);

           cout << "Sum of values == " << sum << endl;

         long product =accumulate(v.begin(), v.end(), 1, multiplies<long>());//注意这行

           cout << "Product of values == " << product << endl;