C++ std::set uniqueness override

Question

How does the std::set<T> container check if two objects are unique? I tried overriding the equality operators (==), but it didn't work.

The reason I want to do this is that I have let's say a class Person and I specify that my Person is the same person if they have the same name (maybe even birthdate, address, etc.).

In ccpreference.com, they write the following (which is a bit unclear to me):

Everywhere the standard library uses the Compare concept, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent (not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a).

I assume, that this question also expands to other STL containers and even algorithms (maybe even to the whole STL). So if in future, I want to use the function std::find, I would be looking up the name of the person and not the object itself. Is this correct?

EDIT

I want to add some example code.

// My operator overloading comparing two strings.
bool operator==(Node & rhs) const {
        return this->name.compare(rhs.name);
}

Then, in the UnitTest I add twice an object with the same name into the set. It is added twice (but should be the same according to the operator==.

void test_adding_two_identical_nodes() {
    // The pool is a set<Node> inside
    model::Node_Pool pool{};
    pool.store_node(model::Node{"Peter"});
    pool.store_node(model::Node{"Peter"});
    // Should be only 1 because the same node should be added once into a set.
    ASSERT_EQUAL(1, pool.size());
}

You write "it didn't work"; can you show us a (minimal) example of code that didn't work? — max66, Jan 04 '17 at 16:53
related/dupe: http://stackoverflow.com/questions/1114856/stdset-with-user-defined-type-how-to-ensure-no-duplicates — NathanOliver, Jan 04 '17 at 16:54
Also, see "Relational Operators" on this page: http://en.cppreference.com/w/cpp/language/operators — Robᵩ, Jan 04 '17 at 17:28

Robᵩ · Accepted Answer · 2017-01-04T17:15:23.720

std::set<T> doesn't compare using ==. It compares, by default, using std::less<T>. In turn std::less<T> uses, by default, the operator <.

One way to implement a set is to override operator<, like so:

#include <set>
#include <cassert>

struct Person {
    const char *name;
    int uid;
};
bool operator<(const Person& a, const Person& b) {
    return a.uid < b.uid;
}
int main () {
   Person joe = {"joseph", 1};
   Person bob = {"robert", 2};
   Person rob = {"robert", 3};
   Person sue = {"susan", 4};

   std::set<Person> people;
   people.insert(joe);
   people.insert(bob);
   people.insert(rob);

   assert(people.count(joe) == 1);
   assert(people.count(bob) == 1);
   assert(people.count(rob) == 1);
   assert(people.count(sue) == 0);

   Person anonymous_3 = {"", 3};
   assert( std::strcmp(people.find(anonymous_3)->name, "robert") == 0);
}

Alternatively, one can pass a compare operator as a template parameter when declaring the set. In the example above, this might be the compare operator:

struct Person_Compare {
    bool operator()(const Person& a, const Person& b) const {
        return a.uid < b.uid;
    }
};

And the std::set declaration might look like this:

std::set<Person, Person_Compare> people;

The rest of the example is unchanged.

Would this also work if I use the function std::find? Would it find two objects with the same uid? — El Mac, Jan 04 '17 at 17:06
@ElMac: No. That needs `operator==`. But you wouldn't use `std::find` with a set. — Lightness Races in Orbit, Jan 04 '17 at 17:10
@Robᵩ what happens if I have for example a `shared_ptr` of a `Person` and my set is of `set>`? How can I find a name of a person, if the Person in the `set` is first nested in a `shared_ptr`? I mean I want to do something like `my_set.find("STRING");` — El Mac, Jan 05 '17 at 08:53

score 0 · Answer 2 · answered Jan 04 '17 at 16:57

0

First of all, don't override comparison operators to compare anything but TOTAL equivalence. Otherwise you end up with a maintenance nightmare.

That said, you'd override operator <. You should instead give set a comparitor type though.

struct compare_people : std::binary_function<person,person,bool>
{
    bool operator () ( person const& a, person const& b) const { return a.name() < b.name();
};

std::set<person, compare_people> my_set;

answered Jan 04 '17 at 16:57

Edward Strange

40,307
7
73
125

4

`std::binary_function` is deprecated and should no longer be used. – NathanOliver Jan 04 '17 at 17:00
1

@NathanOliver - `std::binary_function` is deprecated because there are newer styles for doing this sort of thing that don't need the names it introduces, but there's nothing wrong with using it when you're writing old-style comparators. – Pete Becker Jan 04 '17 at 17:12
2

@PeteBecker My warning was because this is tagged as C++14. – NathanOliver Jan 04 '17 at 17:19
1

@NathanOliver - non sequitur. – Pete Becker Jan 04 '17 at 17:28

C++ std::set uniqueness override

EDIT

2 Answers2