Home > Net >  How does std::set determine whether to include a new insert?
How does std::set determine whether to include a new insert?

Time:12-10

The answer seems obvious, but I have an example like this (simplified, not real code):

class A {
  double a;
  double b;
operator>(..) { return this->a < other.a; }
operator==(..) { return this->b == other.b; }

I find that if I insert a new entry into std::set<A> with a unique c, but the same a it does not get inserted, as though it is considered equal.

What is the explanation?

CodePudding user response:

For the purpose of std::set or any ordered container two values are equivalent if neither is smaller than the other, with "smaller" referring to the result of < via std::less by default if no other comparator to replace it is specified. ==, !=, <=, > and >= are not used in this determination.

CodePudding user response:

In C , std::set is an associative container that contains a sorted set of unique objects of type A. It is typically implemented using a red-black tree. When you insert a new object into a std::set, it uses the object's comparison operators, operator> and operator==, to determine whether the object is equivalent to an element already in the set, and to determine its position in the set.

In your example, you have defined operator> to compare objects of type A based on their a member, and operator== to compare their b member. This means that when you insert a new object into the std::set, it will first be compared to the existing elements using operator>, and then, if no existing element is found to be greater than the new object, it will be compared to the existing elements using operator== to determine whether it is equivalent to any of them.

If the new object has a unique c member, but the same a as an existing element, then operator> will not find any existing element that is greater than the new object. However, the operator== will find that the new object is equivalent to the existing element with the same a, and the new object will not be inserted into the set.

To fix this issue, you can either modify the comparison operators to compare objects based on their c member instead of their a and b members, or you can use a different container, such as std::unordered_set, which does not require the use of comparison operators and allows you to insert objects with the same values for their a and b members.

  • Related