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::


On 9/6/06, Paolo Carlini <pcarlini@suse.de> wrote:
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).

Yes. The proposal is not to replace std::search, etc.... but to provide extensions so that people who want to use them(if they know that a certain algo. would be better suited to a certain data set) can use them without having to write the code themselves every time.



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!


If people here find this suggestion do able, please let me know, since
I'm willing to take charge of it.


Regards, -Dhruv.





--
  -Dhruv Matani.
http://www.geocities.com/dhruvbird/

"Life is wasted on the living"
 - Zaphod Beeblebrox the Fourth.


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