std::map with keys that have no ordering

Question

Which approach should be taken if I want to have a std::map using a user defined object as key?

Let's consider this minimal bogous code (which compiles but won't run correctly):

#include <map>

class Object
{
public:
  int x, y;
  Object(int x, int y) : x(x), y(y) {};
  bool operator<(const Object& o) const { return 1;};   // bogus just to make compiler happy
};

int main()
{
  Object o1(1, 2), o2(3, 4);
  std::map<Object, int> objmap;
  objmap.insert(std::make_pair(o1, 11));
  objmap.insert(std::make_pair(o2, 22));
}

In order to be able to use an object as key in a std::map, we need a <operator.

So far so good, but what can be done if the objects can't be compared in terms of "less" or "greater", but only in terms of "different"?

You're going to need to establish some total order, you can then use `<` or a custom comparator. — NathanOliver, Feb 28 '20 at 15:34
You may want to consider `std::unordered_map` if the objects can only be compared in terms of equality. — JFMR, Feb 28 '20 at 15:35
`std::map` is an *ordered* collection. That implies all items in the collection must have a total order relationship. If your object cannot grant this property somehow, you cannot keep them in an ordered data structure. Maybe you may have a look at other solutions, such as a *hash table*? — BiagioF, Feb 28 '20 at 15:35
`return a.x < b.x || (a.x == b.x && a.y < b.y);` This is also a good candidate for a hash map using x^y for the hash. — Brannon, Feb 28 '20 at 15:35
It doesn't need to mean anything, it just needs to stable and consistent. Meaning, it's the same answer for the same args, `a — Lou Franco, Feb 28 '20 at 15:37
@眠りネロクyes, `unordered_map` is probably the thing I need. Thanks. — Jabberwocky, Feb 28 '20 at 15:38
@LouFranco yes, I know that, but it's not always possible. But anyway `unordered_map` is most likely what I need as alread commented. — Jabberwocky, Feb 28 '20 at 15:39
to use `unordered_map` you will need to provide a valid `hash`, which is just as complex as providing a valid `<` — Caleth, Feb 28 '20 at 16:25
@Jabberwocky If the object can be "different" they must contain some data. There is always a way to interpret the data so you can order it. — super, Feb 28 '20 at 16:50

bitmask · Answer 1 · 2020-02-28T15:49:30.647

Your objects have to respect strict total order. That means, most importantly, your < relation must be irreflexive and transitive. In your case, consider just using std::tuple, which already provides a functioning operator< with lexicographical ordering.

This would be "a" correct ordering, but most likely not at all what you would want:

friend bool operator<(Object const& a, Object const& b) {
  return a.x < b.x; // probably not what you want, but legal
}

Because it would mean that an Object{1,100} and Object{1,101} would result in std::map assuming they are the same key (unless you want exactly that).

However, you can actually break map, if you provide the following:

friend bool operator<(Object const& a, Object const& b) {
  return a.x <= b.x; // this will break map
}

because it is not irreflexive (i.e. x < x will not yield false).

In general you have to consider all properties of your object, in order to avoid aliasing (i.e. map considers two distinct objects equal). Unless you show us your Object, there is no way to show you how to implement a correct operator<.

In most cases std::unordered_map is a better (and more efficient) choice.

`std::tuple` would indead be a possibility, but `int x, y;` in my code is just an simple example. For more complex objects `std::tuple` isn't an option. — Jabberwocky, Feb 28 '20 at 15:41

score 1 · Answer 2 · answered Feb 28 '20 at 16:12

1

So far so good, but what can be done if the objects can't be compared in terms of "less" or "greater", but only in terms of "different"?

You can generally synthesise an ordering, e.g.

bool operator<(const Object& o) const { return std::tie(a, b) < std::tie(o.a, o.b); }

Incidentally, this construction is what C++20's default comparison will use.

auto operator<=>(const Object& o) const = default;

answered Feb 28 '20 at 16:12

Caleth

52,200
2
44
75

That looks interesting, though I don't entirely understand `std::tie`. I'm looking into it. Thanks. – Jabberwocky Feb 28 '20 at 16:27
@Jabberwocky it makes a tuple of references, and `std::tuple` defines `<` e.g. `std::tie(a, b)` makes a `std::tuple`. – Caleth Feb 28 '20 at 16:31

Jabberwocky · Answer 3 · 2020-02-28T16:59:51.010

As here there is no total order relationship between Objects, one possibility is to use unorded_map instead of map.

Therefore the object class needs at least an overloaded == operator and a custom hash function:

#include <unordered_map>
#include <iostream>

class Object
{
public:
  int x, y;
  Object(int x, int y) : x(x), y(y) {};

  bool operator==(const Object& o) const
  {
    std::cout << "equal hashes, using == operator on (" << x << "," << y << ")\n";
    auto isequal = x == o.x && y == o.y;
    std::cout << "objects are " << (isequal ? "" : "not ") << "equal\n";
    return isequal;
  };

  friend std::ostream& operator<<(std::ostream& os, const Object& o);
};

std::ostream& operator<<(std::ostream& os, const Object & o)
{
  os << "(" << o.x << "," << o.y << ")";
  return os;
}

struct ObjectHash {
  size_t operator()(const Object& o) const
  {
    std::cout << "hashing (" << o.x << "," << o.y << ")\n";;
    return o.x + o.y;  // purposly bad hash function, so we get collisions
                       // (o.x * 127) ^ o.y  would be better, still not ideal
  }
};


int main()
{
  Object o1(1, 2);
  Object o2(3, 4);  // different from o1, o3 and o4
  Object o3(1, 2);  // equal to o1
  Object o4(2, 1);  // different from o1, o2 and o3 but same hash as o1

  std::unordered_map<Object, int, ObjectHash> objmap;
  std::cout << "Inserting " << o1 << "\n"; objmap.insert(std::make_pair(o1, 11));
  std::cout << "Inserting " << o2 << "\n"; objmap.insert(std::make_pair(o2, 22));
  std::cout << "Inserting " << o3 << "\n"; objmap.insert(std::make_pair(o3, 33));
  std::cout << "Inserting " << o4 << "\n"; objmap.insert(std::make_pair(o4, 33));
}

The std::couts are there for illustration purposes.

Output:

Inserting (1,2)
hashing (1,2)
Inserting (3,4)
hashing (3,4)
Inserting (1,2)
hashing (1,2)
equal hashes, using == operator on (1,2)
objects are equal
Inserting (2,1)
hashing (2,1)
equal hashes, using == operator on (2,1)
objects are not equal

std::map with keys that have no ordering

3 Answers3