find_end()

Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• See Also
• Standards Conformance

Algorithm that finds the last occurrence of a sub-sequence in a sequence

#include <algorithm>

namespace std {
  template <class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 find_end(ForwardIterator1 start1, 
                            ForwardIterator1 finish1,
                            ForwardIterator2 start2, 
                            ForwardIterator2 finish2);
  template <class Forward Iterator1, class ForwardIterator2, 
            class BinaryPredicate>
  ForwardIterator1 find_end(ForwardIterator1 start1, 
                            ForwardIterator1 finish1,
                            ForwardIterator2 start2,
                            ForwardIterator2 finish2,
                            BinaryPredicate binary_pred);
}

The find_end() algorithm finds the last occurrence of a sub-sequence, indicated by [start2, finish2), in a sequence, [start1,finish1). The algorithm returns an iterator pointing to the first element of the found sub-sequence, or finish1 if no match is found.

More precisely, the find_end() algorithm returns the last iterator i in the range [start1, finish1 - (finish2-start2)) such that for any non-negative integer n < (finish2-start2), the following corresponding conditions hold:

*(i+n)  ==  *(start2+n),    
binary_pred(*(i+n),*(start2+n)) == true.

Or returns finish1 if no such iterator is found.

Two versions of the algorithm exist. The first uses the equality operator as the default binary predicate, and the second allows you to specify a binary predicate.

At most (finish2-start2)*(finish1-start1-(finish2-start2)+1) applications of the corresponding predicate are done.

//
// find_end.cpp
//

#include <algorithm>   // for find_first_of, find_end
#include <functional>  // for equal_to
#include <iostream>    // for cout, endl
#include <list>        // for list


int main ()
{
    typedef std::list<int, std::allocator<int> > list;

    const list::value_type a1[] = { 
        0, 1, 6, 5, 3, 2, 2, 6, 5, 7 
    };
    const list::value_type a2[] = { 
        6, 5, 0, 0 
    };

    // Set up two sequences.
    const list l1 (a1, a1 + sizeof a1 / sizeof *a1);
    const list l2 (a2, a2 + 2);

    // Try both find_first_of variants.
    list::const_iterator it1 =
        std::find_first_of(l1.begin(), l1.end(), 
                           l2.begin(), l2.end());

    list::const_iterator it2 =
        std::find_first_of(l1.begin(), l1.end(),
                           l2.begin(), l2.end(),
                           std::equal_to<list::value_type>());

    // Try both find_end variants.
    list::const_iterator it3 =
        std::find_end(l1.begin(), l1.end(), 
                      l2.begin(), l2.end()); 

    list::const_iterator it4 =
        std::find_end(l1.begin(), l1.end(), 
                      l2.begin(), l2.end(),
                      std::equal_to<list::value_type>());

    // Output results of find_first_of.
    // Iterator now points to the first element that matches
    // one of a set of values.

    std::ostream_iterator<list::value_type, char,
            std::char_traits<char> > out(std::cout, " " );

    if(it3 == it4 && it1 == it2) {

        std::cout << "For the sequences { ";
        std::copy(l1.begin(), l1.end(), out);

        std::cout << "} and { ";
        std::copy(l2.begin(), l2.end(), out);
             
        std::cout << "} \nboth versions of "
                  << "find_first_of point to: "
                  << *it1 << std::endl;

        // Output results of find_end.
        // Iterator now points to the first element of the last
        // find subsequence.

        std::cout << "both versions of find_end point to: "
                  << *it3 << std::endl;
    }

    return 0;
}


Program Output:

For the sequences { 0 1 6 5 3 2 2 6 5 7 } and { 6 5 } 
both versions of find_first_of point to: 6
both versions of find_end point to: 6

Algorithms, find(), find_if(), adjacent_find()

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.1.3