泛型算法

c/c++

浏览数:385

2019-3-30

顺序容器中只定义了添加删除访问等简单操作,用户更多的需求,只能通过泛型算法实现。此类算法称之为”泛型”是因为它们可以用于不同类型的元素和多种容器类型。

泛型算法分类

大多数泛型算法都定义在algorithm中,标准库还在numeric中定义了一组数值泛型算法。常见的泛型算法可以分为:只读算法、写容器算法、重排容器算法、定制操作等四个类别。下面将分别进行简单介绍。

1 只读算法

以下大部分算法都有自己的重载版本,感兴趣的同学可以查找相关资料,进行深入学习。下面用代码的方式对常见只读算法进行介绍。

1.1 find查找
//查找目标元素在容器中的位置
void find_element_pos(vector<int> & v, int val){
    cout << find(v.begin(), v.end(), val) - v.begin() << endl;
}
1.2 accumulate求和
void accumulate_display(){
    vector<int> vi = { 1, 2, 3, 4 };
    vector<string>vs = { "accu", "disp" };
    //整数累加初值设为0
    cout << accumulate(vi.begin(), vi.end(), 0) << endl;
    //字符累加初值设为"";
    cout << accumulate(vs.begin(), vs.end(), string("")) << endl;
}
1.3 count计算目标元素的个数
void count_element(vector<int> & v, int val){
    cout << count(v.begin(), v.end(), val) << endl;
}
1.4 equal判断两容器是否相等
void equal_display(){
    list <char*>a = { "a", "b" };
    vector<const char *> b = { "a", "b" };
    cout << equal(a.begin(), a.end(), b.begin())<<endl;
}
//两点说明:
//1. equal假设,第二序列b至少与a一样长,程序员有责任对此作出保证。
//2. 两序列中的元素类型不必完全相同,只要能够使用==进行比较即可。

2 写容器算法

当我们将新值赋予序列中元素时,必须保证序列原大小足够大。算法保持泛型,不会进行具体的容器操作(容器接口可能不同),因此算法自身不能改变容器的大小。常见用法如下:

2.1 填充fill/fill_n
void fill_container(){
    //fill_n/fill无法改变容器大小
    vector<int> vi;
    fill_n(vi.begin(), 10, 0);//错误,试图在空的vi中填入10个元素
    vi.push_back(1);
    vi.push_back(2);
    fill_n(vi.begin(), vi.size(), 0);//正确,将所有元素置为0
    fill(vi.begin(), vi.end(), 1);//正确,将所有元素置为1
}
2.2 拷贝copy
void copy_display(){
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int b[sizeof(a) / sizeof(*a)];
    auto pos = copy(begin(a), end(a), b);
    //三点说明:
    //1. sizeof在编译时计算,所以支持用来定义数组b的大小
    //2. begin(a),end(a)指向a的第一个元素,以及尾后位置
    //3. 返回值pos指向目标迭代器递增后的值,此例中pos恰好指向b的尾后迭代器
}
2.3 替代replace
void replace_display(){
    vector<int> vi = { 1, 2, 1, 4, 1, 6, 1, 8, 1 };
    int nOld = 1, nNew = 10;
    replace(vi.begin(), vi.end(), nOld, nNew);
}
//将vi中所有1替换为10

3 重排算法

某些算法会重排容器中元素的顺序,例如sortunique,前者对元素进行排序,后者将唯一的元素移至前段,重复的元素移至后端。常见的用法如下:

3.1 sort/stable_sort
bool compare_int(int& a, int& b){
    return a > b;
}
void sort_display(){
    vector<int> vi = { 3, 1, 4, 2, 4, 2, 1, 3, 5, 6, 8, 4, -5 };
    sort(vi.begin(), vi.end());//升序重排
    sort(vi.rbegin(), vi.rend());//降序重排
    sort(vi.begin(), vi.end(), compare_int);//支持二元谓词
}
//三点说明:
//1. `sort`用快速排序实现,是不稳定的排序算法,`stable_sort`用归并排序实现,是稳定的排序算法
//2. `sort`和`stable_sort`都支持二元谓词,来重新定义元素间的比较
//3. 基本数据类型的降序重排,可以直接使用`rbegin()`和`rend()`实现
3.2 unique/unique_copy
void unique_display(){
    vector<int> vi = { -5, 3, 1, 4, 2, 4, 2, 1, 3, 5, 6, 8, 4 };
    sort(vi.begin(), vi.end());//升序重排
    auto pos = unique(vi.begin(), vi.end());
    for (size_t i = 0; i < vi.size(); ++i){
        cout << vi[i] << " ";
    }
    cout << endl<<*pos << endl;
    //vi此时为{-5,1,2,3,4,5,6,8,4,4,5,6,8};
    //pos指向不重复区域的下一个迭代器,此处指向vi[4] = 4;
}
//unique_copy是unique的“_copy”版本,返回的是生成的序列的最后一个元素的下一个位置

4 定制操作

4.1 谓词

谓词(predicate)是一个可调用的表达式,其返回结果是一个能用做条件的值,标准库算法将谓词分为一元谓词和二元谓词两类。谓词可以作为参数传递进函数,如上例3.1所示。

4.2 lambda表达式

使用谓词给算法传递参数时,受到严格的限制。当需要传递更多参数给算法时,可以使用lambda表达式。lambda 表达式是一个可调用的代码单元,我们可以将它理解为一个匿名的内联函数。

C++11 的 lambda 表达式规范如下。其中,capture表示捕获列表,它可以捕获所在函数的定义的局部变量。paramsretbody和普通函数一样,代表参数、返回类型和函数体。

(1) [ capture ] ( params ) mutable exception attribute -> ret { body }   
(2)    [ capture ] ( params ) -> ret { body }        
(3) [ capture ] ( params ) { body }  
(4) [ capture ] { body }

下面通过几个简单的实例来了解其用法

  • (1) 忽略参数列表和返回类型
void lambda_dispaly1(){
    auto f = [] {return 10; };
    cout << f() << endl;
}
//capture,返回类型为空,只定义了body
  • (2) 向lambda传参
void lambda_dispaly2(){
    auto f = [](const string a, const string b) {return a <b; };
    cout << f("1", "2") << endl;
}
//capture为空,定义了params和body
  • (3) 使用捕获列表
void lambda_dispaly3(size_t size){
    auto f = [size](const string a) {return a.size() >= size; };
    cout << f("123") << endl;
}
//从所定义的函数体中捕获局部变量size
  • (4) 引用捕获
//与普通函数相同,lambda表达式传递参数时也有传值和传引用两种,前述的都是传值捕获,下例为引用捕获
void lambda_dispaly4(size_t &size){
    auto f = [&size](const string a) {return a.size() >= size; };
    cout << f("123") << endl;
}
//从所定义的函数体中捕获局部变量size的引用
  • (5) 隐式捕获、混合捕获
void lambda_dispaly5(vector<string>&words, size_t size){
    stable_sort(words.begin(), words.end(),
        [](const string& a, const string & b)
            {return a.size() < b.size(); });
    //查找第一个满足size()>size的元素
    auto pos = find_if(words.begin(), words.end(), 
        [&](string & a)
            {return a.size() > size; });
    int count = words.end() - pos;
    cout << count << endl;
}
//说明三点:
//1. 除显示捕获外,我们还可以让编译器来推断我们要捕获的变量。
//2. 我们需要在capture捕获列表中填写 = 或 & 指示编译器采用值捕获还是引用捕获
//3. 当我们想混合使用隐式和显示捕获时,捕获列表的一个元素必须是 = 或 &,此符号指定了默认捕获方式为引用和值。
  • (6) 可变lambda
void lambda_dispaly6(){
    size_t vi = 10;
    auto f = [vi]()mutable{return  ++vi; };
    cout << f() << endl;
}
//默认情况下,对于一个值被拷贝的对象,lambda表达式不会改变其值,因此必须加上mutable来申请,其捕获的变量值可变。
  • (7) 指定返回类型lambda
void lambda_dispaly7(){
    auto f = [](const string &a, const string &b)->bool 
    {if (a < b) return true; else return false; };
    cout << f("1", "2") << endl;
}
//默认情况下,如果lambda函数体包含return之外的任何语句,编译器则返回void。
//此时,当我们需要为lambda定义返回类型,必须使用尾置返回类型。
4.3 参数绑定

对于只在一两个地方使用的简单操作,lambda表达式是最高效的,如果需要在多个地方使用相同的定制操作,我们可以使用标准库bind函数。bind可以重排参数顺序。

bind函数定义在头文件functional中,使用格式如下:

auto newFun = bind(Fun, arg_list);

newFun本身是一个可调用对象,arg_list是一个用逗号分隔的参数列表,其中可能包含”_n“的名字(定义在std::placeholders中),此为”占位符“,表示newFun中的参数。_1newFun的第一个参数对应,_2newFun第二参数对应,依次类推。

  • (1) 重排参数
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std::placeholders;
using namespace std;
auto bind_display1 = bind(lambda_dispaly5, _2, _1);//lambda_dispaly5定义参见4.2
int main(){
    vector<string> vecStr = { "abc", "bscd", "tsed" };
    bind_display1(4, vecStr);
    return 0;
}
  • (2) 参数个数修改
auto bind_display2 = bind(lambda_dispaly5, _1, 4);
int main(){
    vector<string> vecStr = { "abc", "bscd", "tsed" };
    bind_display2(vecStr);
    return 0;
}
//将lambda_dispaly5中第二参数设置为4
//注意,bind中第2个到第n个函数与lambda_dispaly5相对应。"_1","_2"与bind_display函数对应。

5 迭代器

除了为每个容器定义的迭代器之外,标准库在头文件iterator中还定义了额外几种迭代器。这些迭代器包括以下几种:

  • 1)插入迭代器
    这些迭代器被绑定到一个容器上,可用来向容器插入元素
  • 2)流迭代器
    这些迭代器被绑定到输入或输出上,可用来遍历所有关联的IO流
  • 3)反向迭代器
    这些迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器
  • 4)移动迭代器
    这些专用的迭代器不是拷贝其中的元素,而是移动它们。
1)插入迭代器

插入迭代器接受一个容器,生成一个迭代器,能够为给定容器添加元素。其根据插入位置不同,分为以下三种类型:

  • back_inserter创建一个使用push_back的迭代器
  • front_inserter创建一个使用push_front的迭代器
  • inserter创建一个使用insert的迭代器。
2)流迭代器

虽然iostream类型不是容器,但标准库定义了用于这些IO类型对象的迭代器。istream_iterator读取输入流,ostream_iterator向一个输出流写数据。通过使用流迭代器,我们可以用泛型算法从流对象读取数据以及向其写入数据。

3)反向迭代器

反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。对于反向迭代器,递增(以及递减)操作的含义会颠倒过来。递增一个反向迭代器(++it)会移动到前一个元素;递减一迭代器(--it)会移动到下一个元素。

除了forward_list之外,其他容器都支持反向迭代器。我们可以通过调用rbeginrcendcrbegincrend成员函数来获得反向迭代器。这些成员函数返回指向容器尾元素和首元素之前一个位置的迭代器。与普通迭代器一样,反向迭代器也有const和非const版本。