Как карта STL знает, что карта содержит данный элемент?

Question

В вопросе Использование char в качестве ключа в stdmap рекомендуется использовать пользовательскую функцию сравнения / функтор:

struct cmp_str
{
   bool operator()(char const *a, char const *b)
   {
      return std::strcmp(a, b) < 0;
   }
};

map<char *, int, cmp_str> BlahBlah;

Это позволяет map определить, меньше ли ключ A, чем ключ B. Но, например, map<>::find() возвращает end, если элемент не найден, и итератор, если он найден. Таким образом, карта знает об эквивалентности, а не только меньше, чем. Как?

Answer 1

Условие равенства двух ключей a а также b это что a<b а также b<a оба ложные. Сама карта обычно реализуется в виде сбалансированного бинарного дерева^*, поэтому сравнение "меньше" используется для прохождения карты от корневого узла до тех пор, пока не будет найден соответствующий элемент. При поиске ключа kСравнение меньше, чем используется, пока не будет найден первый элемент, для которого сравнение ложно. Если обратное сравнение также ложно, k был найден. Иначе, k нет на карте. Карта использует только меньше, чем сравнение с этой целью.

Обратите внимание, что std::set использует точно такой же механизм, с той лишь разницей, что каждый элемент является его собственным ключом.

^* Строго говоря, стандарт C++ не устанавливает, что std::map быть сбалансированным двоичным деревом, но ограничения сложности, которые оно накладывает на такие операции, как вставка и поиск, означают, что реализации выбирают такие структуры, как красно-черное дерево.

Answer 2

Эквивалентность /operator== может быть выражена как функция operator<:

bool operator==(T left, T right) {
  return !(left < right) && !(right < left);
}

Answer 3

Это связано с тем, что компаратор карты должен реализовывать строгий слабый порядок, такой как <,

Одним из математических свойств такого отношения является антисимметрия, которая утверждает, что для любого x а также y, затем not (x < y) а также not (y < x) подразумевает x == y,

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