Jump to content
  • Advertisement
Sign in to follow this  
kittycat768

Sorting a vector multipled times using sort

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was reading a thread about display modes when somebody made a post about EnumDisplaySettings(); I'm familiar with the concept because it's really the only way to get a display mode in XLib. I wrote a simple program to spit out what display modes my video card supports and suffice it to say the items don't come out sorted to my criteria. I can sort once by the width factor but I can't figure out how to sort the vector again to sort the heights from lowest to highest while keeping the previous sort intact. And example of thing is how spreadsheets do it. When I sort a second time the first criteria gets thrown out the window. My goal is to sort them from lowest to highest width -> height -> bitsperpixel -> refresh rate.
#include <windows.h>
#include <vector>
#include <algorithm>

bool UDSort1(DEVMODE, DEVMODE);
bool UDSort2(DEVMODE, DEVMODE);



int WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
	std::vector<DEVMODE> ModeList;
	std::vector<DEVMODE>::iterator Iter;
	DEVMODE Mode;
	unsigned int i = 0;

	while(EnumDisplaySettings(0, i, &Mode))
	{
		ModeList.push_back(Mode);
		i++;
	}

	sort(ModeList.begin(), ModeList.end(), UDSort1);
	sort(ModeList.begin(), ModeList.end(), UDSort2);


	// Print list of display modes
	for(Iter = ModeList.begin(); Iter != ModeList.end(); Iter++)
	{
		printf("%ix%ix%i@%i\n", (unsigned int)Iter -> dmPelsWidth, (unsigned int)Iter -> dmPelsHeight, (unsigned int)Iter -> dmBitsPerPel, (unsigned int)Iter -> dmDisplayFrequency);
	}

	ModeList.clear();

	return 0;
}



bool UDSort1(DEVMODE d1, DEVMODE d2)
{
	return d1.dmPelsWidth < d2.dmPelsWidth;
}



bool UDSort2(DEVMODE d1, DEVMODE d2)
{
	if((d1.dmPelsWidth == d2.dmPelsWidth) && (d1.dmPelsHeight < d2.dmPelsHeight)) return 1;
	return 0;
}

Share this post


Link to post
Share on other sites
Advertisement
You can do it in one sort. Change your comparison function to handle tied values appropriately. You can test if a member is equal, and if so, go on and test the next member, and keep doing so until you have tested all the members. (When I say members, I mean members of the object which influence the sorting, starting with the members with highest sorting priority first and ending with members with lowest sorting priority last). Change your comparison function into:

bool UDSort(DEVMODE d1, DEVMODE d2)
{
if (d1.dmPelsWidth == d2.dmPelsWidth)
{
if (d1.dmPelsHeight == d2.dmPelsHeight)
{
if (d1.bitsperpixel == d2.bitsperpixel)
{
return d1.refreshrate < d2.refreshrate;
}
else
{
return d1.bitsperpixel < d2.bitsperpixel;
}
}
else
{
return d1.dmPelsHeight < d2.dmPelsHeight;
}
}
else
{
return d1.dmPelsWidth < d2.dmPelsWidth;
}
}



Note I haven't tested this code, and I actually don't know what the bitsperpixel or refresh rate members are called, so I made them up.

Share this post


Link to post
Share on other sites
Quote:
Original post by MikeTacular
You can do it in one sort. Change your comparison function to handle tied values appropriately. You can test if a member is equal, and if so, go on and test the next member, and keep doing so until you have tested all the members. (When I say members, I mean members of the object which influence the sorting, starting with the members with highest sorting priority first and ending with members with lowest sorting priority last). Change your comparison function into:

*** Source Snippet Removed ***

Note I haven't tested this code, and I actually don't know what the bitsperpixel or refresh rate members are called, so I made them up.


Wow! That worked flawlessly. Thank you!

#include <windows.h>
#include <vector>
#include <algorithm>

bool UDSort(DEVMODE, DEVMODE);



int WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
std::vector<DEVMODE> ModeList;
std::vector<DEVMODE>::iterator Iter;
DEVMODE Mode;
unsigned int i = 0;

while(EnumDisplaySettings(0, i, &Mode))
{
ModeList.push_back(Mode);
i++;
}

// Sort ModeList by width -> height -> bpp -> hz from lowest to highest
sort(ModeList.begin(), ModeList.end(), UDSort);

// Print list of display modes
for(Iter = ModeList.begin(); Iter != ModeList.end(); Iter++)
{
printf("%ix%ix%i@%i\n", (int)Iter -> dmPelsWidth, (int)Iter -> dmPelsHeight, (int)Iter -> dmBitsPerPel, (int)Iter -> dmDisplayFrequency);
}

ModeList.clear();

return 0;
}



bool UDSort(DEVMODE d1, DEVMODE d2)
{
if(d1.dmPelsWidth == d2.dmPelsWidth)
{
if(d1.dmPelsHeight == d2.dmPelsHeight)
{
if(d1.dmBitsPerPel == d2.dmBitsPerPel) return d1.dmDisplayFrequency < d2.dmDisplayFrequency;
else return d1.dmBitsPerPel < d2.dmBitsPerPel;
}
else return d1.dmPelsHeight < d2.dmPelsHeight;
}
else return d1.dmPelsWidth < d2.dmPelsWidth;
}

Share this post


Link to post
Share on other sites
FWIW, here's the idiom I've most commonly seen for writing multidimensional comparisons:


bool MySort(MyStruct const& a, MyStruct const& b)
{
if(a.a < b.a) return true;
if(a.a > b.a) return false;
if(a.b < b.b) return true;
if(a.b > b.b) return false;
if(a.c < b.c) return true;
if(a.c > b.c) return false;
return (a.d < b.d);
}


It's all a matter of personal preference, though.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
FWIW, here's the idiom I've most commonly seen for writing multidimensional comparisons:

*** Source Snippet Removed ***
It's all a matter of personal preference, though.


Thanks for posting that. As I was writing my sample, I was getting tired of writing it all, plus it was getting hard to read. I'm definitely going to have to remember that style.

Share this post


Link to post
Share on other sites
I couldn't understand that at first but when I realize that the first two lines don't return at all if the values equal each other it all made sense. I'd say that's a very nice but hard to understand way of coding it. That and let's say the spreadsheet or w/e decided to sort in the opposite manner the < and > would be swapped. It'd require 2-3 x as much code but it'd be perfect.

Share this post


Link to post
Share on other sites
Quote:
Original post by kittycat768
I couldn't understand that at first but when I realize that the first two lines don't return at all if the values equal each other it all made sense. I'd say that's a very nice but hard to understand way of coding it.

That's the good and bad thing about idioms. Once you've understood it once you'll always understand it, but it might take you a bit the first time.

Share this post


Link to post
Share on other sites
... Finally, although writing a comparator that does all the criteria is the right way to solve this, the answer to the original question is to use std::stable_sort(). It works just like std::sort(), except that it preserves the original ordering of elements which are considered equal under the current comparison.

Share this post


Link to post
Share on other sites
I've become very impressed with sort. This is what I finally wound up with:

bool SortList[4] = { 0, 1, 0, 1 };
bool Sort_DEVMODE(DEVMODE, DEVMODE);

bool Sort_DEVMODE(DEVMODE d1, DEVMODE d2)
{
if(SortList[0])
{
if(d1.dmPelsWidth > d2.dmPelsWidth) return 1;
if(d1.dmPelsWidth < d2.dmPelsWidth) return 0;
}
else
{
if(d1.dmPelsWidth < d2.dmPelsWidth) return 1;
if(d1.dmPelsWidth > d2.dmPelsWidth) return 0;
}

if(SortList[1])
{
if(d1.dmPelsHeight > d2.dmPelsHeight) return 1;
if(d1.dmPelsHeight < d2.dmPelsHeight) return 0;
}
else
{
if(d1.dmPelsHeight < d2.dmPelsHeight) return 1;
if(d1.dmPelsHeight > d2.dmPelsHeight) return 0;
}

if(SortList[2])
{
if(d1.dmBitsPerPel > d2.dmBitsPerPel) return 1;
if(d1.dmBitsPerPel < d2.dmBitsPerPel) return 0;
}
else
{
if(d1.dmBitsPerPel < d2.dmBitsPerPel) return 1;
if(d1.dmBitsPerPel > d2.dmBitsPerPel) return 0;
}

if(SortList[3]) return d1.dmDisplayFrequency > d2.dmDisplayFrequency;
else return d1.dmDisplayFrequency < d2.dmDisplayFrequency;
}



int WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int)
{
std::vector<DEVMODE> ModeList;
std::vector<DEVMODE>::iterator Iter;
DEVMODE Mode;
unsigned int i = 0;

while(EnumDisplaySettings(0, i, &Mode))
{
ModeList.push_back(Mode);
i++;
}

// Sort ModeList by width -> height -> bpp -> hz from lowest to highest
sort(ModeList.begin(), ModeList.end(), Sort_DEVMODE);

// Print list of display modes
for(Iter = ModeList.begin(); Iter != ModeList.end(); Iter++)
{
printf("%ix%ix%ibpp@%ihz\n", (int)Iter -> dmPelsWidth, (int)Iter -> dmPelsHeight, (int)Iter -> dmBitsPerPel, (int)Iter -> dmDisplayFrequency);
}

ModeList.clear();

return 0;
}



bool Sort_DEVMODE(DEVMODE d1, DEVMODE d2)
{
if(SortList[0])
{
if(d1.dmPelsWidth > d2.dmPelsWidth) return 1;
if(d1.dmPelsWidth < d2.dmPelsWidth) return 0;
}
else
{
if(d1.dmPelsWidth < d2.dmPelsWidth) return 1;
if(d1.dmPelsWidth > d2.dmPelsWidth) return 0;
}

if(SortList[1])
{
if(d1.dmPelsHeight > d2.dmPelsHeight) return 1;
if(d1.dmPelsHeight < d2.dmPelsHeight) return 0;
}
else
{
if(d1.dmPelsHeight < d2.dmPelsHeight) return 1;
if(d1.dmPelsHeight > d2.dmPelsHeight) return 0;
}

if(SortList[2])
{
if(d1.dmBitsPerPel > d2.dmBitsPerPel) return 1;
if(d1.dmBitsPerPel < d2.dmBitsPerPel) return 0;
}
else
{
if(d1.dmBitsPerPel < d2.dmBitsPerPel) return 1;
if(d1.dmBitsPerPel > d2.dmBitsPerPel) return 0;
}

if(SortList[3]) return d1.dmDisplayFrequency > d2.dmDisplayFrequency;
else return d1.dmDisplayFrequency < d2.dmDisplayFrequency;
}



I set it up as 0, 1, 0, 1 just to test if it actually worked and it did. 0 is ascending order and 1 is descending order.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
FWIW, here's the idiom I've most commonly seen for writing multidimensional comparisons:

*** Source Snippet Removed ***
It's all a matter of personal preference, though.


Just curious, what do you think about this style:

bool MySort(MyStruct const& a, MyStruct const& b)
{
if (a.a != b.a)
return a.a < b.a;
if (a.b != b.b)
return a.b < b.b;
if (a.c != b.c)
return a.c < b.c;
return a.d < b.d;
}


One place this style can be useful is if the comparison function should return an int describing the order of the elements (like strcmp() does).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!