Оценка равенства в ассоциативных контейнерах (STL)

Question

Мне известно, что ассоциативные контейнеры STL (и другие контейнеры, которые, как я предполагаю, сортируются) используют критерий сортировки для проверки на равенство.

Критерий сортировки для контейнеров по умолчанию равен st :: less, таксделал бы тест на равенство для контейнера:

if (! (lhs < rhs || rhs < lhs))

или что-то подобное.У меня была пара вопросов по этому поводу ...

Прежде всего, это кажется странно неэффективным способом сравнения на равенство - почему STL делает это так?Я ожидал бы, что контейнеры STL просто примут вместо этого дополнительный параметр по умолчанию для равенства.

Мой второй вопрос больше касается оценки оператора if в целом.В C ++, сколько из этого утверждения будет оценено (lhs> rhs), было правдой?Перестанет ли он пытаться после оценки стороны, которая потерпела неудачу, таким образом сохраняя некоторую эффективность?Если да, какая часть выражения вычисляется первой?

Answer 1

В «Эффективном STL» Скотт Мейерс подробно обсуждает это в Item 19 :

Понять разницу между равенством и эквивалентностью.

Равенство , как и следовало ожидать, основано на operator==.

Эквивалентность"основана на относительном порядке значений объектов в отсортированном диапазоне ... Два объекта имеют эквивалентные значения в контейнере c, если ни один из них не предшествует другому в сортировке c порядок. "

Мейерс выражает это так:

!( w1 < w2 ) // it's not true that w1 < w2
&&           // and
!( w2 < w1 ) // it's not true that w2 < w1

Мейерс затем повторяет:

Это имеет смысл: два значения эквивалентны (по отношению к некоторым критерий упорядочения), если ни один не предшествует другому (в соответствии с этим критерий.)

А почему STL делает это так:

Используя только одну функцию сравнения и используя эквивалентность в качестве арбитра того, что значит быть "тем же самым", стандартные ассоциативные контейнеры ... избежать путаницы возникнет в результате смешивания использования равенства и эквивалентности внутри стандартные ассоциативные контейнеры.

Прочитайте статью 19 (которая охватывает большую часть 6 страниц), чтобы получить полный вкус.

Answer 2

STL ассоциативные контейнеры

Вы имеете в виду: стандартные C ++ отсортированные ассоциативные контейнеры.

Я бы ожидал, что контейнеры STL просто примут дополнительный параметр по умолчанию для равенства.

Чего бы это достигло? В вашем учебнике алгоритм красно-черного дерева вместо

if (x < y)
    // ...
else if (y < x)
    // ...
else
    // equality

у вас будет

if (x == y)
    // equality
else if (x < y)
    // ...
else
    // y < x

так что еще два сравнения в худшем случае.

Отвечая на комментарии к этому ответу: наличие оператора с меньшим количеством ресурсов существенно упрощает использование контейнеров, поскольку нет необходимости поддерживать согласованность между меньшими и равными. Представим, что у вас есть программа для хранения чисел с плавающей запятой. Однажды кто-то решает заменить приближенную функцию float_equals побитового равенства, которая только что использовалась неким контейнером , но и их кодом . Если этот человек не обновляет функцию float_less, поскольку его код не использует эту функцию , то ваш контейнерный код таинственным образом нарушается.

(Да, и в показанном примере кода, как всегда, применяется короткое замыкание.)

Answer 3

Относительно второго вопроса: применяются стандартные ленивые правила оценки для логических выражений.Если LHS || истинно, RHS не оценивается.

Answer 4

Прежде всего, это выглядит странно неэффективным способом сравнения на равенство

Да, но отсортированные контейнеры делают этот тест относительно редко.

Использование сравненияфункция как strcmp будет лучше.Использовать и «меньше», и «сравнить» было бы еще лучше.

В C ++ какая часть этого оператора была бы оценена (lhs> rhs), было ли это правда?

ВC и в C ++ a && b, a || b, a, b, a ? b : c оцениваются слева направо, при этом оценивается только полезная правая часть (за исключением перегрузки &&, ||, , операторы в C ++).

Это позволяет выполнять несколько полезных коротких тестов, таких как: p != NULL && *p > 2

Answer 5

C ++ оценивает, если () слева направо для вашего случая с ||. Оценивает левую сторону (lhs