Sorting multiple properties are inverting items
I am trying to implement sorting multiple properties on some data and came up to the problem by going backwards stable_sorts
:
bool DecreasingA(const Data & a, const Data & b) {
return a.A >= b.A;
}
bool DecreasingB(const Data & a, const Data & b) {
if (a.B)
return true; // if a.B is true, maintain ordering
if (b.B)
return false; // a.B is false, but b.B is true, to swap elements
return true; // a.B and b.B are false, maintain ordering
}
std::vector<Data> myVector;
// add Data to vector here
std::stable_sort(myVector.begin(), myVector.end(), DecreasingA());
std::stable_sort(myVector.begin(), myVector.end(), DecreasingB());
But after that, myVector
has property A in reverse order which I want. Although it was correctly sorted after the firststable_sort
Example:
Before sorting:
A B C
1 0 5
1 1 8
2 0 2
0 1 3
After the first sort (decreasing A) looks good:
A B C
2 0 2
1 0 5
1 1 8
0 1 3
After the second sort (decrementing B), I get this:
A B C
0 1 3
1 1 8
1 0 5
2 0 2
Instead of what I want:
A B C
1 1 8
0 1 3
2 0 2
1 0 5
I think this is a problem with my function DecreasingB
, but I've tried all sorts of logics and keep getting this inversion. Any suggestions?
I know I can write one comparison function to handle this particular situation, but I need the end user to be able to choose which properties to sort and in what order they are applied.
source to share
Your comparison functions are broken. None of these follow the strict strict ordering required std::stable_sort
. In particular,
- Irreflexive:
f(x, x)
Must be false. - Antisymmetry:
f(x, y)
means!f(y, x)
Your features don't work on both accounts.
You probably want this:
bool DecreasingA(const Data & a, const Data & b) {
return a.A > b.A; // > instead of >=
}
bool DecreasingB(const Data & a, const Data & b) {
if (a.B == b.B) // both equal, so a does not precede b
return false;
if (b.B) // b.B is true and a.B is false, so a does not precede b
return false;
return true; // a.B is true and b.B is false, so a does precede b
}
source to share
You can just write DecreasingBThenA
#include <algorithm>
#include <tuple>
#include <vector>
#include <iostream>
struct Data
{
int A, B, C;
};
bool DecreasingBThenA(const Data & a, const Data & b)
{
return std::tie(a.B, a.A) > std::tie(b.B, b.A);
}
int main()
{
auto myVector = std::vector<Data>
{{ 1, 0, 5}, {1, 1, 8}, {2, 0, 2}, {0, 1, 3}};
std::stable_sort(myVector.begin(), myVector.end(), DecreasingBThenA);
for (auto&& t : myVector)
std::cout << "{" << t.A << ", " << t.B << ", " << t.C << "}\n";
}
A live example that gives the desired result.
If you have N
items in Data
, and you want to be able to execute arbitrary sorting, then you really only need DecreasingA
through DecreasingN
comparisons (each returns a.X > b.X
to the data item X
), and then perform multiple passes using a std::sort
reverse order of criteria that you want to sort. Therefore, it BThenA
requires first sorting by A
, then by B
. This is the same as sorting data in Excel on different columns at the same time using the sort by column button.
source to share