Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk