std::ranges::search

来自cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
算法库
受约束算法及范围上的算法 (C++20)
受约束算法: std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
Partitioning operations
划分操作
排序操作
(C++11)
二分搜索操作
集合操作(在已排序范围上)
堆操作
(C++11)
最小/最大操作
(C++11)
(C++17)

排列
数值运算
未初始化存储上的操作
(C++17)
(C++17)
(C++17)
C 库
 
受约束算法
不修改序列的操作
修改序列的操作
划分操作
排序操作
二分搜索操作
集合操作(在已排序范围上)
堆操作
最小/最大操作
排列
未初始化存储上的操作
返回类型
 
在标头 <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 起)
1) 在范围 [first1, last1) 中搜索元素序列 [first2, last2)首次出现。在分别用 proj1proj2 投影后用二元谓词 pred 比较元素。
2)(1) ,但以 r1 为第一范围并以 r2 为第二范围,如同以 ranges::begin(r1)first1 ,以 ranges::end(r1)last1 ,以 ranges::begin(r2)first2 ,并以 ranges::end(r2)last2

此页面上描述的仿函数实体是 niebloid,即:

实际上,它们能以函数对象,或者某些特殊编译器扩展实现。

参数

first1, last1 - 要检验的元素范围(又称草堆
first2, last2 - 要搜索的元素范围(又称
r1 - 要检验的元素范围(又称草堆
r2 - 要搜索的元素范围(又称
pred - 应用到投影后元素的谓词
proj1 - 应用到第一范围中元素的投影
proj2 - 应用到第二范围中元素的投影

返回值

1) 返回作为序列 [first2, last2) (又称),在分别应用 proj1proj2 到两个序列的元素,再应用二元谓词 pred 比较投影后元素之后,于范围 [first1, last1) (又称草堆)中首次出现的 ranges::subrange 值。

若找不到这种序列,则返回 ranges::subrange{last1, last1}

若待搜索范围(又称)为空,即 first2 == last2 ,则返回 ranges::subrange{first1, first1}
2)(1) ,但返回类型为 ranges::borrowed_subrange_t<R1>

复杂度

至多应用 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);
 
    // ‘针’范围为空:
    constexpr auto none {""sv};
    constexpr auto found3 = std::ranges::search(haystack, none);
    print(3, haystack, none, found3);
 
    // 不会找到‘针’范围:
    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}

参阅

查找首对相邻的相同(或满足给定谓词的)元素
(niebloid)
查找满足特定条件的的第一个元素
(niebloid)
查找特定范围中最后出现的元素序列
(niebloid)
查找元素集合中的任一元素
(niebloid)
若一个序列是另一个的子列则返回 true
(niebloid)
寻找两个范围出现不同的首个位置
(niebloid)
在范围中搜索一定量的某个元素的连续副本
(niebloid)
搜索一个元素范围
(函数模板)