std::ranges::search
| Определено в заголовке <algorithm>
|
||
| Сигнатура вызова |
||
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 ranges::subrange<I1>
search( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(1) | (начиная с C++20) |
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 ranges::borrowed_subrange_t<R1>
search( R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(2) | (начиная с C++20) |
[first2, last2) в диапазоне [first1, last1). Элементы сравниваются с помощью бинарного предиката pred после проекции с помощью proj2 и proj1 соответственно.r1 как первый исходный диапазон и r2 как второй исходный диапазон, как если бы использовались ranges::begin(r1) как first1, ranges::end(r1) как last1, ranges::begin(r2) как first2 и ranges::end(r2) как last2.Сущности, подобные функциям, описанные на этой странице, являются объектами функций алгоритмов (неформально известными как niebloids), то есть:
- Явные списки аргументов шаблона не могут быть указаны при вызове любой из них.
- Ни одна из них не видна при поиске, зависящем от аргументов.
- Когда любая из них найдена с помощью обычного неквалифицированного поиска как имя слева от оператора вызова функции, поиск, зависящий от аргументов, запрещён.
Параметры
| first1, last1 | - | пара итератор-страж, определяющая диапазон элементов для проверки (также называемый haystack ) |
| first2, last2 | - | пара итератор-страж, определяющая диапазон элементов для поиска (также называемый needle ) |
| r1 | - | диапазон элементов для проверки (также называемый haystack ) |
| r2 | - | диапазон элементов для поиска (также называемый needle ) |
| pred | - | бинарный предикат, применяемый к проецируемым элементам |
| proj1 | - | проекция, применяемая к элементам первого диапазона |
| proj2 | - | проекция, применяемая к элементам второго диапазона |
Возвращаемое значение
[
first2
,
last2
)
(также называемой
needle
) в диапазоне
[
first1
,
last1
)
(также называемом
haystack
), после применения проекций
proj1
и
proj2
к элементам обеих последовательностей соответственно с последующим применением бинарного предиката
pred
для сравнения спроецированных элементов.
Если такое вхождение не найдено, возвращается ranges:: subrange { last1, last1 } .
Если диапазон для поиска (также называемый needle ) пуст, то есть first2 == last2 , тогда возвращается ranges:: subrange { first1, first1 } .Сложность
Максимум
S * N
применений соответствующего предиката и каждой проекции, где
(1)
S
=
ranges::
distance
(
first2, last2
)
и
N
=
ranges::
distance
(
first1, last1
)
;
(2)
S
=
ranges::
distance
(
r2
)
и
N
=
ranges::
distance
(
r1
)
.
Возможная реализация
struct search_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 ranges::subrange<I1> operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { for (;; ++first1) { I1 it1 = first1; for (I2 it2 = first2;; ++it1, ++it2) { if (it2 == last2) return {first1, it1}; if (it1 == last1) return {it1, it1}; if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2))) break; } } } 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 ranges::borrowed_subrange_t<R1> operator()(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { return (*this)(ranges::begin(r1), ranges::end(r1), ranges::begin(r2), ranges::end(r2), std::move(pred), std::move(proj1), std::move(proj2)); } }; inline constexpr search_fn search {}; |
Пример
#include <algorithm> #include <cctype> #include <iostream> #include <iterator> #include <string_view> using namespace std::literals; void print(int id, const auto& haystack, const auto& needle, const auto& found) { std::cout << id << ") search(\"" << haystack << "\", \"" << needle << "\"); "; const auto first = std::distance(haystack.begin(), found.begin()); const auto last = std::distance(haystack.begin(), found.end()); if (found.empty()) std::cout << "not found;"; else { std::cout << "found: \""; for (const auto x : found) std::cout << x; std::cout << "\";"; } std::cout << " subrange: {" << first << ", " << last << "}\n"; } int main() { constexpr auto haystack {"abcd abcd"sv}; constexpr auto needle {"bcd"sv}; // поиск использует пары итераторов begin()/end(): constexpr auto found1 = std::ranges::search( haystack.begin(), haystack.end(), needle.begin(), needle.end()); print(1, haystack, needle, found1); // поиск использует диапазоны r1, r2: constexpr auto found2 = std::ranges::search(haystack, needle); print(2, haystack, needle, found2); // диапазон 'needle' пуст: constexpr auto none {""sv}; constexpr auto found3 = std::ranges::search(haystack, none); print(3, haystack, none, found3); // 'needle' не будет найден: constexpr auto awl {"efg"sv}; constexpr auto found4 = std::ranges::search(haystack, awl); print(4, haystack, awl, found4); // поиск использует пользовательский компаратор и проекции: constexpr auto bodkin {"234"sv}; auto found5 = std::ranges::search(haystack, bodkin, [](const int x, const int y) { return x == y; }, // pred [](const int x) { return std::toupper(x); }, // proj1 [](const int y) { return y + 'A' - '1'; }); // proj2 print(5, haystack, bodkin, found5); }
Вывод:
1) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
2) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
3) search("abcd abcd", ""); not found; subrange: {0, 0}
4) search("abcd abcd", "efg"); not found; subrange: {9, 9}
5) search("abcd abcd", "234"); found: "bcd"; subrange: {1, 4}
См. также
(C++20) |
находит первые два смежных элемента, которые равны (или удовлетворяют заданному предикату) (объект-функция алгоритма) |
(C++20)(C++20)(C++20) |
находит первый элемент, удовлетворяющий определённым критериям (объект-функция алгоритма) |
(C++20) |
находит последнюю последовательность элементов в заданном диапазоне (объект-функция алгоритма) |
(C++20) |
ищет любой из набора элементов (объект-функция алгоритма) |
(C++23)(C++23) |
проверяет, содержит ли диапазон заданный элемент или поддиапазон (объект-функция алгоритма) |
(C++20) |
определяет, является ли одна последовательность подпоследовательностью другой (объект-функция алгоритма) |
(C++20) |
находит первую позицию, где два диапазона различаются (объект-функция алгоритма) |
(C++20) |
ищет первое вхождение нескольких последовательных копий элемента в диапазоне (объект-функция алгоритма) |
| ищет первое вхождение диапазона элементов (шаблон функции) |