BDE 4.14.0 Production release
Loading...
Searching...
No Matches
Public Types | Public Member Functions | List of all members
bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL > Class Template Reference

#include <bslstl_boyermoorehorspoolsearcher.h>

Public Types

typedef bsl::iterator_traits< RNDACC_ITR_NEEDLE >::value_type value_type
 
typedef bsl::hash< typename bsl::iterator_traits< RNDACC_ITR_NEEDLE >::value_type > DefaultHash
 the default type for the HASH optional template parameter
 
typedef bsl::equal_to< typename bsl::iterator_traits< RNDACC_ITR_NEEDLE >::value_type > DefaultEqual
 the default type for the EQUAL optional template parameter
 

Public Member Functions

 BoyerMooreHorspoolSearcher (RNDACC_ITR_NEEDLE needleFirst, RNDACC_ITR_NEEDLE needleLast, HASH hash=HASH(), EQUAL equal=EQUAL(), BloombergLP::bslma::Allocator *basicAllocator=0)
 
 BoyerMooreHorspoolSearcher (const BoyerMooreHorspoolSearcher &original)
 
 BoyerMooreHorspoolSearcher (BloombergLP::bslmf::MovableRef< BoyerMooreHorspoolSearcher > original) BSLS_KEYWORD_NOEXCEPT
 
 BoyerMooreHorspoolSearcher (const BoyerMooreHorspoolSearcher &original, BloombergLP::bslma::Allocator *basicAllocator)
 
 BoyerMooreHorspoolSearcher (BloombergLP::bslmf::MovableRef< BoyerMooreHorspoolSearcher > original, BloombergLP::bslma::Allocator *basicAllocator)
 
 ~BoyerMooreHorspoolSearcher ()=default
 
BoyerMooreHorspoolSearcher & operator= (const BoyerMooreHorspoolSearcher &rhs)
 
BoyerMooreHorspoolSearcher & operator= (BloombergLP::bslmf::MovableRef< BoyerMooreHorspoolSearcher > rhs)
 
template<class RNDACC_ITR_HAYSTACK >
bsl::pair< RNDACC_ITR_HAYSTACK, RNDACC_ITR_HAYSTACK > operator() (RNDACC_ITR_HAYSTACK haystackFirst, RNDACC_ITR_HAYSTACK haystackLast) const
 
RNDACC_ITR_NEEDLE needleFirst () const
 
RNDACC_ITR_NEEDLE needleLast () const
 
HASH hash () const
 Return the hashing functor supplied on construction.
 
EQUAL equal () const
 Return the equality comparison functor supplied on construction.
 
BloombergLP::bslma::Allocator * allocator () const
 Return the allocator used by this object to supply memory.
 

Detailed Description

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

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

See bslstl_boyermoorehorspoolsearcher

Member Typedef Documentation

◆ DefaultEqual

template<class RNDACC_ITR_NEEDLE , class HASH = bsl::hash< typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>, class EQUAL = bsl::equal_to< typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>>
typedef bsl::equal_to< typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type> bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::DefaultEqual

◆ DefaultHash

template<class RNDACC_ITR_NEEDLE , class HASH = bsl::hash< typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>, class EQUAL = bsl::equal_to< typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>>
typedef bsl::hash< typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type> bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::DefaultHash

◆ value_type

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

the type of the values that can be obtained by dereferencing a RNDACC_ITR_NEEDLE

Constructor & Destructor Documentation

◆ BoyerMooreHorspoolSearcher() [1/5]

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::BoyerMooreHorspoolSearcher ( RNDACC_ITR_NEEDLE  needleFirst,
RNDACC_ITR_NEEDLE  needleLast,
HASH  hash = HASH(),
EQUAL  equal = EQUAL(),
BloombergLP::bslma::Allocator *  basicAllocator = 0 
)

Create a BoyerMooreHorspoolSearcher object that can search for the sequence of value_type values found in the specified range [needleFirst, needleLast). Generate meta-data and save for use by operator(). The complexity of this process is O(M) where M is the length of the "needle". Optionally specify a hash functor mapping mis-matched values to the size of the next step in the search – as large as, needleLast - needleFirst. Optionally specify an equal functor for use with hash and for use by operator(). See {Requirements for HASH and EQUAL}. Optionally specify basicAllocator to supply memory. If basicAllocator is 0 or not supplied, the currently installed default allocator is used. The behavior is undefined unless needleFirst can be advanced to needleLast.

◆ BoyerMooreHorspoolSearcher() [2/5]

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::BoyerMooreHorspoolSearcher ( const BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL > &  original)

Create a BoyerMooreHorspoolSearcher object having same state – needleFirst(), needleLast(), hash(), and equal() – as the specified original object, and that uses the currently installed default allocator to supply memory.

◆ BoyerMooreHorspoolSearcher() [3/5]

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::BoyerMooreHorspoolSearcher ( BloombergLP::bslmf::MovableRef< BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL > >  original)

Create a BoyerMooreHorspoolSearcher object having same state – needleFirst(), needleLast(), hash(), and equal() – as the specified original object by moving (in constant time) the state of original to the new searcher. The allocator of original is propagated for use in the newly created searcher. The original object is left in an unspecified (valid) state.

◆ BoyerMooreHorspoolSearcher() [4/5]

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::BoyerMooreHorspoolSearcher ( const BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL > &  original,
BloombergLP::bslma::Allocator *  basicAllocator 
)

Create a BoyerMooreHorspoolSearcher object having same state – needleFirst(), needleLast(), hash(), and equal() – as the specified original object. Optionally specify a basicAllocator used to supply memory. If basicAllocator is 0, the currently installed default allocator is used.

◆ BoyerMooreHorspoolSearcher() [5/5]

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::BoyerMooreHorspoolSearcher ( BloombergLP::bslmf::MovableRef< BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL > >  original,
BloombergLP::bslma::Allocator *  basicAllocator 
)

Create a BoyerMooreHorspoolSearcher object having same state – needleFirst(), needleLast(), hash(), and equal() – as the specified original object. The specified basicAllocator is used to supply memory. If basicAllocator is 0, the currently installed default allocator is used. The state of original is moved (in constant time) to the new searcher if basicAllocator == original.allocator(), and is move-inserted (in linear time) using basicAllocator otherwise. The original object is left in an unspecified (valid) state.

◆ ~BoyerMooreHorspoolSearcher()

template<class RNDACC_ITR_NEEDLE , class HASH = bsl::hash< typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>, class EQUAL = bsl::equal_to< typename bsl::iterator_traits<RNDACC_ITR_NEEDLE>::value_type>>
bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::~BoyerMooreHorspoolSearcher ( )
default

Member Function Documentation

◆ allocator()

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
BloombergLP::bslma::Allocator * bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::allocator ( ) const
inline

◆ equal()

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
EQUAL bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::equal ( ) const
inline

◆ hash()

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
HASH bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::hash ( ) const
inline

◆ needleFirst()

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
RNDACC_ITR_NEEDLE bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::needleFirst ( ) const
inline

Return an iterator referring to the first element of the sequence of value_type values that can be sought by this searcher object.

◆ needleLast()

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
RNDACC_ITR_NEEDLE bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::needleLast ( ) const
inline

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()()

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
template<class RNDACC_ITR_HAYSTACK >
bsl::pair< RNDACC_ITR_HAYSTACK, RNDACC_ITR_HAYSTACK > bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::operator() ( RNDACC_ITR_HAYSTACK  haystackFirst,
RNDACC_ITR_HAYSTACK  haystackLast 
) const

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.

◆ operator=() [1/2]

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL > & bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::operator= ( BloombergLP::bslmf::MovableRef< BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL > >  rhs)
inline

Assign to this object the state of the specified rhs object – needleFirst(), needleLast(), hash(), and equal() – and return a non-const reference to this searcher. The rhs is left in an unspecified (valid) state.

◆ operator=() [2/2]

template<class RNDACC_ITR_NEEDLE , class HASH , class EQUAL >
BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL > & bslstl::BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL >::operator= ( const BoyerMooreHorspoolSearcher< RNDACC_ITR_NEEDLE, HASH, EQUAL > &  rhs)
inline

Assign to this object the state – needleFirst(), needleLast(), hash(), and equal() – of the specified rhs object, and return a non-const reference to this searcher.

The documentation for this class was generated from the following file: