Как я могу вставить структуру в качестве ключа на карту?

Question

Я получаю ошибку компиляции для кода ниже, после удаления символов комментария из первой строки insert.Я не могу вставить структуру в карту, пока целые числа в порядке.

# include <iostream>
# include <map>

using namespace std;

struct node
{int test;} temp;

int main()
{
    temp.test = 24;
    int test = 30;
    map<node, bool> mymap1;
    map<int, bool> mymap2;
    //mymap1.insert(make_pair(temp, true));
    mymap2.insert(make_pair(test, true));
    return 0;
}

Как я могу исправить ошибку?

Answer 1

Чтобы тип служил ключом для карты, он должен быть упорядоченным . Практически это означает, что для типа должно быть определено operator<. Если вы определили глобальный operator<(const node&, const node&), это должно работать нормально; то есть.,

bool operator<(const node& n1, const node& n2) {
    return n1.test < n2.test;
}

Answer 2

Ключи std :: map хранятся внутри в двоичном дереве поиска. Чтобы ключи были сохранены и искали в двоичном дереве поиска, они должны быть сопоставимы. Например, требование к бинарному дереву поиска состоит в том, чтобы ключ левого потомка был меньше ключа его родителя, а ключ правого потомка больше, чем ключ его родителя. Однако, если ключи несопоставимы, как мы можем определить, больше или меньше детей родительский? Мы не можем сформировать дерево, и поэтому std :: map не будет работать с этими типами.

Вам просто нужно определить оператор меньше чем:

bool operator<(const node& n1, const node& n2)
{
    return n1.test < n2.test;
}

Это также должно быть другом вашей структуры узла, если «тестовый» элемент данных является закрытым (теперь он общедоступный, поскольку узел в настоящее время является структурой). Тем не менее, я, вероятно, сделал бы это так:

#include <map>

class node
{
    public:
        int getTest() const { return _test; }
        void setTest(int test) { _test = test; }
    private:
        int _test;
};

bool operator<(const node& n1, const node& n2)
{
    return n1.getTest() < n2.getTest();
}

int main()
{
    std::map<node,bool> foo;
    node n;
    n.setTest(25);

    foo[n] = true;

    return 0;
}

Answer 3

Вот как прочитать сообщения об ошибках:

/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_function.h: In member function ‘bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = node]’:
/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_tree.h:1141:   instantiated from ‘std::pair<typename std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(const _Val&) [with _Key = node, _Val = std::pair<const node, bool>, _KeyOfValue = std::_Select1st<std::pair<const node, bool> >, _Compare = std::less<node>, _Alloc = std::allocator<std::pair<const node, bool> >]’
/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_map.h:469:   instantiated from ‘std::pair<typename std::_Rb_tree<_Key, std::pair<const _Key, _Tp>, std::_Select1st<std::pair<const _Key, _Tp> >, _Compare, typename _Alloc::rebind<std::pair<const _Key, _Tp> >::other>::iterator, bool> std::map<_Key, _Tp, _Compare, _Alloc>::insert(const std::pair<const _Key, _Tp>&) [with _Key = node, _Tp = bool, _Compare = std::less<node>, _Alloc = std::allocator<std::pair<const node, bool> >]’
prog.cpp:15:   instantiated from here
/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_function.h:230: error: no match for ‘operator<’ in ‘__x < __y’

Во-первых, мы игнорируем большинство строк 'instantiated from', потому что они просто говорят о том, как расширились шаблоны.Важным является последний, ссылающийся на наш исходный код, потому что он сообщает нам, где произошла ошибка.Конечно, мы все равно знали об этом, поэтому пропустим и это.Мы также проигнорируем путь к рассматриваемому заголовку библиотеки, потому что нам все равно, как компилятор хранит свои вещи.

stl_function.h: In member function ‘bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = node]’:
stl_function.h:230: error: no match for ‘operator<’ in ‘__x < __y’

Итак ... наш код косвенно вызывает ‘bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = node]’, илиесли мы действительно сделаем эту замену, ‘bool std::less<node>::operator()(const node&, const node&) const’.И это проблема, потому что в реализации std::less есть no match for ‘operator<’ in ‘__x < __y’.

__x и __y - переменные (вы должны быть в состоянии догадаться об этом).Исходя из названия, мы можем догадаться (и если бы мы изучали стандартную библиотеку, мы бы знали), что std::less - это функция шаблона, которая сравнивает две вещи одного и того же типа и возвращает значение того, меньше ли первое второе, чем второе.

Как это происходит?Конечно, используя operator<.Вот что нам нужно сделать, чтобы решить проблему: в нем говорится, что operator< не для того, что сравнивается, поэтому мы должны его предоставить.Что сравнивается?node с, конечно.Итак, мы определяем operator< для нашего класса.

Почему он это делает?Таким образом, мы можем написать функции, которые принимают операцию сравнения в качестве аргумента (либо шаблонный аргумент, либо параметр времени выполнения - но первый гораздо более распространенный), и передают std::less.Вот причина существования std::less: оно превращает процесс сравнения вещей в функцию, а реальные функции несколько более полезны.

Насколько это актуально?Потому что, как говорили другие, std :: map фактически передает std::less в качестве аргумента.На самом деле это аргумент по умолчанию для шаблона std::map, который используется для сравнения элементов.В конце концов, часть интерфейса карты состоит в том, что каждый ключ уникален.Как вы собираетесь проверять ключи на уникальность, если не можете их сравнить?Конечно, технически вам нужно будет только сравнить их на равенство, чтобы это работало.Но оказывается, что возможность заказа ключей позволяет создать гораздо более эффективную структуру данных.(Вы бы знали об этом, если бы вы действительно проходили курсы в университете по программированию и CS.)

Почему не было проблемы с int?Теперь вы должны догадаться: operator< уже естественно работает для int с.Но вы должны сказать C ++, как это сделать для любых пользовательских типов, потому что вы можете иметь в виду что-то еще.

Answer 4

C ++ 11

Как уже упоминалось в Эндрю Расмуссена в ответе , ключи std::map должны быть сопоставимы. Однако вы также можете предоставить пользовательский объект сравнения для вашей карты вместо определения operator< для вашей структуры. Более того, поскольку C ++ 11 , вы можете использовать лямбда-выражение вместо определения объекта сравнения. В результате вы можете сделать код таким коротким, как показано ниже:

auto comp = [](const node& n1, const node& n2) { return n1.test < n2.test; };
std::map<node, bool, decltype(comp)> mymap1(comp);

Код на Ideone