How can I use a C++ unordered_set for a custom class?

Question

How can I store objects of a class in an unordered_set? My program needs to frequently check if an object exists in this unordered_set and if it does, then do some update on that object.

I have looked up online on how to use unordered_set, but sadly most tutorials are about using it on int or string types. But how can I use it on a class? How can I define a hash function to make the node_id in the following example the key of the unordered_set?

#include <iostream>
#include <unordered_set>

using namespace std;

// How can I define a hash function that makes 'node' use 'node_id' as key?    
struct node
{
    string node_id;
    double value;
    node(string id, double val) : node_id(id), value(val) {}
};

int main()
{
    unordered_set<node> set;
    set.insert(node("1001", 100));
    if(set.find("1001") != set.end()) cout << "1001 found" << endl;
}

Solution 1

You could try using the following hash function object (it's pretty basic so you may want to improve it to avoid too many collisions).

struct node_hash {
    std::size_t operator()(const node& _node) const {
        return std::hash<std::string>()(_node.node_id);
    }
}
// ...
std::unordered_set<node, node_hash> node_set;

However, as one of the comments points out, you may be better off using a std::unordered_map<std::string, double> here.

Solution 2

Since this is the top Google result on Stack Overflow for C++ unordered_set of objects I'll post a simple yet completely illustrative and copy/paste runnable example:

// UnorderedSetOfObjects.cpp

#include <iostream>
#include <vector>
#include <unordered_set>

struct Point
{
  int x;
  int y;

  Point() { }
  Point(int x, int y)
  {
    this->x = x;
    this->y = y;
  }
  
  bool operator==(const Point& otherPoint) const
  {
    if (this->x == otherPoint.x && this->y == otherPoint.y) return true;
    else return false;
  }

  struct HashFunction
  {
    size_t operator()(const Point& point) const
    {
      size_t xHash = std::hash<int>()(point.x);
      size_t yHash = std::hash<int>()(point.y) << 1;
      return xHash ^ yHash;
    }
  };
};

int main(void)
{
  std::unordered_set<Point, Point::HashFunction> points;

  points.insert(Point(1, 1));
  points.insert(Point(2, 2));
  points.insert(Point(1, 1));   // notice this is a duplicate with the 1st point so it won't change the set

  std::cout << "points: " << "\n";
  for (auto& point : points)
  {
    std::cout << "(" << point.x << ", " << point.y << ")" << "\n";
  }

  return 0;
}

Solution 3

I agree to sjrowlinson that for your specific use case an std::unordered_map<std::string, double> might be the better choice. However, if you want to stick to an unordered_set due to some reason, then you can also use a lambda expression instead of defining a hash function. But you also have to provide a comparison function (equal) to make your code working. If you want two node instances to be equal if they have the same node_id, then you can use the following code:

auto hash = [](const node& n){ return std::hash<std::string>()(n.node_id); };
auto equal = [](const node& n1, const node& n2){ return n1.node_id == n2.node_id; };
std::unordered_set<node, decltype(hash), decltype(equal)> set(8, hash, equal);

However, if you want to use std::unordered_set::find(), then you cannot simply provide a string (e.g. "1001") to that function, because it expects a node object as parameter. The following code (which creates a temporary object) does the trick, though:

set.insert(node("1001", 100));
if (set.find(node("1001", 0)) != set.end())
    std::cout << "1001 found" << std::endl;

Please note that the output 1001 found is printed, although the value of the inserted node is different from the value of the node given to the find() function (100 and 0, respectively). This is, because the comparison function equal only considers the node_id when checking for equality.

Code on Ideone

Solution 4

You need to implement a custom hash function (I'd suggest using the function in the Boost library) to do this. C++ allows you to save pointers to objects of a class using unordered_set. For most purposes, that should do the trick.

View more solutions

Comments

[JohnB]

Maybe this helps? stackoverflow.com/questions/15869066/…

[n. m.]

It looks like you need a map rather than a set.

[daydayup]

I was actually using map. but it read that unordered set has a O(1) complexity for looking up

[Rotem]

@daydayup So does unordered_map.

[Kenny Ostrom]

One caution: you said you are looking up the object for the purposes of changing it. If this change effects the key, you will need to delete the old key and re-insert with the new key.

[nada]

If you don't need the iterator set.count(node("1001", 0)) != 0 is an option, too.

[daydayup]

can i ask what is the advantage of saving pointers instead of the objects? always wonder

[ucsunil]

As far as hashing goes, pointers are just values that point to memories - memory addresses if you will, that can be hashed just as any other number (like int, double, etc.) because they themselves are similar. In the big picture pointers are references which when passed around avoid superfluous copies.

[425nesp]

Is there a way to achieve this with only 1 template parameter? std::unordered_set<Point> points