[C++ 面试基础知识总结] 泛型算法

参考书籍：《C++ Primer》

目录

• C 面试基础知识总结 泛型算法
  • 目录
  • 基础泛型算法
    • 只读算法
    • 写容器算法
    • 重排容器元素算法
  • 定制操作
    • 向算法传递函数
    • lambda表达式
    • 参数绑定
  • 特殊迭代器
    • 插入迭代器
    • iostream迭代器
    • 反向迭代器
    • 5类迭代器
  • 链表的特定容器算法

基础泛型算法

泛型算法本身运行于迭代器之上，不会执行容器的操作，可以改变容器中保存元素的值，也可以在容器内移动元素，但永远不会直接添加或删除元素。插入迭代器是一种特殊的迭代器，当算法操作插入迭代器时，迭代器可以向容器添加元素，但算法本身永远不会做这样的事。

只读算法

只读算法只会读取其输入范围内的元素，而从不改变元素。

    vector<int> v = {1,2,3,4,5,4,3,2,1};
    string s1 = "Summer love C++";
    string s2 = "Summer love Swift";

    auto f = find(v.begin(), v.end(), 2);  //find函数是查找给定值在给定范围内的位置
    cout << (f != v.end()) << endl;  //如果查找到，返回第一个等于给定值元素的迭代器，否则返回尾后迭代器
    auto c = count(v.begin(), v.end(), 2);  //count函数返回的是给定值在给定范围内的出现次数
    auto sum = accumulate(v.begin(), v.end(), 0);  //accumulate函数是将给定范围内的所有元素相加，最后一个参数为初始值
    auto sSum = accumulate(s1.begin(), s1.end(), string("Hello:")); // 字符串字面值不能执行+运算，所以最后一个参数不能写成"Hello:"
    auto isEuqal = equal(s1.begin(),s1.end() - 3,s2.begin());//isEqual函数是比较两个序列是否相等，前两个参数表示第一个序列的范围，最后一个参数表示第二个序列的起始位置（两个序列长度相等）

写容器算法

    vector<int> v = {1,2,3,4,5};
    vector<int> v2;

    fill(v.begin(), v.end(), 0);  //将给定范围内的元素全部替换为0
    fill_n(v.begin(), 3, -1);  //将给定位置开始的3个元素全部替换为-1
    fill_n(back_inserter(v), 5, 1);  //使用插入迭代器在容器尾部添加5个值为1的元素
    replace(v.begin(), v.end(), 0, 1);  //将给定范围内所有值为0的元素替换为1
    replace_copy(v.begin(), v.end(), back_inserter(v2), -1, 1);  //将给定范围内的所有元素拷贝出来，再将所有为-1的元素替换为1后有插入迭代器添加在v2尾部，v1中的元素没有变化

重排容器元素算法

    vector<int> v = {1,2,3,4,5,4,3,2,1};

    sort(v.begin(), v.end());  //按大小重排v中的元素 {1，1，2，2，3，3，4，4，5}
    auto end_unique = unique(v.begin(), v.end()); //将不重复的元素覆盖到容器前部，后部不动 {1，2，3，4，5，3，4，4，5}，并返回不重复区域之后第一个位置的迭代器
    v.erase(end_unique,v.end()); // 可利用上面返回的迭代器删除重复元素

定制操作

向算法传递函数

可以使用自定义的条件来给容器中的元素排序。下面以给几个两位数排序为例。

//自定义排序规则为按照各位数字的大小来排序
bool isSmaller(const int &i1, const int &i2){
    return i1%10 < i2%10;
}

    vector<int> v = {15,24,33,42,51,41,32,23,14};
    //在sort函数后增加第三个参数，自定义的谓词，排序结果：51 41 42 32 33 23 24 14 15
    sort(v.begin(), v.end(),isSmaller);

如果希望个位数字大小相同的数字，再按十位数字大小来排序，可以用稳定排序

    vector<int> v = {15,24,33,42,51,41,32,23,14};

    //先按照两位数大小进行排序，顺便按十位数字大小排序
    sort(v.begin(), v.end());
    //采用稳定排序的函数按照个位数字大小，再对容器进行排序，由于是稳定排序，不会改变相同个位数字大小的元素之间的原有顺序。排序结果：41 51 32 42 23 33 14 24 15
    stable_sort(v.begin(), v.end(), isSmaller);

lambda表达式

调用普通函数：

int func(){
    return 1;
}

auto f = func();

调用lambda表达式可以得到同样结果

// 中括号内为捕获列表，小括号内为参数列表，->后为返回类型，花括号内为函数体
auto f = []() -> int{return 1;};

lambda表达式还可以省略参数列表和返回类型

auto f = []{return 1;};

用lambda表达式可以简化之前的排序的代码：

    vector<int> v = {15,24,33,42,51,41,32,23,14};

    sort(v.begin(), v.end());
    //第三个参数传入一个与isSmaller函数等价的lambda表达式
    stable_sort(v.begin(), v.end(), [](const int &i1, const int &i2){return i1%10 < i2%10;});

在上述vector的基础上，输出所有两位数四舍五入后的值

    int n = 5;
    //采用find_if函数找到第一个复合条件的位置，这里lambda表达式需要使用局部变量n，需要在捕获列表中加入n，函数体才能使用n
    auto pos = find_if(v.begin(), v.end(), [n](const int &i){return i%10 >= n;});
    //for_each函数是对所有序列中的元素分别调用一次lambda表达式
    for_each(v.begin(), pos, [](const int &i){cout << (i/10)*10 <<" ";});
    for_each(pos, v.end(), [](const int &i){cout << (i/10+1)*10<<" ";});

lambda表达式可以采取值捕获和引用捕获两种方式。

    auto v1 = 1, v2 = 2;
    auto f1 = [v1] { return v1;};  //值捕获，之后改变v1的值不会影响f1()的值
    auto f2 = [&v2] { return v2;};  //引用捕获，之后改变v2的值会改变f2()的值
    auto f3 = [=]{return v1 + v2;};  //对所有变量采用值捕获
    auto f4 = [&]{return v1 + v2;};  //对所有变量采用引用捕获
    auto f5 = [=,&v2]{return v1 + v2;};  //对除v2外的所有变量采用值捕获
    auto f6 = [&,v1]{return v1 + v2;};  //对除v1外的所有变量采用引用捕获
    auto f7 = [v1] () mutable {return ++v1;};  //加上mutable关键字可以在函数体内改变捕获变量的值

如果lambda函数体包含了除return以外的任何语句，则编译器会假定lambda返回void，如果要返回其他类型，需要显示指定出来。

auto f = [v1] ()  mutable ->int{ ++v1 ; return v1;};

参数绑定

bool checkNumber(const int &i, int n){
    return i%10 >= n;
}

由于函数有两个参数，而find_if只接受一元谓词，不能写成如下形式：

auto pos = find_if(v.begin(), v.end(), checkNumber);

这个时候就需要用到bind函数

// _1表示第一个生成的可调用对象中参数的位置，依次类推_2表示第二个，使用这些占位符时需要声明使用命名空间 using namespace std::placeholders;
auto pos = find_if(v.begin(), v.end(), bind(checkNumber, _1,n));

等价于

auto pos = find_if(v.begin(), v.end(), [n](const int &i){return i%10 >= n;});

占位符的顺序是传递参数的顺序，例如之前的

sort(v.begin(), v.end(),isSmaller);

如果改写为

sort(v.begin(), v.end(),bind(isSmaller, _2, _1));

则相当于颠倒了两个参数的顺序，最终得到的序列将会是从大到小的。

在bind函数中，非占位符参数是引用的时候，需要用ref函数或cref函数（常量）保护起来，写成以下形式

    int x =5;
    int &n = x;
    auto pos = find_if(v.begin(), v.end(), bind(checkNumber, _1,ref(n)));

    const int &m = 5;
    auto pos = find_if(v.begin(), v.end(), bind(checkNumber, _1,cref(m)));

特殊迭代器

插入迭代器

插入迭代器是一种迭代器适配器，它接收一个容器，生成一个迭代器，能实现给定容器添加元素。该迭代器调用容器操作来向给定容器的指定位置插入一个元素。插入迭代器有3种类型，只是插入位置存在差异。

    list<int> l = {1,2,3,4,5};
    list<int> l1,l2,l3;

    copy(l.begin(), l.end(), front_inserter(l1));  //在头部插入，copy函数执行完成后结果为5 4 3 2 1
    copy(l.begin(), l.end(), back_inserter(l2));  //在尾部插入，copy函数执行完成后结果为1 2 3 4 5
    copy(l.begin(), l.end(), inserter(l3, l3.begin()));  //在指定位置插入，copy函数执行完成后结果为1 2 3 4 5 

需要注意的是，front_inserter会将插入元素序列颠倒过来，类似数据结果中链表的头插法。

iostream迭代器

通过流迭代器，可以用泛型算法从流对象读取数据以及向其写入数据。

    // 定义两个输入流迭代器in，eof，in与cin绑定，eof为空，相当于尾后迭代器
    istream_iterator<int> in(cin), eof;
    // 用accumulate函数对输入的整数求和
    cout << accumulate(in, eof, 0) << endl;

    vector<int> v = {1,2,3,4,5};
    // 定义一个输出流迭代器out,与cout绑定，每个值后面都输出一个" "
    ostream_iterator<int> out(cout," ");
    // 将vector拷贝到输出流迭代器
    copy(v.begin(), v.end(), out);
    cout << endl;

反向迭代器

反向迭代器是在容器中从尾元素向首元素反向移动的迭代器，rbegin函数返回的指向容器尾元素的迭代器，rend函数返回指向容器首元素之前位置的迭代器。crbegin和crend为相应的const型反向迭代器。

    string s = "C++,Objective-C,Swift";
    // 反向查找最后一个单词，找到逗号为止
    auto last = find(s.crbegin(), s.crend(), ',');

    // 输出结果为 tfiwS ，因为构造string的两个迭代器为反向迭代器
    cout << string(s.crbegin(),last) << endl;
    // 输出结果为 Swift，调用base函数可以将反向迭代器转换为普通迭代器
    cout << string(last.base(),s.cend()) << endl;

5类迭代器

算法所要求的迭代器操作可以分为5个类别，每个算法都会对它的每个迭代器参数指明须提供哪类迭代器。

输入迭代器：只读不写，单遍扫描，只能递增，find和accumulate要求输入迭代器，istream_iterator是输入迭代器
输出迭代器：只写不读，单遍扫描，只能递增，copy的第三个参数和ostream_iterator就是输出迭代器
前向迭代器：可读写，多遍扫描，只能递增，replace要求前向迭代器，forward_list上的迭代器也是前向迭代器
双向迭代器：可读写，多遍扫描，可递增递减，reverse要求双向迭代器，list上的迭代器也支持双向迭代器
随机访问迭代器：可读写，多遍扫描，支持全部迭代器运算，sort要求随机访问迭代器，array，deque，string，vector的迭代器和内置数组的指针都是随机访问迭代器。

链表的特定容器算法

由于链表类型不支持要求随机访问迭代器的通用算法，所以定义了一些类似的算法。

//  用于提供比较个位数字大小谓词的函数
bool isSmaller(const int &i1, const int &i2){
    return i1%10 < i2%10;
}

//  用于提供判定各位数字是否相等谓词的函数
bool isEuqal(const int &i1, const int &i2){
    return i1%10 == i2%10;
}

int main(int argc, const char * argv[]) {

    list<int>l {15,24,33,42,51};
    list<int>l2 {41,32,23,14};

    // 将l2的元素全部合并到l中，合并后l2为空。l和l2都必须有序，合并后会自动排序。合并后的l： 14 15 23 24 32 33 41 42 51
    l.merge(l2);  

    // 根据个位数字大小排序  排序后的l：41 51 32 42 23 33 14 24 15
    l.sort(isSmaller);

    // 删除个位数字重复的元素  删除后的l：41 32 23 14 15
    l.unique(isEuqal);
    return 0;
}

链表还定义了splice算法，以下2种写法等价，都是将l2所有元素移动到l尾部，并从l2中删除

    l.splice(l.end(), l2);
    l.splice(l.end(), l2, l2.begin(),l2.end());

如果只移动一个元素可以写成如下形式

    l.splice(l.end(), l2, l2.begin());

注意：多数链表特有算法与其通用版本很相似，但不完全相同，链表特有版本的一个至关重要的区别是会改变底层的容器。例如merge算法将l2合并到l中后，会将l2的全部元素从l2列表中删除。但这些删除的元素依旧存在，只是存在于l中了。