Why does std::sort() use operator=() ?

[Urs Thuermann]

I have written a small class Foo to test the std::sort() routine. My
class implements methods Foo(), ~Foo(), operator<(const Foo &), and
operator=(const Foo&), and a specialization of the template
std::swap(), i.e. void swap(Foo &, Foo &) and all of these print a
message that they have been called followed by theirs argument(s).

The documentation on cpluscplus.com says about swap()

"Because this function template is used as a primitive operation by
many other algorithms, it is highly recommended that large data
types overload their own specialization of this function."

so I assumed that e.g. std::sort() would only use operator<() and
swap() to do its job. But with my test class Foo I could see that
std::sort() in GCC uses many assignments instead of swap() which might
be much more expensive. Why is this done?

I have written a simple selection sort template and a quick-sort
template using only operator<() and swap() just to show that this
really works.

urs

 

[Victor Bazarov]

I have written a small class Foo to test the std::sort() routine. My
class implements methods Foo(), ~Foo(), operator<(const Foo &), and
operator=(const Foo&), and a specialization of the template
std::swap(), i.e. void swap(Foo &, Foo &) and all of these print a
message that they have been called followed by theirs argument(s).

The documentation on cpluscplus.com says about swap()

"Because this function template is used as a primitive operation by
many other algorithms, it is highly recommended that large data
types overload their own specialization of this function."

That's not a normative document for compilers.

so I assumed that e.g. std::sort() would only use operator<() and
swap() to do its job. But with my test class Foo I could see that
std::sort() in GCC uses many assignments instead of swap() which might
be much more expensive. Why is this done?

<shrug> The old[er] Standard did not require the sorted elements to be
ValueSwappable or MoveConstructible, so the implementers were free to do
what they wanted. It's likely that instead of using 'std::swap' they
have their own implementation for swapping the values when moving those
values in the sequence.

I have written a simple selection sort template and a quick-sort
template using only operator<() and swap() just to show that this
really works.

Congratulations.

V

 

[Marc]

I have written a small class Foo to test the std::sort() routine. My
class implements methods Foo(), ~Foo(), operator<(const Foo &), and
operator=(const Foo&), and a specialization of the template
std::swap(), i.e. void swap(Foo &, Foo &) and all of these print a
message that they have been called followed by theirs argument(s).

The documentation on cpluscplus.com says about swap()

"Because this function template is used as a primitive operation by
many other algorithms, it is highly recommended that large data
types overload their own specialization of this function."

so I assumed that e.g. std::sort() would only use operator<() and
swap() to do its job. But with my test class Foo I could see that
std::sort() in GCC uses many assignments instead of swap() which might
be much more expensive. Why is this done?

I have written a simple selection sort template and a quick-sort
template using only operator<() and swap() just to show that this
really works.

Note that, in C++11, gcc probably uses move assignments which are even
faster than swap (indeed swap is usually a valid implementation for
them).

For a number of classes, swap is implemented with 3 operations (tmp=a;
a=b; b=tmp, which makes it not so cheap. One would need a way to
tell the library about the respective performance of swap and = for
each type, which isn't currently possible.

 

[Howard Hinnant]

But with my test class Foo I could see that
std::sort() in GCC uses many assignments instead of swap() which might
be much more expensive.  Why is this done?

In C++98/03 std::sort is allowed to copy construct, copy assign and
swap a type. In C++11 std::sort can no longer copy construct or copy
assign a type. But it can still move construct, move assign and swap
a type. And if your type implements copy assignment, but not move
assignment, a move assignment expression will use your type's copy
assignment operator.

I have written a simple selection sort template and a quick-sort
template using only operator<() and swap() just to show that this
really works.

I too have written a std-conforming std::sort using only operator<()
and swap() (for the CodeWarrior library, years ago). And I did it for
exactly the reasons you obviously have. Since then I've written an
even better std::sort that uses move construction, move assignment and
swap. It is faster than my previous implementation: unless it
encounters a type that is expensive to move construct and move
assign. I consider that a bug in the type, as opposed to a bug in the
sort algorithm. Move construction and move assignment should be
implemented when they are faster than copy construction and copy
assignment.

You may not have heard about C++11 move semantics yet. Search around,
you'll find tons of discussion about it.

One reason I chose to use move construction and move assignment in my
latest implementation of std::sort is because I wanted to sometimes do
an insertion sort on subsequences. And insertion sort favors the use
of move construction and move assignment instead of swap. Insertion
sort has a wonderful property that it is linear on already sorted
sequences. And near linear on "nearly sorted" sequences. When one
suspects that a subsequence is nearly linear, insertion sort becomes a
powerful tool in the toolbox. It would be a shame to outlaw such a
powerful optimization by outlawing the use of move construction and
move assignment under std::sort.

Howard