C++ STL学习笔记之常用算法函数
2020 年 07 月 14 日 279 1081 字 暂无评论

01. STL中算法概述

  • 算法部分主要由头文件<algorithm><numeric><functional>组成。
  • <algorithm>是所有STL头文件中最大的一个,其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等等。
  • <numeric>体积很小,只包括几个在序列上面进行简单数学运算的模板函数,包括加法和乘法在序列上的一些操作。
  • <functional>中则定义了一些模板类,用以声明函数对象。
  • STL提供了大量实现算法的模版函数,只要我们熟悉了STL之后,许多代码可以被大大的化简,只需要通过调用一两个算法模板,就可以完成所需要的功能,从而大大地提升效率。
  • #include<algorithm>
  • #include<numeric>
  • #include<functional>

02. STL中算法分类

  • 操作对象
    • 直接改变容器的内容
    • 将原容器的内容复制一份,修改其副本,然后传回该副本
  • 功能:
    • 非可变序列算法 指不直接修改其所操作的容器内容的算法
      • 计数算法 count、count_if
      • 搜索算法 search、find、find_if、find_first_of、…
      • 比较算法 equal、mismatch、lexicographical_compare
    • 可变序列算法 指可以修改它们所操作的容器内容的算法
      • 删除算法 remove、remove_if、remove_copy、…
      • 修改算法 for_each、transform
      • 排序算法 sort、stable_sort、partial_sort、…
    • 排序算法 包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作
    • 数值算法 对容器内容进行数值计算

03. STL中常用算法

  • 因为STL中算法很多,我们不可能一次性全学会使用,先使用常用算法,再遇到需要使用的再去查找相应用法。
  • 常用的查找算法:
    • adjacent_find()( adjacent 是邻近的意思),binary_search(),count(),count_if(),equal_range(),find(),find_if()
  • 常用的排序算法:
    • merge(),sort(),random_shuffle()(shuffle是洗牌的意思) ,reverse()
  • 常用的拷贝和替换算法:
    • copy(), replace(),
    • replace_if(),swap()
  • 常用的算术和生成算法:
    • accumulate()( accumulate 是求和的意思),fill(),。
  • 常用的集合算法:
    • set_union(),set_intersection(),
    • set_difference()
  • 常用的遍历算法:
    • for_each(), transform()( transform 是变换的意思)

04.几个常用算法函数案例

4.1 adjacent_find()

  • 用来查找连续两个相等的或者符合方法的
  • 案例代码
#include <iostream>  
#include <vector>
#include <algorithm>

using namespace std;

int main()
{   
    int myints[] = { 10,20,30,30,40,40,10,20,50};

    vector<int> myvector(myints, myints + 9);
    vector<int>::iterator it;

    for (it = myvector.begin(); it != myvector.end(); ++it)
        cout << *it << " ";
    cout << endl;

    it = adjacent_find(myvector.begin(), myvector.end());

    if (it != myvector.end())
    {
        cout << "输出首个相邻元素值为: " << *it << endl;
    }
        

    it = adjacent_find(++it, myvector.end());

    if (it != myvector.end())
    {
        cout << "第二个连续重复的元素值为: " << *it << endl;
    }
    return 0;
}
  • 结果
10 20 30 30 40 40 10 20 50
输出首个相邻元素值为: 30
第二个连续重复的元素值为: 40

4.2 find()

  • 用来查找元素是否在容器内。
  • 代码案例
#include <iostream>  
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main()
{   
    string str("Zfh is a handsome man.");
    string str2("man");

    size_t found = str.find(str2);
    if (found != string::npos)
    {
        cout << "str2 在 str 中位置:" << found << endl;
    }

    vector<int> v1;
    v1.push_back(3);
    v1.push_back(3);
    v1.push_back(2);
    v1.push_back(1);
  
    vector<int>::iterator iter = find(v1.begin(),v1.end(),3);
    if (iter != v1.end())
    {
        cout << "寻找到匹配数字:" << *iter << endl;
    }
    return 0;
}
  • 结果
str2 在 str 中位置:18
寻找到匹配数字:3

4.3 find_if()

  • find_if函数 带条件的查找元素,容器元素类型是类的时候,不能使用find函数,只能通过find_if函数来实现。find_if函数依次的遍历容器的元素,返回第一个使函数为true的元素的迭代器,如果查找失败则返回end迭代器。
  • 代码案例
#include <iostream>  
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

template<typename T>
bool equal_3(T value)
{
        return value == 3;
}

struct Point
{
        int x;
        int y;
};
struct PointFindByCoord : public std::binary_function<Point, Point, bool>
{
        bool operator () (const Point& obj1, const Point& obj2) const
        {
                return obj1.x == obj2.x && obj1.y == obj2.y;
        }
};

int main()
{
        vector<int> v1;
        v1.push_back(5);
        v1.push_back(3);
        v1.push_back(8);
        vector<int>::iterator found = find_if(v1.begin(), v1.end(), equal_3<int>);
        if (found != v1.end())
        {
                cout << *found << endl;
        }

        vector<Point> v2;
        for (int i = 0; i < 5; ++i)
        {
                for (int j = 0; j < 5; ++j)
                {
                        Point pt;
                        pt.x = i;
                        pt.y = j;
                        v2.push_back(pt);
                }
        }
        Point needFind;
        needFind.x = 4;
        needFind.y = 3;
        vector<Point>::iterator iter = find_if(v2.begin(), v2.end(), bind2nd(PointFindByCoord(), needFind));
        if (iter != v2.end())
        {
                std::cout << "the index of value Point(" << (*iter).x << ", " << (*iter).y << ")" << std::endl;
        }    
        return 0;
}
  • 结果
3
the index of value Point(4, 3)

4.4 sort()

  • sort并不是简单的快速排序,它对普通的快速排序进行了优化,此外,它还结合了插入排序和推排序。系统会根据你的数据形式和数据量自动选择合适的排序方法,这并不是说它每次排序只选择一种方法,它是在一次完整排序中不同的情况选用不同方法,比如给一个数据量较大的数组排序,开始采用快速排序,分段递归,分段之后每一段的数据量达到一个较小值后它就不继续往下递归,而是选择插入排序,如果递归的太深,他会选择推排序。
  • 代码案例
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    int a[11] = { 0,1,2,13,45,2,33,1,6,78,4 };
    sort(a, a + 11);
    for (int i = 0; i < 11; i++) {
        cout << a[i] << " ";
    }
    return 0;
}
  • 结果
0 1 1 2 2 4 6 13 33 45 78

4.5 merge()

  • 主要实现函数的排序和合并
  • 代码案例
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
        vector<int> v1 = { 1,3,5,7 };
        vector<int> v2 = { 2,4,6,8 };
        vector<int> merge_v(8);

        merge(v1.begin(), v1.end(), v2.begin(), v2.end(), merge_v.begin());

        for (int i = 0; i < merge_v.size(); i++)
        {
                cout << merge_v[i] << " ";
        }    
        cout << endl;
}
  • 结果
1 2 3 4 5 6 7 8

4.6 copy()

  • 复制容器内容到另一个容器
  • 代码案例
#include<vector>
#include<iostream>
#include<iterator>//back_inserter所需要的头文件

using namespace std;

void main() 
{
        vector<int> vec1;
        vector<int> vec2;
        vec1 = { 1,2,3,4,5,6,7,8,9,10 };
        vec2.reserve(vec1.size());//存储vec1的大小
        copy(vec1.begin(), vec1.end(), back_inserter(vec2));//进行拷贝
        cout << "vec1.size()     = " << vec1.size() << endl;//输出vec1的大小
        cout << "vec1.capacity() = " << vec1.capacity() << endl;//输出vec1的容量
        cout << "vec1: ";
        for (vector<int>::const_iterator iter = vec1.begin(); iter < vec1.end(); ++iter) {
                cout << *iter << " ";//输出vec1的值
        }
        cout << endl;
        cout << "vec2.size()     = " << vec2.size() << endl;//输出vec2的大小
        cout << "vec2.capacity() = " << vec2.capacity() << endl;//输出vec2的容量
        cout << "vec2: ";
        for (vector<int>::const_iterator iter = vec2.begin(); iter < vec2.end(); ++iter) {
                cout << *iter << ends;//输出vec2的值
        }
        cout << endl;
}
  • 结果
vec1.size()     = 10
vec1.capacity() = 10
vec1: 1 2 3 4 5 6 7 8 9 10
vec2.size()     = 10
vec2.capacity() = 10
vec2: 1 2 3 4 5 6 7 8 9 10

4.7 replace()

  • replace函数包含于头文件#include<string>中。
  • 泛型算法replace把队列中与给定值相等的所有值替换为另一个值,整个队列都被扫描,即此算法的各个版本都在
  • 线性时间内执行———其复杂度为O(n)。
  • replace的执行要遍历由区间[frist,last)限定的整个队列,以把old_value替换成new_value
  • 代码案例
#include <iostream>
#include <string>

using namespace std;

int main()
{
        string str = "he is a@@ good boy";
        str = str.replace(str.find("a"), 2, "##");//从第一个a位置开始的两个字符替换成#
        cout << str << endl;

        string str2 = "he is@ a@ good boy";
        str2 = str2.replace(str2.begin(), str2.begin() + 5, "#"); //用#替换从begin位置开始的5个字符
        cout << str2 << endl;
        return 0;
}
  • 结果
he is ##@ good boy
#@ a@ good boy

4.8 for_each()

  • 遍历事实上是个function template
  • 代码案例
#include <iostream>     
#include <algorithm>    
#include <vector>   

using namespace std;

void myfunction(int i)
{  
   cout << ' ' << i;
}

struct myclass
{        
    void operator() (int i) 
    {
        cout << ' ' << i; 
    }
} myobject;

int main() {
    vector<int> myvector;
    myvector.push_back(10);
    myvector.push_back(20);
    myvector.push_back(30);

    cout << "myvector contains:";
    for_each(myvector.begin(), myvector.end(), myfunction);
    cout << '\n';

    // or:
    cout << "myvector contains:";
    for_each(myvector.begin(), myvector.end(), myobject);
    cout << '\n';

    return 0;
}
  • 结果
myvector contains: 10 20 30
myvector contains: 10 20 30

版权属于:zfh

本文链接:http://zfhblog.com/index.php/archives/107/



评论已关闭