第二十五章 STL- 常用算法

概述:

• 算法主要是由头文件<algorithm> <functional> <numeric>组成。

• <algorithm>是所有STL头文件中最大的一个，范围涉及到比较、 交换、查找、遍历操作、复制、修改等等

• <numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数

• <functional>定义了一些模板类,用以声明函数对象。

一、常用遍历算法

学习目标：

• 掌握常用的遍历算法

算法简介：

• for_each //遍历容器

• transform //搬运容器到另一个容器中

1、for_each

功能描述：

• 实现遍历容器

函数原型：

• for_each(iterator beg, iterator end, _func);

  // 遍历算法 遍历容器元素

  // beg 开始迭代器

  // end 结束迭代器

  // _func 函数或者函数对象

示例：

?#include <algorithm>
?#include <vector>
??
?//普通函数
?void print01(int val) 
?{
?    cout << val << " ";
?}
?//函数对象
?class print02 
?{
? public:
?    void operator()(int val) 
?    {
?        cout << val << " ";
?    }
?};
??
?//for_each算法基本用法
?void test01() {
??
?    vector<int> v;
?    for (int i = 0; i < 10; i++) 
?    {
?        v.push_back(i);
?    }
??
?    //遍历算法
?    for_each(v.begin(), v.end(), print01);
?    cout << endl;
??
?    for_each(v.begin(), v.end(), print02());
?    cout << endl;
?}
??
?int main() {
??
?    test01();
??
?    system("pause");
??
?    return 0;
?}

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

2、transform

功能描述：

• 搬运容器到另一个容器中

函数原型：

• transform(iterator beg1, iterator end1, iterator beg2, _func);

//beg1 源容器开始迭代器

//end1 源容器结束迭代器

//beg2 目标容器开始迭代器

//_func 函数或者函数对象

示例：

?#include<vector>
?#include<algorithm>
??
?//常用遍历算法  搬运 transform
??
?class TransForm
?{
?public:
?    int operator()(int val)
?    {
?        return val;
?    }
??
?};
??
?class MyPrint
?{
?public:
?    void operator()(int val)
?    {
?        cout << val << " ";
?    }
?};
??
?void test01()
?{
?    vector<int>v;
?    for (int i = 0; i < 10; i++)
?    {
?        v.push_back(i);
?    }
??
?    vector<int>vTarget; //目标容器
??
?    vTarget.resize(v.size()); // 目标容器需要提前开辟空间
??
?    transform(v.begin(), v.end(), vTarget.begin(), TransForm());
??
?    for_each(vTarget.begin(), vTarget.end(), MyPrint());
?}
??
?int main() {
??
?    test01();
??
?    system("pause");
??
?    return 0;
?}

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

二、常用查找算法

学习目标：

• 掌握常用的查找算法

算法简介：

• find //查找元素

• find_if //按条件查找元素

• adjacent_find //查找相邻重复元素

• binary_search //二分查找法

• count //统计元素个数

• count_if //按条件统计元素个数

1、find

功能描述：

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

函数原型：

• find(iterator beg, iterator end, value);

  // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

  // beg 开始迭代器

  // end 结束迭代器

  // value 查找的元素

示例：

?#include <algorithm>
?#include <vector>
?#include <string>
?void test01() {
??
?    vector<int> v;
?    for (int i = 0; i < 10; i++) {
?        v.push_back(i + 1);
?    }
?    //查找容器中是否有 5 这个元素
?    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_Name = name;
?        this->m_Age = age;
?    }
?    //重载==
?    bool operator==(const Person& p) 
?    {
?        if (this->m_Name == p.m_Name && this->m_Age == p.m_Age) 
?        {
?            return true;
?        }
?        return false;
?    }
??
?public:
?    string m_Name;
?    int m_Age;
?};
??
?void test02() {
??
?    vector<Person> v;
??
?    //创建数据
?    Person p1("aaa", 10);
?    Person p2("bbb", 20);
?    Person p3("ccc", 30);
?    Person p4("ddd", 40);
??
?    v.push_back(p1);
?    v.push_back(p2);
?    v.push_back(p3);
?    v.push_back(p4);
??
?    vector<Person>::iterator it = find(v.begin(), v.end(), p2);
?    if (it == v.end()) 
?    {
?        cout << "没有找到!" << endl;
?    }
?    else 
?    {
?        cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl;
?    }
?}

总结： 利用find可以在容器中找指定的元素，返回值是迭代器