I would like to know the calculation amount when comparing C++ set/multiset with equivalent operators.

A set or multiset is a data structure that manages a prime set, but I wondered what would happen if I declared it as set A; and set B; and compared it as A==B.
In vector A; and vector B; when A==B, I think it will be O(N), but please let me know if this view is wrong.

c++

2022-11-30 18:58

2 Answers

The language specification requires the behavior of == as a container requirement (Container requirements) and that the calculation is linear (that is, O(N) in Big O notation).

In other words, any type defined as a container in the language specification (including, of course, set and multiset) can be compared with O(N).

2022-11-30 20:14

It is written on cpprefjp.I'm sure that's how the standard defines it.

set operator==calculated

Linear time for size(), but constant time if x and y are different sizes.

multiset operator==calculated

Linear time for size(), but constant time if x and y are different sizes.

2022-11-30 23:21