std::ranges::search_n

Defined in header <algorithm>

Call signature

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)
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)

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)

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)

1) Ищет в диапазоне [first, last) первую последовательность из count элементов, проекции которых равны заданному значению value согласно бинарному предикату pred.

2) То же, что и (1), но использует r в качестве исходного диапазона, как если бы ranges::begin(r) использовалось в качестве first, а ranges::end(r) в качестве last.

Функциональные сущности, описанные на этой странице, являются ниблеоидами, то есть:

Явные списки аргументов шаблона не могут быть указаны при вызове ни одной из них.
Ни одна из них не видна для поиска зависимого от аргументов.
Когда любая из них найдена обычным поиском без квалификатора в качестве имени слева от оператора вызова функции, поиск зависимый от аргументов подавляется.

На практике они могут быть реализованы как объекты функций или с помощью специальных расширений компилятора.

Параметры

first, last	-	диапазон элементов для проверки (также известный как исходный диапазон)
r	-	диапазон элементов для проверки (также известный как исходный диапазон)
count	-	длина последовательности для поиска
value	-	значение для поиска (также известный как искомый элемент)
pred	-	бинарный предикат, сравнивающий спроецированные элементы с `value`
proj	-	проекция, применяемая к элементам диапазона для проверки

Возвращаемое значение

1) Возвращает объект std::ranges::subrange, содержащий пару итераторов в диапазоне [first, last), указывающих на найденную подпоследовательность.

Если такая подпоследовательность не найдена, возвращает std::ranges::subrange{last, last}. Если count <= 0, возвращает std::ranges::subrange{first, first}.

2) То же, что и (1), но тип возвращаемого значения — ranges::borrowed_subrange_t<R>.

Сложность

Линейная: не более ranges::distance(first, last) применений предиката и проекции.

Примечания

Реализация может улучшить эффективность поиска в среднем, если итераторы моделируют std::random_access_iterator.

Возможная реализация

struct search_n_fn
{
    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>
        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 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>
        operator()(R&& r, ranges::range_difference_t<R> count,
                   const T& value, Pred pred = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       std::move(count), value,
                       std::move(pred), std::move(proj));
    }
};
 
inline constexpr search_n_fn search_n {};

Пример

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string>
 
int main()
{
    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 = std::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 = std::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 = std::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 = std::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 = std::ranges::search_n(nums, count, symbol, is_equ, to_ascii);
    if (not result5.empty())
        std::cout << "Found at position "
                  << std::ranges::distance(nums.begin(), result5.begin()) << '\n';
}

Вывод:

Find a sub-sequence BBB in the ABBCDABBBA
Found at position 6

См. также

ranges::adjacent_find (C++20)	находит первые два смежных элемента, которые равны (или удовлетворяют заданному предикату) (ниблеоид)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)	находит первый элемент, удовлетворяющий определенным критериям (ниблеоид)
ranges::find_end (C++20)	находит последнюю последовательность элементов в определенном диапазоне (ниблеоид)
ranges::find_first_of (C++20)	ищет любой из набора элементов (ниблеоид)
ranges::includes (C++20)	возвращает `true`, если одна последовательность является подпоследовательностью другой (ниблеоид)
ranges::mismatch (C++20)	находит первую позицию, где два диапазона различаются (ниблеоид)
ranges::search (C++20)	ищет диапазон элементов (ниблеоид)
search_n	ищет в диапазоне заданное количество последовательных копий элемента (шаблон функции)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/search_n