This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Possible improvement in next_permutation implementation
- From: Paolo Carlini <pcarlini at suse dot de>
- To: David GONZALEZ MALINE <David dot Gonzalez dot Maline at cern dot ch>
- Cc: libstdc++ at gcc dot gnu dot org
- Date: Fri, 07 Mar 2008 14:04:27 +0100
- Subject: Re: Possible improvement in next_permutation implementation
- References: <47CE831E.2030703@cern.ch>
David GONZALEZ MALINE wrote:
> I wonder whether it would be possible to make an implementation of the
> standard library method closer to what the gsl algorithm does. The
> three algorithms are intrinsically the same one, but the way they have
> been implemented differ in the small details, and that is what makes
> the difference in time.
I'm still checking a few things and performing microbenchmarks, but
apparently the performance gap is due to the fact that
std::next_permutation works with generic bidirectional iterators (i.e,
in the implementation we lack an overload optimized for random access
iterators).
Paolo.