How to consider two structs equal regardless of their second attribute?

Question

I have this structure

struct Event {
    const string event;
    const int order;
    Event(const string& _event, const int& _order):event(_event),order(_order) {}
};

struct EventCompare {
    bool operator()(const Event& lhs, const Event& rhs)
    {
        return (lhs.order < rhs.order);
    }
};

which I would like to use in a set:

set<Event, EventCompare> events;

I do know that sets doesn't allow duplicates. However, I would like to define duplicates as two instance of structs with equal events regardless of their orders, in other words, A = B iff A.event == B.event. This definition has to affect the way the set works, which means that, for example, the set has to ignore Event("holiday", 1), if it already contains Event("holiday", 0).

How can I do that? I've tried to add

if (lhs.event == rhs.event)
    return false;

in my EventCompare, but that didn't work. Will using pair instead of struct help anyhow?

Change `return (lhs.order < rhs.order);` to `return (lhs.event < rhs.event);` ? — user253751, Mar 19 '18 at 04:36
@immibis That still wouldn't provide a correct ordering, since if the events are equal, it may return an incorrect value. `std::tie(x.event, x.order) < std::tie(y.event, y.order)`, will, however, guarantee to provide a correct ordering, albeit, it may not be what the OP wants. — Alex Huszagh, Mar 19 '18 at 05:03
Am I missing something? You say you want equal `events` and don't care about `order`. So why do you compare using: `return (lhs.order < rhs.order);`? Surely, based on what you've described, the obvious thing to use is: `return (lhs.event < rhs.event);`? — Disillusioned, Mar 19 '18 at 05:44
You can have a `std::set` ordered on `event`, and a `std::vector>` that you order on `order`. — super, Mar 19 '18 at 05:51

score 2 · Answer 1 · answered Mar 19 '18 at 04:47

If under the conditions you specified they are considered to be equal, then it's obvious that the result of the < comparison would be false. One is not less than the other, they are considered to be equal. The comparison operator, for the purpose of being used with associative containers, only needs to indicate if one instance is "less" than the other. Since, under these circumstances, they are considered to be equal, neither one is less than the other.

Therefore:

struct EventCompare {
    bool operator()(const Event& lhs, const Event& rhs)
    {
        if (lhs.event == rhs.event)
             return false;

        return (lhs.order < rhs.order);
    }
};

However, this does not address the situation where two instances of the Event object have the same order, but different Events. If such situation is cannot arise, you don't have to worry about it. If it can, simply decide what their ordering would be, and set the return value of the comparison operator, in that case, accordingly.

Just FYI. I copied and pasted the code from your answer in mine. — R Sahu, Mar 19 '18 at 05:06

score 2 · Answer 2 · answered Mar 19 '18 at 04:59

The closest you can use is:

struct EventCompare {
    bool operator()(const Event& lhs, const Event& rhs)
    {
        if (lhs.event == rhs.event)
             return false;

        return (lhs.order < rhs.order);
    }
};

However, the compare criteria you are asking for does not meet the strictly weak ordering, which is required to put objects in a std::set.

Let's you have three objects with the following data:

obj1 = {"foo", 200}
obj2 = {"bar", 300}
obj3 = {"foo", 400}

If you add objects to the set in the order obj1, obj2, obj3, you will see only obj1 and obj2, in that order, in the set.

If you add objects to the set in the order obj2, obj3, obj1, you will see only obj2 and obj3, in that order, in the set.

Not only do you get different objects in the set depending on which object is added to the set first but even the objects appear in different order based on which object was added to the set first. I can only see problems in the future if you follow this strategy.

I think you should take a fresh look at your requirements and look for a cleaner solution. I am not able to suggest a solution without a deeper understanding of what your are trying to do.

score 0 · Answer 3 · answered Mar 19 '18 at 04:47

A set doesn't look for equality. It only checks for an ordering.

Since you want two events to be equal if the event is the same, that means that neither comes before the other, and your comparison function should return false in that case.

bool operator()(const Event& lhs, const Event& rhs) const {
    return lhs.event != rhs.event && lhs.order < rhs.order;
}

However, this won't work since it no longer defines a strict weak ordering, since you can have events where A < B and B < C but !(A < C) if A and C have matching event strings but B's order is between A's and C's.

So no, you can't use a set to store elements where a 2nd non-ordering attribute overrides the ordering one. You'd have to change the ordering to be based on event, but then you won't be able to look things up based on the order.

You could use a map to map the event strings to the order value used to store them into the set. Then you check the map to see if it is already there, and decide which element to keep in the set. Otherwise update both the set and map with the new entry.

score 0 · Answer 4 · answered Mar 19 '18 at 08:05

I seem to be missing something blindingly obvious. But surely all you need to do is compare according to your requirements?

struct EventCompareName
{
    bool operator()(const Event& lhs, const Event& rhs)
    {
        // If you want to compare by event and not order, then do so.
        return (lhs.event < rhs.event);
        // Rather than comparing by order and not event.
        //return (lhs.order < rhs.order);
    }
};

std::set<Event, EventCompareName> events;

Of course, you might also want to compare by order in some cases (even though your question gives absolutely zero indication of that requirement). In which case:

struct EventCompareNameOrder
{
    bool operator()(const Event& lhs, const Event& rhs)
    {
        if (lhs.event != rhs.event)
            return (lhs.event < rhs.event);

        return (lhs.order < rhs.order);
    }
};

std::set<Event, EventCompareNameOrder> allEvents;

How to consider two structs equal regardless of their second attribute?

4 Answers4