BloombergLP::bslstl::BoyerMooreHorspoolSearcher

This class template implements an STL-compliant searcher object that uses the Boyer, Moore, Horspool Algorithm. Several non-standard accessors are also provided.

Synopsis

Declared in <bslstl_boyermoorehorspoolsearcher.h>

template<
    class RNDACC_ITR_NEEDLE,
    class HASH = bsl::hash<bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>,
    class EQUAL = bsl::equal_to<bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>>
class BoyerMooreHorspoolSearcher;

Type Aliases

NameDescription
DefaultEqual the default type for the EQUAL optional template parameter
DefaultHash the default type for the HASH optional template parameter
value_type the type of the values that can be obtained by dereferencing a RNDACC_ITR_NEEDLE

Member Functions

NameDescription
BoyerMooreHorspoolSearcher [constructor]Constructors
operator= Assignment operators
allocator Return the allocator used by this object to supply memory.
equal Return the equality comparison functor supplied on construction.
hash Return the hashing functor supplied on construction.
needleFirst Return an iterator referring to the first element of the sequence of value_type values that can be sought by this searcher object.
needleLast Return an iterator referring to one past the last element of the sequence of value_type values that can be sought by this searcher object.
operator() Search the specified range [haystackFirst, haystackLast)] for the first sequence of value_type values specified on construction. Return the range where those values are found, or the range [haystackLast, haystackLast)] if that sequence is not found. The search is performed using an implementation of the Boyer Moore Horspool algorithm and has a complexity of O(N) for random text. Values of the "needle" sequence and the "haystack" sequence are compared using the equality comparison functor specified on construction. The behavior is undefined unless haystackFirst can be advanced to haystackLast and the iterators used to construct this object, needleFirst() and needleLast(), are still valid. Note that if the "needle" sequence is empty, the range [haystackFirst, haystackFirst)] is returned. Also note that if the "needle" sequence is longer than the "haystack" sequence -- thus, impossible for the "needle" to be found in the "haystack" -- the range [haystackLast, haystackLast)] is returned.