473,324 Members | 2,356 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

Sorting lists containing big objects.

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

Feb 14 '06 #1
4 1442
ALiX wrote:
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
--
Please remove capital As from my address when replying by mail
Feb 14 '06 #2
ALiX wrote:
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).
Feb 14 '06 #3
"ALiX" <al********@hotmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...
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
Feb 15 '06 #4
On 14 Feb 2006 13:00:42 -0800, "ALiX" <al********@hotmail.com> wrote:
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

Feb 15 '06 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

39
by: Erlend Fuglum | last post by:
Hi everyone, I'm having some trouble sorting lists. I suspect this might have something to do with locale settings and/or character encoding/unicode. Consider the following example, text...
5
by: Pratyush | last post by:
Hi, Suppose there is a vector of objects of class A, i.e., std::vector<A> vec_A(N); The class A satisifies all the STL vector requirements. Now I wish to add some attributes for each of the...
16
by: RCS | last post by:
So I have an ArrayList that gets populated with objects like: myAL.Add(new CustomObject(parm1,parm2)); I'm consuming this ArrayList from an ObjectDataSource and would like to have this support...
25
by: Dan Stromberg | last post by:
Hi folks. Python appears to have a good sort method, but when sorting array elements that are very large, and hence have very expensive compares, is there some sort of already-available sort...
2
by: Rob Meade | last post by:
Dear all, I have a class which contains an arraylist populated with other objects, for example: PrescriptionQueue - containing multiple instances of Prescription I have the need on my web...
1
by: Sorting With IComparer | last post by:
Hi, I have implemened a class which is derived form IComparer to sort using IComparer. The sorting is functioning well when the sorting objects are different. But. when the objects are equal...
16
by: Kittyhawk | last post by:
I would like to sort an Arraylist of objects on multiple properties. For instance, I have a Sort Index property and an ID property (both integers). So, the results of my sort would look like this:...
8
by: DierkErdmann | last post by:
Hi ! I know that this topic has been discussed in the past, but I could not find a working solution for my problem: sorting (lists of) strings containing special characters like "ä", "ü",......
5
by: jrod11 | last post by:
hi, I found a jquery html table sorting code i have implemented. I am trying to figure out how to edit how many colums there are, but every time i remove code that I think controls how many colums...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.