如何对向量对进行排序？

Question

我正在尝试对 pair 向量进行排序（其中 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 应该提供默认的小于运算符，所以也许还有另一个问题 - 我们可以看到代码吗？正如托马拉克所说，这可能是因为你无法比较 T。

Answer 2

提供您自己的比较函数（或函子）作为 sort 的最后一个参数。您的比较应该取其中的第一个并进行比较。

例如：

template<typename T>
bool myfunction (const pair<int, T>& i, const pair<int, T>& j)
{ 
   return (i.first < j.first); 
}

sort (myvector.begin(), myvector.end(), myfunction<ActualType>);

Answer 3

如果您从以下开始：

#include <vector>
#include <algorithm>

struct T {
   T(int x) : x(x) {};

   int x;
};

int main() {
   std::vector<std::pair<int, T> > v;

   std::pair<int, T> a = std::make_pair(0, T(42));
   std::pair<int, T> b = std::make_pair(1, T(36));

   v.push_back(a);
   v.push_back(b);

   std::sort(v.begin(), v.end());
}

为 T 添加比较器，则 std::pair 的默认生成的比较器将调用：

struct T {
   T(int x) : x(x) {};
   bool operator<(const T& other) const {
      return x < other.x;
   }

   int x;
};

• 您可能遇到的错误
• 好的结果< /a>

Answer 4

看起来这些是类模板的成员函数。如果是这种情况，则 sortlevel 将需要是静态的（或非成员）才能用作 std::sort() 中的比较器。

另外，您在一些地方编写了例如 order[x]->first ，而它应该是 order[x].first 。

Answer 5

每当您使用 T 时，您都需要确保它位于类或函数中，并且前面有 template 。

在您的代码中：

• 在定义 sortlevel、get_level 和 level_order 之前需要 template
• 调用时， sort 您需要对sortlevel进行分类。
• 调用这些函数时，请使用实际类型进行调用。