составной ключ std map

У меня проблема с методом operator ‹(), который требуется для std :: map. Я использую структуру в качестве составного ключа, которая выглядит следующим образом:

struct MyKey {
  std::string string1;
  std::string string2;
  std::string string3;
  unsigned int uint1;

  friend bool operator<(const MyKey& mk1, const MyKey& mk2)
  {
    return mk1.string1 < mk2.string1 && mk1.string2 < mk2.string2 &&
           mk1.string3 < mk2.string3 && mk1.uint1 < mk2.uint1;
  }
}

Как было сказано выше, я хочу использовать составной ключ с 4 значениями, но не знаю, как этого добиться с помощью метода operator ‹. Я заметил, что одновременно сохраняется только 1 значение!

Кто-нибудь может сказать мне, как выглядит правильное состояние?

Заранее спасибо!


c++ stdmap
person janr    schedule 23.04.2012    source источник

Ответы (3)


arrow_upward
9
arrow_downward

ассоциативные контейнеры стандартной библиотеки, такие как std::map, std::set, std::multiset, std::multimap, std::bitset, требуют, чтобы порядок элементов следовал _ 6_, что означает, что ваша реализация operator< должна следовать строгому слабому порядку.. Итак, одна реализация может быть такой:

friend bool operator<(const MyKey& mk1, const MyKey& mk2)
{
  if (mk1.string1 != mk2.string1 )
       return mk1.string1 < mk2.string1;

  else if ( mk1.string2 != mk2.string2)
       return mk1.string2 < mk2.string2;

  else if (mk1.string3 != mk2.string3)
       return  mk1.string3 < mk2.string3;

  else
       return mk1.uint1 < mk2.uint1;
}

Или вы можете реализовать это как:

friend bool operator<(const MyKey& mk1, const MyKey& mk2)
{
  auto const & t1 = std::tie(mk1.string1, mk1.string2, mk1.string3, mk1.uint1);
  auto const & t2 = std::tie(mk2.string1, mk2.string2, mk2.string3, mk2.uint1);
  return t1 < t2;
}

В этом решении функция std::tie создает два кортежа t1 и t1 ссылки на переданные ему аргументы, а затем сравнить t1 и t2, используя вместо этого перегруженный operator< для std::tuple. оператор ‹ для кортежа сравнивает элементы, лексикографически строгий-слабый порядок достигнуто ..

person Nawaz    schedule 23.04.2012

arrow_upward
2
arrow_downward

Я думаю, у вас проблема в том, что оператор ‹не обязательно реализует строгое слабое упорядочение. Слишком много комбинаций, где A<B ложно и B<A также ложно, где A и B - объекты MyKey. Это интерпретируется как A, равное B.

person juanchopanza    schedule 23.04.2012

arrow_upward
2
arrow_downward

Проблема с вашей реализацией в том, что она нестабильна, подумайте ...

return mk1.string1 < mk2.string1 && mk1.string2 < mk2.string2 &&
       mk1.string3 < mk2.string3 && mk1.uint1 < mk2.uint1;

... оценка { "a", "a", "a", 1 } < { "a", "b", "a", 1 } = a<a && ... = false && ... = false

... но { "a", "b", "a", 1 } < { "a", "a", "a", 1 } = a<a && ... = false && ... = false

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

Рабочее решение: кратко и эффективно проводить все необходимые сравнения строк только один раз ...

friend bool operator<(const MyKey& mk1, const MyKey& mk2)
{
    int x;
    return (x = mk1.string1.compare(mk2.string1)) ? x < 0 :
           (x = mk1.string2.compare(mk2.string2)) ? x < 0 :
           (x = mk1.string3.compare(mk2.string3)) ? x < 0 :
           mk1.uint1 < mk2.uint1;
}
person Tony Delroy    schedule 23.04.2012