#### Archived

This topic is now archived and is closed to further replies.

# stl list < pointer > and sorting = bad?

This topic is 5763 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

i dont know how to do the sorting when using pointers, because when i am using pointers i cant just use sort() i have to use sort(something) and i dont know how that ''something'' works so could someone help me out... here''s some code:
#include <iostream>
#include <list>

using namespace std;

void main(void)
{
list intlist;
list::iterator iter;
int a=1,b=3,c=2;

intlist.push_back(&a);
intlist.push_back(&b);
intlist.push_back(&c);

// sort the list here

for(iter = intlist.begin(); iter != intlist.end(); iter++)
{
cout << **iter << endl;
}

}
[/CODE]

//ziruz    
------------------------------------------------------------ XL is comming soon @ http://ziruz.cjb.net/

##### Share on other sites

        #include <list>#include <iostream>#include <algorithm>template<typename T>class DeletePtr {public:void operator()(T*elem){ delete elem;  }};template<typename T>class IsGreater {public:bool operator()(T *l, T*r) const { return (*l) > (*r);  }};void main(){	std::list<int*> mylist;	mylist.push_back(new int(5));	mylist.push_back(new int(2));	mylist.push_back(new int(8));	mylist.sort(IsGreater<int>());	std::list<int*>::const_iterator i, endi = mylist.end();	for(i = mylist.begin(); i != endi; ++i)	{		std::cout<<**i<<std::endl;	}	std::for_each(mylist.begin(), mylist.end(), DeletePtr<int>());}

Fixed the errors i had in the code, it works for VS .NET as is...dont know about 6 though because i don't have it installed anymore.
Also: Ziruz - that error sounds like you were using my original sort call (which i had typed wrong | The benifits of not having a cup of coffee in the morning )

[edited by - Godballz on October 4, 2002 2:49:54 PM]

##### Share on other sites
Nearly correct.

std::list has its own sort implementation which either sorts by operator or a Compare predicate:

1: void sort();
2: template void sort(greater pr);

If lists are not necessary (e.g. you don't have much insertions and removes running in time critical moments) I'd tend to use std::stable_sort from algorithm in favour of the list implementation of sort. Naturally you have to use containers like vector in that case as these algorithms demand random access iterators which can't be provided by std::list.

regards, Paralax
(this was posted to point out that std::list's sort() function just takes one or no arguments. The code should be correct now)

coder at Speckdrumm demo division
http://speckdrumm.schlucken.org

[edited by - Paralax on October 3, 2002 2:34:40 PM]

##### Share on other sites
quote:

If lists are not necessary (e.g. you don''t have much insertions and removes running in time critical moments) I''d tend to use std::stable_sort from algorithm in favour of the list implementation of sort.

I think he meant if you don''t need std::list, use vector, deques, etc. Those would be faster to sort using std''s algorithm. But if you use std::list, use the std::list''s member function std::list::sort() instead of std::sort( mylist.begin(), mylist.end(), whatever );

##### Share on other sites
quote:
Original post by Paralax
Nearly correct.

From where I stand, that was completely correct. The question was how to sort a list of pointers, not whether it should be a list to begin with. godballz showed how to use the list::sort method correctly.

quote:

std::list has its own sort implementation which either sorts by operator or a Compare predicate:

1: void sort();
2: template void sort(greater pr);

If lists are not necessary (e.g. you don''t have much insertions and removes running in time critical moments) I''d tend to use std::stable_sort from algorithm in favour of the list implementation of sort.

Why would use use stable_sort instead of sort by default? stable_sort is slower, so if you don''t need your data to be stable, don''t use it.

##### Share on other sites
You can''t use std::sort with list iterators as these don''t have the demanded random access property.
but apart from that, yes

##### Share on other sites
quote:
Original post by Stoffel
Why would use use stable_sort instead of sort by default? stable_sort is slower, so if you don''t need your data to be stable, don''t use it.

According to Stroustroup sort is efficient on average (O(n*log(n)) but worst case is O(n*n)

stable_sort on the other hand has a complexity of =(n*log(n)*log(n)) which in case the system has enough memory can be improved towards O(n*log(n))

It may not be important that the data is stable but I''m concerned about std::sort()''s worst case scenario.

Of course it depends on your data and on your needs whter you should use std::sort() or std::stable_sort()

Regards.

coder at Speckdrumm demo division
http://speckdrumm.schlucken.org

##### Share on other sites
std::stable_sort did better than std::sort on my AMD machine, and vice versa on my PIII. Or was it the memory instead of the processor?

PIII - 256mb vs. Athlon2G 512mb

I also tried a home grown MergeSort (stable) and qsort, and got the same result: the AMD machine stable sort better, whereas the pentium one gave the expected result: stable sort is slower.

What''s going on?

##### Share on other sites
Well now that you mention that I have no idea. I thought that since stable_sort is more constrained than sort, it would have to be slower. Did you use the same sequence for the tests?

##### Share on other sites
Yes, I used the same sequence. I used Win2000 and compiled with both VC6 and VC7 (not favoring any processors, of course). the program generates a sequence of randomized longs and then sorts the copy of the sequence using all the sorting versions.

My profiler can''t seem to go to the standard library (it can''t go to codes on .h files), which prevents me from looking deeper.

This really bothers me. I know I should use std::sort if I don''t need it to be stable. But the other day my colleage came to my desk and brought up the exact same issue: "Hey, you know, I used stable_sort and it''s much faster than sort, do you know why?" (He''s also using an AMD machine.) I''m supposed to be the guy to go to in times of trouble in my team and I couldn''t answer him.

I tried to convince him to use the non stable sort as most of our users uses pentiums presumably, but since his performance report to our leader is measured on his AMD machine, I couldn''t convince him. Oh the drama of team development.

1. 1
Rutin
19
2. 2
JoeJ
15
3. 3
4. 4
5. 5

• 24
• 20
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631699
• Total Posts
3001776
×