jpo38 jpo38 - 3 months ago 15
C++ Question

What container to store unique values with no operator< defined

I need to store unique objects in a container. The object provides a

operator==
and
operator!=
(
operator<
nor
operator>
).

I can't use
std::set
, as it requires a
operator<
.
I can't use
std::unordered_set
as it requires a hash function and I have none. Let's say I can't write one considering my object type (or I'm lazy).

Am I really forced to use a
std::vector
and make sure myself that items does not get duplicated in the container (using
std::find
which uses
operator==
)?

Is there really no container that could be used to store unique items only using the
operator==
?

Answer

There's indeed no standard container, and that's because it would be inefficient. O(N), to be precise - exactly the brute force search you imagine.

Both std::set<T> and std::unordered_set<T> avoid a brute-force search by taking advantage of a non-trivial property of T. Lacking either property, any of the existing N members of a container could be equal to a potential new value V, and you must therefore compare all N members using operator== repeatedly.