In C# given a struct:
struct Point {int x, int y}
We can write something like:
List<Point> list;
list.OrderBy(p => p.x).ThenBy(q => q.y);
How can I express this logic in C++ using lambda functions?
4 Answers
It looks too me like you want a lexicographic sort on (y, x)1. You can leverage the library function std::tie. That one returns a tuple of references, and a std::tuple has a less-than operator which performs lexicographic comparison. So you only need to specify the order in which you want the items compared.
Here's how it would look for std::vector (your go to container type in C++, always start with std::vector):
std::vector<Point> my_list;
// Fill my_list
std::sort(begin(my_list), end(my_list), [](auto const& l, auto const& r){
return std::tie(l.y, l.x) < std::tie(r.y, r.x);
});
1 - I'm basing this on the method names only, so this may not be what you are really after.
answered Jan 10, 2018 at 8:25
StoryTeller - Unslander Monica
172k22 gold badges401 silver badges481 bronze badges
5 Comments
n. m. could be an AI
Python lists are more similar to C++ vectors than linked lists.
StoryTeller - Unslander Monica
@n.m.- What about C# lists? The OP asked based on that. I'm not familiar with C# too well myself.
StoryTeller - Unslander Monica
@Aconcagua - Amended answer accordingly. Thank you!
n. m. could be an AI
My bad, assumed Python wrongly but apparently C# lists are also more like vectors.
You can use STL function std::sort. Example:
struct point{
int x;
int y;
};
// Compare function. This can be lambda function too.
bool comp(const point& a,const point& b){
if(a.x > b.x) return true;
else if(a.x == b.x) return a.y > b.y;
return false;
}
int main(){
// v is vector (or any other container which can be iterated) containing points
std::sort(v.begin(),v.end(),comp);
}
7 Comments
Federico
You just sorted by x in this way. You should add
If(a.x==b.x) return a.y>b.y; i guess.
Mayank Jain
Yes. I just wrote some dummy compare function. But I will add the code as per your suggestion for clarity.
n. m. could be an AI
((a.x > b.x) and (a.y > b.y)) is a wrong and dangerous comparison, not suitable for sorting.Mayank Jain
@n.m. It would be great if you can explain me a bit on when can it go wrong.
Benjamin Lindley
Consider the case where
a.x > b.x, but a.y < b.y. Your function will return false for both comp(a, b) and comp(b, a), which indicates that a and b should be considered equal. But they clearly should not. |
Two ways - either you sort twice, first by y, then use a stable sort on x (be aware that this is exactly inverse as in C#!). Bad luck with std::sort, though, as it is not stable, fortunately, as Benjamin hinted to, there is std::stable_sort, too...
The other way is making sure that two points compare such that a difference in x applies first and only in case of equality, y is considered:
std::sort
(
// range to sort
list.begin(), list.end(),
// next the comparator - you wanted a lambda? OK, here it is:
[](point const& a, point const& b)
{
return a.x < b.x || a.x == b.x && a.y < b.y;
}
);
2 Comments
Benjamin Lindley
std::sort may not be stable, but there is another function in the standard library that is. Curiously named std::stable_sort.
Aconcagua
@BenjaminLindley Thanks for the hint. Didn't cope much for the first approach as I consider the second one superior anyway...
You just need to specify the lambda function to std::list::sort().You decide how you want to sort.
list.sort([](Point i,Point j)
{
if(i.x!=j.x)
return i.x<j.x;
else
return i.y<j.y;
}
);
2 Comments
user2807083
You'd better use
const Point &
Kira M. Backes
@user2807083 Actually no, in this case Point is sizeof == 8 on x64 systems, so copying it is better than using a reference
xand then byy?