程序员吧
首页 >编程 >正文

STL-常用算法总结

2023-02-12 18:13出处/作者：小冰整合编辑：@小冰

STL-常用算法总结

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

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

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//普通函数
void myPrint(int val)
{
    cout << val << " ";
}
//仿函数
class myPrint2
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};
int main()
{
    vector<int>v;
    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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Transform
{
public:
    int operator()(int val)
    {
        return val;
    }
};
int main()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    vector<int>v2;
    v2.resize(v.size());
    transform(v.begin(), v.end(), v2.begin(), Transform());
    for (vector<int>::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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//查找内置数据类型
void test01()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    //返回一个迭代器，如果没有找到，返回end()
    vector<int>::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);
    //放入容器中
    vector<Person>p;
    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<Person>::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<iostream> #include<vector> #include<algorithm> using namespace std; //查找内置数据类型 class GreaterFive { public: bool operator()(int v) { return v > 5; } }; void test01() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } vector<int>::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); //放入容器中 vector<Person>p; p.push_back(p1); p.push_back(p2); p.push_back(p3); p.push_back(p4); p.push_back(p5); //查找 vector<Person>::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<iostream> #include<vector> #include<algorithm> using namespace std; void test01() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } v.push_back(5); vector<int>::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<iostream> #include<vector> #include<algorithm> using namespace std; void test01() { vector<int>v; 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<iostream> #include<vector> #include<algorithm> using namespace std; //统计内置数据类型 void test01() { vector<int>v; 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); vector<Person>p; 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<iostream> #include<vector> #include<algorithm> using namespace std; //统计内置数据类型 class GreaterFive { public: bool operator()(int val) { return val > 5; } }; void test01() { vector<int>v; 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); vector<Person>p; 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<iostream> #include<vector> #include<algorithm> using namespace std; void test01() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } //默认升序 sort(v.begin(), v.end()); for (vector<int>::iterator it = v.begin(); it != v.end(); it++) { cout << *it << " " ; } cout << endl; //使用内建函数对象实现降序排列 sort(v.begin(), v.end(), greater<int>()); for (vector<int>::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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void test01()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    random_shuffle(v.begin(), v.end());
    for (vector<int>::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<iostream> #include<vector> #include<algorithm> using namespace std; void Print(int val) { cout << val << " "; } void test01() { vector<int>v1; vector<int>v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 1); } //目标容器 vector<int>v3; //目标容器需要提前开辟空间 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<iostream> #include<vector> #include<algorithm> using namespace std; void Print(int val) { cout << val << " "; } void test01() { vector<int>v1; 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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void Print(int val)
{
    cout << val << " ";
}
void test01()
{
    vector<int>v1;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
    }
    vector<int>v2;
    //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<iostream> #include<vector> #include<algorithm> using namespace std; class Print { public: void operator()(int val) { cout << val << " "; } }; void test01() { vector<int>v1; 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<iostream> #include<vector> #include<algorithm> using namespace std; class Print { public: void operator()(int val) { cout << val << " "; } }; class GreaterFive { public: bool operator()(const int& val) { return val > 5; } }; void test01() { vector<int>v; 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容器1
  • c2容器2

注意必须是同种容器

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Print
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};
class GreaterFive
{
public:
    bool operator()(const int& val)
    {
        return val > 5;
    }
};
void test01()
{
    vector<int>v1;
    vector<int>v2;
    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;
}

常用算术生成算法

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

  • accumulate//计算容器元素累计总和
  • fill//向容器中添加元素accumulate累积accumulate(iterator beg, iterator end, value);//计算容器元素累计总和
  • beg//起始迭代器#include<iostream> #include<vector> #include<numeric> using namespace std; void test01() { vector<int>v1; 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<iostream> #include<vector> #include<numeric> using namespace std; void test01() { vector<int>v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) { cout << *it << " "; } cout << endl; fill(v1.begin(), v1.end(), 0); for (vector<int>::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<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
void myPrint(int val)
{
    cout << val << " ";
}
void test01()
{
    vector<int>v1;
    vector<int>v2;
    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;
    //目标容器需要提前开辟空间，最特殊的情况，大容器包含小容器
    vector<int>v3;
    v3.resize(min(v1.size(), v2.size()));
    //取交集
    vector<int>::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<iostream> #include<vector> #include<numeric> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } void test01() { vector<int>v1; vector<int>v2; 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; //目标容器需要提前开辟空间，最特殊的情况，两个容器没有交集 vector<int>v3; v3.resize(v1.size() + v2.size()); //取并集 vector<int>::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<iostream> #include<vector> #include<numeric> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } void test01() { vector<int>v1; vector<int>v2; 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作为目标容器开辟空间 vector<int>v3; v3.resize(max(v1.size(),v2.size())); //取并集 vector<int>::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; }
  • 求并集的两个集合必须为有序数列
  • 目标容器开辟空间需要从两个容器中取大值
机器学习（三）：人工智能主要分支
Nginx实现崩溃重启

网友评论

登录 注册
iCMS
验证码 换一张
取 消
暂无评论...
24小时内最火资讯
  1. 1Python之列表推导式最全汇总(上篇)
  2. 2Win11安装VMware Workstation Pro,Centos,Xshell,Xftp图文教程(Linux学习必备)
  3. 3springboot使用mybatis开启事务回滚
  4. 4windows2003 的安装及安装过程遇到的问题小结
  5. 5git可视化工具Sourcetree使用全攻略(git冲突解决)
  6. 6django+vue项目搭建实现前后端通信
  7. 7Redis 分片集群的实现
  8. 8springboot使用mybatis开启事务回滚
  9. 9GPU版本安装Pytorch的最新方法步骤
  10. 10Win11安装VMware Workstation Pro,Centos,Xshell,Xftp图文教程(Linux学习必备)
三日内热门评论文章
  1. 1 Win11安装VMware Workstation Pro,Centos,Xshell,Xftp图文教程(Linux学习必备)
  2. 2 Redis处理高并发之布隆过滤器详解
  3. 3 一文带你了解MySQL字符集和比较规则
  4. 4 MySQL常见内置函数以及其使用教程
  5. 5 解决Spring Cloud feign GET请求无法用实体传参的问题
  6. 6 Feign调用中的两种Header传参方式小结
  7. 7 yocto queue微型队列数据结构源码解读
  8. 8 Idea中如何查看SpringSecurity各Filter信息
  9. 9 arrify 转数组实现示例源码解析
  10. 10 Css-In-Js实现classNames库源码解读
精彩图赏
热门视频
月度热门文章
  1. 264
    全网最强下载神器IDM使用教程之利用IDM加速下载百度网盘大文件的方法
    ·
  2. 218
    MySQL如何查看正在运行的SQL详解
    ·
  3. 198
    关于yolov8训练的一些改动及注意事项
    ·
  4. 150
    chatgpt国内镜像 pycharm idea插件使用详解
    ·
  5. 149
    VS Code里使用Debugger for Unity插件调试的方法(2023最新版)
    ·
  6. 125
    全网最强下载神器IDM使用教程之利用IDM加速下载百度网盘大文件的方法
    ·
  7. 117
    JavaWeb day5 Tomcat配置及idea创建Maven-Tomcat项目
    ·
  8. 103
    buildcheck包报错问题排查解决
    ·
  9. 97
    vscode远程开发使用SSH远程连接服务器的方法「内网穿透」
    ·
  10. 96
    全网最强下载神器IDM使用教程之利用IDM加速下载百度网盘大文件的方法
    ·
关键词

为您推荐
  • 相关阅读
  • 业界资讯
  • 手机通讯
  • 电脑办公
  • 新奇数码
  • 软件游戏
  • 科学探索
用户反馈 返回首页 相关阅读 参与讨论 回到顶部

程序员吧感受编程的乐趣

法律声明：本站内容均为网友上传，网站举办方负责审核和监督，如存在版权或非法内容，欢迎举报，我们将尽快予以删除。

Copyright © 2022 程序员吧. All rights reserved. Powered by ITBeta V7.0.16