当前位置: 代码迷 >> 综合 >> generic algorithm
  详细解决方案

generic algorithm

热度:97   发布时间:2023-09-29 12:23:34.0

generic algorithm(泛型算法)

  1. 可用于不同元素/容器类型
  2. 算法运行于迭代器之上,不会执行容器操作。所以算法不会直接添加或者删除元素。
  3. 由于算法可以依靠迭代器完成大部分的操作,所以并不需要依靠容器的类型;但是依赖元素类型提供的操作。
  4. 大多数标准库算法对2个迭代器(第2个为尾后迭代器)表示的范围进行操作。
  5. 插入算法都假定具有足够空间
  6. 对于list和forward_list应优先使用成员函数版本CP369
  7. 命名规范
    • 一些算法允许通过重载传递谓词
    • _if代表函数使用谓词来代替元素值
    • _copy代表将处理结果写入到额外的目的空间(同时写回输入序列)
  8. 形参形式
Func(beg,end,other args);
Func(beg,end,dest,other args);//dest:指定目的位置
Func(beg,end,beg2,other args);
Func(beg,end,beg2,end2,other args);//从beg2开始的空间至少和beg,end一样大
  • 只读算法:

    • 如果算法只访问并不改变元素,建议使用cbegin()和cend()
    • 对于操作2个序列的算法:
      • 序列的容器类型可以不填
      • 用单一迭代器表示第2个序列编译器假定第2个序列和第1个序列一样长。
    • find
    • find_if:寻找第一个具有某种特征的值
      • 接收3个参数
      • 第3个参数为谓词
      • 不存在时返回尾后迭代器
    • accumulate:求和
    • 接收3个参数
    • 第3个参数为和的初值,决定加法运算符的类型和返回类型
    • 序列中的元素类型必须能和第3个参数的类型匹配,并定义了+运算符
    • equal:比较序列是否相同
    • 接收3个参数
    • 第3个参数为第2个序列的首元素
  • 只写算法:

    • 确保原大小必须等于/大于算法写入的元素数目
    • 编译器假定有足够的空间,不会进行检查

    • fill:将给定的值赋给序列中的每个元素

    • 接收3个参数
    • 第3个参数被赋值的元素

    • fill_n

fill_n(dest,n,val)//将从dest开始的n个元素变为val
  • copy
    • 接收3个参数
    • 第3个参数表示目的序列的起始位置
    • 必须确保目的序列的容量
    • 返回目的迭代器之后的值
int a1[]={
   0,1,2,3,4};
//保证大小一致
int a2[sizeof(a1)/sizeof(*a1)];
//将a1拷贝给a2
auto ret=copy(begin(a1),end(a1),a2);
  • replace:将序列中指定的值都替换成新值

    • 接收4个参数
    • 第3个参数表示需要替换的值
  • replace_copy:将改变后的原序列的备份保存到别的地方

    • 相比replace额外接收第3个迭代器参数指出保存位置
replace_copy( list.cbegin(),list.cend(),back_inserter(ivec),0,42 );
这里写代码片
  • 排序算法
  • sort
  • unique:将重复的元素放在输入序列的最后,返回指向非重复序列之后的迭代器
void fun(vector<string> &word)
{sort(words.begin(),words.end());auto end_unique=unique(words.begin(),words.end());words.erase( end_unique,words.end() );
}

5标准库允许算法提供自己定义的操作来代替运算符
谓词:

  • 返回值可作为条件的表达式
  • 一元谓词:接收1个参数
  • 二元谓词:接收2个参数

例如

//二元谓词
bool isShorter(const string &s1,const string &s2)
{return s1.size()<s2.size(); }
sort( words.begin(),words.end(),isShorter );
//该算法保持相等元素的原有顺序
//在此例中相等为长度相同
stable_sort( words.begin(),words.end(),isShorter );

可调用对象:可以使用(args)(调用运算符)

  • 函数:适用于在多个地方重复使用
  • 函数指针
  • 重载调用运算符的类
    如果类定义了调用运算符,则该类对象称作函数对象。
    例如
struct absInt{int operator(){
   int val}const{return val<0?-val:val;}
};int i=-42;
absInt absobj;
//可以像使用函数一样调用该类的对象
int ui=absobj(i);
  • 标准库的函数对象CP510:可以代替运算符
  • 可用于泛型算法的实参
stable_sort(words.begin(),words.end(),Shortstring());
  • lambda表达式:适用于只需要在少数地方使用

调用形式:指明了返回类型和参数类型
不同类型的可调用对象可以共享同一调用形式。
例如

//虽然执行了不同的算术运算
int add(int i,int j){ return i%j; }
auto mod=[]{
   int i,int j}{ return i+j; }

函数表:存储指向可调用对象的指针
考虑使用map实现

map< string,function<int(int,int)> > binops;
/*实际存储的是指针(不是函数指针),无法分辨重载函数。考虑输入函数指针或者lambda CP513*/binops.insert( {
   "+",add} );
binops["+"](10,5);//指针指向add函数并传入参数
  相关解决方案