Why constructor of std::set compares the same elements two times?

Question

Let's consider the following example:

#include <iostream>
#include <set>

struct Obj {
  int x;
  int operator<=> (const Obj& obj) const {
    std::cout << __FUNCTION__ << " " << *this << " " << obj << std::endl;
    return x - obj.x;
  }
  friend std::ostream& operator<< (std::ostream& os, const Obj& obj);
};

std::ostream& operator<< (std::ostream& os, const Obj& obj) {
  return os << "{ x: " << obj.x << " }";
}

int main() {
  std::set<Obj> st2{{1}, {2}};
  return 0;
}

It would yield two rows:

operator<=> { x: 1 } { x: 2 }
operator<=> { x: 2 } { x: 1 }

At this moment I wonder why it performs two comparisons.

UPD: g++-10 version: 10.2.0

You'd need to state your tool-chain/standard library implementation. Some do just one comparison. — StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica, Commented Feb 20, 2021 at 12:11
@StoryTeller-UnslanderMonica Strange. The same configuration gives one comparison on wandbox and two comparisons on godbolt. I wonder what is missing for the optimization. — Yksisarvinen
– Yksisarvinen, Commented Feb 20, 2021 at 12:23
@Yksisarvinen - ¯\_(ツ)_/¯ . There's plenty of things each site's backend can do differently. I thought the OP would like to pin point the reason, but it seems like they were after a more general explanation of why it's possible. — StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica, Commented Feb 20, 2021 at 12:33
@StoryTeller-UnslanderMonica, if there were more detailed explanation of that phenomenon, I would appreciate it. I mean why it is sometimes optimized and sometimes - not. — unegare
– unegare, Commented Feb 20, 2021 at 12:48
@dronte7 - It's not that it's optimized or not. It's that sometimes we short-circuit and sometimes we don't. It's ultimately due to the order in which the initializer list is processed. For instance, swapping the elements to {2}, {1}).. — StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica, Commented Feb 20, 2021 at 13:36

Kirill Dmitrenko · Accepted Answer · 2021-02-20 12:23:50Z

3

It probably test them for equality. If you look at std::set's template parameters, you can see that it only requires a less function to be provided. So how can we test two elements for equality given that we have only <? Compare twice. If !less(a, b) && !less(b, a), then a == b.

answered Feb 20, 2021 at 12:23

Kirill Dmitrenko

3,68727 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Deduplicator Over a year ago

That works. If you have a full order. Some types only have a partial order though.

Aykhan Hagverdili Over a year ago

If !less(a, b) && !less(b, a), then they are considered equivalent not equal. std::map works on equivalence.

Collectives™ on Stack Overflow

Why constructor of std::set compares the same elements two times?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related