Is it impossible to use an STL map together with a struct as key?

Question

I have the following code:

struct Node
{
  int a;
  int b;
};

Node node;
node.a = 2;
node.b = 3;

map<int, int> aa;
aa[1]=1; // OK.

map<Node, int> bb;
bb[node]=1; // Compile error.

When I tried to map an instance of my struct Node to an int, I got a compile error. Why?

score 23 · Accepted Answer · answered Feb 06 '10 at 18:59

23

For a thing to be usable as a key in a map, you have to be able to compare it using operator<(). You need to add such an operator to your node class:

struct Node
{
 int a;
 int b;

 bool operator<( const Node & n ) const {
   return this->a < n.a;   // for example
 }
};

Of course, what the real operator does depends on what comparison actually means for your struct.

answered Feb 06 '10 at 18:59

1

@Steve To be even more precise, pointers MAY not be comparable with < - it depends what they point to. – Feb 07 '10 at 08:46
Yes, what I meant was, "pointers of the same type are not in general comparable with `<`". Pointers to different parts of the same object/array are comparable, and for that matter all pointers may be comparable if the implementation says so. – Steve Jessop Feb 08 '10 at 10:14

sellibitze · Answer 2 · 2010-02-06T19:04:48.633

You have to tell std::map how to compare the Node objects. By default it tries to do so by using the less than operator. But you didn't provide any less than operator for Node. The easiest solution would be to supply one.

Free function example:

bool operator<(Node const& n1, Node const& n2)
{
    return n1.a<n2.a || (n1.a==n2.a && n1.b<n2.b);
}

Note that, for any pair of node objects x,y with !(x<y) and !(y<x) the map will regard x and y as equal (same key).

score 7 · Answer 3 · edited May 23 '17 at 11:45

You need to define less-than operator to enable comparisons for your Node type:

struct Node
{
 int a;
 int b;
};

bool operator<(Node const& n1, Node const& n2)
{  
   // TODO: Specify condition as you need
   return ... ;
}

Here you may check what LessThan Comparable mean for a user-defined type.

Alternative solution is to define a functor based on std::binary_function. From design point of view, this option has advantages because comparison is effectively decoupled from the Node class. This makes it possible to define maps specialised with different comparison conditions (functors).

#include <map>

struct Node
{
 int a;
 int b;
};

struct NodeLessThan
    : public std::binary_function<Node, Node, bool>
{
    bool operator() (Node const& n1, Node const& n2) const
    {
        // TODO: your condition
        return n1.a < n2.a;
    }
};

int main()
{
    Node node;
    node.a = 2;
    node.b = 3;

    typedef std::map<Node, int, NodeLessThan> node_map_t;
    node_map_t bb;
    bb[node] = 1;
}

So, you can define more comparisons than just NodeLessThan, for example using different conditions or one comparing only by Node::a another comparing both components, Node::a and Node::b. Then, defined different types of maps:

typedef std::map<Node, int, NodeLessThan>    node_map_t;
typedef std::map<Node, int, NodeLessThanByA> node_map_a_t;

Such decoupling is less intrusive (does not touch Node class at all) and is beneficial to achieve more extensible solution.

Manuel · Answer 4 · 2010-02-07T10:05:09.317

3

If you don't really need to have your data sorted by key, you can use the new unordered_map:

#include <unordered_map>

... 

std::tr1::unordered_map<Node, int> aa;  // Doesn't require operator<(Node, Node)

You'll need a recent compiler for this to work.

UPDATE As Neil points out you need an specialized hash function if you want an unordered_map with Node keys.

struct NodeHash : std::unary_function<Node, size_t>
{ 
    size_t operator()(Node const & node) const
    {
        return static_cast<size_t>(node.a + 1) * static_cast<size_t>(node.b + 1);
    }
};

And then the map becomes:

 std::tr1::unordered_map<Node, int, NodeHash> aa;

Also, as sellibitze says, an operator== is needed to compare keys in case of hash collision:

bool operator==(const Node & lhs, const Node & rhs)
{
    return lhs.a == rhs.a && rhs.b == rhs.b;
}

So I guess that std::map is much easier to use after all.

edited Feb 07 '10 at 10:05

answered Feb 06 '10 at 19:09

Manuel

12,749
1
27
35

4

You are correct - you don't need operator<(). But instead you must provide a hash function, which is typically far harder to write than operator<(). – Feb 06 '10 at 19:15
@Manuel I think you have nicely illustrates how hard it is to write a good hash function :-) Your function will have the the same value (1) for the (a,b) pairs (0,1) and (1,0) and for lots of other pairs too. – Feb 06 '10 at 20:39
Doesn't unordered_map also need operator== for the keys? – sellibitze Feb 06 '10 at 22:45
@Neil - Yes it's hard indeed. Shouldn't the standard provide a simple way to deal with this? Maybe a function "mem_hash" to which you pass the address of a block and its size in bytes, and which returns a hash for the contents of that block. – Manuel Feb 07 '10 at 09:26
@Neil - Looks like (a+1)*(b+1) works much better as hash function. In my tests ( http://codepad.org/Vvc0DILo ) a tr1::unordered_set equipped with this hash function performs lookup operations twice as fast as an std::set. – Manuel Feb 07 '10 at 10:08
@Manuel I'm sure it will be fast - but adding 1 to the variables makes no difference to the quality of the function. In this case it doesn't matter much, but for types where the function is expensive to calculate, providing one that gives a good spread of values is essential otherwise the combination of slow hashing speed and collision handling can severely degrade performance. – Feb 07 '10 at 10:12
@Neil Butterworth - I just discovered that the Boost.Hash library has a function hash_combine which does precisely what is needed in this case. – Manuel Feb 08 '10 at 12:22
Also note that `std::unordered_map` was introduced only from C++11. – Julien Guertault Aug 19 '14 at 10:44

score 1 · Answer 5 · answered Feb 06 '10 at 18:57

1

Could you please post the compiler error - They're intended to tell you, what's wrong.

I guess your error occurs since Node doesn't implement a comparison operator which is required by the map in order to identify it's elements.

answered Feb 06 '10 at 18:57

Dario

48,658
8
97
130

score 0 · Answer 6 · answered Sep 16 '19 at 12:22

As a std::map is sorted by its keys, you have to define how to compare two Node objects. Since C++11 you can also use a lambda expression instead of defining a comparison operator. As a result, you can keep your code as short as follows:

int main() {
    Node node{ 2, 3 };

    auto comp = [](const Node& n1, const Node& n2) {
        return n1.a < n2.a || (n1.a == n2.a && n1.b < n2.b);
    };
    std::map<Node, int, decltype(comp)> bb(comp);
    bb[node] = 1;

    for (auto const &kv : bb)
        std::cout << kv.first.a << ", " << kv.first.b << ": " << kv.second << std::endl;

    return 0;
}

Output:

2, 3: 1

Please replace the body of the lambda expression according to your needs.

Code on Ideone

Is it impossible to use an STL map together with a struct as key?

6 Answers6

Linked