Рекурсивный компаратор структур C++

Я создал структуру для использования в качестве ключа на карте, чтобы избежать дублирования элементов. Структура содержит указатели на дочерние и одноуровневые элементы своего типа. Для карты я создал собственный компаратор, который должен рекурсивно просматривать элемент, дочерние элементы и братья и сестры, пока не будет найдено различие, чтобы убедиться, что элементы одинаковы. Однако по какой-то причине это не работает, и я все еще получаю дубликаты. Проверив их в отладчике, я пришел к выводу, что они действительно одинаковы насквозь, поэтому проблема, вероятно, должна быть где-то там.

Это структура.

struct controlIdentifier
{
    DWORD m_dwID;
    DWORD m_dwDefaultID;
    DWORD m_dwDisableID;

    BYTE m_bType;

    int m_nWidth;
    int m_nHeight;

    int m_nMargineH;
    int m_nMargineV;

    shared_ptr<controlIdentifier> m_pCHILD;
    shared_ptr<controlIdentifier> m_pNEXT;

    bool operator<(const controlIdentifier& id) const
    {
        if (m_dwDefaultID < id.m_dwDefaultID)
            return true;

        if (m_dwDisableID < id.m_dwDisableID)
            return true;

        if (m_bType < id.m_bType)
            return true;

        if (m_nWidth < id.m_nWidth)
            return true;

        if (m_nHeight < id.m_nHeight)
            return true;

        if (m_nMargineH < id.m_nMargineH)
            return true;

        if (m_nMargineV < id.m_nMargineV)
            return true;

        if (!m_pCHILD && id.m_pCHILD)
            return true;

        if (m_pCHILD && !id.m_pCHILD)
            return false;

        if (!m_pNEXT && id.m_pNEXT)
            return true;

        if (m_pNEXT && !id.m_pNEXT)
            return false;

        bool smaller = false;
        if (m_pCHILD && id.m_pCHILD)
            smaller = *m_pCHILD < *id.m_pCHILD;

        if (!smaller)
        {
            if (m_pNEXT && id.m_pNEXT)
                return *m_pNEXT < *id.m_pNEXT;
        }
        else
            return smaller;

        return false;
    }
};

И вот как это используется.


struct cmpBySharedPtr {
    bool operator()(const shared_ptr<controlIdentifier>& a, const shared_ptr<controlIdentifier>& b) const {
        return *a < *b;
    }
};

std::set<FRAMEDESC_SHAREDPTR> m_curFrames;
std::map<shared_ptr<controlIdentifier>, FRAMEDESC_SHAREDPTR, cmpBySharedPtr> m_serialFrames;

for (auto&& frame : m_curFrames)
{
    shared_ptr<controlIdentifier> id;
    makeIdentifiers(frame, id);
    id->m_dwID = newId;

    auto find = m_serialFrames.find(id);
    if (find == m_serialFrames.end())
    {
        m_serialFrames.insert(std::pair(id, frame));
        newId++;
    }
}

m_dwID не сравнивается намеренно.

Из здесь: «Говоря неточно, два объекта a и b считаются эквивалентными (не уникальными), если ни один из них сравнивается меньше, чем другой: !comp(a, b) && !comp(b, a)». Это кажется хорошим началом для создания тестового примера.

0x5453 16.12.2020 15:50
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
1
125
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Рассмотрим A = (child = 5, next = 6) и B = (child = 6, next = 5). Теперь A<B истинно, поскольку (A.child < B.child) истинно, и он просто возвращает это. Теперь рассмотрим B<A. B.child < A.child равно false, поэтому он проверяет поля next. Теперь B.next < A.next истинно, поэтому ваше сравнение возвращает true.

Так что это бессмысленно -> A<B верно и B<A верно. Это означает, что ваш компаратор недействителен.

Технический термин для этого — компаратор требует строгого слабого упорядочения — см. https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings. Ваш компаратор нарушает требование асимметрии.

Вдобавок к этому более безопасным шаблоном (для более ранних участников) является if (x.m1 < y.m1) return true; else if (y.m1 < x.m1) return false; else if (x.m2 < y.m2) return true; else if... Или, что более удобно, const auto members1 = std::make_tuple(x.m1, x.m2, ...); const auto members2 = std::make_tuple(y.m1, y.m2, ...); if (members1 < members2) return true; else if (members2 < members1) return false; else...

aschepler 16.12.2020 15:54

Вы можете построить operator <, сравнивая поле за полем. Но то, что ты сделал, слишком мало. В основном это должно выглядеть так:

bool operator < (const A& left, const A& right)
{
     if (left.firstField < right.firstField) return true;
     if (right.firstField < left.firstField) return false; // this case is missing

     if (left.secondField < right.secondField) return true;
     if (right.secondField < left.secondField) return false; // this case is missing


    ....
    return false; 
}

Вы упускаете случаи, когда можно сделать вывод, что левый объект наверняка "больше", чем правый.

Другие вопросы по теме