std::ranges:: search_n

From cppreference.net

定义于头文件 `<algorithm>`
调用签名
	(1)
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 = { } ) ;			(C++20 起) (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 = { } ) ;			(C++26 起)
		(2)
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 = { } ) ;				(C++20 起) (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 = { } ) ;				(C++26 起)

1) 在范围

first

last

中搜索首个由 count 个元素组成的序列，这些元素的投影值均根据二元谓词 pred 与给定 value 相等。

2) 与 (1) 相同，但使用 r 作为源范围，如同使用 ranges:: begin ( r ) 作为 first ，以及 ranges:: end ( r ) 作为 last 。

本页面描述的函数式实体是 算法函数对象 （非正式称为 niebloids ），即：

在调用其中任何一个时，都不能指定显式模板实参列表。
它们对实参依赖查找均不可见。
当通过常规非限定查找将其中任何一个作为函数调用运算符左侧的名称找到时，会抑制实参依赖查找。

first, last	-	定义待检查元素范围的迭代器-哨位对（即 haystack ）
r	-	待检查的元素范围（即 haystack ）
count	-	要搜索的序列长度
value	-	要搜索的值（即 needle ）
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 要求，实现可 在平均情况下 提升搜索效率。

功能测试宏	值	标准	功能
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	算法的列表初始化

可能的实现

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)}; // 找到匹配序列
                    if (++first == last)
                        return {first, first}; // 未找到匹配序列
                    if (!std::invoke(pred, std::invoke(proj, *first), value))
                        break; // 当前元素不等于目标值
                }
            }
        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::end(r),
                       std::move(count), value,
                       std::move(pred), std::move(proj));
    }
};
inline constexpr search_n_fn search_n {};

示例

运行此代码

#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 // 找到
    (
        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 // 找到
    (
        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 // 未找到
    (
        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 // 未找到
    (
        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 << "在序列中查找子序列 " << std::string(count, symbol) << "：";
    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 << "在位置 "
                  << ranges::distance(nums.begin(), result5.begin()) << " 处找到\n";
    std::vector<std::complex<double>> nums2{{4, 2}, {4, 2}, {1, 3}};</

参见

ranges::adjacent_find (C++20)	查找首个相邻的相等元素（或满足给定谓词的元素对） (算法函数对象)
ranges::find ranges::find_if ranges::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	在范围内搜索首个连续出现指定次数的元素序列 (函数模板)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std::ranges:: search_n

目录

参数

返回值

复杂度

注释

可能的实现

示例

参见