🔒 Locked

[C++] std::set does not erase(value)

Started by Decrius Jun 30, 2010 at 3:32 AM 1 reply 850+ views

Original Post

Jun 30, 2010 at 3:32 AM

I'm having a very nasty bug. I finally found what the problem is, but I'm unsure whether this has to do with a problem elsewhere (memory overwrite?) or my usage with a std::set. I'm also not sure how a std::set can determine whether items are equal purely based on the result of the lesser-then operator.

    class Signal;    ////////////////////////////////////////////////////////////////    struct SignalID    {        Signal *signal;        unsigned int id;        SignalID(Signal *i_signal, unsigned int i_id);        bool operator < (const SignalID &instance) const;    };    ////////////////////////////////////////////////////////////////    SignalID::SignalID(Signal *i_signal, unsigned int i_id) :        signal(i_signal),        id(i_id)    {    }    inline bool SignalID::operator < (const SignalID &instance) const    {        return (signal < instance.signal || id < instance.id);    }    ////////////////////////////////////////////////////////////////    ////////////////////////////////////////////////////////////////    ////////////////////////////////////////////////////////////////    class Signal    {    public:        ...        void detach_signal(Signal *signal, unsigned int id);          ...        std::set<SignalID> signal_ids;    };    void Signal::detach_signal(Signal *signal, unsigned int id)    {        for (std::set<SignalID>::iterator iterator = signal_ids.begin(); iterator != signal_ids.end(); ++iterator)        {            std::cerr << (*iterator).id << " " << (*iterator).signal << " compared with " << id << " " << signal << " gives " << ((*iterator) < SignalID(signal, id)) << "\n";            if (signal_ids.find(SignalID(signal, id)) != signal_ids.end())            {                std::cerr << "found\n";            }        }        std::cerr << "erased " << signal_ids.erase(SignalID(signal, id)) << "\n";    }

What happens:
- Sometimes it does not find() equal SignalID's and then it wont erase it.
- Sometimes it find()s both unequal and equal SignalID's, but then only erases the equal one.

Am I using a std::set wrong? Or does this look like memory corruption?

Thanks!

rozz666

Jun 30, 2010 at 3:42 AM

Your operator< is wrong. Your elements should have strict weak ordering.
With your implementation different elements are equal, because a == b <=> ~(a < b) and ~(b < a). Have a look how std::pair implements operator<.

Decrius

Author

Decrius

Jun 30, 2010 at 3:57 AM

Ah thanks now I see how it can compare items.

I've implemented it now as follows:

    inline bool SignalID::operator < (const SignalID &instance) const    {        return (signal < instance.signal || (signal == instance.signal && id < instance.id));    }

EDIT: Yes! Bug fixed! This one took me a day! -.-

[Edited by - Decrius on June 30, 2010 4:57:07 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.