Archived

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

ziruz

stl list < pointer > and sorting = bad?

Recommended Posts

ziruz    122
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 this post


Link to post
Share on other sites
Washu    7829

        
#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 this post


Link to post
Share on other sites
Paralax    134
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 this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
Stoffel    250
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 this post


Link to post
Share on other sites
Paralax    134
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 this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
Stoffel    250
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 this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Cedric    158
From Sedgewick''s Algorithms

Quicksort:
- Unstable
- Worst: O(N²/2)
- Average: O(2N ln(N) )

Mergesort:
- Stable
- Always: O(N lg(N) )
- Use extra space proportional to N

He also mentions that quicksort can perform poorly on data that is practically sorted.

Obvious advice: try both and see which one is best for you. That''s what generic algorithms are for.

Cédric

Share this post


Link to post
Share on other sites
davepermen    1047
your profiler can''t handle .h files? weird, very weird..
simple solution: open the .h file, copy the code out of it into your cpp testfile, don''t include the .h file and profile:D

this is weird, very weird.. athons perform bether on the slower algo:D

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
DrPizza    160
quote:
Original post by cedricl
From Sedgewick''s Algorithms

Quicksort:
- Unstable
- Worst: O(N²/2)
- Average: O(2N ln(N) )

Mergesort:
- Stable
- Always: O(N lg(N) )
- Use extra space proportional to N

In general, maybe, but lists can be merge sorted with constant extra space.

Merge sort''s constant factors are typically better than other n log n sorts; it''s the space requirements that tend to hurt it.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Could someone with an access to both processors confirm my results? Or prove me wrong? I''m really curios on this. I used tried both VC6 and 7''s stl versions.

Share this post


Link to post
Share on other sites
Washu    7829
His question was on how to sort a list of pointers ( and not by memory address ) which i answered. However, on the std::sort vs std::stable_sort issue: Yes, stable_sort can fun faster than sort depending on the order of the data before the sort is executed, and available memory. And my materials state that if the worst case senario for sort is a priority, then using stable_sort is a good fall back.

[edited by - godballz on October 3, 2002 2:20:09 PM]

Share this post


Link to post
Share on other sites
ziruz    122
sorry, the code from godballz doesnt work for me =(
i use msvc6sp5.

the compiler complains about:

error C2661: ''sort'' : no overloaded function takes 3 parameters

thanks any way to every one that tries to help me... and i cant just use an array because the data is quite dynamic =/

//ziruz

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

Share this post


Link to post
Share on other sites
Stoffel    250
Wow, there are some errors with that code, but I think you''re out of luck with MSVC6.0. Looks like MSVC STL does something pretty un-swift once again. In list.:
typedef greater<_Ty> _Pr3;
void sort(_Pr3 _Pr)

So basically you can''t make it work. If you have the next rev (VS.NET), the following code works:

  
#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>());
}


HTTP 500 retry #1..

Share this post


Link to post
Share on other sites