std::ranges::search_n
From cppreference.com
| Defined in header <algorithm>
|
||
| Call signature |
||
template< std::forward_iterator I, std::sentinel_for<I> S, class T,
class Pred = ranges::equal_to, class Proj = std::identity >
requires std::indirectly_comparable<I, const T*, Pred, Proj>
constexpr ranges::subrange<I>
search_n( I first, S last, std::iter_difference_t<I> count,
const T& value, Pred pred = {}, Proj proj = {} );
|
(1) | (since C++20) (until C++26) |
template< std::forward_iterator I, std::sentinel_for<I> S,
class Pred = ranges::equal_to, class Proj = std::identity,
class T = std::projected_value_t<I, Proj> >
requires std::indirectly_comparable<I, const T*, Pred, Proj>
constexpr ranges::subrange<I>
search_n( I first, S last, std::iter_difference_t<I> count,
const T& value, Pred pred = {}, Proj proj = {} );
|
(since C++26) | |
template< ranges::forward_range R, class T,
class Pred = ranges::equal_to, class Proj = std::identity >
requires std::indirectly_comparable
<ranges::iterator_t<R>, const T*, Pred, Proj>
constexpr ranges::borrowed_subrange_t<R>
search_n( R&& r, ranges::range_difference_t<R> count,
const T& value, Pred pred = {}, Proj proj = {} );
|
(2) | (since C++20) (until C++26) |
template< ranges::forward_range R,
class Pred = ranges::equal_to, class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj> >
requires std::indirectly_comparable
<ranges::iterator_t<R>, const T*, Pred, Proj>
constexpr ranges::borrowed_subrange_t<R>
search_n( R&& r, ranges::range_difference_t<R> count,
const T& value, Pred pred = {}, Proj proj = {} );
|
(since C++26) | |
template< /*execution-policy*/ Ep,
std::random_access_iterator I, std::sized_sentinel_for<I> S,
class Pred = ranges::equal_to, class Proj = std::identity,
class T = std::projected_value_t<I, Proj> >
requires std::indirectly_comparable<I, const T*, Pred, Proj>
ranges::subrange<I>
search_n( Ep&& policy, I first, S last, std::iter_difference_t<I> count,
const T& value, Pred pred = {}, Proj proj = {} );
|
(3) | (since C++26) |
template< /*execution-policy*/ Ep, ranges::forward_range R,
class Pred = ranges::equal_to, class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj> >
requires std::indirectly_comparable
<ranges::iterator_t<R>, const T*, Pred, Proj>
ranges::borrowed_subrange_t<R>
search_n( Ep&& policy, R&& r, ranges::range_difference_t<R> count,
const T& value, Pred pred = {}, Proj proj = {} );
|
(4) | (since C++26) |
For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.
Searches the source range for the first occurrence of count consecutive elements (projected by proj) equal to value, according to the binary predicate pred.
1) The source range is
[first, last).2) The source range is
r.3,4) Same as (1,2), but executed according to
policy.The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:
- Explicit template argument lists cannot be specified when calling any of them.
- None of them are visible to argument-dependent lookup.
- When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.
Parameters
| first, last | - | the iterator-sentinel pair defining the source range |
| r | - | the source range |
| count | - | the number of consecutive elements to search for |
| value | - | the value to search for |
| pred | - | the predicate to be applied to the (projected) elements and value
|
| proj | - | the projection to be applied to the elements |
| policy | - | the execution policy to use |
Return value
If count is positive, returns a subrange corresponding to the first occurrence in the source range.
If count is non-positive or there is no such occurrence in the source range, returns an empty subrange.
Complexity
Given N as ranges::distance(first, last) or ranges::distance(r):
1,2) Exactly N applications of
pred and proj.3,4) 𝓞(N) applications of
pred and proj.Exceptions
3,4) 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
An implementation can improve efficiency of the search in average if the iterators model random_access_iterator.
| Feature-test macro | Value | Std | Feature |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type |
202403 |
(C++26) | List-initialization for algorithms |
Possible implementation
struct search_n_fn
{
template<std::forward_iterator I, std::sentinel_for<I> S,
class Pred = ranges::equal_to, class Proj = std::identity,
class T = std::projected_value_t<I, Proj>>
requires std::indirectly_comparable<I, const T*, Pred, Proj>
constexpr ranges::subrange<I>
operator()(I first, S last, std::iter_difference_t<I> count,
const T& value, Pred pred = {}, Proj proj = {}) const
{
if (count <= 0)
return {first, first};
for (; first != last; ++first)
if (std::invoke(pred, std::invoke(proj, *first), value))
{
I start = first;
std::iter_difference_t<I> n{1};
for (;;)
{
if (n++ == count)
return {start, std::next(first)}; // found
if (++first == last)
return {first, first}; // not found
if (!std::invoke(pred, std::invoke(proj, *first), value))
break; // not equ to value
}
}
return {first, first};
}
template<ranges::forward_range R,
class Pred = ranges::equal_to, class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj>>
requires std::indirectly_comparable<ranges::iterator_t<R>, const T*, Pred, Proj>
constexpr ranges::borrowed_subrange_t<R>
operator()(R&& r, ranges::range_difference_t<R> count,
const T& value, Pred pred = {}, Proj proj = {}) const
{
return (*this)(ranges::begin(r), ranges::next(ranges::begin(r), ranges::end(r)),
std::move(count), value,
std::move(pred), std::move(proj));
}
};
inline constexpr search_n_fn search_n{};
|
Example
Run this code
#include <algorithm>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
int main()
{
namespace ranges = std::ranges;
static constexpr auto nums = {1, 2, 2, 3, 4, 1, 2, 2, 2, 1};
constexpr int count{3};
constexpr int value{2};
typedef int count_t, value_t;
constexpr auto result1 = ranges::search_n
(
nums.begin(), nums.end(), count, value
);
static_assert // found
(
result1.size() == count &&
std::distance(nums.begin(), result1.begin()) == 6 &&
std::distance(nums.begin(), result1.end()) == 9
);
constexpr auto result2 = ranges::search_n(nums, count, value);
static_assert // found
(
result2.size() == count &&
std::distance(nums.begin(), result2.begin()) == 6 &&
std::distance(nums.begin(), result2.end()) == 9
);
constexpr auto result3 = ranges::search_n(nums, count, value_t{5});
static_assert // not found
(
result3.size() == 0 &&
result3.begin() == result3.end() &&
result3.end() == nums.end()
);
constexpr auto result4 = ranges::search_n(nums, count_t{0}, value_t{1});
static_assert // not found
(
result4.size() == 0 &&
result4.begin() == result4.end() &&
result4.end() == nums.begin()
);
constexpr char symbol{'B'};
auto to_ascii = [](const int z) -> char { return 'A' + z - 1; };
auto is_equ = [](const char x, const char y) { return x == y; };
std::cout << "Find a sub-sequence " << std::string(count, symbol) << " in the ";
std::ranges::transform(nums, std::ostream_iterator<char>(std::cout, ""), to_ascii);
std::cout << '\n';
auto result5 = ranges::search_n(nums, count, symbol, is_equ, to_ascii);
if (not result5.empty())
std::cout << "Found at position "
<< ranges::distance(nums.begin(), result5.begin()) << '\n';
std::vector<std::complex<double>> nums2{{4, 2}, {4, 2}, {1, 3}};
#ifdef __cpp_lib_algorithm_default_value_type
auto it = ranges::search_n(nums2, 2, {4, 2});
#else
auto it = ranges::search_n(nums2, 2, std::complex<double>{4, 2});
#endif
assert(it.size() == 2);
}
Output:
Find a sub-sequence BBB in the ABBCDABBBA
Found at position 6
See also
| searches for the first occurrence of a number consecutive copies of an element in a range (function template) | |
(C++20) |
searches for the first occurrence of a range of elements (algorithm function object) |
(C++20) |
finds the first two adjacent items that are equal (or satisfy a given predicate) (algorithm function object) |
(C++20)(C++20)(C++20) |
finds the first element satisfying specific criteria (algorithm function object) |
(C++20) |
finds the last sequence of elements in a certain range (algorithm function object) |
(C++20) |
searches for any one of a set of elements (algorithm function object) |
(C++20) |
determines if one sequence is a subsequence of another (algorithm function object) |
(C++20) |
finds the first position where two ranges differ (algorithm function object) |