Озадачен методом сравнения сортировки в C ++

Question

Я попробовал два метода сравнения, но не получил ожидаемого результата. Первый метод сравнения находится внутри настроенного класса MyTreeNode как operator<; Второй - это новый класс сравнения 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. Если вы хотите изменить порядок так, чтобы

узел с большим значением y был первым,

, вы должны изменить порядок в компараторе. А именно, вместо 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<, то вы можете использовать простую лямбду в качестве компаратора:

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

---

^* std::sort использует operator< для сравнения элементов. Сравнение < между двумя несвязанными указателями (которые не указывают на элементы одного и того же массива) является неопределенным поведением . std::less следует использовать в качестве пользовательского компаратора, чтобы избежать UB, даже если вы хотите отсортировать указатели по их значениям (адресам).