I have a set of structs where the struct is

struct sub_tree
{
    vector <int> nodes;
    int weight;
};

and the set along with the comparator function is

set <sub_tree, decltype (comp)*> s(comp);
bool comp (sub_tree a, sub_tree b)
{
    return (a.weight < b.weight);
}

Now when I input two structs with the same weight but different node vectors, like weight1 = 96 node1 = 5 and weight2 = 96 node2 = 6 it accepts only the first one in the set. But if I use the following comparator then it accepts both the values.

set <sub_tree, decltype (comp)*> s(comp);
bool comp (sub_tree a, sub_tree b)
{
    return (a.weight <= b.weight);
}

Can someone explain this behavior?

CodePudding user response：

The comparison object for set must adhere to the Compare named requirement. This means

equiv(a, b), an expression equivalent to !comp(a, b) && !comp(b, a)

i.e. if applying the function with the original and swapped order both return false, both values are considered the same.

The contract of std::set::insert specifies that no modification of the set takes place, if an equal object is already in the set. With the first comparison this is considered the case.

The second one does not adhere to the requirements of Compare though.

Let's assume the requirement cited above applies for your compare function: Pass 2 equal values a1 and a2.

• comp(a1, a2) is true
• comp(a2, a1) is true

therefore according to the requirement of Compare a1 and a2 are not the same, which is a contradiction. Therefore the requirement is violated.

If you want to store multiple elements with the same weight in a set, you need to introduce a tie breaker or go with a std::multiset

CodePudding user response：

I believe it is because you are working with an ordered set. So, the function it is looking for should return <0, 0 and >0. Your function simply returns true and false, which gets implicitly translated to 0 or 1. When you return false, it is interpreted as 0, meaning, the items are equal, meaning, since it is a set, only the first item ought to be included. When you return true, it is interpreted as 1, which is >0, so it interprets that as, the first is greater than the second, so include both, but put the second before the first (assuming default ordering is ascending, which I think it is).