Note: This paper explores potential future standardization directions and alternatives. It does not discuss or propose to amend the C++14 Committee Draft paper whose ballot is currently in progress.

A new WG21 paper is available. A copy is linked below, and the paper will also appear in the next normal WG21 mailing. If you are not a committee member, please use the comments section below or the std-proposals forum for public discussion.

Document number: N3703

Date: 2013-06-28

Extending std::search to use Additional Searching Algorithms (Version 3)

by Marshall Clow

Excerpt:

Note:

• This is an update of n3606, presented in Portland. The major differences are support for comparison predicates in Boyer-Moore and Boyer-Moore-Horspool, and wording for the standard.
• n3606 was an update of n3411, presented in Portland. The major difference is a different interface for the search functions.

[...]

std::search is a powerful tool for searching sequences, but there are lots of other search algorithms in the literature. For specialized tasks, some of them perform significantly better than std::search. In general, they do this by precomputing statistics about the pattern to be searched for, betting that this time can be made up during the search.

The basic principle is to break the search operation into two parts; the first part creates a "search object", which is specific to the pattern being searched for, and then the search object is passed, along with the data being searched, to std::search.

This is done by adding an additional overload to std::search, and some additional functions to create the search objects. ...