C++算法接口参考

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;
}

//-----Example-----
#include <iostream>  // std::cout
#include <algorithm> // std::all_of
#include <array>     // std::array

int main()
{
    std::array<int, 8> foo = {3,5,7,9,11,13,15,17};

    if (std::all_of(foo.begin(), foo.end(), [](int i){return i%2;}))
    {
        std::cout << "All the elements are odd numbers.\n";
    }

    return 0;
}

//-----Output-----
//All the elements are odd numbers.

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;
}

//-----Example-----
#include <iostream>  // std::cout
#include <algorithm> // std::any_of
#include <array>     // std::array

int main()
{
    std::array<int ,7> foo = {5,3,1,0,-1,-3,-5};

    if (std::any_of(foo.begin(), foo.end(), [](int i){return i<0;}))
    {
        std::cout << "There are negative elements in the range.\n";
    }

    return 0;
}

//-----Output-----
//There are negative elements in the range.

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;
}

//-----Example-----
#include <iostream>  // std::cout
#include <algorithm> // std::none_of
#include <array>     // std::array

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

    if ( std::none_of(foo.begin(), foo.end(), [](int i){return i<0;}) )
    {
        std::cout << "There are no negative elements in the range.\n";
    }

    return 0;
}

//-----Output-----
//There are no negative elements in the range.

template<class InputIterator, class Function>
Function forEach(InputIterator first, InputIterator last, Function fn)
{
    while (first != last)
    {
        fn(*first);
        ++first;
    }

    //return move(fn);
    return fn;       // or, since c++11: return move(fn);
}

//-----Example-----
#include <iostream>  // std::cout
#include <algorithm> // std::for_each
#include <vector>    // std::vector

void myfunction(int i)
{
    std::cout << ‘ ‘ << i;
}

struct myclass
{
    void operator() (int i) {std::cout << ‘ ‘ << i;}
}myobject;

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

    std::cout << "myvector contains:";
    forEach (myvector.begin(), myvector.end(), myfunction);
    std::cout << ‘\n‘;

    // or:
    std::cout << "myvector contains:";
    forEach(myvector.begin(), myvector.end(), myobject);
    std::cout << ‘\n‘;

    return 0;
}

//-----Output-----
//myvector: 10 20 30
//myvector: 10 20 30

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;
}

//-----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);
    p = 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);
    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;
}

//-----Output-----
//Element found in myints:30
//Element found in myvector:30

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;
}

//-----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;
}

//-----Output-----
//The first odd value is:25

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

    return last;
}

//-----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;
}

//-----Output-----
//The first even value is:2

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator2 last1,
                          ForwardIterator2 first2, ForwardIterator2 last2)
{
    if (first2 == last2)
    {
        return last1;
    }

    ForwardIterator1 ret = last1;

    while (first1 != last1)
    {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        while (*it1 == *it2)
        {
            ++it1;
            ++it2;
            
            if (it2 == last2)
            {
                ret = first1; 
                break;
            }

            if (it1 == last1)
            {
                return ret;
            }
        }

        ++first1;
    }

    return ret;
}

//-----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;
}

//-----Output-----
//needle1 found at position:5
//needle2 found at position:3

template<class InputIterator, class ForwardIterator>
InputIterator findFirstOf(InputIterator first1, InputIterator last1,
        ForwardIterator first2, ForwardIterator last2)
{
    while (first1 != last1)
    {
        for (ForwardIterator it=first2; it!=last2; ++it)
        {
            if (*it == *first1)
            {
                return first1;
            }
            ++first1;
        }
    }

    return last1;
}

//-----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 = findFirstOf(haystack.begin(), haystack.end(), needle, needle+3);
    if (it != haystack.end())
    {
        std::cout << "The first match is:" << *it << ‘\n‘;
    }

    // using predicate comparison:
    //it = findFirstOf(haystack.begin(), haystack.end(), needle, needle+3, comp_case_insensitive);
    //if (it != haystack.end())
    //{
    //    std::cout << "The first match is:" << *it << ‘\n‘;
    //}

    return 0;
}

//-----Output-----
//The first match is:A
//The first match is:a

template<class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
{
    if (first != last)
    {
        ForwardIterator next = first;
        ++next;
        while (next != last)
        {
            if (*first == next)
            {
                return first;
            }
            ++first;
            ++next;
        }
    }

    return last;
}

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

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‘;
    }

    return 0;
}

//-----Output-----
//The first pair of repeated elements are:30

template <class InputIterator, class T>
int count(InputIterator first, InputIterator last, const T& val)
{
    int ret = 0;
    while (first != last)
    {
        if (*first == val)
        {
            ++ret;
        }
        ++first;
    }

    return ret;
}

//-----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,40}; // 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;
}

//-----Output-----
//10 appears 3 times.
//20 appears 2 times.

template<class InputIterator, class UnaryPredicate>
int countIf(InputIterator first, InputIterator last, UnaryPredicate pred)
{
    int ret = 0;
    while (first != last)
    {
        if (pred(*first))
        {
            ++ret;
        }
        ++first;
    }

    return ret;
}

//-----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);
    }

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

    return 0;
}

//-----Output-----
//myvector contains 5 odd values.

#include <utility>  // std::pair
template<class InputIterator1, class InputIterator2>
std::pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
{
    while ((first1 != last1) && (first1 == first2))
    {
        ++first1;
        ++first2;
    }

    return std::make_pair(first1, first2);
}

//-----Example-----
#include <iostream>  // std::cout
#include <algorithm> // std::mismatch
#include <vector>    // std::vector

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

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

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

    std::pair<std::vector<int>::iterator, int*> mypair;
    // using defautl 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;
}

//------Output------
//First mismatching elements:30 and 80
//Second mismatching elements:40 and 320

template<class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
{
    while (first1 != last1)
    {
        if (first1 != first2)
        {
            return false;
        }
        ++first1;
        ++first2;
    }

    return true;
}

//-----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};
    std::vector<int> myvector(myints, myints+5);

    // 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;
    // using predicate comparison:
    if (std::equal(myvector.begin(), myvector.end(), myints, mypredicate))
    {
        std::cout << "Second contents of both sequences are equal.\n";
    }
    else
    {
        std::cout << "Second contents of both sequences differ.\n";
    }

    return 0;
}

//-----Putput-----
//The contents of both sequences are equal.
//Second contents of both sequence differ.

#include <iostream>  // std::cout

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(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;
            }
        }
    }
}

//-----Example-----
#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;
}

//------Output-----
//foo and bar contain the same elements.

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2)
{
    if (first2 == last2)
    {
        return first1;
    }    

    while (first1 != last1)
    {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        while(*it1 == *it2)
        {
            ++it1;
            ++it2;
            if (it2 == last2)
            {
                return first1;
            }

            if (it1 == last1)
            {
                return last1;
            }
        }
        ++first1;
    }

    return first1;
}

//-----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;    // 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;
}

//-----Output-----
//needle1 found at position:3
//needle2 not found.

#include <iostream>  // std::cout

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)
        {
            ++it;
            if (++i == count)
            {
                return first;
            }
        }
        ++first;
    }

    return last;
}

//-----Example-----
#include <algorithm> // std::searcn_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 << "Match1 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:" << (it-myvector.begin()) << ‘\n‘;
    }
    else
    {
        std::cout << "Match2 not found.\n";
    }

    return 0;
}

//-----Output-----
//Two 30s found at position:2
//Two 10s found at position:5