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?

Answer 1

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.

Answer 2

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).

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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