#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;
}
Sorting a vector multipled times using sort
Author
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.
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:
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.
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.
Author
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;}
FWIW, here's the idiom I've most commonly seen for writing multidimensional comparisons:
It's all a matter of personal preference, though.
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.
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.
Author
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.
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.
... 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.
Author
I've become very impressed with sort. This is what I finally wound up with:
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.
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.
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
