CODEWITHSUNDEEP
c++c++17
Konstantin Schlegel
Konstantin Schlegel

Reputation: 149

C++ recursive struct comparator

I have created a struct to use as a key in a map to avoid having duplicate elements. The struct contains pointers to children and siblings of its own type. For the map, I have created a custom comparator that is supposed to recursively look at the element, the children and the siblings until a difference is found to make sure the elements are the same. However, for some reason it is not working and Im still getting duplicates. After checking them out in the debugger, I concluded that they are indeed the exact same through and through so the problem must probably be somewhere in there.

This is the struct.

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;
    }
};

And this is how it's used.


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 is not being compared on purspose.

Upvotes: 1

Views: 130

Answers (2)

Mike Vine
Mike Vine

Reputation: 9837

Consider A = (child = 5, next = 6) and B = (child = 6, next = 5). Now A<B is true as (A.child < B.child) is true and it just returns that. Now consider B<A. B.child < A.child is false, so it checks the next fields.. Now B.next < A.next is true, so your comparison returns true.

So this is nonsensical -> A<B is true and B<A is true. This means your comparator is invalid.

The technical term for this is the comparator requires strict weak ordering - see https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings. Your comparator breaks the asymmetry requirement.

Upvotes: 4

PiotrNycz
PiotrNycz

Reputation: 24392

You can construct operator < by comparing field by field. But what you did is too little. Basically it shall look like this:

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; 
}

You are missing cases when you can conclude, that for sure, left object is "greater" than right object.

Upvotes: 2

Related Questions