Проблемы с переопределением оператора less для уникальных элементов набора

Question

У меня есть следующий класс с тремя переменными-членами.

Edge::Edge(Vertex v1, Vertex v2, float initialCost)
{
    if (v1.getId() < v2.getId()) {
        _v1 = v1;
        _v2 = v2;
    } else {
        _v1 = v2;
        _v2 = v1;
    }
    _cost = initialCost;
}

И оператор <, определенный как таковой </p>

bool operator<(const Edge &lhs, const Edge &rhs) {
    return (lhs._v1.getId() != rhs._v1.getId() || lhs._v2.getId() != rhs._v2.getId()) && lhs._cost < rhs._cost;
}

Вот как раскладывается класс вершин

Vertex::Vertex(int id)
{
   // _position = position;
    _id = id;
}

int Vertex::getId() {
    return _id;
}

Я реализую это следующим образом в наборе.

        set<Edge> test = set<Edge>();

        Vertex v0 = new Vertex(0);
        Vertex v1 = Vertex(1);
        Vertex v2 = Vertex(2);
        Vertex v3 = Vertex(3);
        Vertex v4 = Vertex(4);
        Vertex v5 = Vertex(5);

        Edge e1(v0, v1, 0.2);
        Edge e2(v1, v2, 0.4);
        Edge e3(v2, v3, 0.7);
        Edge e4(v3, v4, 0.6);
        Edge e5(v4, v3, 0.6);
        Edge e6(v4, v5, 0.3);
        Edge e7(v4, v1, 0.4);

        test.insert(e1);
        test.insert(e2);
        test.insert(e3);
        test.insert(e4);
        test.insert(e5);
        test.insert(e6);
        test.insert(e7);
        Edge e(v1, v2, 0.0);
        cout << "ERASING" << endl;
        test.erase(e);
        cout << "DONE" << endl;

Я бы ожидал, что оператор erase внизу только сотрет e2 из набора. Мне нужно иметь возможность стереть элементы в наборе на основе их вершин без указания их стоимости.

На самом деле происходит то, что каждое ребро, кроме e3 и e4, удаляется из набора , Если я не вызываю стирание, я получаю ожидаемое поведение (только те ребра с одинаковыми вершинами считаются дубликатами). Почему это происходит?

Answer 1

Оператор сравнения для уникальных контейнеров должен отвечать всем требованиям для строгого слабого заказа. Чтобы упростить основное требование, в некоторой степени строгое слабое упорядочение означает, что: 1) если a<b истинно и 2) b<c верно, то 3) a<c также должно быть истинно.

Ваш < оператор нарушает это правило. Нетрудно придумать три Edge с, которые нарушат это правило, например:

Edge    v1->getId()    v2->getId()    cost
 A:        1              2            10
 B:        3              4            11
 C:        1              2            12

Ваш оператор < вернет true для A<B и true для B<C, но ложно для A<C.

Answer 2

std::set требует от вашего operator< строгого слабого порядка . Ваш operator< не работает, потому что для двух Edges a и b оба значения a < b и b > a могут быть истинными, даже если a != b.

bool operator<(const Edge &lhs, const Edge &rhs) {
    return (lhs._v1->getId() != rhs._v1->getId() || lhs._v2->getId() != rhs._v2->getId()) && lhs._cost < rhs._cost;
}

Возвращает true для любых двух Edges, чьи _v1 имеют разные идентификаторы.