STL常用算法

STL里面的容器是非常频繁使用的，但是关于算法部分可能使用不是太多，导致简洁的STL容器往往搭配繁琐低效的自实现算法。为此此章专门记录一些常用的STL算法。主要涉及到的头文件为<algorithm>和<numeric>。

查询算法

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <binders.h>
#include <functional>

using namespace std;

int main()
{
    vector<int> ivec{1, 3, 2, 0, 3, 5, 12, 4, 4, 4, 6, 6, 7, 6, 20};
    vector<string> svec{"apple", "test", "god", "dog", "dog", "json", "orange"};
    /*
     * std::adjacent_find
     * 查找相邻重复的元素,默认版本是两个相同的元素为判断条件。对于数值型的数据一般按照默认规则
     * 即可，对于字符串类型的数据，可能会使用长度相同作为判断条件。STL大部分的算法都提供自定义
     * 规则入口。
    */
    cout << *std::adjacent_find(ivec.begin(), ivec.end()) << endl;
    cout << *std::adjacent_find(svec.begin(), svec.end()) << endl;
    cout << *std::adjacent_find(svec.begin(), svec.end(), [](const string & left,
    const string & right) {
        return left.size() == right.size();
    }) << endl;
    /*
     *count
     * 计算给定范围内指定的值的个数
     * count_if
     * 按照自定义规则计算给定范围内指定的值的个数
    */
    cout << std::count(ivec.begin(), ivec.end(), 3) << endl;
    cout << std::count_if(ivec.begin(), ivec.end(), std::bind(std::less<int>(),  std::placeholders::_1, 10)) << endl;

    /*
     * std::binary_search
     * 二分查找，需要先对数据进行排序，然后才能使用二分查找，不然会一直返回false
    */
//    std::sort(ivec.begin(), ivec.end());
    cout << std::boolalpha << std::binary_search(ivec.begin(), ivec.end(), 400) << endl;
    /*
     * std::lower_bound 、std::upper_bound、 std::equal_range
     * 二分查找，需要先对数据进行排序。std::equal_range为前两个操作的综合操作，会
     * 得到一个pair类型的结果，first表示std::lower_bound的结果，second表示upper_bound
     * 的结果，都是迭代器类型。std::lower_bound表示查找序列中第一个大于或等于指定值的值，
     * 而std::upper_bound表示查找第一个大于指定值的值，和前者的不同之处在于是否包含等于。
    */
    cout << *std::lower_bound(ivec.begin(), ivec.end(), 8) << endl;
    cout << *std::upper_bound(ivec.begin(), ivec.end(), 8) << endl;
    auto pairIt = std::equal_range(ivec.begin(), ivec.end(), 6);
    cout << *pairIt.first << endl;
    cout << *pairIt.second << endl;

    /*
     * std::find
     * 查找元素是否存在，存在返回该元素的迭代器，不存在则返回end()
     * std::find_if
     * find的增加版，可以自定义规则
    */
    cout << *std::find(ivec.begin(), ivec.end(), 12) << endl;
    cout << *std::find_if(ivec.begin(), ivec.end(), std::bind(std::greater<int>(),  std::placeholders::_1, 12)) << endl;

    /*
     * std::search
     * 在前者序列中搜索后者序列是否存在，存在返回前者序列中被查找到的序列首位置
     * std::search_n
     * 在序列中查找是否存在连续n个一样的值，重点是连续，而不单是数量
    */
    std::vector<int> ivec1{12, 20};
    cout << "search:" << *std::search(ivec.begin(), ivec.end(), ivec1.begin(), ivec1.end()) << endl;
    cout << "search_n:" << *std::search_n(ivec.begin(), ivec.end(), 2, 6) << endl;

    return 0;
}