欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-02-05 13:22:16
基础泛型算法 泛型算法本身运行于迭代器之上,不会执行容器的操作,可以改变容器中保存元素的值,也可以在容器内移动元素,但永远不会直接添加或删除元素。插入迭代器是一种特殊的迭代器,当...

基础泛型算法

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

只读算法

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

    vector 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 v = {1,2,3,4,5};
    vector 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 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 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 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 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 l = {1,2,3,4,5};
    list 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 in(cin), eof;
    // 用accumulate函数对输入的整数求和
    cout << accumulate(in, eof, 0) << endl;

    vector v = {1,2,3,4,5};
    // 定义一个输出流迭代器out,与cout绑定,每个值后面都输出一个" "
    ostream_iterator 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[]) {

    listl {15,24,33,42,51};
    listl2 {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中了。