std::search() 算法

自 C++20 起

// (1)
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last );

// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last,
                   BinaryPredicate p );

// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy,
                   ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last );

// (4)
template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy,
                   ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last,
                   BinaryPredicate p );

// (5)
template< class ForwardIt, class Searcher >
constexpr ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );

自 C++17 起

// (1)
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last );

// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last,
                   BinaryPredicate p );

// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy,
                   ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last );

// (4)
template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy,
                   ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last,
                   BinaryPredicate p );

// (5)
template< class ForwardIt, class Searcher >
ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );

C++17 之前

// (1)
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last );

// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last,
                   BinaryPredicate p );

在一个范围内搜索另一个范围内的元素第一次出现的位置。

• (1 - 4) 在范围 [first; last) 中搜索元素序列 [s_first; s_last) 的第一次出现。

  • (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 时才参与重载决议。

• (5) 在序列 [first; last) 中搜索 searcher 构造函数中指定的模式。实际执行 return searcher(first, last).first;。

  重要

  搜索器不能是 可复制构造的（CopyConstructible）。

  标准库提供以下搜索器

  自 C++17 起

  default_searcher	标准 C++ 库搜索算法实现。
  boyer_moore_searcher	Boyer-Moore 搜索算法实现。
  boyer_moore_horspool_searcher	Boyer-Moore-Horspool 搜索算法实现。

参数

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

类型要求

ForwardIt1 ForwardIt2	LegacyForwardIterator
Searcher	Searcher

返回值

• (1 - 4) 序列 [s_first; s_last) 在范围 [first; last) 中第一次出现的起始迭代器。 如果 [s_first; s_last) 为空，或者没有找到这样的序列，则返回 last。 (C++11 起)

  
  如果未找到此类序列，则返回 last。 (直到 C++11)

• (5) 返回搜索器的 operator() 的结果，即指向找到子字符串位置的迭代器，如果未找到则返回 last 的副本。

复杂度

(1 - 4) 给定 S 为 std::distance(s_first, s_last)，N 为 std::distance(first, last)：最多 S * N 次比较。

(5) 取决于搜索器。标准搜索器没有保证的复杂度。

异常

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

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

可能的实现

search (1)

template<class ForwardIt1, class ForwardIt2>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last)
{
    while (true)
    {
        ForwardIt1 it = first;
        for (ForwardIt2 s_it = s_first; ; ++it, ++s_it)
        {
            if (s_it == s_last)
                return first;
            if (it == last)
                return last;
            if (!(*it == *s_it))
                break;
        }
        ++first;
    }
}

search (2)

template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last,
                            BinaryPredicate p)
{
    while (true)
    {
        ForwardIt1 it = first;
        for (ForwardIt2 s_it = s_first; ; ++it, ++s_it)
        {
            if (s_it == s_last)
                return first;
            if (it == last)
                return last;
            if (!p(*it, *s_it))
                break;
        }
        ++first;
    }
}

示例

Main.cpp

#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <string_view>
#include <vector>
using namespace std::literals;

bool contains(const auto& cont, std::string_view s)
{
    // str.find() (or str.contains(), since C++23) can be used as well
    return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}

int main()
{
    const auto str {"why waste time learning, when ignorance is instantaneous?"sv};

    std::cout << std::boolalpha
              << contains(str, "learning") << '\n'   // true
              << contains(str, "lemming")  << '\n';  // false

    const std::vector vec(str.begin(), str.end());
    std::cout << contains(vec, "learning") << '\n'   // true
              << contains(vec, "leaning")  << '\n';  // false

    // The C++17 overload with searchers demo:
    constexpr auto haystack
    {
        "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
        "do eiusmod tempor incididunt ut labore et dolore magna aliqua"sv
    };

    for (const auto needle : {"pisci"sv, "Pisci"sv})
    {
        const std::boyer_moore_searcher searcher(needle.begin(), needle.end());
        const auto it = std::search(haystack.begin(), haystack.end(), searcher);
        std::cout << "The string " << std::quoted(needle) << ' ';
        if (it == haystack.end())
            std::cout << "not found\n";
        else
            std::cout << "found at offset " << it - haystack.begin() << '\n';
    }
}

输出

true
false
true
false
The string "pisci" found at offset 43
The string "Pisci" not found