ALiX wrote:
> Can a call to std::list<MyClass>::sort() result in copying of the
> objects in the list (this is relevant for example when objects of type
> MyClass can be big in size)? AFAIK, nothing is said explicitly about
> this in the standard. Someone suggested that this 'no copy behaviour'
> might be implied by other requirements in the standards, e.g. the fact
> that iterators remain valid even after a call to sort, and time
> complexity requirements.
>
> However, I can't deduce any such conclusion from what I know about the
> requirements. As an example, I can imagine a bad algorithm that copies
> the entire list into a vector (along with some information about the
> internal structure of the list), sorts the vector and then reinserts
> the objects (and/or reassigns internal pointers), making sure that any
> iterators remain valid. This would still lead to a N log(N) time
> complexity.

The complexity requirements for the operation in question will answer
your question. For example, the complexity requirements for std::list's
sort method are:

    Approximately N log(N) comparisons, where N == size().
                                            [   23.2.2.4/32]

In other words, the only type of operation performed upon std::list's
items while conducting this operation is a comparison - around N log(N)
of them. Since no other type of operation is mentioned, no other kind
of operation upon the list's items is allowed. Since copying an item
would be considered an operation upon that item, we can safely conclude
that calling std list's sort routine will never result in any of its
items being copied.

Greg


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Greg Herlihy wrote:
> ALiX wrote:
> > Can a call to std::list<MyClass>::sort() result in copying of the
> > objects

I'll assume that your comparison predicate doesn't make copies.

> The complexity requirements for the operation in question will answer
> your question. For example, the complexity requirements for std::list's
> sort method are:
>
>     Approximately N log(N) comparisons, where N == size().
>                                             [   23.2.2.4/32]
>
> In other words, the only type of operation performed upon std::list's
> items while conducting this operation is a comparison - around N log(N)
> of them. Since no other type of operation is mentioned, no other kind
> of operation upon the list's items is allowed. Since copying an item
> would be considered an operation upon that item, we can safely conclude
> that calling std list's sort routine will never result in any of its
> items being copied.

Of course the complexity requirements for ::std::sort say essentially
the same thing.  I know how to implement std::sort while performing
only only O(N) copies.  Implementing it with no copies at all seems
tricky (put that memory-management-unit to work).

I don't think the standard promises that list::sort won't copy
elements.  At this point I'd consider it a QOI issue.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

wade@stoner.com wrote:
> I don't think the standard promises that list::sort won't copy
> elements.  At this point I'd consider it a QOI issue.

Technically, I think this is correct -- an implementation *could*, for
example, provide a std::list::sort that simply called std::sort.
However, it's very obvious that the Standard intends implementations to
provide a std::list::sort that avoids any copying, and pretty
straightforward to implement.  Given that, I'd be astonished if an
implementation chose to do copying.

On a related note, I was surprised to notice that std::list::sort has
no "Throws" paragraph.  Many of the other similar functions (e.g.
splice, unique, remove, remove_if) are documented not to throw unless
their predicate / comparator throws.  Why the omission from merge and
sort?

--
Richard Smith

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

wade@stoner.com wrote:
> Greg Herlihy wrote:
> > ALiX wrote:
> > > Can a call to std::list<MyClass>::sort() result in copying of the
> > > objects
>
> I'll assume that your comparison predicate doesn't make copies.
>
> > The complexity requirements for the operation in question will answer
> > your question. For example, the complexity requirements for std::list's
> > sort method are:
> >
> >     Approximately N log(N) comparisons, where N == size().
> >                                             [   23.2.2.4/32]
> >
> > In other words, the only type of operation performed upon std::list's
> > items while conducting this operation is a comparison - around N log(N)
> > of them. Since no other type of operation is mentioned, no other kind
> > of operation upon the list's items is allowed. Since copying an item
> > would be considered an operation upon that item, we can safely conclude
> > that calling std list's sort routine will never result in any of its
> > items being copied.
>
> Of course the complexity requirements for ::std::sort say essentially
> the same thing.  I know how to implement std::sort while performing
> only only O(N) copies.  Implementing it with no copies at all seems
> tricky (put that memory-management-unit to work).

The std::sort algorithm swaps items when sorting them. It does not copy
them. Of course a swap operation for a particular type may involve a
copy operation, or it may not. But whether it does or not is an
implementation detail. The amount of work perfomed by std::sort to sort
a sequence of items is calculated from the total number of comparison
and swap operations the routine performed.

A complexity guarantee for an operation would be meaningless unless it
were to limit in some way the total amount of work ever needed to
complete the operation. Now we can deduce from its swappable items
requirement that some portion of the work std::sort performs may be
devoted to swapping items. But since the complexity guarantee for the
entire operation is specified solely in terms of the number of
comparisons performed, we also know that the number of swap operations
must be bounded by the number of comparisons performed.

In other words, the number of swap operations to sort a sequence could
never exceed the number of comparisons performed and still have
std::sort meet its complexity guarantee. Therefore the total work that
std::sort will ever perform to sort N items is the work of performing N
log(N) comparisons combined with the work of performing S swap
operations with S in the range 0 to the number of comparisons actually
performed (inclusive).

Now the requirements for std::list's sort method are quite different
than those for std::sort. For one, a std::list container does not
require that its items be swappable or even be assignable. So no
portion of the work that std::list's sort routine performs is devoted
to swapping or assigning items. Moreover the complexity guarantees as
specified for containers - and unlike those for algorithms - are
clearly expressed in terms of operations upon the contained items. For
example, std::list's push_front method is required to make exactly one
call to the contained type's copy constructor. No more and no less.

Since there is no mention how many times that std::list's sort routine
is allowed to call an item's copy constructor, the number of calls
permitted must either be 0 or unlimited. But because an unlimited
number of calls to copy constructors during a sort operation would not
be bounded by the number of comparisons performed, we can conclude that
0 is the only permissible number of copy contructor calls that
std::list sort is allowed to make and still be able to meet its
complexity guarantee. In other words, we can be certain that calling
std::list's sort method will never copy any of its items.

> I don't think the standard promises that list::sort won't copy
> elements.  At this point I'd consider it a QOI issue.

Even if such a promise cannot be deduced from the Standard's current
requirements (and non-requirements) than the Standard should be amended
to reflect both current implementations and the set of commonly held
expectations for std::list. I can see no motivating reason for allowing
std::list implementations unbounded latitude in behavior and
performance delivered.

Greg


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Richard Smith" <richard@ex-parrot.com> writes:

> On a related note, I was surprised to notice that std::list::sort has
> no "Throws" paragraph.  Many of the other similar functions (e.g.
> splice, unique, remove, remove_if) are documented not to throw unless
> their predicate / comparator throws.  Why the omission from merge and
> sort?

Good question.  I have no idea, but you might go back and look at our
original proposals to see if there's a rationale.

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

I don't recall either, sorry.

On Feb 23, 2006, at 9:49 PM, David Abrahams wrote:
> "Richard Smith" <richard@ex-parrot.com> writes:
>
>> On a related note, I was surprised to notice that std::list::sort has
>> no "Throws" paragraph.  Many of the other similar functions (e.g.
>> splice, unique, remove, remove_if) are documented not to throw unless
>> their predicate / comparator throws.  Why the omission from merge and
>> sort?
>
> Good question.  I have no idea, but you might go back and look at our
> original proposals to see if there's a rationale.
>
> --
> Dave Abrahams
> Boost Consulting
> www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <1140743371.154111.286370@i39g2000cwa.googlegroups.com>,
Greg Herlihy <greghe@pacbell.net> wrote:

>
> The std::sort algorithm swaps items when sorting them. It does not copy
> them. Of course a swap operation for a particular type may involve a
> copy operation, or it may not. But whether it does or not is an
> implementation detail. The amount of work perfomed by std::sort to sort
> a sequence of items is calculated from the total number of comparison
> and swap operations the routine performed.

 first the sort algorithms [even if written for bidirectional
iterators, which they are not specified for] don't satisfy the
requirements of list::sort member function.

the fact that the revised standard says the elements are swappable,
implies that swap or iter_swap is used, but the number of swaps is not
specified in any way.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <1140718623.655388.65330@z34g2000cwc.googlegroups.com>,
Richard Smith <richard@ex-parrot.com> wrote:

> wade@stoner.com wrote:
> > I don't think the standard promises that list::sort won't copy
> > elements.  At this point I'd consider it a QOI issue.
>
> Technically, I think this is correct -- an implementation *could*, for
> example, provide a std::list::sort that simply called std::sort.
> However, it's very obvious that the Standard intends implementations to
> provide a std::list::sort that avoids any copying, and pretty
> straightforward to implement.  Given that, I'd be astonished if an
> implementation chose to do copying.
>
  Note list::sort() must be stable but std::sort() is not often stable,
in fact that is why there is an std::stable_sort().

   It MIGHT be POSSIBLE to do list::sort() with copying but I have not
heard of such an algorithm.  Given that merge sort is so easy to
impliment with the node pointers, is stable and is O(NlogN), I don't
see any implimentation copying data.

  If you are really have such a list::sort() implementation, or suspect
such copying is slowing you down, you can impliment merge sort your
self with a sort function that uses list::splice and a few temp lists
to sort the data without copying.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Greg Herlihy wrote:
> Now the requirements for std::list's sort method are quite different
> than those for std::sort. For one, a std::list container does not
> require that its items be swappable or even be assignable.

23.1/3 says a list's items must be Assignable.

I hope that limiting the number of comparisons is intended to limit the
total amount of work.  I'm not sure the standard actually has that as a
requirement.

I also agree that programmers expect list::sort to splice, rather than
swap, and that existing implementations meet that expectation.  I
certainly wouldn't object to the standard making this a requirement.
I'm just not convinced that it is an existing requirement.

Meta ramblings follow:

There are a lot of things I "know" that aren't promised by the
standard.  I believe the following are true for any implementation I've
ever used:
  operator++(int) is relatively fast
  struct {int a,b; } x; assert(&x.b == &x.a+1);
  <iostream> gives me <istream>
but it is difficult or impossible to show that the standard requires
them to be true.

So when a thread in this newsgroup begins with "Can a call to std::foo
result in bar?", I think it is important to consider

  1) What the standard requires.
  2) What the standard suggests.
  3) What existing implementations do.
  4) What "reasonable" implementations might do.
along with the ever popular
  5) What the standard should say.

and try to be clear about the category of your reply.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Can a call to std::list<MyClass>::sort() result in copying of the
objects in the list (this is relevant for example when objects of type
MyClass can be big in size)? AFAIK, nothing is said explicitly about
this in the standard. Someone suggested that this 'no copy behaviour'
might be implied by other requirements in the standards, e.g. the fact
that iterators remain valid even after a call to sort, and time
complexity requirements.

However, I can't deduce any such conclusion from what I know about the
requirements. As an example, I can imagine a bad algorithm that copies
the entire list into a vector (along with some information about the
internal structure of the list), sorts the vector and then reinserts
the objects (and/or reassigns internal pointers), making sure that any
iterators remain valid. This would still lead to a N log(N) time
complexity.

Regards,
ALiX

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]