как отсортировать вектор пар?

Question

Я пытаюсь отсортировать вектор по pair<int, T> (где 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

Предоставьте свою собственную функцию сравнения (или функтор) в качестве последнего аргумента 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 2

Опубликованный код не компилировался, но когда я пытался его скомпилировать, я заметил, что вы, вероятно, хотите:

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 3

Похоже, что это функции-члены шаблона класса. Если это так, то sortlevel должен быть статическим (или не являющимся членом), чтобы использоваться в качестве компаратора в std::sort().

Кроме того, вы написали, например, order[x]->first в некоторых местах, когда должно быть order[x].first.

Answer 4

Если вы начинаете с:

#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<int, T>, вызовет:

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

   int x;
};

• Ошибки, которые вы, вероятно, получали
• Хороший результат

Answer 5

Всякий раз, когда вы используете T, вам нужно убедиться, что он входит в класс или функцию с template<typename T> перед ним.

в вашем коде:

• вам нужно template<typename T> до определения sortlevel, get_level и level_order
• при вызове sort вам нужно классифицировать sortlevel<T>.
• при вызове этих функцийНазовите их с фактическим типом.