C/C++编程：Algorithm

傷城~ 2022-05-16 23:35 59阅读 0赞

**Algorithm**

## 头文件 ##

\#include <algorithm>

## 区间 ##

算法的处理的都是半开区间\[begin, end）

## 示例 ##

### std::max ###

**作用：返回各给定值中的较大者**

**参考：[c++标准库][c]max说明**

#include <algorithm>
    #include <iostream>
    #include <string>
     
    int main()
    {
        std::cout << "larger of 1 and 9999: " << std::max(1, 9999) << '\n'
                  << "larger of 'a', and 'b': " << std::max('a', 'b') << '\n'
                  << "longest of \"foo\", \"bar\", and \"hello\": " <<
                      std::max( { "foo", "bar", "hello" },
                                [](const std::string& s1, const std::string& s2) {
                                     return s1.size() < s2.size();
                                 }) << '\n';
    }

效果：

![20210222142604754.png][]

### std::max\_element ###

**作用：返回范围内的最大元素**

**参考：[C++标准库max\_element说明][C_max_element]**

#include <algorithm>
    #include <iostream>
    #include <vector>
    #include <cmath>
     
    static bool abs_compare(int a, int b)
    {
        return (std::abs(a) < std::abs(b));
    }
     
    int main()
    {
        std::vector<int> v{ 3, 1, -14, 1, 5, 9 }; 
        std::vector<int>::iterator result;
     
        result = std::max_element(v.begin(), v.end());
        std::cout << "max element at: " << std::distance(v.begin(), result) << '\n';
     
        result = std::max_element(v.begin(), v.end(), abs_compare);
        std::cout << "max element (absolute) at: " << std::distance(v.begin(), result) << '\n';
    }

![20210222143155307.png][]

![20210222142020992.png][]

### 处理单个区间 ###

#include <algorithm>
    #include <vector>
    #include <iostream>
    using namespace std;
    
    int main()
    {
        // create vector with elements from 1 to 6 in arbitrary order
        vector<int> coll = { 2, 5, 4, 1, 6, 3 };
    
        // 区间内找最大值或者最小值
        // 参数： 传入想要处理的元素范围
        // 返回值：返回一个迭代器，分别指向最大元素或者最小元素
        auto minpos = min_element(coll.cbegin(), coll.cend());  // 处理当前元素的所有元素
        cout << "min: " << *minpos << endl;
        auto maxpos = max_element(coll.cbegin(), coll.cend());
        cout << "max: " << *maxpos << endl;
    
        // 区间内排序
        sort(coll.begin(), coll.end());
    
        // 在给定范围内找某个值
        // --- 找到了就返回一个迭代器，指向目标元素
        // --- 找不到返回一个迭代器，指向coll.end()
        // - no cbegin()/cend() because later we modify the elements pos3 refers to
        auto pos3 = find(coll.begin(), coll.end(), 3);                     
    
        // 将第3个元素到最后一个元素之间的所有元素反转放置
        reverse(pos3, coll.end());
    
        // print all elements
        for (auto elem : coll) {
            cout << elem << ' ';
        }
        cout << endl;
    }

# ![20210131175255181.png][] #

#include <algorithm>
    #include <list>
    #include <iostream>
    using namespace std;
    
    int main()
    {
        list<int> coll;
    
        for (int i = 20; i <= 40; ++i) {
            coll.push_back(i);
        }
    
        // - there is none, so pos3 gets coll.end()
        auto pos3 = find(coll.begin(), coll.end(),   3);                         
    
    // reverse the order of elements between found element and the end
    // - because pos3 is coll.end() it reverses an empty range
        reverse(pos3, coll.end());
    
        // find positions of values 25 and 35
        list<int>::iterator pos25, pos35;
        pos25 = find(coll.begin(), coll.end(),  25);          
        pos35 = find(coll.begin(), coll.end(), 35);                    
    
    // print the maximum of the corresponding range
    // - note: including pos25 but excluding pos35
        cout << "max: " << *max_element(pos25, pos35) << endl;
    
        // process the elements including the last position
        cout << "max: " << *max_element(pos25, ++pos35) << endl;  
        // list容器可以使用++取出pos35的下一个位置‘
        // 如果是vectors或者deques等随机存取迭代器，可以使用pos35 + 1 
    }

![2021013118004877.png][]

### 处理多个区间 ###

如果需要同时处理多个区间：通常必须设置第一个区间的起点和终点，至于其他区间，只需要设置起点即可，终点通常可以由第一区间的元素数量推导出来。

如果某个算法用来处理多个区间，那么请务必保证其他区间所拥有的元素个数，至少和第一区间的元素个数相同

#include <algorithm>
    #include <list>
    #include <vector>
    #include <deque>
    using namespace std;
    
    int main()
    {
        list<int>   coll1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        vector<int> coll2;
    
        //调整destination的大小，以有足够的空间覆盖算法
        coll2.resize(coll1.size());
    
        //从第一个集合复制元素到第二个集合
        // -覆盖destination中现有的元素
        copy(coll1.cbegin(), coll1.cend(),   // source
            coll2.begin());                 // destination
    
        //创建有足够空间的第三个集合
        // -初始大小作为参数传递
        deque<int> coll3(coll1.size());
    
        //从第一个集合复制元素到第三个集合
        copy(coll1.cbegin(), coll1.cend(),   // source
            coll3.begin());                 // destination
    }

# 泛型算法通则 #

*  所有算法的前两个参数都是一对iterators：\[frist，last)，用来指出容器内一个范围内的元素
 *  每个算法的声明中，都表现出它所需要的最低层次的iterator类型。

![70][]

*  大部分算法都可以用functioin object 来更改准则。function object又称functor

![70 1][]

[c]: https://zh.cppreference.com/w/cpp/algorithm/max
[20210222142604754.png]: /images/20220517/18a64487fd8740d08d28bd55f7e50b0b.png
[C_max_element]: https://zh.cppreference.com/w/cpp/algorithm/max_element
[20210222143155307.png]: /images/20220517/ef1eafe85b9b4b81a616d897ac4f6a48.png
[20210222142020992.png]: /images/20220517/657d9107cedc4bd4a869cf099789c877.png
[20210131175255181.png]: /images/20220517/6699b70a6ba54e6895958b0d972248f5.png
[2021013118004877.png]: /images/20220517/b6699a118a3c4db1a40064cb90e4a37a.png
[70]: /images/20220517/7fef00b36cec4b55ac905e932f091bd1.png
[70 1]: /images/20220517/ffeb649d0e504349af45d98ee69b1deb.png