¿Es imposible usar el mapa stl con 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 

Cuando traté de asignar una estructura a int, me dio un error de compilación. ¿Por qué? ¡Gracias!

Answer 1

Para que una cosa se pueda utilizar como clave en un mapa, tiene que poder compararla usando operator<(). Es necesario añadir dicho operador a su clase de nodo:

struct Node 
{ 
int a; 
int b; 

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

Por supuesto, lo que hace el operador de bienes depende de lo que realmente significa la comparación de su estructura.

Answer 2

Podría por favor, puesto que el error del compilador - Están destinadas a decir que , lo que está mal.

Supongo que su error se produce porque Node no implementa un operador de comparación que es requerido por el mapa para identificar sus elementos.

Answer 3

Tienes que decirle a std :: map cómo comparar los objetos del nodo. Por defecto, intenta hacerlo utilizando el operador menor que. Pero no proporcionó ningún operador menor para Node. La solución más fácil sería proporcionar uno.

función ejemplo libre:

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

Tenga en cuenta que, para cualquier par de nodos objetos x, y con !(x<y) y !(y<x) el mapa considerará x e y como igual (la misma tecla).

Answer 4

es necesario definir operador menor que para permitir comparaciones para su tipo de nodo:

struct Node 
{ 
int a; 
int b; 
}; 

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

Aquí se puede comprobar lo LessThan Comparable significa para un tipo definido por el usuario.

La solución alternativa es definir un functor basado en std::binary_function. Desde el punto de vista del diseño, esta opción tiene ventajas porque la comparación está efectivamente desacoplada de la clase Node. Esto hace posible definir mapas especializados con diferentes condiciones de comparación (funtores).

#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; 
} 

Por lo tanto, se puede definir más comparaciones que sólo NodeLessThan, por ejemplo usando diferentes condiciones o uno que comparaba únicamente por Node::a otra comparación de ambos componentes, Node::a y Node::b. Entonces, se define diferentes tipos de mapas:

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

Tal desacoplamiento es menos intrusivo (no toca clase de nodo en absoluto) y es beneficioso para conseguir la disolución más extensible.

Answer 5

Si usted no necesita realmente que sus datos ordenados por clave, puede utilizar la nueva unordered_map:

#include <unordered_map> 

... 

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

Usted necesitará un compilador reciente para que esto funcione.

ACTUALIZACIÓN Como Neil señala que necesita una función hash especializado si desea una unordered_map con Node llaves.

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); 
    } 
}; 

Y a continuación, el mapa se convierte en:

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

Además, como dice sellibitze, un operador == se necesita para comparar claves en caso de colisión de hash:

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

Por lo tanto, Supongo que std :: map es mucho más fácil de usar después de todo.