Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
31 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to General and Gameplay Programming

stl list < pointer > and sorting = bad?

Started by
15 comments, last by ziruz 21 years, 6 months ago
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;
	}

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

        #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]

In time the project grows, the ignorance of its devs it shows, with many a convoluted function, it plunges into deep compunction, the price of failure is high, Washu's mirth is nigh.

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]
coder at Speckdrumm demo divisionhttp://speckdrumm.schlucken.org
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 );



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.
You can''t use std::sort with list iterators as these don''t have the demanded random access property.
but apart from that, yes
coder at Speckdrumm demo divisionhttp://speckdrumm.schlucken.org
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
coder at Speckdrumm demo divisionhttp://speckdrumm.schlucken.org
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?
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?
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.

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
Jikoob
Too many managers? General and Gameplay Programming
ReignOnU
Do your part to stop global warming and climate change GDNet Lounge
Konjointed
C++ how do you use dependency injection? For Beginners
aigan
The promise of freedom in story games Game Design and Theory
robertrobert
Facebook Ads for sales on steam, does it work? Games Business and Law
Advertisement

Recommended Tutorials

diligentcircle
You Don't Need to Hide Your Source Code Business and Law
Myopic Rhino
Data Compression Algorithms of LARC and LHarc General and Gameplay Programming
Myopic Rhino
Games Middleware in a Changing Market Engines and Middleware
RRAway
Standard Gameplay and IAP Metrics for Mobile Games General and Gameplay Programming
Myopic Rhino
Dynamic 3D Scene Graphs Graphics and GPU Programming

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top