Search algorithms in __gnu_cxx::
Wed Sep 6 17:26:00 GMT 2006
Dhruv Matani wrote:
> 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:
are certainly welcome, in principle!
More information about the Libstdc++