This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]