Разве нельзя использовать stl map со структурой? - PullRequest
Новая
       24

Разве нельзя использовать stl map со структурой?

14 голосов
/ 06 февраля 2010 
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

Когда я попытался отобразить структуру в int, это дало мне ошибку компиляции. Зачем? Спасибо!

Ответы [ 5 ]

23 голосов
/ 06 февраля 2010

Чтобы вещь могла быть использована в качестве ключа на карте, вы должны иметь возможность сравнить ее с помощью operator<(). Вам нужно добавить такой оператор в класс вашего узла: 

struct Node
{
 int a;
 int b;

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

Конечно, реальный оператор зависит от того, что на самом деле означает сравнение для вашей структуры.

9 голосов
/ 06 февраля 2010

Вы должны указать std :: map, как сравнивать объекты Node.По умолчанию он пытается сделать это, используя оператор less than.Но вы не предоставили меньше, чем оператор для узла.Самое простое решение - предоставить один.

Пример свободной функции: 

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) и !(y<x) картойбудет считать x и y равными (тот же ключ).

6 голосов
/ 06 февраля 2010

Вам нужно определить оператор меньше чем, чтобы включить сравнения для вашего типа узла: 

struct Node
{
 int a;
 int b;
};

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

Здесь вы можете проверить, что LessThan Comparable означает для пользовательского типа.

Альтернативное решение - определить функтор на основе std :: binary_function . С точки зрения дизайна, этот вариант имеет преимущества, потому что сравнение эффективно отделено от класса Node. Это позволяет определять карты, специализированные с различными условиями сравнения (функторы). 

#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) и полезна для достижения более расширяемого решения.

3 голосов
/ 06 февраля 2010

Если вам не нужно сортировать данные по ключу, вы можете использовать новую unordered_map: 

#include <unordered_map>

... 

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

Вам понадобится недавний компилятор, чтобы это работало.

UPDATE Как указывает Нейл, вам нужна специализированная хеш-функция, если вы хотите unordered_map с Node ключами. 

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 намного проще в использовании.

1 голос
/ 06 февраля 2010

Не могли бы вы опубликовать ошибку компилятора - Они предназначены, чтобы сообщить вам , , что не так .

Я полагаю, ваша ошибка произошла, поскольку Node не реализует оператор сравнения, который необходим карте для определения ее элементов.

...