Re: Can 'qsort' have an advantage over 'std::sort'?
johnchx2@yahoo.com wrote:
Greg Herlihy wrote:
So how does std::sort rearrange items in a container if not
by copying them? The answer is: by swapping them.
I thought that this might be the case, but (a) I can't find
any requirement in the standard that it do so and (b) the
implementations I have handy (STLPort and libstdc++) appear to
require the copy constructor and assignment operator, even
though I provide a suitable swap() overload.
Well, that's a requirement of the standard. Recent versions of
g++ will complain that they are missing even if it doesn't use
them.
In fact, g++ does use them. For small sequences, insertion sort
is faster than quick sort (at least for built-in types), so the
g++ implementation switches to insertion sort (which doesn't
swap) when the partition becomes small enough. And quick sort
has some degenerate cases, where it is O(n^2); g++ detects when
quick sort starts to degenerate, and switches to a heap sort --
which also doesn't use swap.
Note that typically, an implementation will not use swap
directly, but will use iter_swap -- and iter_swap must work even
if the iterators are of different types, and have different
value_types. Which means that it cannot normally use swap
directly -- g++ contains some meta-programming so that it will
use swap if the value types of the iterators are identical,
apparently in response to DR 187 (but DR 187 requires an
implementation of iter_swap which doesn't work if the value
types are different, without introducing an additional
constraint to require that they be the same). I wouldn't be
sure that other implementations are up to date here, and there
is still no guarantee that std::sort use either swap or
iter_swap.
--
James Kanze GABI Software
Conseils en informatique orient?e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]