Search algorithms in __gnu_cxx::

Dhruv Matani
Thu Sep 7 07:27:00 GMT 2006

On 9/6/06, Paolo Carlini <> 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:
> 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.


   -Dhruv Matani.

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

More information about the Libstdc++ mailing list