Предварительная декларация набора 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, но это было бы довольно дорого с точки зрения эффективности, поэтому мне было интересно, есть ли другой путь.
Решение
Вы можете сделать это так:
#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 ()
Другие решения
Делать 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);
Но имейте в виду наличие узла содержащий коллекция ребер — это красный флаг. Вы уверены в своем дизайне?