Sorting lists containing big objects.

A

ALiX

I am using a std::list<MyClass> where objects of type MyClass can be
big in size. Can using std::list<>::sort result in objects inside the
list being copied around or does the list merely reassign internal
pointers? Is there any such demands/guarantees from the standard?

Regards,
ALiX
 
A

Alan Johnson

ALiX said:
I am using a std::list<MyClass> where objects of type MyClass can be
big in size. Can using std::list<>::sort result in objects inside the
list being copied around or does the list merely reassign internal
pointers? Is there any such demands/guarantees from the standard?

Regards,
ALiX

Here is everything the standard has to say about list's sort member.

void sort();
template <class Compare> void sort(Compare comp);
Requires: operator< (for the first version) or comp (for the second
version) defines a strict weak
ordering (25.3).
Effects: Sorts the list according to the operator< or a Compare function
object.
Notes: Stable: the relative order of the equivalent elements is
preserved. If an exception is thrown the
order of the elements in the list is indeterminate.
Complexity: Approximately NlogN comparisons, where N == size().

My interpretation is that copying of objects is not forbidden (even if
most implementations optimize such that it doesn't happen).
 
V

Victor Bazarov

ALiX said:
I am using a std::list<MyClass> where objects of type MyClass can be
big in size. Can using std::list<>::sort result in objects inside the
list being copied around or does the list merely reassign internal
pointers? Is there any such demands/guarantees from the standard?

You are cordially invited to look at the implementation that is most
likely right there in the header <list>, and complain to your compiler
vendor if it is not up to your expectations. The Standard does require
the 'sort' to have the complexity of NlogN comparisons, but say nothing
about copying, which leads me to believe that pointers are swapped and
not objects.

V
 
P

P.J. Plauger

I am using a std::list<MyClass> where objects of type MyClass can be
big in size. Can using std::list<>::sort result in objects inside the
list being copied around or does the list merely reassign internal
pointers? Is there any such demands/guarantees from the standard?

All implementations I know sort the list by splicing elements (what
you call reassigning internal pointers). I don't think it's a
requirement, but they all do.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
 
R

Roland Pibinger

I am using a std::list<MyClass> where objects of type MyClass can be
big in size. Can using std::list<>::sort result in objects inside the
list being copied around or does the list merely reassign internal
pointers? Is there any such demands/guarantees from the standard?

The STL guarantees it, see: http://www.sgi.com/tech/stl/List.html

"void sort(); ... All iterators remain valid and continue to point to
the same elements."

AFAIK, the C++ Standard gives no such guarantee. This may be an
oversight. Perhaps alert people can derive this guarantee from other
guarantees for std::list (e.g. complexity guarantees). You should also
post to comp.std.c++.

The general problem with STL is that it is desigend only for values
(small objects without identity like 'int'). STL is a 80:20 solution.
80% of the solution space is omitted.

Best wishes,
Roland Pibinger
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top