头条焦点：STL-常用算法总结

2023-02-13 19:15:15 来源:腾讯云

STL-常用算法总结

算法主要由头文件,,组成是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历、复制、删除等体积很小，只包括几个在序列上面进行简单数学运算的模板函数定义了一些模板类，用来声明函数对象常用遍历算法for_each遍历for_each(iterator beg, iterator end, _func);//遍历容器beg//起始迭代器end//结束迭代器_func()//函数或函数对象

for_each是实际开发中最常用的遍历算法，需要熟练掌握

(资料图片)

#include#include#includeusing namespace std;//普通函数void myPrint(int val){    cout << val << " ";}//仿函数class myPrint2{public:    void operator()(int val)    {        cout << val << " ";    }};int main(){    vectorv;    for (int i = 0; i < 10; i++)    {        v.push_back(i);    }    for_each(v.begin(), v.end(), myPrint);    cout << endl;    for_each(v.begin(), v.end(), myPrint2());    return 0;}

transform搬运

transform(iterator beg1, iterator end1, iterator beg2, _func);//搬运容器

beg1//源容器开始迭代器end1//源容器结束迭代器beg2//目标容器开始迭代器_func//函数或函数对象

搬运的目标容器必须提前开辟空间，否则无法正常搬运

#include#include#includeusing namespace std;class Transform{public:    int operator()(int val)    {        return val;    }};int main(){    vectorv;    for (int i = 0; i < 10; i++)    {        v.push_back(i);    }    vectorv2;    v2.resize(v.size());    transform(v.begin(), v.end(), v2.begin(), Transform());    for (vector::iterator it = v2.begin(); it != v2.end(); it++)    {        cout << *it << " ";    }    return 0;}

常用查找算法

find//查找元素find_if//按条件查找元素adjacent_find//查找相邻重复元素binary_search//二分查找法count//统计元素个数count_if//按条件统计元素个数find按值查找find(iterator beg, iterator end, value);//按值查找beg//开始迭代器end//结束迭代器value//查找的元素

返回一个迭代器，如果没有找到，返回end()

查找自定义数据类型需要重载==运算符，否则底层不知道如何对比

#include#include#includeusing namespace std;//查找内置数据类型void test01(){    vectorv;    for (int i = 0; i < 10; i++)    {        v.push_back(i);    }    //返回一个迭代器，如果没有找到，返回end()    vector::iterator it = find(v.begin(), v.end(), 5);    if (it == v.end())        cout << "没找到" << endl;    else        cout << "找到了" << *it << endl;}//查找自定义数据类型class Person{public:    Person(string name,int age)    {        this->m_age = age;        this->m_name = name;    }    //重载==运算符，让find知道如何对比Person类型数据    bool operator==(const Person& p)    {        if (p.m_age == this->m_age && p.m_name == this->m_name)            return true;        else            return false;    }    string m_name;    int m_age;};void test02(){    //准备数据    Person p1("A", 1);    Person p2("B", 2);    Person p3("C", 3);    Person p4("D", 4);    Person p5("E", 5);    //放入容器中    vectorp;    p.push_back(p1);    p.push_back(p2);    p.push_back(p3);    p.push_back(p4);    p.push_back(p5);    //查找    Person p6("A", 1);    vector::iterator it = find(p.begin(), p.end(), p6);    //输出，验证结果    if (it == p.end())        cout << "没找到" << endl;    else        cout << "找到了" << it->m_name << it->m_age << endl;}int main(){    test01();    test02();    return 0;}

find_if条件查找

find_if(iterator beg, iterator end, _Pred);

beg//开始迭代器#include#include#includeusing namespace std;//查找内置数据类型class GreaterFive{public: bool operator()(int v) { return v > 5; }};void test01(){ vectorv; for (int i = 0; i < 10; i++) { v.push_back(i); } vector::iterator it = find_if(v.begin(), v.end(), GreaterFive()); if (it == v.end()) cout << "没找到" << endl; else cout << "找到了" << *it << endl;}//查找自定义数据类型class Person{public: Person(string name, int age) { this->m_age = age; this->m_name = name; } string m_name; int m_age;};class GreaterThree{public: bool operator()(Person& p) { return p.m_age > 3; }};void test02(){ //准备数据 Person p1("A", 1); Person p2("B", 2); Person p3("C", 3); Person p4("D", 4); Person p5("E", 5); //放入容器中 vectorp; p.push_back(p1); p.push_back(p2); p.push_back(p3); p.push_back(p4); p.push_back(p5); //查找 vector::iterator it = find_if(p.begin(), p.end(), GreaterThree()); //输出，验证结果 if (it == p.end()) cout << "没找到" << endl; else cout << "找到了" << it->m_name << it->m_age << endl;}int main(){ test01(); test02(); return 0;}adjacent_find查找相邻重复元素如果查到，返回相邻重复元素的第一个位置的迭代器adjacent_find(iterator beg, iterator end)end//结束迭代器_Pred//函数或者谓词（返回bool数据类型的仿函数）beg//开始迭代器#include#include#includeusing namespace std;void test01(){ vectorv; for (int i = 0; i < 10; i++) { v.push_back(i); } v.push_back(5); vector::iterator it=adjacent_find(v.begin(), v.end()); if (it == v.end()) cout << "未找到相邻重复元素" << endl; else cout << "找到了相邻重复元素" << *it << endl;}int main(){ test01(); return 0;}binary_search二分查找bool binary_search(iterator beg, iterator end, value);end//结束迭代器查找指定的元素，查到返回true，否则返回false#include#include#includeusing namespace std;void test01(){ vectorv; for (int i = 0; i < 10; i++) { v.push_back(i); } cout << binary_search(v.begin(), v.end(), 5) << endl;}int main(){ test01(); return 0;}count统计对于统计自定义数据类型，需要重载==运算符#include#include#includeusing namespace std;//统计内置数据类型void test01(){ vectorv; v.push_back(10); v.push_back(20); v.push_back(10); cout << count(v.begin(), v.end(), 10) << endl;}//统计自定义数据类型class Person{public: Person(string name, int age) { this->m_name = name; this->m_age = age; } //需要重载==运算符 //底层要求加const bool operator==(const Person& p) { if (this->m_name == p.m_name) return true; } string m_name; int m_age;};void test02(){ Person p1("A", 1); Person p2("B", 2); Person p3("A", 3); Person p4("A", 4); vectorp; p.push_back(p1); p.push_back(p2); p.push_back(p3); cout << "与p4同名的元素个数" << count(p.begin(), p.end(), p4) << endl;}int main(){ test01(); test02(); return 0;}count_if条件统计按条件统计元素出现次数count_if(iterator beg, iterator end, _Pred);注意：在无序列表中不可用，如果是无序序列，结果未知beg//开始迭代器end//结束迭代器value//查找的元素beg//开始迭代器#include#include#includeusing namespace std;//统计内置数据类型class GreaterFive{public: bool operator()(int val) { return val > 5; }};void test01(){ vectorv; for (int i = 0; i < 10; i++) { v.push_back(i); } cout << count_if(v.begin(), v.end(), GreaterFive()) << endl;}//统计自定义数据类型class Person{public: Person(string name, int age) { this->m_name = name; this->m_age = age; } string m_name; int m_age;};class AgeGreaterTwo{public: bool operator()(const Person& p) { return p.m_age > 2; }};void test02(){ Person p1("A", 1); Person p2("B", 2); Person p3("A", 3); Person p4("A", 4); vectorp; p.push_back(p1); p.push_back(p2); p.push_back(p3); p.push_back(p4); //统计年龄大于2的人数 cout << count_if(p.begin(), p.end(), AgeGreaterTwo()) << endl;}int main(){ test01(); test02(); return 0;}常用排序算法end//结束迭代器_Pred//函数或者谓词（返回bool数据类型的仿函数）sort//对容器内元素进行排序random_shuffle//随机洗牌，将指定范围内的元素重新排序merge//容器元素合并，并储存到另一个容器中reverse//反转指定范围的元素sort排序sort(iterator beg, iterator end, _Pred)//排序beg//开始迭代器#include#include#includeusing namespace std;void test01(){ vectorv; for (int i = 0; i < 10; i++) { v.push_back(i); } //默认升序 sort(v.begin(), v.end()); for (vector::iterator it = v.begin(); it != v.end(); it++) { cout << *it << " " ; } cout << endl; //使用内建函数对象实现降序排列 sort(v.begin(), v.end(), greater()); for (vector::iterator it = v.begin(); it != v.end(); it++) { cout << *it << " "; }}int main(){ test01(); return 0;}random_shuffle随机洗牌random_shuffle(iterator beg, iterator end);//随机洗牌end//结束迭代器_Pred//函数或者谓词，可填可不填，不填则默认升序排列只需要提供开始迭代器和结束迭代器

srand((unsigned int)time(NULL));可以设置系统时间为随机数种子

#include#include#includeusing namespace std;void test01(){    vectorv;    for (int i = 0; i < 10; i++)    {        v.push_back(i);    }    random_shuffle(v.begin(), v.end());    for (vector::iterator it = v.begin(); it != v.end(); it++)    {        cout << *it << " " ;    }    cout << endl;}int main(){    test01();    return 0;}

merge合并

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, dest);//将两个容器元素合并，并储存到另一个容器中

两个容器必须是有序的#include#include#includeusing namespace std;void Print(int val){ cout << val << " ";}void test01(){ vectorv1; vectorv2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 1); } //目标容器 vectorv3; //目标容器需要提前开辟空间 v3.resize(v1.size() + v2.size()); merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); //合并后仍然是有序容器 for_each(v3.begin(), v3.end(), Print);}int main(){ test01(); return 0;}reverse反转reverse(iterator beg, iterator end);//反转指定范围内的元素beg1//容器1开始迭代器end1//容器1结束迭代器beg2//容器2开始迭代器end2//容器2结束迭代器dest//目标容器开始迭代器beg//起始迭代器#include#include#includeusing namespace std;void Print(int val){ cout << val << " ";}void test01(){ vectorv1; for (int i = 0; i < 10; i++) { v1.push_back(i); } for_each(v1.begin(), v1.end(), Print); cout << endl; //反转 reverse(v1.begin(), v1.end()); for_each(v1.begin(), v1.end(), Print);}int main(){ test01(); return 0;}常用拷贝和替换算法end//结束迭代器copy//容器内指定范围的元素拷贝到另一个容器中replace//将容器内指定范围的旧元素修改为新元素replace_if//容器内指定范围满足条件的元素替换为新元素swap//互换两个容器的元素copy拷贝copy(iterator beg, iterator end, iterator dest);//容器内指定范围的元素拷贝到另一个容器中beg//开始迭代器end//结束迭代器dest//目标容器的开始迭代器

用到的比较少，直接用赋值操作更简单

#include#include#includeusing namespace std;void Print(int val){    cout << val << " ";}void test01(){    vectorv1;    for (int i = 0; i < 10; i++)    {        v1.push_back(i);    }    vectorv2;    //v2要提前开辟空间    v2.resize(v1.size());    copy(v1.begin(), v1.end(), v2.begin());    for_each(v2.begin(), v2.end(), Print);}int main(){    test01();    return 0;}

replace替换

replace(iterator beg, iterator end, oldvalue, newvalue);//将区间内的旧元素替换为新元素

beg//起始迭代器#include#include#includeusing namespace std;class Print{public: void operator()(int val) { cout << val << " "; }};void test01(){ vectorv1; v1.push_back(1); v1.push_back(2); v1.push_back(1); v1.push_back(3); for_each(v1.begin(), v1.end(), Print()); cout << endl; //替换 replace(v1.begin(), v1.end(), 1, 2); for_each(v1.begin(), v1.end(), Print());}int main(){ test01(); return 0;}replace_if条件替换replace_if(iterator beg, iterator end, _Pred, newvalue);//容器内指定范围满足条件的元素替换为新元素end//结束迭代器oldvalue//旧元素newvalue//新元素beg//开始迭代器#include#include#includeusing namespace std;class Print{public: void operator()(int val) { cout << val << " "; }};class GreaterFive{public: bool operator()(const int& val) { return val > 5; }};void test01(){ vectorv; for (int i = 0; i < 10; i++) { v.push_back(i); } replace_if(v.begin(), v.end(), GreaterFive(), 0); for_each(v.begin(), v.end(), Print());}int main(){ test01(); return 0;}swap互换swap(container c1, container c2);//互换两个容器的元素end//结束迭代器_Pred//谓词newvalue//替换的新元素c1容器1c2容器2

注意必须是同种容器

#include#include#includeusing namespace std;class Print{public:    void operator()(int val)    {        cout << val << " ";    }};class GreaterFive{public:    bool operator()(const int& val)    {        return val > 5;    }};void test01(){    vectorv1;    vectorv2;    for (int i = 0; i < 10; i++)    {        v1.push_back(i);        v2.push_back(i + 2);    }    //交换前    for_each(v1.begin(), v1.end(), Print());    for_each(v2.begin(), v2.end(), Print());    cout << endl;    //交换后    swap(v1, v2);    for_each(v1.begin(), v1.end(), Print());    for_each(v2.begin(), v2.end(), Print());}int main(){    test01();    return 0;}

常用算术生成算法

算术生成算法属于小型算法，使用时包含的头文件为

accumulate//计算容器元素累计总和fill//向容器中添加元素accumulate累积accumulate(iterator beg, iterator end, value);//计算容器元素累计总和beg//起始迭代器#include#include#includeusing namespace std;void test01(){ vectorv1; for (int i = 0; i < 10; i++) { v1.push_back(i); } int total = accumulate(v1.begin(), v1.end(), 0); cout << total << endl;}int main(){ test01(); return 0;}fill填充fill(iterator beg, iterator end, value);//向容器中添加元素end//结束迭代器value//起始值beg//起始迭代器#include#include#includeusing namespace std;void test01(){ vectorv1; for (int i = 0; i < 10; i++) { v1.push_back(i); } for (vector::iterator it = v1.begin(); it != v1.end(); it++) { cout << *it << " "; } cout << endl; fill(v1.begin(), v1.end(), 0); for (vector::iterator it = v1.begin(); it != v1.end(); it++) { cout << *it << " "; }}int main(){ test01(); return 0;}常用集合容器end//结束迭代器value//填充的值set_intersection//求两个容器的交集set_union//求两个容器的并集set_difference//求两个容器的差集set_intersection求交集set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//求两个容器的交集beg1//容器1开始迭代器end1//容器1结束迭代器beg2//容器2开始迭代器end2//容器2结束迭代器dest//目标容器开始迭代器

注意事项：

返回值为迭代器，指向交集最后一个元素的下一个位置求交集的两个集合必须为有序数列目标容器开辟空间需要从两个容器中取小值

交集就是两个容器重复的元素

#include#include#include#includeusing namespace std;void myPrint(int val){    cout << val << " ";}void test01(){    vectorv1;    vectorv2;    for (int i = 0; i < 10; i++)    {        v1.push_back(i);        v2.push_back(i + 2);    }    for_each(v1.begin(), v1.end(), myPrint);    cout << endl;    for_each(v2.begin(), v2.end(), myPrint);    cout << endl;    //目标容器需要提前开辟空间，最特殊的情况，大容器包含小容器    vectorv3;    v3.resize(min(v1.size(), v2.size()));    //取交集    vector::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());    for_each(v3.begin(), itEnd, myPrint);    cout << endl;    //如果不用返回的itEnd，会把0也给打印出来    for_each(v3.begin(), v3.end(), myPrint);}int main(){    test01();    return 0;}

set_union求并集

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//求两个容器的并集

beg1//容器1开始迭代器end1//容器1结束迭代器beg2//容器2开始迭代器end2//容器2结束迭代器dest//目标容器开始迭代器

注意事项：

返回值为迭代器，指向并集最后一个元素的下一个位置#include#include#include#includeusing namespace std;void myPrint(int val){ cout << val << " ";}void test01(){ vectorv1; vectorv2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 2); } for_each(v1.begin(), v1.end(), myPrint); cout << endl; for_each(v2.begin(), v2.end(), myPrint); cout << endl; //目标容器需要提前开辟空间，最特殊的情况，两个容器没有交集 vectorv3; v3.resize(v1.size() + v2.size()); //取并集 vector::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); for_each(v3.begin(), itEnd, myPrint); cout << endl; //如果不用返回的itEnd，会把0也给打印出来 for_each(v3.begin(), v3.end(), myPrint);}int main(){ test01(); return 0;}set_difference求差集set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//求两个容器的差集求并集的两个集合必须为有序数列目标容器开辟空间需要两个容器相加beg1//容器1开始迭代器end1//容器1结束迭代器beg2//容器2开始迭代器end2//容器2结束迭代器dest//目标容器开始迭代器

注意事项：

返回值为迭代器，指向并集最后一个元素的下一个位置#include#include#include#includeusing namespace std;void myPrint(int val){ cout << val << " ";}void test01(){ vectorv1; vectorv2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 2); } for_each(v1.begin(), v1.end(), myPrint); cout << endl; for_each(v2.begin(), v2.end(), myPrint); cout << endl; //目标容器需要提前开辟空间，最特殊的情况，大容器和小容器没有交集 //取两个容器中大的size作为目标容器开辟空间 vectorv3; v3.resize(max(v1.size(),v2.size())); //取并集 vector::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); for_each(v3.begin(), itEnd, myPrint); cout << endl; //如果不用返回的itEnd，会把0也给打印出来 for_each(v3.begin(), v3.end(), myPrint);}int main(){ test01(); return 0;}求并集的两个集合必须为有序数列目标容器开辟空间需要从两个容器中取大值

编辑：