2

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?

John Tan
  • 1,331
  • 1
  • 19
  • 35

4 Answers4

7

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.

StoryTeller - Unslander Monica
  • 165,132
  • 21
  • 377
  • 458
1

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);
}
Mayank Jain
  • 2,504
  • 9
  • 33
  • 52
  • 1
    You just sorted by x in this way. You should add `If(a.x==b.x) return a.y>b.y;` i guess. – Federico Jan 10 '18 at 08:23
  • Yes. I just wrote some dummy compare function. But I will add the code as per your suggestion for clarity. – Mayank Jain Jan 10 '18 at 08:24
  • 2
    `((a.x > b.x) and (a.y > b.y))` is a wrong and dangerous comparison, not suitable for sorting. – n. m. could be an AI Jan 10 '18 at 08:41
  • @n.m. It would be great if you can explain me a bit on when can it go wrong. – Mayank Jain Jan 10 '18 at 08:43
  • 2
    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. – Benjamin Lindley Jan 10 '18 at 08:44
  • Thanks!. I changed it. – Mayank Jain Jan 10 '18 at 08:47
  • Just a slight remark for performance: as equality is probably the least frequent case you could put it last in the if/else suite for a slightly more efficient comparison, and use ternary operator which is very readable for simple expressions like these (this is just a suggestion, I like if/else). So that would be `return (a.x < b.x) ? true : (a.x > b.x) ? false : (a.y > b.y);` – Francis Pierot Apr 23 '22 at 07:37
1

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;
    }
);
Aconcagua
  • 24,880
  • 4
  • 34
  • 59
  • `std::sort` may not be stable, but there is another function in the standard library that is. Curiously named `std::stable_sort`. – Benjamin Lindley Jan 10 '18 at 08:50
  • @BenjaminLindley Thanks for the hint. Didn't cope much for the first approach as I consider the second one superior anyway... – Aconcagua Jan 10 '18 at 08:55
0

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;
             }
          );
Gaurav Sehgal
  • 7,422
  • 2
  • 18
  • 34