std::search_n() 算法

自 C++20 起

// (1)
template< class ForwardIt, class Size, class T >
constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );

// (2)
template< class ForwardIt, class Size, class T, class BinaryPredicate >
constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p );

// (3)
template< class ExecutionPolicy, class ForwardIt, class Size, class T >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                    Size count, const T& value );

// (4)
template< class ExecutionPolicy, class ForwardIt,
          class Size, class T, class BinaryPredicate >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                    Size count, const T& value, BinaryPredicate p );

自 C++17 起

// (1)
template< class ForwardIt, class Size, class T >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );

// (2)
template< class ForwardIt, class Size, class T, class BinaryPredicate >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p );

// (3)
template< class ExecutionPolicy, class ForwardIt, class Size, class T >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                    Size count, const T& value );

// (4)
template< class ExecutionPolicy, class ForwardIt,
          class Size, class T, class BinaryPredicate >
ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                    Size count, const T& value, BinaryPredicate p );

C++17 之前

// (1)
template< class ForwardIt, class Size, class T >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );

// (2)
template< class ForwardIt, class Size, class T, class BinaryPredicate >
ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p );

在给定范围内搜索第一个由 count 个相同元素组成的序列，每个元素都等于给定的 value。

• (1) 元素使用 operator== 进行比较。

• (2) 元素使用给定的二元谓词 p 进行比较。

• (3 - 4) 与 (1 - 2) 相同，但根据 policy 执行。

  重载决议

  这些重载仅在 std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>  (直到 C++20) std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>  (从 C++20 开始) 为 true 时参与重载决议。

参数

first last	要检查的元素范围。
s_first s_last	要搜索的元素范围。
policy	要使用的执行策略。有关详细信息，请参阅执行策略。
searcher	封装搜索算法和要查找模式的搜索器。
p	二元谓词，如果元素应被视为相等，则返回 true。 函数的签名应与以下内容等效 bool fun(const Type1& a, const Type2& b); 签名不需要包含 const&。 函数不得修改传递给它的对象。 必须接受所有类型（可能是 const）Type1 和 Type2 的值，无论值类别如何（因此不允许 Type1&，也不允许 Type1，除非对于 Type1 移动等同于复制 (从 C++11 开始)） 类型 Type1 必须是这样，即类型为 ForwardIt 的对象可以被解引用，然后隐式转换为它们。 类型 Type2 必须是这样，即类型为 T 的对象可以被隐式转换为它们。

类型要求

ForwardIt	LegacyForwardIterator
Size	必须能够隐式转换为整型。

返回值

如果 count 为正，则返回指向范围 [first; last) 中找到的第一个序列开头的迭代器。

序列中的每个迭代器都应满足以下条件

• (1, 3) *it == value
• (2, 4) p(*it, value)

如果未找到此类序列，则返回 last。
如果 count 为零或负数，则返回 first。

复杂度

给定 N 为 std::distance(first, last)

• (1, 3) 最多使用 operator== 与 value 进行 N 次比较。
• (2, 4) 最多应用谓词 p N 次。

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

• 如果作为算法一部分调用的函数执行时抛出异常且 ExecutionPolicy 是标准策略之一，则调用 std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
• 如果算法未能分配内存，则抛出 std::bad_alloc。

可能的实现

search_n (1)

template<class ForwardIt, class Size, class T>
ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value)
{
    if (count <= 0)
        return first;

    for (; first != last; ++first)
    {
        if (!(*first == value))
            continue;

        ForwardIt candidate = first;

        for (Size cur_count = 1; true; ++cur_count)
        {
            if (cur_count >= count)
                return candidate; // success

            ++first;
            if (first == last)
                return last; // exhausted the list

            if (!(*first == value))
                break; // too few in a row
        }
    }
    return last;
}

search_n (2)

template<class ForwardIt, class Size, class T, class BinaryPredicate>
ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value,
                   BinaryPredicate p)
{
    if (count <= 0)
        return first;

    for (; first != last; ++first)
    {
        if (!p(*first, value))
            continue;

        ForwardIt candidate = first;

        for (Size cur_count = 1; true; ++cur_count)
        {
            if (cur_count >= count)
                return candidate; // success

            ++first;
            if (first == last)
                return last; // exhausted the list

            if (!p(*first, value))
                break; // too few in a row
        }
    }
    return last;
}

示例

Main.cpp

#include <algorithm>
#include <iostream>
#include <iterator>

template<class Container, class Size, class T>
[[nodiscard]]
constexpr bool consecutive_values(const Container& c, Size count, const T& v)
{
    return std::search_n(std::begin(c), std::end(c), count, v) != std::end(c);
}

int main()
{
    constexpr char sequence[] = "1001010100010101001010101";

    static_assert(consecutive_values(sequence, 3, '0'));

    std::cout << std::boolalpha
              << "Has 4 consecutive zeros: "
              << consecutive_values(sequence, 4, '0') << '\n'
              << "Has 3 consecutive zeros: "
              << consecutive_values(sequence, 3, '0') << '\n';
}

输出

Has 4 consecutive zeros: false
Has 3 consecutive zeros: true