string::find complexity.

[Paolo Carlini]

Matt Austern wrote:

> There are really two questions here.
>  (1) Why is string::find implemented from scratch, instead of just
>         implemented as a thin wrapper around std::search()?
>  (2) Why doesn't either of them use KMP?
>
> The answer to the first question: no good reason that I can think
> of.  std::string::find and std::search both do substring matches.
> It shouldn't be implemented twice.  Doing it once means that
> whatever bug fixes and performance tweaks you make apply
> in more places.

Agreed, I'll try to do that. Actually, the issue seems rather serious
since, currently, in my preliminary experiments, the performance
are rather poor, both on P4 and on x86-64 even if compared to
very-very simple alternatives hand-written (not to mention what is
achieved by our competitors :(

Thanks for your message,
Paolo.