Namespaces
Variants

std::ranges::search

来自 zh.cppreference.net
 
 
算法库
受约束算法和范围算法 (C++20)
受约束算法,例如 ranges::copy, ranges::sort, ...
排序和相关操作
划分操作
(C++11)    

排序操作
二分搜索操作
(在已划分的范围上)
集合操作(在已排序范围上)
合并操作(在已排序范围上)
堆操作
最小/最大操作
(C++11)
(C++17)
字典序比较操作
排列操作


 
受约束算法
此菜单中的所有名称都属于命名空间 std::ranges
非修改序列操作
修改序列操作
划分操作
排序操作
二分搜索操作(在已排序范围上)
       
       
集合操作(在已排序范围上)
堆操作
最小/最大操作
       
       
排列操作
折叠操作
数值操作
(C++23)            
未初始化存储上的操作
返回类型
 
定义于头文件 <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) 搜索首次出现元素序列[first2, last2)在范围[first1, last1)中。元素通过二元谓词pred在分别用proj2和proj1投影后进行比较。
2) 同(1),但使用r1作为第一源范围,r2作为第二源范围,如同使用ranges::begin(r1)作为first1,ranges::end(r1)作为last1,ranges::begin(r2)作为first2,ranges::end(r2)作为last2。

此页面上描述的函数式实体是 算法函数对象(非正式地称为 niebloids),即:

参数

first1, last1 - 定义待检查元素范围的迭代器-哨位对(称为 haystack )
first2, last2 - 定义待查找元素范围的迭代器-哨位对(称为 needle )
r1 - 待检查的元素范围(称为 haystack )
r2 - 待查找的元素范围(称为 needle )
pred - 应用于投影元素的二元谓词
proj1 - 应用于第一个范围元素的投影
proj2 - 应用于第二个范围元素的投影

返回值

1) 返回一个 ranges:: subrange 值,表示序列 [ first2 , last2 ) (称为 needle )在范围 [ first1 , last1 ) (称为 haystack )中的首次出现位置,其中已分别对两个序列的元素应用投影 proj1 和 proj2 ,并随后应用二元谓词 pred 来比较投影后的元素。

如果未找到该序列,则返回 ranges:: subrange { last1, last1 } 。

如果要搜索的范围(称为 needle )为空,即 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);
    // 'needle' 范围为空:
    constexpr auto none {""sv};
    constexpr auto found3 = std::ranges::search(haystack, none);
    print(3, haystack, none, found3);
    // 'needle' 将不会被找到:
    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}

参见

查找首对相邻的相等(或满足给定谓词)的元素
(算法函数对象)
查找满足特定条件的首个元素
(算法函数对象)
查找特定范围内元素的最后一个序列
(算法函数对象)
搜索元素集合中的任意一个元素
(算法函数对象)
检查范围是否包含给定元素或子范围
(算法函数对象)
确定一个序列是否为另一个序列的子序列
(算法函数对象)
查找两个范围第一个出现差异的位置
(算法函数对象)
搜索范围内元素连续出现指定次数的首次出现
(算法函数对象)
搜索元素集合的首次出现
(函数模板)