[boost] [Review:Algorithms] Comments about search algorithms

Subject: [boost] [Review:Algorithms] Comments about search algorithms
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-09-24 14:22:37

Dear All,

Here are some observations about the proposed search algorithms:

- I was confused as to whether the caller must keep the pattern pointed 
to by the iterators passed to the constructor after the constructor 
returns.  My guess was that once the internal tables were built the 
pattern would not be needed any more - but that turns out to be wrong.  
At the least, the docs need to explain this.

- The three algorithms have very similar interfaces.  The docs could 
perhaps define a "searcher" concept and explicitly declare these 
algorithms' classes to be models of that concept.

- std::search is similar to the three algorithms' free function 
versions (congratulations on getting the arguments in the same 
order!).  For completeness, how about adding a searcher class that uses std::search?

- A user faced with these three (or four) algorithms will need to 
choose one.  The docs should offer some guidance, e.g. benchmarks or 
rules-of-thumb, about which to use.

- It would sometimes be useful to have a variant of the constructor 
that takes a const char* pattern.

- The tables store ints.  For patterns shorter than 256 characters I 
think that uint8_t would be sufficient, and would reduce the size of a 
table from 1024 or 2048 bytes to only 256 bytes.  Similarly uint16_t or 
uint32_t could be used for larger patterns.  It is not obvious how to 
implement this, though; perhaps an optional max_pattern_length template 
parameter, making it the user's responsibility to ensure the supplied 
pattern is not too long.

- The docs describe some methods that are private to the 
implementation; why?

Regards,  Phil.