C ++ набор с компаратором для сортировки и другой для уникальности

Question

Edge - это класс с 3 полями: weight, from_vertex, to_vertex.Я хочу создать набор, содержащий все уникальные ребра на графике.(Если from_vertex и to_vertex поменялись местами - и веса равны - это все тот же край.) Кроме того, я хочу, чтобы этот набор был отсортирован по весам ребер.Это возможно при реализации набора или есть лучший способ?

Answer 1

Конечно, это возможно.Но только потому, что вам на самом деле не нужны два компаратора.

Основная идея заключается в лексической сортировке кортежа <weight, min_vertex, max_vertex>, где min_vertex - это меньшее из to_vertex или from_vertex, и max_vertex больше.Конечно, два противоположных ребра с одинаковым весом будут иметь одинаковый кортеж, а два противоположных ребра без одинакового веса будут различаться.Набор будет в целом отсортирован по весу, так как это наиболее значимый элемент кортежа.

Одна вещь, которую этот не дает вам, - это возможность поиска ребра, если вызнаю from,to, но не знаю вес.Точно так же он не делает все ребра для конкретной пары from,to последовательными (что, конечно, было бы несовместимо с сортировкой по весу).Если вы хотите такого рода вещи, вам, вероятно, потребуется поддерживать несколько структур.