Сравнение глобального неравенства для пары <> в стандарте C ++ - PullRequest
Новая
       14

Сравнение глобального неравенства для пары <> в стандарте C ++

5 голосов
/ 20 января 2012

Как и в случае cppreference :

При сравнении неравенства (<,>) первые элементы сравниваются первыми, и только если сравнение неравенства для них неверно, сравниваются вторые элементы.

, что переводится примерно так: 

return ((a.first < b.first) || (!(b.first < a.first) && (a.second < b.second)));

Мой вопрос: почему это так не интуитивно понятно? В чем причина этого?И есть ли примеры, когда это рассуждение приводит к правильным ответам?

Я думал, что реализация будет просто: 

return a.first < b.first && a.second < b.second

Ответы [ 3 ]

12 голосов
/ 20 января 2012

Такое сравнение называется лексикографическим порядком и является одним из наиболее естественных способов объединения двух разных порядков в один.

Упорядочения, которыезапрашиваемые в C ++ называются строгие слабые порядки .Это означает, что должно быть верно следующее:

  • Нерефлексивность: x
  • Транзитивность: Если x
  • Антисимметрия: Если x
  • Транзитивность эквивалентности: Если x и y несопоставимы, а y и z несравнимы, то x и z несопоставимы.

Эти свойства необходимы для гарантии того, что вы можете получить списокобъекты и положить их в отсортированном порядке возрастания.Это означает, что вы можете использовать std::sort на них или хранить их в std::set.

. Вы можете немного математически доказать, что если у вас два разных строгих слабых порядка, то лексикографический порядок васполучить, комбинируя их как std::pair, также является строгим слабым порядком.Лексикографическое упорядочение - это один из немногих способов, которым вы можете комбинировать строгие слабые упорядочения для создания новых строгих слабых упорядочений.

Однако предложенный вами порядок упорядочения , а не строгий слабыйи приведет к нарушению определенных предположений.В частности, рассмотрим пары (0, 5), (3, 3) и (1, 6).Тогда (0, 5) несопоставимо с (3, 3) и (3, 3) несопоставимо с (1, 6).Однако у нас действительно есть то (0, 5) <(1, 6), что нарушает правило <em>транзитивности эквивалентности .В результате многие алгоритмы сортировки, которые предполагают, что эквивалентность является транзитивной (что включает в себя большинство основных алгоритмов сортировки), не будут корректно работать в вашем диапазоне, что означает, что std::sort может работать неправильно.Это также означает, что вы также не можете сохранить их в std::set, потому что std::set хранит все вместе в некотором сортированном порядке (обычно это сбалансированное двоичное дерево поиска), и вы можете получить совершенно неправильные результаты.

Надеюсь, это поможет!

6 голосов
/ 20 января 2012

Если a.first меньше b.first, то пара уже меньше. Нет причин сравнивать вторую часть. Пары неявно сортируются первыми по первой части, точно так же, как имена сортируются первыми по первой букве. «Яблоко» предшествует «Зебре», потому что «А» предшествует «Z», мы вообще не сравниваем «р» с «е».

Итак, если a.first < b.first, мы закончили. Однако, если нет, мы еще не закончили. Есть и другой способ a, который может быть меньше b. Это если b.first < a.first не так, а a.second < b.second.

Аналогия будет "Зебра" и "Зиман". «Z» не меньше, чем «Z», но «e» меньше, чем «y», поэтому опять первое меньше второго.

Иногда вы увидите, что это закодировано следующим образом: 

bool operator<(const foo& a, const foo& b) {
 if (a.first < b.first) return true;
 if (a.first > b.first) return false;
 return (a.second < b.second);
}

Мне легче понять это интуитивно, но логика та же:

4 голосов
/ 20 января 2012

Интуитивность в глазах смотрящего. На самом деле я нахожу это довольно интуитивным.

Он действует так же, как и вы, когда сравниваете другие последовательности. Например, вы бы сказали, что строка "az" предшествует "ba", верно? Но у вас нет 'a' < 'b' && 'z' < 'a'! То же самое относится и к парам. Он не только более интуитивен, но и поддерживает все желательные свойства такого отношения.

...