c++ - 如何对成对的 vector 进行排序？

Question

我正在尝试对 pair<int, T> 的 vector 进行排序(其中 T 是类的模板化值类型)和代码块给了我大量错误，我不明白为什么。是否需要一些特殊的语法来排序 vector<pair<int, T> > ？我确实做了比较函数，完全没有使用T

这是代码

  bool sortlevel(pair<int, T> a, pair<int, T> b){
    return a.first < b.first;
  }

  void get_level(Node<T> * root, vector <pair<int, T> > & order, int level = 0){
    // changes the tree to a vector
    if (root){
        order.push_back(pair(level, root -> value));
        get_level(root -> left, order, level + 1);
        get_level(root -> right, order, level + 1);
    }
  }

  void level_order(ostream & ostr ) {
    vector<pair<int, T> > order;
    get_level(root_, order);
    sort(order.begin(), order.end(), sortlevel);
    int max_level = order[order.size() - 1] -> first;
    int x = 0;
    int current_level = order[x] -> first;
    while (x < order.size()){
        for(int y = 0; y < current_level - x; y++)
            cout << "\t";
        while (order[x] -> first == current_level){
            cout << order[x] -> second << " ";
            x++;
        }
    }
  }

Answer 1

发布的代码没有编译但是当我试图让它编译时我注意到你可能想要:

order.push_back(std::make_pair(level, root -> value));

还有:

int max_level = order[order.size() - 1]. first;

你的这个固定版本为我编译:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class T
{};

template <class T> class Node
{
public:
T value;
Node<T>* left;
Node<T>* right;
};

Node<T>* root_;

bool sortlevel(pair<int, T> a, pair<int, T> b){
    return a.first < b.first;
  }

  void get_level(Node<T> * root, vector <pair<int, T> > & order, int level = 0){
    // changes the tree to a vector
    if (root){
        order.push_back(std::make_pair(level, root -> value));
        get_level(root -> left, order, level + 1);
        get_level(root -> right, order, level + 1);
    }
  }

  void level_order(ostream & ostr ) {
    vector<pair<int, T> > order;
    get_level(root_, order);
    sort(order.begin(), order.end(), sortlevel);
    int max_level = order[order.size() - 1]. first;
    int x = 0;
    int current_level = order[x].first;
    while (x < order.size()){
        for(int y = 0; y < current_level - x; y++)
            cout << "\t";
        while (order[x]. first == current_level){
//            cout << order[x]. second << " ";
            x++;
        }
    }
  }

这部分是在完整代码发布之前发布的，但对于试图弄清楚排序的人可能仍然有用，所以我将其保留在:通常对于排序，您可能需要提供一种比较对的方法，例如看这里: http://www.cplusplus.com/reference/algorithm/sort/

如果您使用排序算法，它会自动对任何定义了小于运算符但对其他类型无效的事物起作用。

std::pair 应该提供一个默认的小于运算符，所以可能还有另一个问题——我们能看到代码吗？正如 Tomalak 指出的那样，这可能是因为您无法比较 T。