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

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

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

Ответ 1

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

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

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

Ответ 2

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

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

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

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

Ответ 4

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

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