How to have a set of structs in C++

Question

I have a struct which has a unique key. I want to insert instances of these structs into a set. I know that to do this the < operator has to be overloaded so that set can make a comparison in order to do the insertion.

The following does not work:

#include <iostream>
#include <set>
using namespace std;
struct foo 
{
      int key;
};

bool operator<(const foo& lhs, const foo& rhs)
{
      return lhs.key < rhs.key;
}

set<foo> bar;

int main()
{
    foo *test = new foo;
    test->key = 0;
    bar.insert(test);
}

Answer 1

This might help:

struct foo
{
  int key;
};

inline bool operator<(const foo& lhs, const foo& rhs)
{
  return lhs.key < rhs.key;
}

If you are using namespaces, it is a good practice to declare the operator<() function in the same namespace.

---

For the sake of completeness after your edit, and as other have pointed out, you are trying to add a foo* where a foo is expected.

If you really want to deal with pointers, you may wrap the foo* into a smart pointer class (auto_ptr, shared_ptr, ...).

But note that in both case, you loose the benefit of the overloaded operator< which operates on foo, not on foo*.

Answer 2

struct Blah
{
    int x;
};

bool operator<(const Blah &a, const Blah &b)
{
    return a.x < b.x;
}

...

std::set<Blah> my_set;

However, I don't like overloading operator< unless it makes intuitive sense (does it really make sense to say that one Blah is "less than" another Blah?). If not, I usually provide a custom comparator function instead:

bool compareBlahs(const Blah &a, const Blah &b)
{
    return a.x < b.x;
}

...

std::set<Blah,compareBlahs> my_set;

Answer 3

You can overload the operator < inside the class also as,

struct foo 
{
  int key;
  bool operator < (const foo &other) const { return key < other.key; }
};

In your question, if you want to use set<foo> bar; as declaration then, you should insert value as,

bar.insert(*test);

But that won't be a good idea, as you are making redundant copy.

Answer 4

see ereOn's answer, it's right.

The real problem in you code is this:

foo *test = new foo;
test->key = 0;
bar.insert(test);

You insert a pointer in the set, not a struct. Change the insert to:

 bar.insert( *test );
 //          ^

---

EDIT: but then you'll need to delete foo, as it will be copied in the set. Or just create it on the stack (using set with pointers is not a good idea, because the arrangement will be "strange" - the set will sort according to the pointers' addresses )

Answer 5

The best thing to do is to give foo a constructor:

struct foo
{
    foo(int k) : key(k) { }
    int key;
};

Then to add, rather than...

foo *test = new foo;
test->key = 0;
bar.insert(test);   // BROKEN - need to dereference ala *test
// WARNING: need to delete foo sometime...

...you can simply use:

bar.insert(foo(0));

Answer 6

In c++11 we can use a lambda expression, I used this way which is similar to what @Oliver was given.

#include <set>
#include <iostream>
#include <algorithm>

struct Blah
{
    int x;
};



int main(){

    auto cmp_blah = [](Blah lhs, Blah rhs) { return lhs.x < rhs.x;};

    std::set<Blah, decltype(cmp_blah)> my_set(cmp_blah);

    Blah b1 = {2};
    Blah b2 = {2};
    Blah b3 = {3};

    my_set.insert(b1);
    my_set.insert(b2);
    my_set.insert(b3);

    for(auto const& bi : my_set){
        std::cout<< bi.x << std::endl;
    }

}

demo

Answer 7

The problem isn't in your set; it's in your test object. You're using Java style there. In C++, we just write:

set<foo> bar;

int main()
{
    foo test; // Local variable, goes out of scope at }
    test.key = 0;
    bar.insert(test); // Insert _a copy of test_ in bar.
}