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

Question

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

У меня есть структура графика, которая использует узлы (вершины), которые, в свою очередь, имеют края, прикрепленные в виде 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, но это было бы довольно дорого с точки зрения эффективности, поэтому мне было интересно, есть ли другой путь.

4

c++cross-reference forward-declaration graph

Решение

Другие решения

Делать 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);

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

3

Источник

Accepted Answer

Вы можете сделать это так:

#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, для объявления — нет, нужно только знать о существовании структуры с таким именем:

Форвард объявить Node как структуру (необходимо для объявления EdgeComparator)
Объявите EdgeComparator без определения оператора () (который должен знать о члене Node :: n)
Объявить и определить узел
Определить EdgeComparator :: operator ()

6