Граф в Мультисете

Question

Граф в Мультисете

Я использовал C ++ STL некоторое время, но никогда не удосужился использовать мультимножества (или мультикарты). У меня есть вопрос, основанный на подсчете количества элементов с одинаковым ключом. Например,
Вот неупорядоченный_мультисет {0, 2, 5, 1, 1, 2, 7, 5}

Если я скажу count (5), он должен вернуть 2. Есть два способа добиться этого с помощью стандартов unordered_multiset C ++ 11.
1) подсчитывать
2) equal_range и затем вычитая полученные итераторы.

1) говорят, что занимает линейное время в количестве случаев, но 2) постоянное время. Это почему?

0

c++c++11 stl unordered-multiset

Решение

Другие решения

Проблема заключается в том, что equal_range возвращает «прямой итератор» (это упомянуто в предоставленной вами ссылке), который имеет только операцию увеличения, определенную в отличие от итераторов произвольного доступа. Таким образом, чтобы вычислить разницу между двумя, мы должны увеличивать первое до тех пор, пока оно не станет равным второму — это дает время линейного счета.

И, например, в стандартной библиотеке gcc счетчик реализован именно так:

count(const _Key& __k) const
{
pair<const_iterator, const_iterator> __p = equal_range(__k);
const size_type __n = std::distance(__p.first, __p.second);
return __n;
}

2

Пример: mymultiset.count (73)

Логарифмический по размеру: чтобы найти элемент в самом первом же как бинарный поиск

Линейный по количеству совпадений: поскольку элемент найден, он будет течь линейно, чтобы узнать количество совпадений, потому что, как мы знаем, наборы отсортированы

«Функция возвращает пару, у которой member pair :: first является нижней границей диапазона (такой же, как lower_bound), а pair :: second является верхней границей (такой же, как upper_bound).»

Отметьте наименьшую сложность, чтобы получить верхнюю / нижнюю границу, которую вы найдете (логарифмический размер)
Вы также можете проверить эту ссылку: http://www.cplusplus.com/reference/set/multiset/equal_range/

1

Источник

Accepted Answer

Во-первых, сложность equal_range описана по ссылке, которую вы сами предоставляете:

Average case: constant.
Worst case: linear in container size.

Во-вторых, логический Операция «вычитания получающихся итераторов» должна быть реализована с использованием линейной итерации со сложностью O(bucket_size(bucket(key))), перебирая список или вектор хеш-значений, проверяющих совпадения, так что …

"2) equal_range and then subtracting the resulting iterator"..."is constant time"

…не является обоснованным утверждением.

Что касается «1) подсчета», его сложность также задокументирована — в этом случае:

Average case: linear in the number of elements counted.
Worst case: linear in container size.

Который снова может отличается от вашего «линейного времени по количеству происшествий». Причина в том, что средний это нормально с max_load_factor при значении по умолчанию 1.0 и хорошей хэш-функции будут происходить только коллизии, как при случайном рассеянии — что-то около 10-20%, поэтому самый времени только ключи, хэширующие к определенному сегменту, будут теми, на которые вы рассчитываете — при этом среднее значение будет постоянным, кратным 1,1x или 1,2x, что, следовательно, будет линейным.

3