std::ranges::search() 算法

自 C++20 起

简化

// (1)
constexpr ranges::subrange<I1>
    search( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

// (2)
constexpr ranges::borrowed_subrange_t<R1>
    search( R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

参数类型是泛型的，并具有以下约束

• I1, I2 - std::forward_iterator
• S1, S2 - std::sentinel_for<I1>, std::sentinel_for<I2>
• Pred - (无)
• Proj1, Proj2 - (无)
• (2) - R1, R2 - std::ranges::forward_range

Proj1 和 Proj2 模板参数对于所有重载都具有默认类型 std::identity。

此外，每个重载都有以下约束

• (1) - indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
• (2) - indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2>

（为方便阅读，此处省略了 std:: 命名空间）

详细

// (1)
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 = {} );

// (2)
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 = {} );

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

• (1) 在范围 [first1; last1) 中搜索元素序列 [first2; last2) 的第一次出现。元素在使用 proj2 和 proj1 分别进行投影后，使用二元谓词 pred 进行比较。

• (2) 与 (1) 相同，但使用 r1 作为第一个源范围，r2 作为第二个源范围，如同使用 ranges::begin(r1) 作为 first1，ranges::end(r1) 作为 last1，ranges::begin(r2) 作为 first2，以及 ranges::end(r2) 作为 last2。

本页描述的函数类实体是niebloids。

参数

first1 last1	要检查的元素范围。
first2 last2	要搜索的元素范围。
r1	要检查的元素范围。
r2	要搜索的元素范围。
pred	用于比较元素的二元谓词。
proj1	应用于第一个范围中元素的投影。
proj2	应用于第二个范围中元素的投影。

返回值

• (1) 类型为 ranges::subrange<I1> 的值，初始化如下

  {
    i,
    i + (i == last1 ? 0 : ranges::distance(first2, last2))
  }

  表示序列 [first2; last2) (又名“针”) 在范围 [first1; last1) (又名“草堆”) 中（在用 proj1 和 proj2 投影并随后用二元谓词 pred 比较之后）的第一次出现。

  如果 [first2; last2) 为空，或者没有找到这样的序列，则返回值实际上初始化为 { last1, last1 }。

• (2) 与 (1) 相同，只是返回类型为 ranges::borrowed_subrange_t<R1>。

复杂度

• (1) 给定 S 为 ranges::distance(first2, last2)，N 为 ranges::distance(first1, last1)
• (2) 给定 S 为 ranges::distance(r2)，N 为 ranges::distance(r1)

最多 S * N 次谓词和每次投影的应用。

异常

(无)

可能的实现

search(1)

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 {};

示例

Main.cpp

#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};

    // the search uses iterator pairs begin()/end():
    constexpr auto found1 = std::ranges::search(
        haystack.begin(), haystack.end(),
        needle.begin(), needle.end());
    print(1, haystack, needle, found1);

    // the search uses ranges r1, r2:
    constexpr auto found2 = std::ranges::search(haystack, needle);
    print(2, haystack, needle, found2);

    // 'needle' range is empty:
    constexpr auto none {""sv};
    constexpr auto found3 = std::ranges::search(haystack, none);
    print(3, haystack, none, found3);

    // 'needle' will not be found:
    constexpr auto awl {"efg"sv};
    constexpr auto found4 = std::ranges::search(haystack, awl);
    print(4, haystack, awl, found4);

    // the search uses custom comparator and projections:
    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}