Search algorithms in __gnu_cxx::

[Paolo Carlini]

Dhruv Matani wrote:
> On this page:
> http://www.movsd.com/bm.htm
> you can find a complete description of the 3 different kinds of tables
> which _may_ be used in any Boyer Moore algorithm implementation. I am
> using the Good Character & Bad Character shift tables ONLY. As you can
> see from the description, that's perfectly fine to do.
To be clear, it's not about *me*, it's about implementing something well 
known and of known properties. That means, the pointer above must be 
part of the documentation, as a comment in the code, at least. Likewise 
for any other extension we may add in the future.
>> Also, I think we have to do something for that unordered_map, I don't
>> think covering the general case via lookups in a map leads to something
>> close to the original spirit, in any possible sense...
> Nope, it doesn't because the algorithm wasn't meant for any search,
> but was designed for string searching in particular. Hence the use of
> the static tables, etc.... However, using the unordered_map<> as an
> approximation to preserve generality will only hurt the performance
> and not the correctness. Again, since this is an extension, people
> will use it only for strings if we document it accordingly.
No, we don't want to do that. Because using a map like that means that 
all the complexity figures of the Boyer-Moore algorithm are not valid 
anymore. Therefore, either we find a better way to deal with that 
problem (I suggest we don't give up so quickly, no reason to rush) or we 
have to deliver the algorithm only for chars.

Paolo.