CODEWITHSUNDEEP
c++std
DannyX
DannyX

Reputation: 405

Basic std set logic

This may be dull question, but I want to be sure. Lets say I have a struct:

struct A
{
    int number;
    bool flag;

    bool operator<(const A& other) const
    {
        return number < other.number;
    }
};

Somewhere in code:

A a1, a2, a3;
std::set<A> set;

a1.flag = true;
a1.number = 0;

a2.flag = false;
a2.number = 10;

a3 = a1;

set.insert(a1);
set.insert(a2);

if(set.find(a3) == set.end())
{
    printf("NOT FOUND");
}
else
{
    printf("FOUND");
}

The output I get is "FOUND". I understand that, since I am passing values, elements in set are compared by value. But how can objects A be compared by their values, since equality operator is not overrided? I dont understand how overriding operator '<' can be enough for sets finding function.

Upvotes: 1

Views: 288

Answers (3)

BoBTFish
BoBTFish

Reputation: 19767

The flag member is entirely irrelevant here. The set has found an element that is equivalent to the searched-for value, with respect to <.

That is, if a is not less than b, and b is not less than a, then a and b must be equal. This is how it works with normal integers. That is how it is decided 2 values are equivalent in a std::set.

std::set doesn't use == at all. (unordered_set, which is a hash set, does use it, because it's the only way to distinguish hash collisions).

You can also provide a function to do the work of <, but it must behave as a strict weak ordering. Which is a bit heavy on the maths, but basically you could use > instead, via std::greater, or define your own named function rather than defining operator<.

So there is nothing technically to stop you defining an operator== that behaves differently from the notion of equivalence that comes from your operator<, but std::set won't use it, and it would probably confuse people.

Upvotes: 2

birkett
birkett

Reputation: 10101

From the documentation of set

two objects a and b are considered equivalent (not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a)

http://en.cppreference.com/w/cpp/container/set

In the template you can see

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

std::less

will call operator< and that is why it works.

Upvotes: 1

Kerrek SB
Kerrek SB

Reputation: 476970

The ordered containers (set, multiset, map, multimap) use one single predicate to establish the element order and find values, the less-than predicate.

Two elements are considered equal if neither one is less-than the other.

This notion if "equality" may not be the same as some other notion of equality you may have. Sometimes the term "equivalent" is preferred to distinguish this notion that's induced by the less-than ordering from other, ad-hoc notions of equality that may exist simultaneously (e.g. an overloaded operator==).

For "sane" value types (also called regular types), ad-hoc equality and less-than-induced equivalence are required to be the same; many naturally occurring types are regular (e.g. arithmetic types (if NaNs are removed)). In other cases, especially if the less-than predicate is provided externally and not by the type itself, it's entirely possible that the less-than equivalence classes contain many non-"equal" values.

Upvotes: 3

Related Questions