# includes

Category: algorithms | Component type: function

### Prototype

`Includes` is an overloaded name; there are actually two `includes` functions.

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

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

### Description

`Includes` tests whether one sorted range includes another sorted range. That is, it returns `true` if and only if, for every element in `[first2, last2)`, an equivalent element [1] is also present in `[first1, last1)` [2]. Both `[first1, last1)` and `[first2, last2)` must be sorted in ascending order.

The two versions of `includes` differ in how they define whether one element is less than another. The first version compares objects using `operator<`, and the second compares objects using the function object `comp`.

### Definition

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

### Requirements on types

For the first version:

- `InputIterator1` is a model of Input Iterator.
- `InputIterator2` is a model of Input Iterator.
- `InputIterator1` and `InputIterator2` have the same value type.
- `InputIterator`'s value type is a model of LessThan Comparable.
- The ordering on objects of `InputIterator1`'s value type is a strict weak ordering, as defined in the LessThan Comparable requirements.

For the second version:

- `InputIterator1` is a model of Input Iterator.
- `InputIterator2` is a model of Input Iterator.
- `InputIterator1` and `InputIterator2` have the same value type.
- `StrictWeakOrdering` is a model of Strict Weak Ordering.
- `InputIterator1`'s value type is convertible to `StrictWeakOrdering`'s argument type.

### Preconditions

For the first version:

- `[first1, last1)` is a valid range.
- `[first2, last2)` is a valid range.
- `[first1, last1)` is ordered in ascending order according to `operator<`. That is, for every pair of iterators `i` and `j` in `[first1, last1)` such that `i` precedes `j`, `*j < *i` is `false`.
- `[first2, last2)` is ordered in ascending order according to `operator<`. That is, for every pair of iterators `i` and `j` in `[first2, last2)` such that `i` precedes `j`, `*j < *i` is `false`.

For the second version:

- `[first1, last1)` is a valid range.
- `[first2, last2)` is a valid range.
- `[first1, last1)` is ordered in ascending order according to `comp`. That is, for every pair of iterators `i` and `j` in `[first1, last1)` such that `i` precedes `j`, `comp(*j, *i)` is `false`.
- `[first2, last2)` is ordered in ascending order according to `comp`. That is, for every pair of iterators `i` and `j` in `[first2, last2)` such that `i` precedes `j`, `comp(*j, *i)` is `false`.

### Complexity

Linear. Zero comparisons if either `[first1, last1)` or `[first2, last2)` is an empty range, otherwise at most `2 * ((last1 - first1) + (last2 - first2)) - 1` comparisons.

### Example

    int A1[] = { 1, 2, 3, 4, 5, 6, 7 };
    int A2[] = { 1, 4, 7 };
    int A3[] = { 2, 7, 9 };
    int A4[] = { 1, 1, 2, 3, 5, 8, 13, 21 };
    int A5[] = { 1, 2, 13, 13 };
    int A6[] = { 1, 1, 3, 21 };

    const int N1 = sizeof(A1) / sizeof(int);
    const int N2 = sizeof(A2) / sizeof(int);
    const int N3 = sizeof(A3) / sizeof(int);
    const int N4 = sizeof(A4) / sizeof(int);
    const int N5 = sizeof(A5) / sizeof(int);
    const int N6 = sizeof(A6) / sizeof(int);

    cout << "A2 contained in A1: "
         << (includes(A1, A1 + N1, A2, A2 + N2) ? "true" : "false") << endl;
    cout << "A3 contained in A1: "
         << (includes(A1, A1 + N2, A3, A3 + N3) ? "true" : "false") << endl;
    cout << "A5 contained in A4: "
         << (includes(A4, A4 + N4, A5, A5 + N5) ? "true" : "false") << endl;
    cout << "A6 contained in A4: "
         << (includes(A4, A4 + N4, A6, A6 + N6) ? "true" : "false") << endl;

The output is:

    A2 contained in A1: true
    A3 contained in A1: false
    A5 contained in A4: false
    A6 contained in A4: true

### Notes

[1] This reads "an equivalent element" rather than "the same element" because the ordering by which the input ranges are sorted is permitted to be a strict weak ordering that is not a total ordering: there might be values `x` and `y` that are equivalent (that is, neither `x < y` nor `y < x` is true) but not equal. See the LessThan Comparable requirements for a fuller discussion.) If you're using a total ordering (if you're using `strcmp`, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.

[2] Note that the range `[first2, last2)` may contain a consecutive range of equivalent elements: there is no requirement that every element in the range be unique. In this case, `includes` will return `false` unless, for every element in `[first2, last2)`, a distinct equivalent element is also present in `[first1, last1)`. That is, if a certain value appears `n` times in `[first2, last2)` and `m` times in `[first1, last1)`, then `includes` will return `false` if `m < n`.

### See also

`set_union`, `set_intersection`, `set_difference`, `set_symmetric_difference`, `sort`

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation