std::includes

template <class InputIterator1, class InputIterator2> bool includes ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 );template <class InputIterator1, class InputIterator2, class Compare> bool includes ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp );

Test whether sorted range includes another sorted range

Returns true if the sorted range [first1,last1) contains all the elements in the sorted range [first2,last2).

The elements are compared using operator< for the first version, and comp for the second. Two elements, a and b are considered equivalent if (!(a<b) && !(b<a)) or if (!comp(a,b) && !comp(b,a)).

The elements in the range shall already be ordered according to this same criterion (operator< or comp).

The behavior of this function template is equivalent to:

template <class InputIterator1, class InputIterator2>
 bool includes (InputIterator1 first1, InputIterator1 last1,
 InputIterator2 first2, InputIterator2 last2)
{
 while (first2!=last2) {
 if ( (first1==last1) || (*first2<*first1) ) return false;
 if (!(*first1<*first2)) ++first2;
 ++first1;
 }
 return true;
}

Parameters

first1, last1: Input iterators to the initial and final positions of the first sorted sequence (which is tested on whether it contains the second sequence). The range used is [first1,last1), which contains all the elements between first1 and last1, including the element pointed by first1 but not the element pointed by last1.
first2, last2: Input iterators to the initial and final positions of the second sorted sequence (which is tested on whether it is contained in the first sequence). The range used is [first2,last2).
comp: Binary function that accepts two elements as arguments (one from each of the two sequences, in the same order), and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.

Return value

true if every element in the range [first2,last2) is contained in the range [first1,last1), false otherwise.

If [first2,last2) is an empty range, the result is unspecified.

If [first2,last2) is an empty range, the function returns true.

Example

// includes algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::includes, std::sort
bool myfunction (int i, int j) { return i<j; }
int main () {
 int container[] = {5,10,15,20,25,30,35,40,45,50};
 int continent[] = {40,30,20,10};
 std::sort (container,container+10);
 std::sort (continent,continent+4);
 // using default comparison:
 if ( std::includes(container,container+10,continent,continent+4) )
 std::cout << "container includes continent!\n";
 // using myfunction as comp:
 if ( std::includes(container,container+10,continent,continent+4, myfunction) )
 std::cout << "container includes continent!\n";
 return 0;
}

Output:

container includes continent!
container includes continent!

Complexity

Up to linear in twice the distances in both ranges: Performs up to 2*(count1+count2)-1 comparisons (where countX is the distance between firstX and lastX).

Data races

Some (or all) of the objects in both ranges are accessed (twice each at most).

Exceptions

Throws if any element comparison (or call to comp) throws or if any of the operations on iterators throws.
Note that invalid arguments cause undefined behavior.