Как я могу использовать std :: maps с пользовательскими типами в качестве ключа? - PullRequest
Новая
       62

Как я могу использовать std :: maps с пользовательскими типами в качестве ключа?

53 голосов
/ 09 июля 2009

Мне интересно, почему я не могу использовать карты STL с пользовательскими классами. Когда я компилирую код ниже, я получаю следующее загадочное сообщение об ошибке. Что это значит? Кроме того, почему это происходит только с пользовательскими типами? (Примитивные типы в порядке, когда они используются в качестве ключа.)

C: \ MinGW \ Bin .. \ Lib \ НКУ \ mingw32 \ 3.4.5 ........ \ включать \ C ++ \ 3.4.5 \ бит \ stl_function.h || В функция-член `bool std :: less <_Tp> :: operator () (const _Tp &, const _Tp &) const [с _Tp = Class1]: |

C: \ MinGW \ Bin .. \ Lib \ НКУ \ mingw32 \ 3.4.5 ........ \ включить \ C ++ \ 3.4.5 \ бит \ stl_map.h | 338 | экземпляры из `_Tp & std :: map <_Key, _Tp, _Compare, _Alloc> :: operator [] (const _Key &) [с _Key = Class1, _Tp = int, _Compare = std :: less, _Alloc = std :: allocator>] '|

C: \ Users \ Admin \ Documents \ DEV \ песочнице \ песочница \ sandbox.cpp | +24 | экземпляры отсюда |

C: \ MinGW \ bin .. \ lib \ gcc \ mingw32 \ 3.4.5 ........ \ include \ c ++ \ 3.4.5 \ bits \ stl_function.h | 227 | ошибка: нет соответствия для 'оператора <' в '__x < __y '| || === Сборка завершена: 1 ошибка, 0 предупреждений === | </p> 

#include <iostream>
#include <map>

using namespace std;

class Class1
{
public:
    Class1(int id);

private:
    int id;
};

Class1::Class1(int id): id(id)
{}

int main()
{
    Class1 c1(1);

    map< Class1 , int> c2int;
    c2int[c1] = 12;

    return 0;
}

Ответы [ 7 ]

125 голосов
/ 09 июля 2009

У вас нет , чтобы определить operator< для вашего класса, на самом деле. Вы также можете создать класс объекта функции сравнения и использовать его для специализации std::map. Чтобы расширить ваш пример: 

struct Class1Compare
{
   bool operator() (const Class1& lhs, const Class1& rhs) const
   {
       return lhs.id < rhs.id;
   }
};

std::map<Class1, int, Class1Compare> c2int;

Просто так получается, что по умолчанию для третьего параметра шаблона std::map установлено std::less, которое делегирует operator<, определенное для вашего класса (и завершается неудачей, если его нет). Но иногда вы хотите, чтобы объекты могли использоваться в качестве ключей карты, но на самом деле у вас нет значимой семантики сравнения, и поэтому вы не хотите вводить людей в заблуждение, предоставляя operator< для вашего класса только для этого , Если это так, вы можете использовать вышеупомянутый трюк.

Еще один способ добиться того же - специализироваться std::less: 

namespace std
{
    template<> struct less<Class1>
    {
       bool operator() (const Class1& lhs, const Class1& rhs) const
       {
           return lhs.id < rhs.id;
       }
    };
}

Преимущество этого состоит в том, что он будет выбран std::map "по умолчанию", и все же вы не выставите operator< клиентскому коду в противном случае.

22 голосов
/ 09 июля 2009

По умолчанию std::map (и std::set) используйте operator< для определения сортировки. Поэтому вам нужно определить operator< для вашего класса.

Два объекта считаются эквивалентными if !(a < b) && !(b < a).

Если по какой-то причине вы хотите использовать другой компаратор, третий аргумент шаблона map можно изменить, например, на std::greater.

12 голосов
/ 09 июля 2009

Вам необходимо определить operator < для Class1.

Карта должна сравнивать значения, используя оператор 

class Class1
{
public:
    Class1(int id);

    bool operator <(const Class1& rhs) const
    {
        return id < rhs.id;
    }
private:
    int id;
};
3 голосов
/ 06 ноября 2015 
class key
{
    int m_value;
public:
    bool operator<(const key& src)const
    {
        return (this->m_value < src.m_value);
    }

};
int main()
{
    key key1;
    key key2;
    map<key,int> mymap;
    mymap.insert(pair<key,int>(key1,100));
    mymap.insert(pair<key,int>(key2,200));
    map<key,int>::iterator iter=mymap.begin();
    for(;iter!=mymap.end();++iter)
    {
        cout<<iter->second<<endl;
    }


}
3 голосов
/ 09 июля 2009

Ключи должны быть сопоставимы, но вы не определили подходящий operator< для своего пользовательского класса.

0 голосов
/ 06 марта 2019

Я бы хотел немного подробнее рассказать о ответе Павла Минаева , который вы должны прочитать, прежде чем читать мой ответ. Оба решения, представленные Павлом, не будут компилироваться, если сравниваемый элемент (например, id в коде вопроса) является закрытым. В этом случае VS2013 выдает мне следующую ошибку:

ошибка C2248: 'Class1 :: id': невозможно получить доступ к закрытому члену, объявленному в классе 'Class1'

Как упомянуто SkyWalker в комментариях на Павел , с помощью объявления friend помогает. Если вас интересует правильный синтаксис, вот он: 

class Class1
{
public:
    Class1(int id) : id(id) {}

private:
    int id;
    friend struct Class1Compare;      // Use this for Pavel's first solution.
    friend struct std::less<Class1>;  // Use this for Pavel's second solution.
};

Код на Ideone

Однако, если у вас есть функция доступа для вашего личного участника, например, getId() для id, как показано ниже: 

class Class1
{
public:
    Class1(int id) : id(id) {}
    int getId() const { return id; }

private:
    int id;
};

тогда вы можете использовать его вместо friend декларации (т.е. вы сравниваете lhs.getId() < rhs.getId()). Начиная с C ++ 11 , вы также можете использовать лямбда-выражение для Павла первое решение вместо определения класса объекта функции компаратора. Собрав все воедино, код можно написать следующим образом: 

auto comp = [](const Class1& lhs, const Class1& rhs){ return lhs.getId() < rhs.getId(); };
std::map<Class1, int, decltype(comp)> c2int(comp);

Код на Ideone

0 голосов
/ 24 августа 2018

Правильным решением является специализация std::less для вашего класса / структуры.

• В основном карты в cpp реализованы как деревья бинарного поиска.

  1. BST сравнивают элементы узлов, чтобы определить организацию дерева.
  2. Узлы, чей элемент сравнивается меньше, чем у родительского узла, размещаются слева от родительского узла, а узлы, элементы которых сравниваются больше, чем элемент родительских узлов, размещаются справа т.е.

Для каждого узла: node.left.key

Каждый узел в BST содержит Элементы, а в случае карт его KEY и значение, а ключи А должны быть упорядочены. Подробнее о реализации карты: Тип данных карты .

В случае карт cpp ключи являются элементами узлов, а значения не участвуют в организации дерева, это просто дополнительные данные.

Значит, ключи должны быть совместимы с std::less или operator<, чтобы их можно было упорядочить. Пожалуйста, проверьте параметры карты .

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

Решение : Specialize std::less:

Третий параметр в шаблоне карты является необязательным, и он std::less, который будет делегировать operator<,

Итак, создайте новый std::less для вашего определенного пользователем типа данных. Теперь этот новый std::less будет выбран по умолчанию std::map. 

namespace std
{
    template<> struct  less<MyClass>
    {
        bool operator() (const MyClass& lhs, const MyClass& rhs) const
        {
            return lhs.anyMemen < rhs.age;
        }
    };

}

Примечание. Вам необходимо создать специализированный std::less для каждого определенного пользователем типа данных (если вы хотите использовать этот тип данных в качестве ключа для карт cpp).

Плохое решение: Перегрузка operator< для вашего пользовательского типа данных. Это решение также будет работать, но его очень плохо, поскольку оператор < будет перегружен повсеместно для вашего типа данных / класса. что нежелательно в клиентских сценариях.

Пожалуйста, проверьте ответ Ответ Павла Минаева

...