Как карта STL знает, что карта содержит данный элемент?
Обсуждаемый Использование 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;
Это позволяет карте определять, является ли ключ A меньше, чем ключ B. Но например карта<> :: находка () возвращается конец если элемент не найден, и итератор к нему, если он найден. Таким образом, карта знает об эквивалентности, а не только меньше, чем. Как?
Решение
Условие равенства двух ключей a а также b это что a<b а также b<a оба ложные. Сама карта обычно реализуется как сбалансированное двоичное дерево*, поэтому сравнение меньше чем используется для прохождения карты от корневого узла до тех пор, пока не будет найден соответствующий элемент. При поиске ключа kСравнение меньше, чем используется, пока не будет найден первый элемент, для которого сравнение ложно. Если обратное сравнение также ложно, k был найден. Иначе, k нет на карте. Карта использует только меньше, чем сравнение с этой целью.
Обратите внимание, что std::set использует точно такой же механизм, с той лишь разницей, что каждый элемент является его собственным ключом.
* Строго говоря, стандарт C ++ не устанавливает, что std::map быть сбалансированным двоичным деревом, но ограничения сложности, которые оно накладывает на такие операции, как вставка и поиск, означают, что реализации выбирают такие структуры, как красно-черное дерево.
Другие решения
Эквивалентность /operator== может быть выражена как функция operator<:
bool operator==(T left, T right) {
return !(left < right) && !(right < left);
}
Это связано с тем, что компаратор карты должен реализовывать строгий слабый порядок, такой как <,
Одним из математических свойств такого отношения является Антисимметрия, в котором говорится, что для любого x а также y, затем not (x < y) а также not (y < x) подразумевает x == y,
Следовательно, после нахождения первого элемента, который не должен сравниваться, меньше, чем ключ, который вы ищете, реализация просто проверяет, сравнивается ли этот элемент больше, и он не меньше и не больше, тогда он должен быть равен.