Почему unordered_map::equal_range upper_bound возвращает end, если ключ меньше первого элемента карты

Question

Я заметил, что unordered_map::equal_range upper_bound (first) возвращает end, если переданный ключ меньше первого ключа карты

#include <iostream>
#include <map>
#include <tr1/unordered_map>

using namespace std;

int main ()
{
    {
        std::map<char,int> mymap;
        mymap['c'] = 60;
        std::map<char,int>::iterator itup = mymap.equal_range('a').first;
        std::cout << "map::itup " << itup->first << std::endl;
    }

    {
        tr1::unordered_map<char, int> mymap;
        mymap['c'] = 60;
        mymap['d'] = 70;

        tr1::unordered_map<char, int>::iterator itlo = mymap.equal_range('a').first;
        tr1::unordered_map<char, int>::iterator itup = mymap.equal_range('a').second;

        cout << "unordered_map::itup " << (itup == mymap.end() ? "END" : "NOT END") << std::endl;
        cout << "unordered_map::itlo " << (itlo == mymap.end() ? "END" : "NOT END") << std::endl;
    }

    return 0;
}

Выход:

map::itup c
unordered_map::itup END
unordered_map::itlo END

Обратите внимание, что поведение для map и unordered_map отличается - какие-либо причины для этого или это проблема в unordered_map?

Спасибо Александр

Answer 1

Это происходит потому, что unordered_map это, что не удивительно, неупорядочено.

См. §22.2.7 [unord.req], таблица 70, относительно требований к equal_range:

Возвращает: диапазон, содержащий все элементы с ключами, эквивалентными k, Возвращает make_­pair(b.end(), b.end()) если таких элементов не существует.

Это отличается от требований к заказанному ассоциативному контейнеру, например std::map, где equal_range определяется с точки зрения lower_bound а также upper_bound,

std::unordered_map не имеет lower_bound а также upper_boundпо понятным причинам.

Answer 2

Вы просили диапазон, состоящий из всех элементов в вашем unordered_map чей ключ 'a', Ваша неупорядоченная карта не содержит таких элементов. Итак, диапазон пуст.

То же самое относится и к map дело. Однако способ обозначения этого условия различается в зависимости от контейнера (хотя на самом деле это не так; продолжайте читать). Контейнеры std::map а также std::unordered_map это не одно и то же (следовательно, они имеют разные имена). Первый упорядочен, а второй нет, поэтому по причинам логической реализации он работает немного иначе:

unordered_map

Возвращаемое значение
std::pair содержащий пару итераторов, определяющих требуемый диапазон. Если таких элементов нет, то конец (см. end()) итераторы возвращаются как оба элемента пары.

map

Возвращаемое значение
std::pair содержащий пару итераторов, определяющих требуемый диапазон: первый указывает на первый элемент, который не меньше key а второй указывает на первый элемент больше, чем key, Если нет элементов не меньше, чем key, конец - конец (см. end()) итератор возвращается как первый элемент. Аналогично, если нет элементов больше key, последний итератор возвращается как второй элемент.)

Эта разница не имеет значения. В любом случае вы должны просто повторить ( first , second ], чтобы изучить элементы (если они есть) в вашем диапазоне, как если бы вы использовали любой диапазон итераторов.

В своем коде вы не исследовали обе части пары, возвращенной в вашем map дело. Если вы это сделаете, то вы обнаружите, что first == second (опять же, обозначение пустого диапазона).

Ваш map код эффективно разыменовывает итератор "из конца в конец" возвращаемого диапазона.

---

#include <iostream>
#include <map>
#include <unordered_map>

using namespace std;

int main ()
{
    {
        std::map<char,int> mymap;
        mymap['c'] = 60;
        std::map<char, int>::iterator itlo = mymap.equal_range('a').first;
        std::map<char, int>::iterator itup = mymap.equal_range('a').second;

        // This compares each range extent to the map's end, which is not really useful
        cout << "map::itup " << (itup == mymap.end() ? "END" : "NOT END") << '\n';
        cout << "map::itlo " << (itlo == mymap.end() ? "END" : "NOT END") << '\n';

        // This examines the range itself
        cout << "map range empty: " << (itlo == itup ? "YES" : "NO") << '\n';
        cout << "map range size: " << std::distance(itlo, itup) << '\n';
    }

    {
        std::unordered_map<char, int> mymap;
        mymap['c'] = 60;
        mymap['d'] = 70;

        std::unordered_map<char, int>::iterator itlo = mymap.equal_range('a').first;
        std::unordered_map<char, int>::iterator itup = mymap.equal_range('a').second;

        // This compares each range extent to the map's end, which is not really useful
        cout << "unordered_map::itup " << (itup == mymap.end() ? "END" : "NOT END") << std::endl;
        cout << "unordered_map::itlo " << (itlo == mymap.end() ? "END" : "NOT END") << std::endl;

        // This examines the range itself
        cout << "unordered_map range empty: " << (itlo == itup ? "YES" : "NO") << '\n';
        cout << "unordered_map range size: " << std::distance(itlo, itup) << '\n';
    }
}

// Output:
// 
// map::itup NOT END
// map::itlo NOT END
// map range empty: YES
// map range size: 0
// unordered_map::itup END
// unordered_map::itlo END
// unordered_map range empty: YES
// unordered_map range size: 0

( живое демо)