У меня есть следующий код:
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.
Когда я пытался отобразить экземпляр своей структуры Node
к int
, Я получил ошибку компиляции. Почему?
Чтобы объект можно было использовать в качестве ключа на карте, вы должны иметь возможность сравнивать его с помощью operator <()
. Вам нужно добавить такой оператор в класс вашего узла:
struct Node
{
int a;
int b;
bool operator<( const Node & n ) const {
return this->a < n.a; // for example
}
};
Конечно, то, что делает настоящий оператор, зависит от того, что на самом деле означает сравнение для вашей структуры.
Для включения сравнения для своего типа узла необходимо определить менее чем оператор:
struct Node
{
int a;
int b;
};
bool operator<(Node const& n1, Node const& n2)
{
// TODO: Specify condition as you need
return ... ;
}
Здесь Вы можете проверить, что означает Меньшее значение для сравнения для пользовательского типа.
Альтернативным решением является определение функции на основе std::binary_function. С конструктивной точки зрения это решение имеет преимущества, так как сравнение эффективно отделяется от класса Node
. Это позволяет определить карты, специализирующиеся на различных условиях сравнения (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;
}
Таким образом, можно определить больше сличений, чем просто NodeLessThan
, например, используя различные условия или сравнивая только один с помощью Node::a
другого сравнивая оба компонента, Node::a
и Node::b
. Далее, определены различные типы карт:
typedef std::map<Node, int, NodeLessThan> node_map_t;
typedef std::map<Node, int, NodeLessThanByA> node_map_a_t;
Такая развязка менее навязчива (вообще не касается класса Node) и выгодна для достижения более расширяемого решения.
Если вам действительно не нужно сортировать данные по ключу, вы можете использовать новый unordered_map:
#include <unordered_map>
...
std::tr1::unordered_map<Node, int> aa; // Doesn't require operator<(Node, Node)
Чтобы это работало, вам понадобится последняя версия компилятора.
ОБНОВЛЕНИЕ
Как указывает Нил, вам нужна специализированная хеш-функция, если вы хотите unordered_map с ключами узла
.
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);
}
};
И тогда карта становится:
std::tr1::unordered_map<Node, int, NodeHash> aa;
Кроме того, как говорит sellibitze, для сравнения ключей в случае хеш-коллизии необходим оператор ==:
bool operator==(const Node & lhs, const Node & rhs)
{
return lhs.a == rhs.a && rhs.b == rhs.b;
}
Так что я предполагаю, что std :: map намного проще использовать после все.
Не могли бы вы опубликовать ошибку компилятора - они предназначены для того, чтобы сообщить вам , , что не так .
Думаю, ваша ошибка возникает из-за того, что узел
не реализует оператор сравнения, который требуется карте для идентификации ее элементов.
Вы должны указать std :: map, как сравнивать объекты Node. По умолчанию он пытается сделать это с помощью оператора «меньше». Но вы не предоставили для Node. Самым простым решением было бы поставить его.
Пример бесплатной функции:
bool operator<(Node const& n1, Node const& n2)
{
return n1.a<n2.a || (n1.a==n2.a && n1.b<n2.b);
}
Обратите внимание, что для любой пары узловых объектов x, y с ! (X
! (Y