This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Search algorithms in __gnu_cxx::
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.