首页 > 代码库 > 仿函数(函数对象)和STL算法
仿函数(函数对象)和STL算法
1仿函数可当作排序准则
程序员经常将某些class obect以有序的形式置于容器中或许你是 不能或不想反正你无法使用一般的operator<来对这些对象排序，你必须以某种特别规则通常基于某些成员函数此时仿函数派上用场例如：
Class Person
{
Public：
String firstname() const;
String lastname() const;
}
Class personsortCriterion
{
Bool operator()(const Person& p1,const Person& p2)
{
Return p1.lastname()<p2.lastname()||(!(p2.lastname()<p1.lastname()&&p1.firstname()<p2.fisrtname())
}
};
Int main()
{
Typedefset<Person,PersonsortCriterion>Personset;
Personset col;
}
2 拥有内部状态的仿函数
下面例子讲展示仿函数如何模拟哈书在同一时刻拥有多个状态
class IntSequence
{
private:
intvalue;
public:
IntSequence(intinitialValue):value(initialValue){}
intoperator()(){
returnvalue++;
}
};
void main()
{
list<int>col;
intistart=1;
generate_n(back_inserter(col),9,IntSequence(istart));
for_each(col.begin(),col.end(),print);
cout<<endl;
generate(++col.begin(),--col.end(),IntSequence(istart));
for_each(col.begin(),col.end(),print);
cout<<endl;
list<int>coll;
IntSequence seq(istart);
generate_n(back_inserter(coll),9,seq);
for_each(coll.begin(),coll.end(),print);
cout<<endl;
}
有两个办法可以从运用了仿函数的算法中的结果和反馈
1) 以by reference的方式传递仿函数
2) 运用for_each()算法的返回值
运用reference方式传递只需将template参数明白加以表示
Generate<back_insert_iterator<list<init>>,int,IntSequence&>(back_insert(col),4,seq)
For_each()的返回值
如果你使用的算法是for_each()那就不必大费周折的实作仿函数的引用计数版本来存取最终状态。For——each有独门绝技其他算法没有那就是可以返回其仿函数
classMeanValue
{
private:
longnumber;
longsum;
public:
MeanValue():number(0),sum(0)
{}
voidoperator()(intelem)
{
number++;
sum+=elem;
}
doublevalue()
{
returnstatic_cast<double>(sum)/static_cast<double>(number);
}
};
void main()
{
vector<int>col;
for(inti=1;i<9;++i)
{
col.push_back(i);
}
MeanValue mv=for_each(col.begin(),col.end(),MeanValue());
cout<<"Mean Value:"<<mv.value()<<endl;
}
3判断式和仿函数
应该将判别式的operator()声明为const成员函数
4预定义的仿函数
Negate<type>() -param
Plus<type>() param1+param2;
Minus<type>() -
Multiplies<type>() *
Divides<type>() /
Modulus<type>() %
Equal_to<type>() ==
Not_equal_to<type>()
Less_equal<type>() <
Greater<type>() >
Less_equal<type>() <=
Greater_equal<type>()
Logical_not<type>() !param
Logical_and &&
Logical_or<type>() ||
要使用这些仿函数必须包含头文件<functional>
8.2.1函数配接器
函数配接器就是指能够将仿函数和另一个仿函数或者某个值或某个一般函数结合起来的仿函数声明于<functional>
例如find_if(coll.begin(),coll.end(),bind2nd(greater<int>(),42))
其中bind2nd(greater<int>(),42)d导致一个组合型仿函数检查某个值是否大于42
预定义的函数配接器
Bind1st（op,value） op(value,param)
Bind2nd(op,value) op(value,param)
Not1(op) !op(param)
Not2(op) !op(param1,param2);
下面语句返回某群集中第一个偶数值
Find_if(coll.begin(),coll.end(),not1(Bind2nd(modulus<int>(),2)))
8.5针对成员函数设计的配接器
成员函数配接器
Mem_fun_ref(op) 调用op那是某对象的一个const成员函数
Mem_fun(op) 调用op那是对象指针的一个const成员函数
一下例子：
classPerson
{
private:
std::string name;
public:
voidprint()const
{
std::cout<<name<<endl;
}
voidPrintWrite(stringprefix)
{
cout<<prefix<<endl;
}
};
void foo(constvector<Person>&coll)
{
for_each(coll.begin(),coll.end(),mem_fun_ref(&Person::print));
for_each(coll.begin(),coll.end(),bind2nd(mem_fun_ref(&Person::PrintWrite),"person:"));
}
对于mem_fun其作用的对象时指针序列
void foo(constvector<Person*>&coll)
{
for_each(coll.begin(),coll.end(),mem_fun(&Person::print));
for_each(coll.begin(),coll.end(),bind2nd(mem_fun(&Person::PrintWrite),"person:"));
}
注意：被mem_fun和mem_fun_ref调用的成员函数必须是const C++标准库并不针对non_const成员函数提供函数配接器
6针对一般函数设计的函数配接器
另一个函数配接器ptr_fun允许在其他函数配接器中使用一般函数
Ptr_fun(op) op(param)
Op(param1,param2)
一般函数 boolcheck(int elem)
Pos=find_if(coll.begin(),coll.end(),not1(ptr_fun(check))
第二种用法：
当你有一个双参数全局函数又想把它当成一个单参数函数来使用可以用如下语句：
Pos=find_if(coll.begin(),coll.end(),bind2nd(ptr_fun(strcmp),””);
7让自己的仿函数也可以使用函数配接器
你可以编写自己的仿函数但是如果希望他们能够和函数配接器搭配使用就必须满足某些点条件必须提供一些型别成员来反应参数和返回值的型别C++标准库提供一下结构：
Temple<classArg,class Result>
Structunary_funcation
{
TypedefArg argument_type;
TypedefResult result_type;
};
Template<classArg1,class Arg2,class Result>
Structbinary_function
{
TypedefArg1 first_argument_type;
TypedefArg2 second_argument_type;
TypedefResult result_type;
};
如此一来仿函数只要继承以上形式之一就能轻松满足配接器的条件
下面定义一个完整的防函数该例第二个参数做指数计算第一个参数的幕
#include<functional>
#include<cmath>
Template<classt1,class t2>
Structfopow:public std::binary_function<t1,t2,t1>
{
t1 operator()(t1 base,t2 exp)const
{
Return std::pow(base,exp);
}
}
使用：
Transform(coll.begin(),coll.end(),ostream_iterator<int>(cout,”,”),bind2nd(fopow<folat,int>(),3);
8. 辅助用仿函数
用已有仿函数组合成新的仿函数
组合型配接器：
f(g(elem))：一元组合函数的一般形式g()的执行结果被当做发（（）的参数整个表达式是一个一元函数
f(g(elem1,elem2))：作为一个二元判断式
f(g(elem),h(elem)):整个作为一元函数
f(g(elem1),h(elem2)):作为二元函数..
这些组合型配接器并未纳入标准规范中，所以我们没有他们的标准名字
可能的名字：
f(g(elem)) 本书采用compose_f_gx SGI STL采用：compose1
f(g(elem1,elem2)) compose_f_gxy
f(g(elem),h(elem)) compose_f_gx_hx compose2
f(g(elem1),h(elem2)) compose_f_gx_hy
9一元组合函数配接器
Compose_f_gx
一下例子进行加10再乘以4运算：
template<classop1,classop2>
classcomplose_f_gx_t:publicunary_function<typenameop2::argument_type,typenameop1::result_type>
{
private:
op1 op11;
op2 op22;
public:
complose_f_gx_t(constop1&o1,constop2&o2):op11(o1),op22(o2){}
typenameop1::result_typeoperator()(consttypenameop2::argument_type&x)const
{
returnop11(op22(x));
}
};
template<classop1,classop2>
inlinecomplose_f_gx_t<op1,op2>
complose_f_gx(constop1&o1,constop2&o2)
{
returncomplose_f_gx_t<op1,op2>(o1,o2);
}
void main()
{
vector<int>col;
for(inti=1;i<9;++i)
{
col.push_back(i);
}
for_each(col.begin(),col.end(),print);
cout<<endl;
transform(col.begin(),col.end(),ostream_iterator<int>(cout,","),complose_f_gx(bind2nd(multiplies<int>(),5),bind2nd(plus<int>(),10)));
}
【compose_f_gx_hx】组合两个算准则
template<classop1,classop2，class op3>
classcomplose_f_gx_t:publicunary_function<typenameop2::argument_type,typenameop1::result_type>
{
private:
op1 op11;
op2 op22;
op3 op33;
public:
complose_f_gx_t(constop1&o1,constop2&o2,const op3& o3):op11(o1),op22(o2),op33(o3){}
typenameop1::result_typeoperator()(consttypenameop2::argument_type&x)const
{
returnop11(op22(x),op33(x));
}
};
template<classop1,classop2,class op3>
inlinecomplose_f_gx_t<op1,op2,op3>
complose_f_gx(constop1&o1,constop2&o2,const op3& o3)
{
returncomplose_f_gx_t<op1,op2,op3>(o1,o2,o3);
}
Compose_f_gx_hx将两个一元表达式对同一对象的运算结果再以一个表达式加以组合
Compose_f_gx_hx(op1,op2,op3);
【二元组合函数配接器】
Compose_f_gx_hy下面是可能的实作手法
template<classop1,classop2，class op3>
classcomplose_f_gx_hy_t:publicunary_function<typenameop2::argument_type, typenameop3::argument_type，typenameop1::result_type>
{
private:
op1 op11;
op2 op22;
op3 op33;
public:
complose_f_gx_hy_t(constop1&o1,constop2&o2,const op3& o3):op11(o1),op22(o2),op33(o3){}
typenameop1::result_typeoperator()(consttypenameop2::argument_type&x ,consttypenameop2::argument_type&y)const
{
returnop11(op22(x),op33(y));
}
};
template<classop1,classop2,class op3>
inlinecomplose_f_gx_hy_t<op1,op2,op3>
complose_f_gx_hy(constop1&o1,constop2&o2,const op3& o3)
{
returncomplose_f_gx_hy_t<op1,op2,op3>(o1,o2,o3);
}
STL算法讲解1 【算法概览】
STL算法采用覆盖模式而非安插模式，所以调用者必须保证目标区间拥有足够元素空间
2算法分类
(1)尾词 _if
如果算法有两种形式，参数个数相同，但第 一形式的参数要求传递一个值，第二形式的参数要求传递数值那么_if就派上用场，无尾词传递数值有尾词_if传递函数或者仿函数例如find()和find_if
2)尾词_copy
这个尾词用来表示此算法中，元素不光被操作，还会被被复制到目标区间Reverse()将区间元素颠倒次序，而reverse_copy（）翻转并复制到目标区间
非变动性算法：
非变动性算法既不改动元素次序也不改动元素的值他们透过input迭代器和forward迭代器完成工作因此可以作用在所有容器上一下是所有非变动算法
变动性算法：
变动性算法要不直接改变元素值要不就是在复制到另一区间的过程中改变元素值如果是第二种情况原区间不会发生变化
最基本的变动性算法是for_each()和transfrom()他们行为不同点：
For_each()
例如：
Void square(int& elem)
{
Elem=elem*elem;
}
For_each(col.begin(),col.end(),squre)
Transform()运用某项操作，该操作返回被改动后的参数，其奥妙在于可以被用来将结果赋值给原元素例如：
Int square（int elem）
{
Returnelem*elem；
}
Transform(coll.begin(),coll.end(),coll.begin(),square);
为了安全起见最好只针对以有序的区间调用merge（）
移除性算法：
移除性算法是一种特殊的变动性算法，他们可以移除某些区间内的元素，也可以
在复制过程中执行移除动作和变动性算法类似移除性算法的目标区间也不能是关联式容器
注意移除性算法只是在逻辑上移除元素手段是将不需要被移除的元素往前覆盖应该被移除的元素。至于是否使用这个位置进行诸如“实际移除元素”这就是操作者的事了
变序性算法：
所谓变序性算法是透过元素值的赋值和交换，改变元素的顺序但不改变元素的值(操作不能是关联式容器)：
排序算法
排序算法是一种特殊的变序性算法但是比一般的变序性算法复杂花费更多时间，实事实上排序算法的复杂度通常低于线性算法的而且通常需要动用随机存取迭代器
Sort()内部采用quicksort算法因此保证了很好的平均性服复杂度为n*log(n)但最差情况下也可能具有非常差的性能二次复杂度
Partial_sort()内部采用heapsort算法n*log(n)复杂度大多数情况下比quicksort慢2-5倍partial_sort()的优点是任何时候都能保证n*log(n)的性能
Stable_sort（）内部采用mergesort他对所有元素排序然而只有保证有足够内存时她才具有n*log(n)复杂度否则复杂度为n*log(n)*log(n)优点是会保持元素之间的相对次序
List没有提供随机存取迭代器所以不能对他使用排序算法，但是其本身提供sort算法
已序区间算法:
前5个算法属于非变动算法，他们只是依名搜索元素其他算法用来将两个已序区间合并然后把结果写到目标区间一般而言这些算法的结果仍然有序
数值算法：
数值算法以不同方式组合数值元素
Accumulate()和inner_product()返回一个值而且不变动区间。其他算法把结果写到目标区间该区间与源区间的元素个数相同
以上算法特别灵活在缺省情况下accumulate求取所有元素的总和诶过把它作用咋string上就可以产生字符串连接功效，adjacent_difference()和partial_sum可将区间在相对值和绝对值之间互相转换
仿函数(函数对象)和STL算法