Действительно ли невозможно использовать карту STL вместе со структурой как ключ?

У меня есть следующий код:

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, Я получил ошибку компиляции. Почему?

14
задан honk 16 September 2019 в 12:27
поделиться

5 ответов

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

struct Node
{
 int a;
 int b;

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

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

23
ответ дан 1 December 2019 в 06:39
поделиться

Для включения сравнения для своего типа узла необходимо определить менее чем оператор:

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

7
ответ дан 1 December 2019 в 06:39
поделиться

Если вам действительно не нужно сортировать данные по ключу, вы можете использовать новый 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 намного проще использовать после все.

3
ответ дан 1 December 2019 в 06:39
поделиться

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

Думаю, ваша ошибка возникает из-за того, что узел не реализует оператор сравнения, который требуется карте для идентификации ее элементов.

1
ответ дан 1 December 2019 в 06:39
поделиться

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

10
ответ дан 1 December 2019 в 06:39
поделиться
Другие вопросы по тегам:

Похожие вопросы: