C++1zでは、文字列内の文字列を高速に検索するためのアルゴリズムとして、「ボイヤー・ムーア法 (Boyer-Moore)」と「ボイヤー・ムーア・ホースプール法 (Boyer-Moore-Horspool)」が導入されます。
これは、既存のstd::search()
アルゴリズムを拡張する形で行われ、検索アルゴリズムを外部から指定するためのパラメータが追加されます。
#include <iostream> #include <string> #include <algorithm> #include <functional> int main() { // ボイヤー・ムーア法で、文字列内の特定文字列を検索 const std::string corpus = "…"; // 検索対象 const std::string pattern = "…"; // 対象の中に見つけたい文字列 auto it = std::search( corpus.begin(), corpus.end(), std::boyer_moore_searcher( pattern.begin(), pattern.end() )); if (it != corpus.end()) { std::cout << "found" << std::endl; } else { std::cout << "not found" << std::endl; } }
検索アルゴリズムは以下の3つが用意されます。
default_searcher
boyer_moore_searcher
boyer_moore_horspool_searcher
default_searcher
はこれまで通りのstd::search()
の動作をします。
宣言
// <algorithm> namespace std { template <class ForwardIterator, class Searcher> ForwardIterator search(ForwardIterator first, ForwardIterator last, const Searcher& searcher); }
// <functional> namespace std { // 検索ポリシークラス template <class ForwardIterator, class BinaryPredicate = equal_to<>> class default_searcher; template <class RandomAccessIterator, class Hash = hash< typename iterator_traits<RandomAccessIterator>::value_type >, class BinaryPredicate = equal_to<>> class boyer_moore_searcher; template <class RandomAccessIterator, class Hash = hash< typename iterator_traits<RandomAccessIterator>::value_type >, class BinaryPredicate = equal_to<>> class boyer_moore_horspool_searcher; }
Boostと標準の差異
Boost 1.50.0でBoost Algorithm Libraryがリリースされ、そこに文字列検索のアルゴリズムが含まれています。Boost 1.61.0現在は、std::search()
を拡張するようなポリシーベースの設計ではなく、アルゴリズムごとに別名の関数が定義されています。
Boostの方には、標準に追加される2つのアルゴリズムに加えて、knuth_morris_pratt_search()
アルゴリズムがあります。これはKMP法という名前で知られているアルゴリズムです。(クヌース・モリス・プラット法)
参照
- N3411 Additional Searching Algorithms
- N3606 Extending
std::search
to use Additional Searching Algorithms - N3703 Extending
std::search
to use Additional Searching Algorithms (Version 3) - N3905 Extending
std::search
to use Additional Searching Algorithms (Version 4) - P0220R0 Adopt Library Fundamentals TS for C++17
- P0220R1 Adopt Library Fundamentals V1 TS Components for C++17 (R1)
- P0253R0 Fixing a design mistake in the searchers interface in Library Fundamentals
- P0253R1 Fixing a design mistake in the searchers interface in Library Fundamentals
お断り
この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。