Puzzled by Sort comparison method in C++

Question

I tried two comparison methods, and did not get expected result. The first comparison method is inside of a customized class MyTreeNode as operator<; The second one is a new comparison class compare with an override method operator()(MyTreeNode*) .

The code is shown below. Both outputs are:

 5 6 1

while the expected order should be 1 5 6. The rule for the ordering is: If two nodes have the same x, then the node with a larger y value comes first. If nodes have equal both x and y, then the node with less treeNode->val comes first.

So, can anyone help explain it for me ? Thanks

#include <vector>
#include <cstddef>
#include <algorithm>
#include <iostream>

using namespace std;

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x) {}
  };


class MyTreeNode{
    public:
    TreeNode* treeNode;
    int x;
    int y;
    public: 
    MyTreeNode(TreeNode* node, int _x, int _y): treeNode(node), x(_x), y(_y){

    }
  //Solution 1. 
  bool operator<(MyTreeNode& node){
    if(x< node.x){
           return true;
       }
       if(x == node.x && y > node.y){
           return true;
       }
       if(x == node.x  && y == node.y
          &&treeNode->val<node.treeNode->val){
           return true;
       }
       return false;
    }

};

//Solution 2
class compare{
 public:
  bool operator()(MyTreeNode* node1, MyTreeNode* node2){
    if(node1->x < node2->x){
           return true;
       }
       if(node1->x == node2->x && node2->y > node1->y){
           return true;
       }
       if(node1->x == node2->x  && node2->y == node1->y
          &&node1->treeNode->val<node2->treeNode->val){
           return true;
       }
       return false;
    }
};


int main(int argc, char* argv[]){
  //Solution so;

  vector<MyTreeNode*> trees;
  trees.push_back(new MyTreeNode(new TreeNode(5), 0, -2));   //A
  trees.push_back(new MyTreeNode(new TreeNode(6), 0, -2));   //Ｂ
  trees.push_back(new MyTreeNode(new TreeNode(1), 0, 0));   //C

  //Solution 1
  sort (trees.begin(), trees.end());

  //Solution 2
  //sort (trees.begin(), trees.end(), compare());    // print 5 6 1 

  //  for(int i=0; i<res.size(); i++){
  for_each(trees.begin(), trees.end(), [](const MyTreeNode* ele){cout<< " "<< ele->treeNode->val ;});
  //}

}
```

According to your rules for sorting in the paragraph above your code, you don't explain what to do if `x` are not equal. From your code it appears that you sort primarily on x, then on y (reversed), then on val. — JohnFilleau, Apr 25 '20 at 12:00

Evg · Accepted Answer · 2020-04-25T12:46:04.113

1. If you want to reverse the order so that

the node with a larger y value comes first,

you should reverse the order in the comparator. Namely, instead of node2->y > node1->y (which is equivalent to node1->y < node2->y) you should write node2->y < node1->y.

2. Note that the line sort(trees.begin(), trees.end()); will sort elements by their pointer values^*, not by element values. The operator MyTreeNode::operator< won't be used - comparison between MyTreeNode* values won't be magically translated into comparison between dereferenced MyTreeNode values. That's not what you want. Use a custom comparator, as in your solution 2.

If you define MyTreeNode::operator<, then you can use a simple lambda as a comparator:

std::sort(trees.begin(), trees.end(), [](auto n1, auto n2) { return *n1 < *n2; });

^* std::sort uses operator< to compare elements. The < comparison between two unrelated pointers (which do not point to elements of the same array) is undefined behaviour. std::less should be used as a custom comparator to avoid UB even if you want to sort pointers by their values (addresses).

So how should I override the `operator<` in `MyTreeNode` so that it would be applicable to `sort(begin(), end())` automatically? Thanks — shijie xu, Apr 25 '20 at 12:09

Puzzled by Sort comparison method in C++

1 Answers1