#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<list>

#include<deque>

#include<algorithm>

using namespace std;

/*************************************************************************************

std::search       从左往右找子区间    全部容器适用                       algorithm

--------------------------------------------------------------------------------------

template <class ForwardIterator1, class ForwardIterator2>

ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,

                          ForwardIterator2 first2, ForwardIterator2 last2 );

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,

                          ForwardIterator2 first2, ForwardIterator2 last2.

                          BinaryPredicate pred );

eg:

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 the pred version

        {

            ++it1;

            ++it2;

            if (it2==last2) return first1;

            if (it1==last1) return last1;

        }

        ++first1;

    }

    return last1;

}

**************************************************************************************/

/*************************************************************************************

std::find_end       从右往左找子区间     全部容器适用                     algorithm

--------------------------------------------------------------------------------------

template <class ForwardIterator1, class ForwardIterator2>

ForwardIterator1 find_end ( ForwardIterator1 first1, ForwardIterator1 last1,

                            ForwardIterator2 first2, ForwardIterator2 last2 );

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

ForwardIterator1 find_end ( ForwardIterator1 first1, ForwardIterator1 last1,

                            ForwardIterator2 first2, ForwardIterator2 last2,

                            BinaryPredicate pred );

eg:

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 the pred version

        {

            ++it1;

            ++it2;

            if (it2==last2)

            {

                ret=first1;

                break;

            }

            if (it1==last1) return ret;

        }

        ++first1;

    }

    return ret;

}

**************************************************************************************/

bool mypredicate (int i, int j)

{

    return (i==j);

}

bool myfunction (int i, int j)

{

    return (i==j);

}

bool check(int elem,bool bo)//二元谓词

{

    if(bo) return !(elem&1);

    else   return  elem&1;

}

int main ()

{

    vector<int> myvector;

    vector<int>::iterator it;

    // set some values:        myvector: 10 20 30 40 50 60 70 80 90

    for (int i=1; i<10; i++) myvector.push_back(i*10);

    // using default comparison:

    int match1[] = {40,50,60,70};

    it = search (myvector.begin(), myvector.end(), match1, match1+4);

    if (it!=myvector.end())

        cout << "match1 found at position " << int(it-myvector.begin()) << endl;

    else

        cout << "match1 not found" << endl;

    // using predicate comparison:

    int match2[] = {20,30,50};

    it = search (myvector.begin(), myvector.end(), match2, match2+3, mypredicate);

    if (it!=myvector.end())

        cout << "match2 found at position " << int(it-myvector.begin()) << endl;

    else

        cout << "match2 not found" << endl;

    /**--------------------------------------find_end-----------------------------------------**/

    int myints[] = {1,2,3,4,5,1,2,3,4,5,1};

    deque<int> mydeque (myints,myints+11);

    deque<int>::iterator itd;

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

    // using default comparison:

    itd = find_end (mydeque.begin(), mydeque.end(), match3, match3+3);

    if (itd!=mydeque.end())

        cout << "match1 last found at position " << int(itd-mydeque.begin()) << endl;

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

    // using predicate comparison:

    itd = find_end (mydeque.begin(), mydeque.end(), match4, match4+3, myfunction);

    if (itd!=mydeque.end())

        cout << "match2 last found at position " << int(itd-mydeque.begin()) << endl;

    /**--------------------------拓展找：偶数奇数奇数------------------------------**/

    cout<<"\n1  2  3  4  5  1  2  3  4  5  1"<<endl;

    vector<int> vec(myints,myints+11);

    bool checkEven[3]={true,false,false};

    //search

    it=search(vec.begin(),vec.end(),checkEven,checkEven+3,check);

    //find_end

    itd=find_end(mydeque.begin(),mydeque.end(),checkEven,checkEven+3,check);

    if (it!=vec.end())

        cout << " even odd odd found at position " << int(it-vec.begin()) << endl;

    else

        cout << "not found" << endl;

    if (itd!=mydeque.end())

        cout << " even odd odd found at position " << int(itd-mydeque.begin()) << endl;

    else

        cout << "not found" << endl;

    return 0;

}

/******

Output:

    match1 found at position 3

    match2 not found

    match1 last found at position 5

    match2 last found at position 3

    1  2  3  4  5  1  2  3  4  5  1

     even odd odd found at position 3

     even odd odd found at position 8

******/