Предварительная декларация набора Comparator - PullRequest
Новая
       9

Предварительная декларация набора Comparator

0 голосов
/ 11 мая 2018

У меня есть структура графика, в которой используются узлы (вершины), которые, в свою очередь, имеют ребра, присоединенные в форме std::pair<Node*, int>, где узел - это другой конец ребра, а целое число - вес ребра. Я бы хотел, чтобы ребра были отсортированы в std::multiset на основе индекса подключенного узла и веса ребра. 

enum color { white, grey, black };

struct EdgeComparator;

struct Node {
  int n;
  std::multiset<std::pair<Node *, int>, EdgeComparator> edges;
  enum color col;
  int d;  // distance to source node

  explicit Node(int n) : n(n), edges(), col(white), d() {};
};

struct EdgeComparator {
  bool operator()(const std::pair<Node *, int> &p1,
                  const std::pair<Node *, int> &p2) {
    if (p1.second == p2.second)
      return p1.first->n < p2.first->n;
    return p1.second < p2.second;
  }
};

При таком подходе прямого объявления возникает ошибка: invalid use of incomplete type struct EdgeComparator. Если я попытаюсь переключить их и объявить узел Node вместо EdgeComparator, поле n больше не будет отображаться для EdgeComparator, поэтому я столкнулся с замкнутым кругом.

Единственный обходной путь, о котором я подумал, - это использовать std::vector вместо std::multiset, а затем применить std::sort, но это будет довольно дорого с точки зрения эффективности, поэтому мне было интересно, есть ли другой способ.

Ответы [ 2 ]

0 голосов
/ 11 мая 2018

Вы могли бы сделать это так: 

#include <set>

enum color { white, grey, black };

struct Node;

struct EdgeComparator {
  bool operator()(const std::pair<Node *, int> &p1,
              const std::pair<Node *, int> &p2);
};

struct Node {
  int n;
  std::multiset<std::pair<Node *, int>, EdgeComparator> edges;
  enum color col;
  int d;  // distance to source node

  explicit Node(int n) : n(n), edges(), col(white), d() {};
};

bool EdgeComparator::operator()(const std::pair<Node *, int> &p1,
              const std::pair<Node *, int> &p2) {
  if (p1.second == p2.second)
    return p1.first->n < p2.first->n;
  return p1.second < p2.second;
}

Это прекрасно скомпилировано на моей стороне.Причина в том, что вы разделяете декларацию и определение.Для определения EdgeComparator :: operator () требуется конкретная структура Node, для объявления - нет, нужно только знать о существовании структуры с таким именем:

  1. Форвард объявляет Node как структуру(необходимо для объявления EdgeComparator)
  2. Объявить EdgeComparator без определения оператора () (который должен знать о члене Node :: n)
  3. Объявить и определить Node
  4. Определить EdgeComparator :: operator ()
0 голосов
/ 11 мая 2018

Сделать EdgeComparator аргументом шаблона.

Во-первых, это решает вашу ситуацию. Во-вторых, это имеет смысл и позволяет вам предоставить другой тип компаратора. 

template<class TEdgeComparator>
struct Node {
  int n;
  std::multiset<std::pair<Node *, int>, TEdgeComparator> edges;
  // ...
};

struct EdgeComparator {
  bool operator()(const std::pair<Node *, int> &p1,
                  const std::pair<Node *, int> &p2) {
    if (p1.second == p2.second)
      return p1.first->n < p2.first->n;
    return p1.second < p2.second;
  }
};

Node<EdgeComparator> myNode(42);

Но имейте в виду, что у узла , содержащего , набор ребер - красный флаг. Вы уверены в своем дизайне?

...