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: string::find complexity.

From: Paolo Carlini <pcarlini at suse dot de>
To: Matt Austern <austern at apple dot com>
Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
Date: Fri, 11 Jun 2004 12:37:44 +0200
Subject: Re: string::find complexity.
References: <1086847470.13398.8.camel@localhost.localdomain> <3EE45452-BB05-11D8-A44B-000A95AA5E5E@apple.com>

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.

References:
- string::find complexity.
  - From: Dhruv Matani
- Re: string::find complexity.
  - From: Matt Austern

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