Component of the Week #24: Standard Searchers

Summary:

  • Searching for substrings (or subsequences) quickly.

The C++17 Standard introduced three classes that that can search a sequence for a particular sub-sequence. When the values are characters (they need not be) we typically describe this as finding a sub-string within a longer string.

Terminology:

  • Needle the sequence being sought.

  • Haystack the longer sequence in which the needle is sought.

BDE has made two of those classes available to all of our supported C++ versions (including C++03):

  • bsl::default_searcher

  • bsl::boyer_moore_horspool_searcher1 (BMH searcher)

Definitions of these classes should be acquired from bsl_functional.h.

The bsl::default_searcher class uses a classic, “naive” algorithm that has a complexity of O(M * N) where M is the length of the needle and N is the length of the haystack. In its favor, this searcher requires only ForwardIterators for the needle and the haystack.

If RandomAccessIterators are available, one can use the bsl::boyer_moore_horspool_searcher class. This searcher has some additional cost on construction when it mines the needle for metadata that allows the searcher to progress through the haystack faster than a default searcher. In typical cases, a BMH searcher’s complexity is O(N). BMH searchers are recommended for very long needles or when the searcher for a given needle can be re-used on many haystacks, thereby amortizing the cost of construction.

As an example, suppose we have the contents of a logfile from some build process and are looking for occurrences of a particular linker (ld) error message.

#include <bsl_functional.h>  // `bsl::boyer_moore_horspool_searcher`

// ...

using namespace BloombergLP;

int main()
{
    const char * const logFile    = /* ... */ ;
    const bsl::size_t  logSize    = bsl::strlen(logFile);
    const char * const logFileEnd = logFile + logSize;

    const bsl::string_view errorMsg = "error: ld returned 1 exit status";

    assert(errorMsg.size() > 0); // Otherwise, infinite `for`-loop below.

First, we construct a searcher object for the sequence of interest (the error message). Since the error message is somewhat long and the logfile typically quite lengthly, we choose the BMH searcher class.

bsl::boyer_moore_horspool_searcher<const char *> ldErrorSearcher(
                                                      errorMsg.begin(),
                                                      errorMsg.end());

Now, we can use the ldErrorSearcher object in concert with the bsl::search algorithm to iteratively find every occurrence of errorMsg in the logfile data (the haystack). Note that after the first match we reset the next search to start after the previous match.

   for (const char *it  = bsl::search(logFile,              logFileEnd, ldErrorSearcher);
                    it != logFileEnd;
                    it  = bsl::search(it + errorMsg.size(), logFileEnd, ldErrorSearcher)) {

       bsl::size_t      offset = bsl::distance(logFile, it);
       bsl::string_view match(it, errorMsg.size());

       bsl::cout << offset << ": " << match << bsl::endl;
   }
}

Both bsl::default_searcher and bsl::boyer_moore_horspool_searcher are compatible with the bsl::search algorithm. If the needle/haystack characteristics had warranted choosing the default searcher we could have defined ldErrorSearcher otherwise without changing the for-loop.

bsl::default_searcher<const char *> ldErrorSearcher(errorMsg.begin(),
                                                    errorMsg.end());

Finally, we observe that there are three matches in this logfile:

15: error: ld returned 1 exit status
63: error: ld returned 1 exit status
126: error: ld returned 1 exit status

There are two other classes provide additional, non-Standard-compliant features:

  • bslstl::DefaultSearcher

  • bslstl::BoyerMooreHorspoolSearcher

For more details and examples, see: