5 STL-常用算法

时间：2023-10-31 21:29 作者：wen 分类： C++

[toc]

STL-常用算法

概述:

算法主要是由头文件<algorithm> <functional> <numeric>组成。
<algorithm>是所有STL头文件中最大的一个，范围涉及到比较，交换，查找，遍历操作，复制，修改等待
<numeric> 体积很小，只包括几个在序列上面进行简单数学运算的模板函数
<functional> 定义了一些模板类，用以声明函数对象。

常用遍历算法

学习目标：

掌握常用的遍历算法

算法简介：

for_each //遍历容器
transform //搬运容器到另一个容器中

for_each

功能描述:

实现遍历容器

函数原型:

for_each(iterator beg, iterator end, _func) //遍历算法遍历容器元素
- beg 开始迭代器
- end 结束迭代器
- _func函数或者函数对象

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

//普通函数
void printA(int val)
{
    cout << val << " ";
}
//仿函数
class PrintB 
{
public:
    void operator()(int val) {
        cout << val << " ";
    }
};

//for_each遍历
void testA()
{
    vector<int> v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    //普通函数
    for_each(v.begin(), v.end(), printA);
    cout << endl;
    //仿函数
    for_each(v.begin(), v.end(), PrintB());
    cout << endl;
    //匿名函数
    for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
}

int main()
{
    testA();
    return 0;
}

transform

功能描述:

搬运容器到另一个容器中

函数原型:

transform(iterator beg1,iterator end1,iterator beg2,_func);
- beg1 源容器开始迭代器
- end1 源容器接受迭代器
- beg2 目标容器开始迭代器
- _func 函数或者函数对象

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

//仿函数
class Transform 
{
public:
    int operator()(int val) {
        return val + 10;
    }
};

class MyPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

//transform
void testA()
{
    vector<int> v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    vector<int> vTarge;//目标容器
    vTarge.resize(v.size());//目标容器需要提前开辟空间
    transform(v.begin(), v.end(), vTarge.begin(), Transform());
    for_each(vTarge.begin(), vTarge.end(), MyPrint());
}

int main()
{
    testA();
    return 0;
}

常用查找算法

学习目标:

掌握常用的查找算法

算法简介:

find //查找元素
find_if //按条件查找元素
adjacent_find //查找相邻重复元素
binary_search //二分查找法
count //统计元素个数
count_if //按条件统计元素个数

find

功能描述

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()

函数原型:

find(iterator beg, iterator end, value);
- beg 开始迭代器
- end 结束迭代器
- value 查找的值

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

//find 查找
void testA()
{
    vector<int> v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }

    vector<int>::iterator pos = find(v.begin(), v.end(), 4);
    if (pos != v.end())
    {
        cout << *pos << endl;
    }
    else {
        cout << "没找到" << endl;
    }
}

//自定义数据类型
class Person
{
public:
    string m_name;
    int m_age;

    Person(const string& m_name, int m_age)
        : m_name(m_name), m_age(m_age)
    {
    }

    // 重载 == 底层find知道如何对比Person数据类型
    bool operator==(const Person& other) const
    {
        return m_name == other.m_name && m_age == other.m_age;
    }
};
void testB()
{
    vector<Person> v;
    Person p1("唐僧", 28);
    Person p2("孙悟空", 999);
    Person p3("沙和尚", 500);
    Person p4("猪八戒", 666);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);

    Person p5("孙悟空", 999);

    vector<Person>::iterator pos = find(v.begin(), v.end(), p5);
    if (pos == v.end())
    {
        cout << "没找到" << endl;
    }
    else {
        cout << "姓名: " << pos->m_name << " 年龄: " << pos->m_age << endl;
    }
}

int main()
{
    testA();
    testB();
    return 0;
}

find_if

功能描述:

按条件查找元素

函数原型:

find_if(iterator beg,iterator end, _Pred);
- _Pred 函数或者谓词(返回bool类型的仿函数)

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

class GreaterFive
{
public:
    bool operator()(int val)
    {
        return val > 5;
    }
};

//find_if 查找
void testA()
{
    vector<int> v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }

    vector<int>::iterator pos = find_if(v.begin(), v.end(), GreaterFive());
    if (pos != v.end())
    {
        cout << *pos << endl;
    }
    else {
        cout << "没找到" << endl;
    }
}

//自定义数据类型
class Person
{
public:
    string m_name;
    int m_age;

    Person(const string& m_name, int m_age)
        : m_name(m_name), m_age(m_age)
    {
    }

    // 重载 == 底层find知道如何对比Person数据类型
    bool operator==(const Person& other) const
    {
        return m_name == other.m_name && m_age == other.m_age;
    }
};

class Greater300
{
public:
    bool operator()(Person& p)
    {
        return p.m_age > 300;
    }
};

void testB()
{
    vector<Person> v;
    Person p1("唐僧", 28);
    Person p2("孙悟空", 999);
    Person p3("沙和尚", 500);
    Person p4("猪八戒", 666);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);

    vector<Person>::iterator pos = find_if(v.begin(), v.end(), Greater300());
    if (pos == v.end())
    {
        cout << "没找到" << endl;
    }
    else {
        cout << "姓名: " << pos->m_name << " 年龄: " << pos->m_age << endl;
    }
}

int main()
{
    testA();
    testB();
    return 0;
}

adjacent_find

功能描述:

查找相邻重复元素

函数原型:

adjacent_find(iterator beg,iterator end);

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

//adjacent_find 查找
void testA()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(20);
    v.push_back(10);

    vector<int>::iterator pos = adjacent_find(v.begin(), v.end());
    if (pos != v.end())
    {
        cout << *pos << endl;
    }
    else {
        cout << "没找到" << endl;
    }
}

int main()
{
    testA();
    return 0;
}

binary_search

功能描述:

查找指定元素是否存在

函数原型:

bool binary_search(iterator beg,iterator end, value);
- value 查找的元素
- 注意：在无序序列中不可用

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

//binary_search  查找
void testA()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    //v.push_back(2); //如果是无序序列,结果未知!

    //注意: 容器必须是一个有序的序列
    bool flag = binary_search(v.begin(), v.end(), 9);
    if (flag)
    {
        cout << "找到" << endl;
    }
    else {
        cout << "未找到" << endl;
    }
}

int main()
{
    testA();
    return 0;
}

count

功能描述:

统计元素个数

函数原型:

count(iterator beg,iterator end, value);
- value 统计的元素

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

//count  统计
void testA()
{
    vector<int>v;
    v.push_back(10);
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    int num = count(v.begin(), v.end(), 10);
    cout << num << endl;
}

//自定义数据类型
class Person
{
public:
    string m_name;
    int m_age;
public:

    Person(const string& m_name, int m_age)
        : m_name(m_name), m_age(m_age)
    {
    }

    bool operator==(const Person& other) const
    {
        return  m_age == other.m_age;
    }
};
void testB()
{
    vector<Person> v;
    Person p1("刘备", 36);
    Person p2("关羽", 36);
    Person p3("张飞", 30);
    Person p4("赵云", 28);
    Person p5("曹操", 36);
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);
    v.push_back(p5);
    Person p("诸葛亮", 36);
    int num = count(v.begin(), v.end(), p);
    cout << num << endl;
}

int main()
{
    testA();
    testB();
    return 0;
}

count_if

功能描述:

按条件统计元素个数

函数原型:

count_if(iterator beg,iterator end, _Pred);
- _Pred 谓词

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

//count_if   条件统计
class Greater10
{
public:
    bool operator()(int val)
    {
        return val > 10;
    }
};
void testA()
{
    vector<int>v;
    v.push_back(10);
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    int num = count_if(v.begin(), v.end(), Greater10());
    cout << num << endl;
}

//自定义数据类型
class Person
{
public:
    string m_name;
    int m_age;
public:

    Person(const string& m_name, int m_age)
        : m_name(m_name), m_age(m_age)
    {
    }

    bool operator==(const Person& other) const
    {
        return  m_age == other.m_age;
    }
};

class AgeGreater28
{
public:
    bool operator()(Person& p)
    {
        return p.m_age > 28;
    }
};
void testB()
{
    vector<Person> v;
    Person p1("刘备", 36);
    Person p2("关羽", 36);
    Person p3("张飞", 30);
    Person p4("赵云", 28);
    Person p5("曹操", 36);
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);
    v.push_back(p5);
    int num = count_if(v.begin(), v.end(), AgeGreater28());
    cout << num << endl;
}

int main()
{
    testA();
    testB();
    return 0;
}

常用排序算法

学习目标:

掌握常用的排序算法

算法简介:

sort //对容器内元素进行排序
random_shuffle //洗牌指定范围内的元素随机调整次序
merge //容器元素合并，并存储到另一个容器中
reverse //反转指定范围的元素

sort

功能描述:

对容器内元素进行排序

函数原型:

sort(iterator beg,iterator end, _Pred);

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

// sort 排序
void testA()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(5);
    v.push_back(2);
    v.push_back(4);
    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()
{
    testA();
    return 0;
}

random_shuffle

功能描述:

洗牌指定范围内的元素随机调整次序

函数原型:

random_shuffle(iterator beg,iterator end);

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

// random_shuffle 排序
void testA()
{
    srand((unsigned int)time(nullptr));
    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 << " ";
    }

}

int main()
{
    testA();
    return 0;
}

merge

功能描述:

两个容器元素合并，并存储到另一个容器中

函数原型:

merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
- beg1-end1 容器1
- beg2-end2 容器2
- dest 目标容器开始迭代器
- 注意：两个容器必须是有序的

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

// merge 合并
void testA()
{
    vector<int> v;
    vector<int> v1;
    for (int i = 0; i < 10; i++)
    {
            v.push_back(i);
            v1.push_back(i+10);
    }
    vector<int> d;
    d.resize(v.size() + v1.size());
    merge(v.begin(), v.end(), v1.begin(), v1.end(), d.begin());
    for_each(d.begin(), d.end(), [](int val) {cout << val << " "; });
    cout << endl;
}

int main()
{
    testA();
    return 0;
}

reverse

功能描述:

反转指定范围的元素

函数原型:

reverse(iterator beg,iterator end);

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

// reverse 反转
void testA()
{
    vector<int> v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    reverse(v.begin(), v.end());
    for_each(v.begin(), v.end(), [](int val) {cout << val << " "; });
    cout << endl;
}

int main()
{
    testA();
    return 0;
}

常用拷贝和替换算法

学习目标:

掌握常用的拷贝和替换算法

算法简介:

copy //容器内指定范围的元素拷贝到另一个容器中
replace //将容器内指定范围的旧元素修改为新元素
replace_if //容器内指定范围满足条件的元素替换为新元素
swap //互换两个容器的元素

copy

功能描述:

容器内指定范围的元素拷贝到另一个容器中

函数原型:

copy(iterator beg,iterator end,iterator dest);
- dest 目标起始迭代器

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

// copy 拷贝
void testA()
{
    vector<int> v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }

    vector<int> vTarge;
    vTarge.resize(v.size());
    copy(v.begin(), v.end(), vTarge.begin());
    for_each(vTarge.begin(), vTarge.end(), [](int val) {cout << val << " "; });
}

int main()
{
    testA();
    return 0;
}

replace

功能描述:

将容器内指定范围的旧元素修改为新元素

函数原型:

replace(iterator beg,iterator end,T old,T new);
- old 旧元素
- new 新元素

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

// replace 替换
void testA()
{
    vector<int> v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }

    replace(v.begin(), v.end(), 3, 13);
    for_each(v.begin(), v.end(), [](int val) {cout << val << " "; });
}

int main()
{
    testA();
    return 0;
}

replace_if

功能描述:

容器内指定范围满足条件的元素替换为新元素

函数原型:

replace_if(iterator beg,iterator end,_Pred,newvalue);
- _Pred 谓词
- newvalue 新元素

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

// replace_if 替换
class GreaterFive
{
public:
    bool operator()(int val)
    {
        return val > 5;
    }
};

void testA()
{
    vector<int> v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }

    replace_if(v.begin(), v.end(), GreaterFive(), 13);
    for_each(v.begin(), v.end(), [](int val) {cout << val << " "; });
}

int main()
{
    testA();
    return 0;
}

swap

功能描述:

互换两个容器的元素

函数原型:

swap(container c1,container c2);
- c1 容器1
- c2 容器2

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

// swap 替换

void testA()
{
    vector<int> v;
    vector<int> v1;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
        v1.push_back(i+10);
    }

    cout << "交换前: " << endl;
    for_each(v.begin(), v.end(), [](int val) {cout << val << " "; });
    cout << endl;
    for_each(v1.begin(), v1.end(), [](int val) {cout << val << " "; });
    cout << endl;
    cout << "交换后: " << endl;
    swap(v, v1);
    for_each(v.begin(), v.end(), [](int val) {cout << val << " "; });
    cout << endl;
    for_each(v1.begin(), v1.end(), [](int val) {cout << val << " "; });
    cout << endl;
}

int main()
{
    testA();
    return 0;
}

常用算术生成算法

学习目标:

掌握常用的算术生成算法

注意:

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

算法简介:

accumulate //计算容器元素累计总和
fill //向容器中填充指定元素

accumulate

功能描述

计算容器元素累计总和

函数原型:

accumulate(iterator beg,iterator end, value);
- value 起始值

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

// accumulate 累加

void testA()
{
    vector<int> v;
    for (int i = 0; i <= 100; i++)
    {
        v.push_back(i);
    }

    int count = accumulate(v.begin(), v.end(), 0);

    cout << count <<  endl;
}
int main()
{
    testA();
    return 0;
}

fill

功能描述

向容器中填充指定元素

函数原型:

fill(iterator beg,iterator end, value);
- value 填充的值

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

// accumulate 累加

void testA()
{
    vector<int> v;
    v.resize(10);

    fill(v.begin(), v.end(), 5050);
    for_each(v.begin(), v.end(), [](int val) {cout << val << " "; });
    cout << endl;
}
int main()
{
    testA();
    return 0;
}

常用集合算法

学习目标:

掌握常用的集合算法

算法简介:

set_intersection //求两个容器的交集
set_union //求两个容器的并集
set_difference //求两个容器的差集

set_intersection

功能描述:

求两个容器的交集，返回结束迭代器

函数原型:

set_intersection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
- 注意：两个集合必须是有序序列
- desc 目标容器的开始迭代器

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

// set_intersection 交集

void testA()
{
    vector<int> v;
    vector<int> v1;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
        v1.push_back(i + 3);
    }
    vector<int> v2;
    // 开辟空间取小容器的值
    //v2.resize(v.size() > v1.size() ? v1.size():v.size());
    v2.resize(min(v.size(),v1.size()));
    vector<int>::iterator v2_end =  set_intersection(v.begin(), v.end(), v1.begin(), v1.end(), v2.begin());
    for_each(v2.begin(), v2_end, [](int val) {cout << val << " "; });
}
int main()
{
    testA();
    return 0;
}

set_union

功能描述:

求两个容器的交集

函数原型:

set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
- 注意：两个集合必须是有序序列
- desc 目标容器的开始迭代器

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

// set_union 并集

void testA()
{
    vector<int> v;
    vector<int> v1;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
        v1.push_back(i + 3);
    }
    vector<int> v2;
    // 开辟空间
    v2.resize(v.size()+v1.size());
    vector<int>::iterator v2_end = set_union(v.begin(), v.end(), v1.begin(), v1.end(), v2.begin());
    for_each(v2.begin(), v2_end, [](int val) {cout << val << " "; });
}
int main()
{
    testA();
    return 0;
}

set_difference

功能描述:

求两个容器的交集

函数原型:

set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);
- 注意：两个集合必须是有序序列
- desc 目标容器的开始迭代器

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

// set_difference 差集

void testA()
{
    vector<int> v;
    vector<int> v1;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
        v1.push_back(i + 3);
    }
    vector<int> v2;
    // 开辟空间
    v2.resize(max(v.size(),v1.size()));
    cout << "v和v1的差集" << endl;
    vector<int>::iterator v2_end = set_difference(v.begin(), v.end(), v1.begin(), v1.end(), v2.begin());
    for_each(v2.begin(),  v2_end, [](int val) {cout << val << " "; });
    cout << endl;
    cout << "v1和v的差集" << endl;
    v2_end = set_difference(v1.begin(), v1.end(), v.begin(), v.end(), v2.begin());
    for_each(v2.begin(), v2_end, [](int val) {cout << val << " "; });
}
int main()
{
    testA();
    return 0;
}

标签: C/C++ c++提高编程