Search algorithms in __gnu_cxx::

Paolo Carlini pcarlini@suse.de
Wed Sep 6 17:26:00 GMT 2006


Dhruv Matani wrote:

> Hello,
>  With all the discussion happening currently, and with what
> transpired a few months ago, I am of the opinion that libstdc++ should
> have alternate search algorithms such as Boyer Moore, etc.... in the
> __gnu_cxx namespace. This is just a suggestion considering that many
> people spend time implementing it themselves plus the fact that we
> already have(had????) hash tables, etc.... in that namespace. 

Actually, the last time we discussed this issue, Matt Austern maintained 
that, to the best of his knowledge, "sophisticated" algorithms had been 
benchmarked quite a few times by Musser et al., for practical 
application in std::search and discarded. As a matter of fact, even the 
relatively simple algorithm in std::search looses *bad* for chars in 
case a well optimized strchr (for short strings too!) is available and 
you cannot assume anything about the strings, lengths, alphabet size, 
etc. (as you certainly noticed).

If I get your point, the above does not mean of course that those 
algorithms are not suited for __gnu_cxx::__bm_search, and also 
__gnu_cxx::__kmp_search, and whatelse... Extension implementations of 
the best algorithms in:

    http://www-igm.univ-mlv.fr/~lecroq/string/

are certainly welcome, in principle!

Paolo.



More information about the Libstdc++ mailing list