STL 算法测一遍（一）

注意：这篇文章上次更新于932天前，文章内容可能已经过时。

提到 STL 算法，大家都知道很牛B。

但是想一想，除了 sort() , 你还会用啥呢？😂

最近抽时间把 STL 所有算法测试一遍，做到心里有个印象。

本文的这些示例基本上都来自于 cppreference.com 和 cplusplus.com

其实就是挨个看一遍，然后复制粘贴一下。

不修改序列的算法

all_of

检查谓词是否对所有元素生效，是返回 true ，否返回 false。

输入参数：

1. 起始迭代器
2. 终止迭代器
3. 可调用对象（谓词条件）

函数行为：

template <class InputIterator, class UnaryPredicate>
bool all_of(InputIterator first, InputIterator last, UnaryPredicate pred)
{
    while (first != last)
    {
        if (!pred(*first))
            return false;
        ++first;
    }
    return true;
}

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

int main(){
    std::vector<int> foo = {3,5,7,9,13,19,21};
    if(std::all_of(foo.begin(),foo.end(),[](int x){ 
        return x%2;
    }))
    {
        std::cout << "All the elements are odd numbers." << std::endl;
    }
    return 0;
}

any_of

检查谓词是否对部分元素生效，是返回 true ，否返回 false。

输入参数：

1. 起始迭代器
2. 终止迭代器
3. 可调用对象（谓词条件）

函数行为：

template <class InputIterator, class UnaryPredicate>
bool any_of(InputIterator first, InputIterator last, UnaryPredicate pred)
{
    while (first != last)
    {
        if (pred(*first))
            return true;
        ++first;
    }
    return false;
}

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

bool mycmp(int x){
    return x%2 == 0;
}

int main(){
    std::vector<int> foo = {3,5,7,9,8,13,19,21};
    if(std::any_of(foo.begin(),foo.end(),mycmp))
    {
        std::cout << "存在偶数元素." << std::endl;
    }
    return 0;
}

none_of

检查谓词是否对全部元素都不生效，是返回 true ，否返回 false。

输入参数：

1. 起始迭代器
2. 终止迭代器
3. 可调用对象（谓词条件）

函数行为：

template <class InputIterator, class UnaryPredicate>
bool none_of(InputIterator first, InputIterator last, UnaryPredicate pred)
{
    while (first != last)
    {
        if (pred(*first))
            return false;
        ++first;
    }
    return true;
}

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

struct mycmp{
    bool operator()(int x){
        return x < 0;
    }
};

int main(){
    std::vector<int> foo = {3,5,7,9,8,13,19,21};
    if(std::none_of(foo.begin(),foo.end(),mycmp()))
    {
        std::cout << "没有小于零的元素" << std::endl;
    }
    return 0;
}

for_each

输入参数：

1. 起始迭代器
2. 终止迭代器
3. 可调用对象 fn

将 fn 作用在每一个对象身上。

函数行为：

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function fn)
{
    while (first != last)
    {
        fn(*first);
        ++first;
    }
    return fn; // or, since C++11: return move(fn);
}

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

struct mycmp{
    void operator()(int x){
        std::cout << " " << x;
    }
}mycmpobj;

int main(){
    std::vector<int> foo = {3,5,7,9,8,13,19,21};
    std::for_each(foo.begin(),foo.end(),mycmpobj);
    std::for_each(foo.begin(),foo.end(),[](int& x){
        x++;
    });
    std::for_each(foo.begin(),foo.end(),mycmpobj);
    return 0;
}

find

输入参数：

1. 起始迭代器
2. 终止迭代器
3. 查找的对象

返回满足条件的迭代器。

PS：从函数行为可以看出自定义对象需要重载 == 运算符。

函数行为：

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T &val)
{
    while (first != last)
    {
        if (*first == val)
            return first;
        ++first;
    }
    return last;
}

示例代码：

// find example
#include <iostream>  // std::cout
#include <algorithm> // std::find
#include <vector>    // std::vector

int main()
{
    // using std::find with array and pointer:
    int myints[] = {10, 20, 30, 40};
    int *p;

    p = std::find(myints, myints + 4, 30);
    if (p != myints + 4)
        std::cout << "Element found in myints: " << *p << '\n';
    else
        std::cout << "Element not found in myints\n";

    // using std::find with vector and iterator:
    std::vector<int> myvector(myints, myints + 4);
    std::vector<int>::iterator it;

    it = find(myvector.begin(), myvector.end(), 30);
    if (it != myvector.end())
        std::cout << "Element found in myvector: " << *it << '\n';
    else
        std::cout << "Element not found in myvector\n";

    return 0;
}

find_if

输入参数：

1. 起始迭代器
2. 终止迭代器
3. 可调用对象

当可调用对象返回 true 时，返回该元素迭代器；查找失败返回终止迭代器。

函数行为：

template <class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred)
{
    while (first != last)
    {
        if (pred(*first))
            return first;
        ++first;
    }
    return last;
}

示例代码：

// find_if example
#include <iostream>  // std::cout
#include <algorithm> // std::find_if
#include <vector>    // std::vector

bool IsOdd(int i)
{
    return ((i % 2) == 1);
}

int main()
{
    std::vector<int> myvector;

    myvector.push_back(10);
    myvector.push_back(25);
    myvector.push_back(40);
    myvector.push_back(55);

    std::vector<int>::iterator it = std::find_if(myvector.begin(), myvector.end(), IsOdd);
    std::cout << "The first odd value is " << *it << '\n';

    return 0;
}

find_if_not

性质基本同上

返回第一个不满足条件的元素迭代器，查找失败返回终止迭代器。

函数行为：

template <class InputIterator, class UnaryPredicate>
InputIterator find_if_not(InputIterator first, InputIterator last, UnaryPredicate pred)
{
    while (first != last)
    {
        if (!pred(*first))
            return first;
        ++first;
    }
    return last;
}

示例代码：

// find_if_not example
#include <iostream>     // std::cout
#include <algorithm>    // std::find_if_not
#include <array>        // std::array

int main () {
  std::array<int,5> foo = {1,2,3,4,5};

  std::array<int,5>::iterator it =
    std::find_if_not (foo.begin(), foo.end(), [](int i){return i%2;} );
  std::cout << "The first even value is " << *it << '\n';

  return 0;
}

find_end

输入参数：

1. 序列①起始迭代器
2. 序列①终止迭代器
3. 序列②起始迭代器
4. 序列②终止迭代器
5. 比较条件（重载版本，默认条件是 == ）

在序列①中查找序列②最后一次出现的位置，查找成功返回序列①中响应的迭代器，查找失败返回序列①的终止迭代器。

函数行为：

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                          ForwardIterator2 first2, ForwardIterator2 last2)
{
    if (first2 == last2)
        return last1; // specified in C++11

    ForwardIterator1 ret = last1;

    while (first1 != last1)
    {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        while (*it1 == *it2)
        { // or: while (pred(*it1,*it2)) for version (2)
            ++it1;
            ++it2;
            if (it2 == last2)
            {
                ret = first1;
                break;
            }
            if (it1 == last1)
                return ret;
        }
        ++first1;
    }
    return ret;
}

示例代码：

// find_end example
#include <iostream>  // std::cout
#include <algorithm> // std::find_end
#include <vector>    // std::vector

bool myfunction(int i, int j)
{
    return (i == j);
}

int main()
{
    int myints[] = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
    std::vector<int> haystack(myints, myints + 10);

    int needle1[] = {1, 2, 3};

    // using default comparison:
    std::vector<int>::iterator it;
    it = std::find_end(haystack.begin(), haystack.end(), needle1, needle1 + 3);

    if (it != haystack.end())
        std::cout << "needle1 last found at position " << (it - haystack.begin()) << '\n';

    int needle2[] = {4, 5, 1};

    // using predicate comparison:
    it = std::find_end(haystack.begin(), haystack.end(), needle2, needle2 + 3, myfunction);

    if (it != haystack.end())
        std::cout << "needle2 last found at position " << (it - haystack.begin()) << '\n';

    return 0;
}

find_first_of

输入参数：

1. 序列①起始迭代器
2. 序列①终止迭代器
3. 序列②起始迭代器
4. 序列②终止迭代器
5. 比较条件（重载版本，默认条件是 == ）

在序列①中进行查找，返回首先满足该元素存在于序列②中的元素迭代器，查找失败返回第一个序列的终止迭代器。

PS: 这个函数和上一个不太一样，上一个是查全部，这个不是。

函数行为：

template <class InputIterator, class ForwardIterator>
InputIterator find_first_of(InputIterator first1, InputIterator last1,
                            ForwardIterator first2, ForwardIterator last2)
{
    while (first1 != last1)
    {
        for (ForwardIterator it = first2; it != last2; ++it)
        {
            if (*it == *first1) // or: if (pred(*it,*first)) for version (2)
                return first1;
        }
        ++first1;
    }
    return last1;
}

示例代码：

// find_first_of example
#include <iostream>  // std::cout
#include <algorithm> // std::find_first_of
#include <vector>    // std::vector
#include <cctype>    // std::tolower

bool comp_case_insensitive(char c1, char c2)
{
    return (std::tolower(c1) == std::tolower(c2));
}

int main()
{
    int mychars[] = {'a', 'b', 'c', 'A', 'B', 'C'};
    std::vector<char> haystack(mychars, mychars + 6);
    std::vector<char>::iterator it;

    int needle[] = {'A', 'B', 'C'};

    // using default comparison:
    it = find_first_of(haystack.begin(), haystack.end(), needle, needle + 3);

    if (it != haystack.end())
        std::cout << "The first match is: " << *it << '\n';

    // using predicate comparison:
    it = find_first_of(haystack.begin(), haystack.end(),
                       needle, needle + 3, comp_case_insensitive);

    if (it != haystack.end())
        std::cout << "The first match is: " << *it << '\n';

    return 0;
}

adjacent_find

输入参数：

1. 起始迭代器
2. 终止迭代器
3. 比较条件（重载版本，默认为 == ）

在序列中查找第一个相等的相邻元素，查找失败返回终止迭代器。

函数行为：

template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
{
    if (first != last)
    {
        ForwardIterator next = first;
        ++next;
        while (next != last)
        {
            if (*first == *next) // or: if (pred(*first,*next)), for version (2)
                return first;
            ++first;
            ++next;
        }
    }
    return last;
}

示例代码：

// adjacent_find example
#include <iostream>  // std::cout
#include <algorithm> // std::adjacent_find
#include <vector>    // std::vector

bool myfunction(int i, int j)
{
    return (i == j);
}

int main()
{
    int myints[] = {5, 20, 5, 30, 30, 20, 10, 10, 20};
    std::vector<int> myvector(myints, myints + 8);
    std::vector<int>::iterator it;

    // using default comparison:
    it = std::adjacent_find(myvector.begin(), myvector.end());

    if (it != myvector.end())
        std::cout << "the first pair of repeated elements are: " << *it << '\n';

    // using predicate comparison:
    it = std::adjacent_find(++it, myvector.end(), myfunction);

    if (it != myvector.end())
        std::cout << "the second pair of repeated elements are: " << *it << '\n';

    return 0;
}

count

输入参数：

1. 起始迭代器
2. 终止迭代器
3. 比较对象

在序列中统计与目标对象相等的元素数量。

PS：没有传入比较条件的参数（传入比较条件的算法叫 count_if ），意味着可能需要重载 == 运算符。

函数行为：

template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type     // 从迭代器的萃取器中获得返回值类型
count(InputIterator first, InputIterator last, const T &val)
{
    typename iterator_traits<InputIterator>::difference_type ret = 0;
    while (first != last)
    {
        if (*first == val)
            ++ret;
        ++first;
    }
    return ret;
}

示例代码：

// count algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::count
#include <vector>    // std::vector

int main()
{
    // counting elements in array:
    int myints[] = {10, 20, 30, 30, 20, 10, 10, 20}; // 8 elements
    int mycount = std::count(myints, myints + 8, 10);
    std::cout << "10 appears " << mycount << " times.\n";

    // counting elements in container:
    std::vector<int> myvector(myints, myints + 8);
    mycount = std::count(myvector.begin(), myvector.end(), 20);
    std::cout << "20 appears " << mycount << " times.\n";

    return 0;
}

count_if

整体同上，第三个参数为比较函数。

函数行为：

template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, UnaryPredicate pred)
{
    typename iterator_traits<InputIterator>::difference_type ret = 0;
    while (first != last)
    {
        if (pred(*first))
            ++ret;
        ++first;
    }
    return ret;
}

示例代码：

// count_if example
#include <iostream>  // std::cout
#include <algorithm> // std::count_if
#include <vector>    // std::vector

bool IsOdd(int i) { return ((i % 2) == 1); }

int main()
{
    std::vector<int> myvector;
    for (int i = 1; i < 10; i++)
        myvector.push_back(i); // myvector: 1 2 3 4 5 6 7 8 9

    int mycount = count_if(myvector.begin(), myvector.end(), IsOdd);
    std::cout << "myvector contains " << mycount << " odd values.\n";

    return 0;
}

mismatch🚩

输入参数：

1. 序列①起始迭代器
2. 序列①终止迭代器
3. 序列②起始迭代器
4. 条件函数（重载版本）

一次比较序列①和序列②，返回第一次匹配失败的位置。返回为 pair 类型，分别记录两个序列第一个不匹配的迭代器。

函数行为：

template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
{
    while ((first1 != last1) && (*first1 == *first2)) // or: pred(*first1,*first2), for version 2
    {
        ++first1;
        ++first2;
    }
    return std::make_pair(first1, first2);
}

示例代码：

// mismatch algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::mismatch
#include <vector>    // std::vector
#include <utility>   // std::pair

bool mypredicate(int i, int j)
{
    return (i == j);
}

int main()
{
    std::vector<int> myvector;
    for (int i = 1; i < 6; i++)
        myvector.push_back(i * 10); // myvector: 10 20 30 40 50

    int myints[] = {10, 20, 80, 320, 1024}; //   myints: 10 20 80 320 1024

    std::pair<std::vector<int>::iterator, int *> mypair;

    // using default comparison:
    mypair = std::mismatch(myvector.begin(), myvector.end(), myints);
    std::cout << "First mismatching elements: " << *mypair.first;
    std::cout << " and " << *mypair.second << '\n';

    ++mypair.first;
    ++mypair.second;

    // using predicate comparison:
    mypair = std::mismatch(mypair.first, myvector.end(), mypair.second, mypredicate);
    std::cout << "Second mismatching elements: " << *mypair.first;
    std::cout << " and " << *mypair.second << '\n';

    return 0;
}

都不需要检查第二个迭代器是否到头吗？

1 2 3 4 5 6

1 2 3

这样传两个序列岂不是 *first2 就越界了？

测试了以下，果然会乱七八糟。

equal

输入参数：

1. 序列①起始迭代器
2. 序列①终止迭代器
3. 序列②起始迭代器
4. 条件函数（重载版本）

检查序列②中以first2起始的序列是否包含序列①。

函数行为：

template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
{
    while (first1 != last1)
    {
        if (!(*first1 == *first2)) // or: if (!pred(*first1,*first2)), for version 2
            return false;
        ++first1;
        ++first2;
    }
    return true;
}

示例代码：

// equal algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::equal
#include <vector>    // std::vector

bool mypredicate(int i, int j)
{
    return (i == j);
}

int main()
{
    int myints[] = {20, 40, 60, 80, 100};          //   myints: 20 40 60 80 100
    std::vector<int> myvector(myints, myints + 5); // myvector: 20 40 60 80 100

    // using default comparison:
    if (std::equal(myvector.begin(), myvector.end(), myints))
        std::cout << "The contents of both sequences are equal.\n";
    else
        std::cout << "The contents of both sequences differ.\n";

    myvector[3] = 81; // myvector: 20 40 60 81 100

    // using predicate comparison:
    if (std::equal(myvector.begin(), myvector.end(), myints, mypredicate))
        std::cout << "The contents of both sequences are equal.\n";
    else
        std::cout << "The contents of both sequences differ.\n";

    return 0;
}

is_permutation🚩

输入参数：

1. 序列①起始迭代器
2. 序列①终止迭代器
3. 序列②起始迭代器
4. 条件函数（重载版本）

检查序列①是否是序列②的置换版本。

函数行为：

template <class InputIterator1, class InputIterator2>
bool is_permutation(InputIterator1 first1, InputIterator1 last1,
                    InputIterator2 first2)
{
    std::tie(first1, first2) = std::mismatch(first1, last1, first2); 
    if (first1 == last1)
        return true;
    InputIterator2 last2 = first2;
    // std::advance 将迭代器向 end 方向移动
    std::advance(last2, std::distance(first1, last1)); 
    for (InputIterator1 it1 = first1; it1 != last1; ++it1)
    {
        if (std::find(first1, it1, *it1) == it1)
        {
            auto n = std::count(first2, last2, *it1);
            if (n == 0 || std::count(it1, last1, *it1) != n)
                return false;
        }
    }
    return true;
}

示例代码：

// is_permutation example
#include <iostream>  // std::cout
#include <algorithm> // std::is_permutation
#include <array>     // std::array

int main()
{
    std::array<int, 5> foo = {1, 2, 3, 4, 5};
    std::array<int, 5> bar = {3, 1, 4, 5, 2};

    if (std::is_permutation(foo.begin(), foo.end(), bar.begin()))
        std::cout << "foo and bar contain the same elements.\n";

    return 0;
}

search

输入参数：

1. 序列①起始迭代器
2. 序列①终止迭代器
3. 序列②起始迭代器
4. 序列②终止迭代器
5. 比较条件（重载版本，默认条件是 == ）

返回序列②在序列①中第一次出现的位置。

PS：与 find_end 对应。

函数行为：

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
                        ForwardIterator2 first2, ForwardIterator2 last2)
{
    if (first2 == last2)
        return first1; // specified in C++11

    while (first1 != last1)
    {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        while (*it1 == *it2)
        { // or: while (pred(*it1,*it2)) for version 2
            ++it1;
            ++it2;
            if (it2 == last2)
                return first1;
            if (it1 == last1)
                return last1;
        }
        ++first1;
    }
    return last1;
}

示例代码：

// search algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::search
#include <vector>    // std::vector

bool mypredicate(int i, int j)
{
    return (i == j);
}

int main()
{
    std::vector<int> haystack;

    // set some values:        haystack: 10 20 30 40 50 60 70 80 90
    for (int i = 1; i < 10; i++)
        haystack.push_back(i * 10);

    // using default comparison:
    int needle1[] = {40, 50, 60, 70};
    std::vector<int>::iterator it;
    it = std::search(haystack.begin(), haystack.end(), needle1, needle1 + 4);

    if (it != haystack.end())
        std::cout << "needle1 found at position " << (it - haystack.begin()) << '\n';
    else
        std::cout << "needle1 not found\n";

    // using predicate comparison:
    int needle2[] = {20, 30, 50};
    it = std::search(haystack.begin(), haystack.end(), needle2, needle2 + 3, mypredicate);

    if (it != haystack.end())
        std::cout << "needle2 found at position " << (it - haystack.begin()) << '\n';
    else
        std::cout << "needle2 not found\n";

    return 0;
}

search_n

输入参数：

1. 起始迭代器
2. 终止迭代器
3. 匹配连续元素的最少数量
4. 比较对象
5. 比较函数（重载版本）

在序列中查找连续n次与目标对象相等的元素的起始位置。

函数行为：

template <class ForwardIterator, class Size, class T>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
                         Size count, const T &val)
{
    ForwardIterator it, limit;
    Size i;

    limit = first;
    std::advance(limit, std::distance(first, last) - count);

    while (first != limit)
    {
        it = first;
        i = 0;
        while (*it == val) // or: while (pred(*it,val)) for the pred version
        {
            ++it;
            if (++i == count)
                return first;
        }
        ++first;
    }
    return last;
}

示例代码：

// search_n example
#include <iostream>  // std::cout
#include <algorithm> // std::search_n
#include <vector>    // std::vector

bool mypredicate(int i, int j)
{
    return (i == j);
}

int main()
{
    int myints[] = {10, 20, 30, 30, 20, 10, 10, 20};
    std::vector<int> myvector(myints, myints + 8);

    std::vector<int>::iterator it;

    // using default comparison:
    it = std::search_n(myvector.begin(), myvector.end(), 2, 30);

    if (it != myvector.end())
        std::cout << "two 30s found at position " << (it - myvector.begin()) << '\n';
    else
        std::cout << "match not found\n";

    // using predicate comparison:
    it = std::search_n(myvector.begin(), myvector.end(), 2, 10, mypredicate);

    if (it != myvector.end())
        std::cout << "two 10s found at position " << int(it - myvector.begin()) << '\n';
    else
        std::cout << "match not found\n";

    return 0;
}

BibiBibi

今天就先看到这了，该睡了。

留个思考题，为什么 mismatch ， is_permutation ， equal 都不需要传第二个容器的终止迭代器呢？而 search 和 find_end 却需要传入第二个容器的终止迭代器。

后半部分应该好回答，因为函数要实现的功能要求它必须要知道两个序列的长度。

对于前半部分还需要再研究研究，今天太晚了，脑子不清醒了。

难道是因为 C++ 设计理念的原因？我听过一种说法，C++ 是一门充分相信程序员的语言，Java 是一门充分不相信程序员的语言。也许这就是原因吧😂

02点30分