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

Question

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

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

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

Answer 1

Во-первых, сложность 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 - следовательно, линейным.

Answer 2

Проблема заключается в том, что 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;
}

Answer 3

1) граф

Сложность: логарифмическая по размеру и линейная по количеству совпадений

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

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

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

2) Равный диапазон

Это сложность: логарифмическая по размеру

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

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