Std:: set имеет двойную запись

У меня есть набор кортежей из 3 целых чисел, и я не хочу дубликатов. То есть, я не хочу 2 записи с одинаковыми 3 значениями.

И вот мой код.

struct Key{
    unsigned a;
    unsigned b;
    unsigned c;
  public:
    Key(unsigned _a, unsigned _b, unsigned _c) :
        a(_a),
        b(_b),
        c(_c) {}
    bool operator<(const Key& rhs) const
    {
        if (a < rhs.a) {
            return true;
        }
        if (b < rhs.b) {
            return true;
        }
        if (c < rhs.c) {
            return true;
        }
        return false;
    };
};
std::set<Key> myset;

Но иногда я вижу дубликаты в myset. Я не могу точно понять, какая последовательность приводит к добавлению дублирующей записи. Это не всегда происходит. Мой вопрос в том, есть ли что-то внутренне неправильное с моей функцией operator<?

Ответы

Ответ 1

Это почти правильно! Но вы слишком быстро каскадируете.

bool operator<(const Key& rhs) const
{
    if (a < rhs.a)
        return true;
    if (a > rhs.a)
        return false;

    if (b < rhs.b)
        return true;
    if (b > rhs.b)
        return false;

    return (c < rhs.c);
};

В противном случае, например, следующий результат дает неправильный результат:

Key lhs{3,1,0};
Key rhs{2,2,0};

assert(lhs < rhs); // passes, wrongly, because !(3 < 2) but then (1 < 2).
                   // you need an immediate `return false` when !(3 < 2)

Безопаснее сделать что-то вроде этого:

bool operator<(const Key& rhs) const
{
    return std::tie(a, b, c) < std::tie(rhs.a, rhs.b, rhs.c);
}

Стандартная библиотека С++ уже знает, что с этим делать, поэтому вам не нужно.

Теперь, как ваша ошибка приведет к дублированию ключей в set?

Устанавливать внутренний алгоритм зависит от того, что упорядочение является строгим слабым порядком — когда вы нарушаете это предварительное условие, вы нарушаете алгоритмы, управляющие внутренним деревом, которое создается и упорядочивается с использованием этого упорядочения в качестве его библии.

Все ад разрывается, в основном. Вы можете получить от этого крах. В вашем случае симптомы были несколько более мягкими (по крайней мере на данный момент), с деформированным/искаженным деревом данных, что привело к появлению дублированных данных.

Неудивительно пытаться рассуждать о конкретной цепочке событий, которая привела к определенному результату, если вы начали с нарушения предварительных условий и вызвали UB.

Ответ 2

Ваш operator<() несовместим, так как key1<key2 и key2<key1 могут быть true (пример: key1={1,3,0}, key2={3,1,0}). Вы должны дать переменным-членам приоритет в сравнении:

    if (a < rhs.a) {
        return true;
    } else if (a == rhs.a) {
        if (b < rhs.b) {
            return true;
        } else if (b == rhs.b) {
            if (c < rhs.c) {
                return true;
            }
        }
    }
    return false;

Ответ 3

В качестве ключа вы действительно можете использовать стандартный класс std::tuple.

Тем не менее оператор можно определить следующим образом:

bool operator <( const Key &rhs ) const
{
    return
    ( a < rhs.a ) ||
    ( !( rhs.a < a ) && ( b < rhs.b ) ) ||
    ( !( rhs.a < a ) && !( rhs.b < b ) && ( c < rhs.c ) );
};

Чтобы этот оператор работал все, что вам нужно, это то, что для типа объектов a, b и c будет определен operator < Конечно, для арифметических типов он уже определен.

На самом деле это то же самое, что

#include <tuple>

//...

bool operator <( const Key &rhs ) const
{
    return std::tie( a, b, c ) < std::tie( rhs.a, rhs.b, rhs.c );
}