对C++中的Sort比较方法感到困惑

Question

我尝试了两种比较方法，都没有得到预期的结果。第一种比较方法在自定义的class里面MyTreeNodeasoperator<；第二个是新的比较 class compare 与覆盖方法 operator()(MyTreeNode*) 。

代码如下所示。两个输出都是：

 5 6 1

而预期的顺序应该是 1 5 6。排序的规则是：如果两个节点的x相同，则y值大的节点在前。如果节点 x 和 y 都相等，则 treeNode->val 较少的节点排在第一位。

所以，谁能帮我解释一下？谢谢

#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 ;});
  //}

}
```

Answer 1

1。如果你想颠倒顺序，这样

the node with a larger y value comes first,

您应该颠倒比较器中的顺序。即，而不是 node2->y > node1->y（相当于node1->y < node2->y）你应该写node2->y < node1->y.

2。请注意，行 sort(trees.begin(), trees.end()); 将按指针值 ^* 而非元素值对元素进行排序。不会使用运算符 MyTreeNode::operator< - MyTreeNode* 值之间的比较不会神奇地转换为取消引用的 MyTreeNode 值之间的比较。那不是你想要的。使用自定义比较器，如您的解决方案 2.

如果你定义MyTreeNode::operator<，那么你可以使用一个简单的lambda作为比较器：

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

^* std::sort 使用 operator< 比较元素。两个不相关的指针（不指向同一数组的元素）之间的 < 比较是 . std::less 应该用作自定义比较器以避免 UB，即使你想按它们的值对指针进行排序（地址）。

对C++中的Sort比较方法感到困惑

Puzzled by Sort comparison method in C++

c++

sorting

comparison