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

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

2 голосов
/ 25 апреля 2019

Я заметил, что 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?

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

Ответы [ 2 ]

2 голосов
/ 25 апреля 2019

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

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

unordered_map

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

map

Возвращаемое значение
std::pair содержит пару итераторов, определяющих требуемый диапазон: первый указывает на первый элемент, который не меньше 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

( демоверсия )

2 голосов
/ 25 апреля 2019

Это происходит потому, что 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 по понятным причинам.

...