Is it impossible to use stl map with struct ?

Question

struct Node
{
 int a;
 int b;
};

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

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

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

When I tried to map a struct into int, it gave me a compile error. Why? Thank you!

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

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

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 4

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 5

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.