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

Discussion in 'C++' started by Urs Thuermann, Jun 29, 2012.

  1. 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
     
    Urs Thuermann, Jun 29, 2012
    #1
    1. Advertising

  2. On 6/29/2012 5:53 PM, Urs Thuermann wrote:
    > 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
    --
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Jun 29, 2012
    #2
    1. Advertising

  3. Urs Thuermann

    Marc Guest

    Urs Thuermann wrote:

    > 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.
     
    Marc, Jun 29, 2012
    #3
  4. On Jun 29, 2:53 pm, Urs Thuermann <> wrote:
    > 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
     
    Howard Hinnant, Jun 30, 2012
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mr. SweatyFinger
    Replies:
    2
    Views:
    2,252
    Smokey Grindel
    Dec 2, 2006
  2. Geoffrey S. Knauth
    Replies:
    6
    Views:
    1,046
    Earl Purple
    Jan 18, 2006
  3. Martin T.
    Replies:
    7
    Views:
    840
    Martin T.
    Mar 10, 2008
  4. curiousEngine
    Replies:
    1
    Views:
    1,393
    James Kanze
    May 9, 2008
  5. Navin
    Replies:
    1
    Views:
    767
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page