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

Question

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

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

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

646 4

c++map stl key

4 ответов:

Comments

Ничего не найдено.

James Kanze · Accepted Answer · 2011-07-04 18:17:14

все, что требуется от ключа, это чтобы он был копируемым и назначаемым. Упорядочение внутри карты определяется третьим аргументом для шаблон (и аргумент конструктора, если используется). Этот по умолчанию до std::less<KeyType>, который по умолчанию < оператор, но нет необходимости использовать значения по умолчанию. Просто напишите сравнение оператор (желательно как функциональный объект):
struct CmpMyType
{
    bool operator()( MyType const& lhs, MyType const& rhs ) const
    {
        //  ...
    }
};
обратите внимание, что он должен определить строгий порядок, т. е. если CmpMyType()( a, b ) возвращает true, затем CmpMyType()( b, a ) должен вернуть false, и если оба возвращают false, элементы считаются равными (члены тот же класс эквивалентности).

BЈовић · Accepted Answer · 2017-09-30 13:42:53

вам нужно определить оператор

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 ));
}

Nemo · Accepted Answer · 2011-07-04 18:14:18

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

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

Kerrek SB · Accepted Answer · 2011-07-04 18:12:46

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

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