std::boyer_moore_searcher

 

C++

編譯器支援

自由（freestanding）與宿主（hosted）

語言

標準庫

標準庫標頭檔案

具名要求

特性測試宏 (C++20)

語言支援庫

概念庫 (C++20)

診斷庫

記憶體管理庫

超程式設計庫 (C++11)

通用工具庫

容器庫

迭代器庫

範圍庫 (C++20)

演算法庫

字串庫

文字處理庫

數值庫

日期和時間庫

輸入/輸出庫

檔案系統庫 (C++17)

併發支援庫 (C++11)

執行控制庫 (C++26)

技術規範

符號索引

外部庫

 

工具庫

語言支援 型別支援（基本型別、RTTI） 庫特性測試宏 (C++20) 程式工具 變參函式 initializer_list (C++11) is_constant_evaluated (C++20) is_within_lifetime (C++26) source_location (C++20) 協程支援 (C++20) 契約支援 (C++26) 三路比較 three_way_comparablethree_way_comparable_with (C++20)(C++20) strong_ordering (C++20) weak_ordering (C++20) partial_ordering (C++20) common_comparison_category (C++20) compare_three_way_result (C++20) compare_three_way (C++20) strong_order (C++20) weak_order (C++20) partial_order (C++20) compare_strong_order_fallback (C++20) compare_weak_order_fallback (C++20) compare_partial_order_fallback (C++20)   is_eqis_ltis_lteq (C++20)(C++20)(C++20)   is_neqis_gtis_gteq (C++20)(C++20)(C++20)

通用工具 函式物件 位操作 (C++20) bitset hash (C++11) 關係運算符 (C++20 中棄用) rel_ops::operator!=rel_ops::operator>    rel_ops::operator<=rel_ops::operator>= 整數比較函式 cmp_equalcmp_lesscmp_less_than (C++20)(C++20)(C++20)   cmp_not_equalcmp_greatercmp_greater_than (C++20)(C++20)(C++20) in_range (C++20) 交換與型別操作 swap ranges::swap (C++20) exchange (C++14) declval (C++11) to_underlying (C++23) forward (C++11) forward_like (C++23) move (C++11) move_if_noexcept (C++11) as_const (C++17) 常用詞彙型別 pair tuple (C++11) optional (C++17) any (C++17) variant (C++17) tuple_size (C++11) tuple_element (C++11) apply (C++17) make_from_tuple (C++17) expected (C++23)

 

函式物件

函式包裝器 function (C++11) move_only_function (C++23) copyable_function (C++26) function_ref (C++26) mem_fn (C++11) bad_function_call (C++11)	部分函式應用 bind_frontbind_back (C++20)(C++23) bind (C++11) is_bind_expression (C++11) is_placeholder (C++11) _1, _2, _3, ... (C++11)
函式呼叫 invokeinvoke_r (C++17)(C++23) 恆等函式物件 identity (C++20)	引用包裝器 reference_wrapper (C++11) refcref (C++11)(C++11) unwrap_referenceunwrap_ref_decay (C++20)(C++20)
運算子包裝器 plus minus negate multiplies divides modulus bit_and bit_or bit_not (C++14)   bit_xor equal_to not_equal_to greater less greater_equal less_equal logical_and logical_or logical_not	透明運算子包裝器 plus<> (C++14) minus<> (C++14) negate<> (C++14) multiplies<> (C++14)   divides<> (C++14) modulus<> (C++14) bit_and<> (C++14) bit_or<> (C++14) bit_not<> (C++14) bit_xor<> (C++14) equal_to<> (C++14) not_equal_to<> (C++14) greater<> (C++14) less<> (C++14) greater_equal<> (C++14) less_equal<> (C++14) logical_and<> (C++14) logical_or<> (C++14) logical_not<> (C++14)
否定器 not_fn (C++17) 搜尋器 default_searcher (C++17) boyer_moore_searcher (C++17) boyer_moore_horspool_searcher (C++17)	受限比較器 ranges::equal_to (C++20) ranges::not_equal_to (C++20) ranges::greater (C++20) ranges::less (C++20) ranges::greater_equal (C++20) ranges::less_equal (C++20) compare_three_way (C++20)
舊繫結器和介面卡
unary_function (直到 C++17*) binary_function (直到 C++17*) ptr_fun (直到 C++17*) pointer_to_unary_function (直到 C++17*) pointer_to_binary_function (直到 C++17*)   mem_fun (直到 C++17*) mem_fun_tmem_fun1_tconst_mem_fun_tconst_mem_fun1_t (until C++17*)(until C++17*)(until C++17*)(until C++17*) not1 (直到 C++20*) not2 (直到 C++20*)	binder1stbinder2nd (直到 C++17*)(直到 C++17*) bind1stbind2nd (直到 C++17*)(直到 C++17*) mem_fun_ref (直到 C++17*) mem_fun_ref_tmem_fun1_ref_tconst_mem_fun_ref_tconst_mem_fun1_ref_t (until C++17*)(until C++17*)(until C++17*)(until C++17*) unary_negate (直到 C++20*) binary_negate (直到 C++20*)

 

定義於標頭檔案 <functional>
template< class RandomIt1,           class Hash = std::hash<typename std::iterator_traits<RandomIt1>::value_type>,           class BinaryPredicate = std::equal_to<> > class boyer_moore_searcher;		(C++17 起)

一個搜尋器，適用於 std::search 的 Searcher 過載，實現了 Boyer-Moore 字串搜尋演算法。

std::boyer_moore_searcher 是 可複製構造的（CopyConstructible） 和 可複製賦值的（CopyAssignable）。

RandomIt1 必須滿足 LegacyRandomAccessIterator 的要求。

成員函式

std::boyer_moore_searcher::boyer_moore_searcher

boyer_moore_searcher( RandomIt1 pat_first,                       RandomIt1 pat_last,                       Hash hf = Hash(),                       BinaryPredicate pred = BinaryPredicate() );

透過儲存 pat_first、pat_last、hf 和 pred 的副本，並設定任何必要的內部資料結構，構造一個 std::boyer_moore_searcher。

RandomIt1 的值型別必須是 可預設構造的（DefaultConstructible）、可複製構造的（CopyConstructible） 和 可複製賦值的（CopyAssignable）。

對於型別 std::iterator_traits<RandomIt1>::value_type 的任意兩個值 A 和 B，如果 pred(A, B) == true，則 hf(A) == hf(B) 應當為 true。

引數

pat_first, pat_last	-	一對迭代器，指示要搜尋的字串
hf	-	一個可呼叫物件，用於對字串元素進行雜湊
pred	-	一個可呼叫物件，用於確定相等性

異常

由以下任一情況丟擲的任何異常：

• RandomIt1 的複製建構函式；
• RandomIt1 的值型別的預設建構函式、複製建構函式和複製賦值運算子；或
• BinaryPredicate 或 Hash 的複製建構函式和函式呼叫運算子。

如果無法為內部資料結構分配所需的額外記憶體，也可能丟擲 std::bad_alloc。

std::boyer_moore_searcher::operator()

template< class RandomIt2 > std::pair<RandomIt2, RandomIt2> operator()( RandomIt2 first, RandomIt2 last ) const;		(C++17 起)

由 std::search 的 Searcher 過載呼叫以使用此搜尋器執行搜尋的成員函式。RandomIt2 必須滿足 LegacyRandomAccessIterator 的要求。

RandomIt1 和 RandomIt2 必須具有相同的值型別。

引數

first, last

-

一對迭代器，指示要檢查的字串

返回值

如果模式 [pat_first, pat_last) 為空，則返回 std::make_pair(first, first)。

否則，返回一對迭代器，指向 [first, last) 中與 [pat_first, pat_last) 透過 pred 定義的比較相等的子序列的起始位置和末尾後一個位置，否則返回 std::make_pair(last, last)。

注意

特性測試宏	值	標準	特性
__cpp_lib_boyer_moore_searcher	201603L	(C++17)	搜尋器

示例

執行此程式碼

#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <string_view>
 
int main()
{
    constexpr std::string_view haystack =
        "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
        "do eiusmod tempor incididunt ut labore et dolore magna aliqua";
 
    const std::string_view needle{"pisci"};
 
    if (const auto it = std::search(haystack.begin(), haystack.end(),
            std::boyer_moore_searcher(needle.begin(), needle.end()));
        it != haystack.end()
    )
        std::cout << "The string " << std::quoted(needle) << " found at offset "
                  << it - haystack.begin() << '\n';
    else
        std::cout << "The string " << std::quoted(needle) << " not found\n";
}

輸出

The string "pisci" found at offset 43

參閱

search	搜尋一個範圍的元素首次出現的位置 (函式模板)
default_searcher (C++17)	標準 C++ 庫搜尋演算法實現 (類模板)
boyer_moore_horspool_searcher (C++17)	Boyer-Moore-Horspool 搜尋演算法實現 (類模板)