◐ Shell
clean mode source ↗

std::ranges::contains, std::ranges::contains_subrange - cppreference.com

Defined in header <algorithm>

Call signature

 
template< std::input_iterator I, std::sentinel_for<I> S,
          class T,
          class Proj = std::identity >
    requires std::indirect_binary_predicate
                 <ranges::equal_to, std::projected<I, Proj>, const T*>
constexpr bool contains( I first, S last, const T& value, Proj proj = {} );
(1) (since C++23)
(until C++26)		 
template< std::input_iterator I, std::sentinel_for<I> S,
          class Proj = std::identity,
          class T = std::projected_value_t<I, Proj> >
    requires std::indirect_binary_predicate
                 <ranges::equal_to, std::projected<I, Proj>, const T*>
constexpr bool contains( I first, S last, const T& value, Proj proj = {} );
(since C++26) 
template< ranges::input_range R,
          class T,
          class Proj = std::identity >
    requires std::indirect_binary_predicate
                 <ranges::equal_to,
                  std::projected<ranges::iterator_t<R>, Proj>, const T*>
constexpr bool contains( R&& r, const T& value, Proj proj = {} );
(2) (since C++23)
(until C++26)		 
template< ranges::input_range R,
          class Proj = std::identity,
          class T = std::projected_value_t<ranges::iterator_t<R>, Proj> >
    requires std::indirect_binary_predicate
                 <ranges::equal_to,
                  std::projected<ranges::iterator_t<R>, Proj>, const T*>
constexpr bool contains( R&& r, const T& value, Proj proj = {} );
(since C++26) 
template< std::forward_iterator I1, std::sentinel_for<I1> S1,
          std::forward_iterator I2, std::sentinel_for<I2> S2,
          class Pred = ranges::equal_to,
          class Proj1 = std::identity, class Proj2 = std::identity >
    requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool contains_subrange( I1 first1, S1 last1, I2 first2, S2 last2,
                                  Pred pred = {},
                                  Proj1 proj1 = {}, Proj2 proj2 = {} );
(3) (since C++23) 
template< ranges::forward_range R1, ranges::forward_range R2,
          class Pred = ranges::equal_to,
          class Proj1 = std::identity, class Proj2 = std::identity >
    requires std::indirectly_comparable
                 <ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                  Pred, Proj1, Proj2>
constexpr bool contains_subrange( R1&& r1, R2&& r2, Pred pred = {},
                                  Proj1 proj1 = {}, Proj2 proj2 = {} );
(4) (since C++23) 
template< /*execution-policy*/ Ep,
          std::random_access_iterator I, std::sized_sentinel_for<I> S,
          class Proj = std::identity,
          class T = std::projected_value_t<I, Proj> >
    requires std::indirect_binary_predicate
                 <ranges::equal_to, std::projected<I, Proj>, const T*>
bool contains( Ep&& policy, I first, S last, const T& value, Proj proj = {} );
(5) (since C++26) 
template< /*execution-policy*/ Ep, /*sized-random-access-range*/ R,
          class Proj = std::identity,
          class T = std::projected_value_t<ranges::iterator_t<R>, Proj> >
    requires std::indirect_binary_predicate
                 <ranges::equal_to,
                  std::projected<ranges::iterator_t<R>, Proj>, const T*>
bool contains( Ep&& policy, R&& r, const T& value, Proj proj = {} );
(6) (since C++26) 
template< /*execution-policy*/ Ep,
          std::random_access_iterator I1, std::sized_sentinel_for<I1> S1,
          std::random_access_iterator I2, std::sized_sentinel_for<I2> S2,
          class Pred = ranges::equal_to,
          class Proj1 = std::identity, class Proj2 = std::identity >
    requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
bool contains_subrange( Ep&& policy, I1 first1, S1 last1, I2 first2, S2 last2,
                        Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
(7) (since C++26) 
template< /*execution-policy*/ Ep,
          /*sized-random-access-range*/ R1, /*sized-random-access-range*/ R2,
          class Pred = ranges::equal_to,
          class Proj1 = std::identity, class Proj2 = std::identity >
    requires std::indirectly_comparable
                 <ranges::iterator_t<R1>, ranges::iterator_t<R2>,
                  Pred, Proj1, Proj2>
bool contains_subrange( Ep&& policy, R1&& r1, R2&& r2, Pred pred = {},
                        Proj1 proj1 = {}, Proj2 proj2 = {} );
(8) (since C++26)

For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.

1,2) Checks whether or not the source range contains the target value value.

1) The source range is [first, last).

2) The source range is r.

3,4) Checks whether or not the target range is a subrange of the source range.

3) The source range is [first1, last1), and the target range is [first2, last2).

4) The source range is r1, and the target range is r2.

5-8) Same as (1-4), but executed according to policy.

The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:

Parameters

first/first1, last/last1 - the iterator-sentinel pair defining the source range
first2, last2 - the iterator-sentinel pair defining the target range
r/r1 - the source range
value - the target value
r2 - the target range
pred/pred1 - the predicate to be applied to the (projected) elements in the source range
pred2 - the predicate to be applied to the (projected) elements in the target range
proj/proj1 - the projection to be applied to the elements in the source range
proj2 - the projection to be applied to the elements in the target range
policy - the execution policy to use

Return value

1) ranges::find(std::move(first), last, value, proj) != last

2) ranges::find(r, value, proj) != ranges::end(r)

3) first2 == last2 || !ranges::search(first1, last1, first2, last2, pred, proj1, proj2).empty()

4) ranges::empty(r2) || !ranges::search(r1, r2, pred, proj1, proj2).empty()

5-8) Same as (1-4), but inserts std::forward<Ep>(policy) to the argument list of

ranges::find

or

ranges::search

as the first argument.

Complexity

Given

  • N as ranges::distance(first, last) or ranges::distance(r),
  • N1 as ranges::distance(first1, last1) or ranges::distance(r1), and
  • N2 as ranges::distance(first2, last2) or ranges::distance(r2):

1,2) At most N comparisons and applications of proj.

3,4) At most N1·N2 applications of pred and proj.

5,6) 𝓞(N) comparisons and applications of proj.

7,8) 𝓞(N1·N2) applications of pred and proj.

Exceptions

5-8) During the execution process:

  • If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
  • If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).

Notes

In C++20, one may implement contains with ranges::find(haystack, needle) != ranges::end(haystack) or contains_subrange with !ranges::search(haystack, needle).empty().

ranges::contains_subrange, like ranges::search, and unlike std::search, has no support for searchers (such as std::boyer_moore_searcher).

Feature-test macro Value Std Feature
__cpp_lib_ranges_contains 202207L (C++23) ranges::contains and ranges::contains_subrange
__cpp_lib_algorithm_default_value_type 202403L (C++26) List-initialization for algorithms (1,2)

Possible implementation

contains (1,2) 
struct contains_fn
{
    template<std::input_iterator I, std::sentinel_for<I> S,
             class Proj = std::identity,
             class T = std::projected_value_t<I, Proj>>
    requires std::indirect_binary_predicate
                 <ranges::equal_to, std::projected<I, Proj>, const T*>
    constexpr bool operator()(I first, S last, const T& value, Proj proj = {}) const
    {
        return ranges::find(std::move(first), last, value, proj) != last;
    }
    
    template<ranges::input_range R,
             class Proj = std::identity,
             class T = std::projected_value_t<ranges::iterator_t<R>, Proj>>
    requires std::indirect_binary_predicate
                 <ranges::equal_to,
                  std::projected<ranges::iterator_t<R>, Proj>, const T*>
    constexpr bool operator()(R&& r, const T& value, Proj proj = {}) const
    {
        return ranges::find(r, value, proj) != ranges::end(r);
    }
};

inline constexpr contains_fn contains{};
contains_subrange (3,4) 
struct contains_subrange_fn
{
    template<std::forward_iterator I1, std::sentinel_for<I1> S1,
             std::forward_iterator I2, std::sentinel_for<I2> S2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
    constexpr bool operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                              Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (first2 == last2) ||
                   !ranges::search(first1, last1, first2, last2,
                                   pred, proj1, proj2).empty();
    }
    
    template<ranges::forward_range R1, ranges::forward_range R2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::indirectly_comparable<ranges::iterator_t<R1>,
                                        ranges::iterator_t<R2>, Pred, Proj1, Proj2>
    constexpr bool operator()(R1&& r1, R2&& r2, Pred pred = {},
                              Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return ranges::empty(r2) ||
                   !ranges::search(r1, r2, pred, proj1, proj2).empty();
    }
};

inline constexpr contains_subrange_fn contains_subrange{};

Example

#include <algorithm>
#include <array>
#include <complex>

namespace ranges = std::ranges;

int main()
{
    constexpr auto haystack = std::array{3, 1, 4, 1, 5};
    constexpr auto needle = std::array{1, 4, 1};
    constexpr auto bodkin = std::array{2, 5, 2};
    
    static_assert
    (
        ranges::contains(haystack, 4) &&
       !ranges::contains(haystack, 6) &&
        ranges::contains_subrange(haystack, needle) &&
       !ranges::contains_subrange(haystack, bodkin)
    );
    
    constexpr std::array<std::complex<double>, 3> nums{{{1, 2}, {3, 4}, {5, 6}}};
    #ifdef __cpp_lib_algorithm_default_value_type
        static_assert(ranges::contains(nums, {3, 4}));
    #else
        static_assert(ranges::contains(nums, std::complex<double>{3, 4}));
    #endif
}

See also