Note: This paper was among the papers adopted into the draft Library Fundamentals TS yesterday at the Issaquah WA USA ISO C++ meeting.

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: N3905

Date: 2014-02-14

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

by Marshall Clow

Excerpt:

Note: This is an update of n3703, from the summer 2013 mailing. ...

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.

Two additional search algorithms are proposed for inclusion into the standard: "Boyer-Moore" and "Boyer-Moore-Horspool". Additionally, the interface for the search objects is documented so that library implementers and end users can create their own search objects and use them with std::search.

...

Thanks to LWG, which reviewed an earlier version of this document, Matt Austern, who suggested overloading std::search, and especially Daniel Krügler, who wrote most of the wording for the standard, and Stephan T. Lavavej, who reviewed it.