CC
А зачем unordered_map, если есть map?
Size: a a a
2020 August 13
CC
А зачем unordered_map, если есть map?
unordered_map может быть быстрее иногда?
VK
А зачем unordered_map, если есть map?
Алгоритмическая сложность операций разная
/¯
Тааак
А как в unordered_map поиск осуществляется?
Если unordered
А как в unordered_map поиск осуществляется?
Если unordered
Хеширование, затем бакет по остатку деления хеша на количество бакетов, затем линейный поиск в std::list
VK
Из хеш-таблицы взятие в среднем O(1), из дерева — O(log n)
CC
Хеширование, затем бакет по остатку деления хеша на количество бакетов, затем линейный поиск в std::list
std::list?
Это типа std::vector? А в чём отличие?
Это типа std::vector? А в чём отличие?
CC
/cppref std::list
F
Search results for "std::list"
1. std::list
2. std::pmr::list
3. std::forward_list
4. std::initializer_list
5. std::chrono::tzdb_list
6. std::pmr::forward_list
7. std::chrono::get_tzdb_list
8. std::errc::argument_list_too_long
9. std::span::last
10. std::chrono::last
11. std::ctype::is
12. std::char_traits::lt
13. std::ctype<char>::is
14. std::ctype_byname::is
1. std::list
2. std::pmr::list
3. std::forward_list
4. std::initializer_list
5. std::chrono::tzdb_list
6. std::pmr::forward_list
7. std::chrono::get_tzdb_list
8. std::errc::argument_list_too_long
9. std::span::last
10. std::chrono::last
11. std::ctype::is
12. std::char_traits::lt
13. std::ctype<char>::is
14. std::ctype_byname::is
/¯
std::list?
Это типа std::vector? А в чём отличие?
Это типа std::vector? А в чём отличие?
У листа операция вставок и удаления в произвольном месте стоит O(1)
VK
У вектора есть произвольный доступ, но элементы лежат последовательно (это массив с динамическим размером — ну, как динамическим, расширение приводит к перевыделению и перемещению элементов из старой области в новую)
CC
У листа операция вставок и удаления в произвольном месте стоит O(1)
Ого
А как это можно реализовать?
А как это можно реализовать?
CC
Даже не O(log n)
Удивительно
Удивительно
O
И, полагаю, разница в гарантиях на отсутствие инвалидации итераторов
/¯
unordered_map может быть быстрее иногда?
В среднем быстрее, а так зависит от хеш-функции и статистики коллизий хеша в реальных данных
VK
А list это связный список
VK
У каждого элемента есть указатели на предыдущий и следующий. Но, как уже очевидно, нет произвольного доступа, чтобы дойти до какого-то элемента, надо пройти все предыдущие
VK
Ну и ещё они не рядом друг с другом лежат, выделяется каждый из кучи
CC
В среднем быстрее, а так зависит от хеш-функции и статистики коллизий хеша в реальных данных
Быстре во вставке и удалении?
А в поиске?
А в поиске?
AB
Быстре во вставке и удалении?
А в поиске?
А в поиске?
Такой же по сложности, но на практике медленнее из-за кеша
/¯
Быстре во вставке и удалении?
А в поиске?
А в поиске?
И в поиске. Но быстрее в среднем не значит, что быстрее всегда