Каким требованиям должны соответствовать классы ключей std :: map, чтобы быть действительными ключами? - PullRequest
Новая
       39

Каким требованиям должны соответствовать классы ключей std :: map, чтобы быть действительными ключами?

68 голосов
/ 04 июля 2011

Я хочу отобразить объекты одного класса на объекты другого.Однако класс, который я хочу использовать в качестве ключа, не был написан мной и представляет собой простой struct с несколькими значениями.std :: map упорядочивает его содержимое, и мне было интересно, как он это делает, и может ли какой-либо произвольный класс использоваться в качестве ключа или есть набор требований (операторов и чего нет), которые необходимо определить.

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

Ответы [ 4 ]

62 голосов
/ 04 июля 2011

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

struct CmpMyType
{
    bool operator()( MyType const& lhs, MyType const& rhs ) const
    {
        //  ...
    }
};

Обратите внимание, что он должен определять строгий порядок, т. Е. Если CmpMyType()( a, b ) возвращает true, тогда CmpMyType()( b, a ) должен возвращать false, а если оба возвращают false, элементы считаются равными (члены тот же класс эквивалентности).

22 голосов
/ 04 июля 2011

Вам нужно определить оператор <, например, так: </p> 

struct A
{
  int a;
  std::string b;
};

// Simple but wrong as it does not provide the strict weak ordering.    
// As A(5,"a") and A(5,"b") would be considered equal using this function.
bool operator<(const A& l, const A& r )
{
  return ( l.a < r.a ) && ( l.b < r.b );
}

// Better brute force.
bool operator<(const A& l, const A& r )
{ 
    if ( l.a < r.a )  return true;
    if ( l.a > r.a )  return false;

    // Otherwise a are equal
    if ( l.b < r.b )  return true;
    if ( l.b > r.b )  return false;

    // Otherwise both are equal
    return false;
}

// This can often be seen written as
bool operator<(const A& l, const A& r )
{
   // This is fine for a small number of members.
   // But I prefer the brute force approach when you start to get lots of members.
   return ( l.a < r.a ) ||
          (( l.a == r.a) && ( l.b < r.b ));
}
3 голосов
/ 04 июля 2011

Ответ на самом деле находится в ссылке, на которую вы ссылаетесь, под описанием аргумента шаблона «Сравнить».

Единственное требование заключается в том, что Compare (по умолчанию less<Key>, по умолчанию используется operator< для сравнения ключей) должно быть "строго слабым порядком".

2 голосов
/ 04 июля 2011

То же, что и для set: класс должен иметь строгий порядок в духе «меньше чем». Либо перегрузите соответствующий operator<, либо предоставьте пользовательский предикат. Любые два объекта a и b, для которых !(a<b) && !(b>a) будет считаться равным.

Контейнер карты на самом деле будет хранить все элементы в порядке, предусмотренном этим порядком, что позволяет достичь O (log n) времени поиска и вставки по значению ключа.

...