Под капотом карта STL - это красно-черное дерево, и она использует оператор своих ключей или пользовательское сравнение, чтобы выяснить местоположение для вставки элемента.Как работает функция STL map :: find без оператора равенства?
карта :: найти() возвращает элемент, который соответствует прилагаемого ключа (если любые совпадения присутствуют)
Как это может сделать это без использования оператора равенства? Скажем, у моей карты есть ключи 1, 2, 3 и 4. Используя только <, я мог видеть, что ключ 2 должен идти после 1, после 2 и до 3. Но я не могу определить, совпадает или нет 2. 2.
Я даже вижу в/usr /include/c++/4.4.3/bits/stl_tree.h, что находка() не использует ничего, кроме функции сравнения поставляемого пользователя:
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
find(const _Key& __k)
{
iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
return (__j == end()
|| _M_impl._M_key_compare(__k,
_S_key(__j._M_node))) ? end() : __j;
}
Cryptic. Бонусные баллы, если вы можете сказать мне, как моя функция сравнения в конечном итоге используется в _M_impl._M_key_compare без очевидного цикла.
Используя подобную логику можно реализовать операции ==,>,> = и <=, используя только оператор < –