Блог

Главная - Вопросы по программированию - оператор перегрузки < для std:: set меня смутил

оператор перегрузки < для std:: set меня смутил

#c #algorithm #sorting #set #std

#c #алгоритм #сортировка #set #std

Вопрос:

Я знаю, что я должен перегрузить operator < для std::set.

Я перегружаю operator < двумя классами: «UniqueID» и «UniqueIDWithBug». Единственное отличие заключается в том, что «UniqueID» добавлен в код this->unique_id_a_ == t.unique_id_a_ при сравнении.

Затем я поместил одинаковые элементы в два набора. Наконец-то я нахожу один элемент внутри наборов. Один набор может его найти, другой — нет. Эта проблема смущала меня долгое время.

 struct UniqueID {
    uint64_t unique_id_a_{0};
    uint64_t unique_id_b_{0};

    bool operator<(const UniqueID amp;t) const {
        if (this->unique_id_a_ < t.unique_id_a_) {
            return true;
        }
        if (this->unique_id_a_ == t.unique_id_a_ amp;amp;
            this->unique_id_b_ < t.unique_id_b_) {
            return true;
        }
        return false;
    }
};

struct UniqueIDWithBug {
    uint64_t unique_id_a_{0};
    uint64_t unique_id_b_{0};

    bool operator<(const UniqueIDWithBug amp;t) const {
        if (this->unique_id_a_ < t.unique_id_a_) {
            return true;
        }
        return (this->unique_id_b_ < t.unique_id_b_);
    }
};

// init data
std::set<UniqueID> _set = {
        {17303934402126834534u, 2922971136},
        {8520106912500150839u,  3118989312},
        {9527597377742531532u,  2171470080},
        {10912468396223017462u, 3972792320},
};
std::set<UniqueIDWithBug> _set_with_bug = {
        {17303934402126834534u, 2922971136},
        {8520106912500150839u,  3118989312},
        {9527597377742531532u,  2171470080},
        {10912468396223017462u, 3972792320}};

UniqueID _unique_id = {10912468396223017462u, 3972792320};
UniqueIDWithBug _unique_id_with_bug = {10912468396223017462u, 3972792320};

if (_set.find(_unique_id) == _set.end()) {
    std::cout << "_set not find" << std::endl;
}

if (_set_with_bug.find(_unique_id_with_bug) == _set_with_bug.end()) {
    std::cout << "_set_with_bug not find" << std::endl;
}

Выходные данные:
_set_with_bug не найден

Комментарии:

1. Да, UniqueIDWithBug это неправильно. Итак, что именно вы спрашиваете. В вашем вопросе отсутствует что-то фундаментальное. Это был бы актуальный, конкретный вопрос.

2. Я запутался, почему UniqueIDWithBug неверен, я думаю, что operator < для UniqueIDWithBug достаточно

3. Проследите и сравните UniqueIDWithBug a{1, 10} и UniqueIDWithBug b{2,5} . Выполняем a < b и b < a оба возвращаем true . Итак, как можно определить порядок?

4. Подумайте об использовании unordered_set ?

5. std::tie делает это правильно намного проще. return std::tie(unique_id_a_, unique_id_b_) < std::tie(t.unique_id_a_, t.unique_id_b_); это все, что вам нужно в вашем operator< . Представьте, что вы расширили свою правильную версию для обработки 4 переменных вручную.

Ответ №1:

Операция «меньше, чем», которую вы определяете для использования с std::set (и другими), должна быть допустимым строгим слабым упорядочением.

Ваш заказ UniqueIDWithBug не является.

Например, рассмотрим:

 UniqueIDWithBug a{1, 10};
UniqueIDWithBug b{2, 5};

Теперь обратите внимание, что оба a < b и b < a являются истинными. Это просто быстрая демонстрация того, что у вас нет строгого слабого упорядочения; на самом деле, это вообще не упорядочение!

Итак, ваша программа имеет неопределенное поведение. Внутренние компоненты std::set механизма предполагают допустимый порядок, но ваш — нет. В этом случае наблюдаемым результатом было «элемент не найден». Это могло быть «приготовить пиццу».

Построение хорошего строгого слабого порядка может быть сложным, но вы уже проделали тяжелую работу, потому что порядок UniqueID правильный.

В качестве альтернативы, полностью откажитесь от упорядочивания, определите хэш-функцию и переключитесь на unordered_set .