Множество и словарь. Реализация на хеш-таблицах: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
Редактирование этой статьи в ближайшее время не планируется. | Редактирование этой статьи в ближайшее время не планируется. | ||
| Строка 6: | Строка 4: | ||
* [http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0 Википедии] (кратко, ёмко); | * [http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0 Википедии] (кратко, ёмко); | ||
* [http://www.rsdn.ru/article/alg/bintree/hash.xml Статьи | * [http://www.rsdn.ru/article/alg/bintree/hash.xml Статьи RSDN] (более подробно); | ||
* Главы 11 [http://www.google.com/search?btnG=1&pws=0&q=%D0%BA%D0%BE%D1%80%D0%BC%D0%B5%D0%BD+%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B+%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5+%D0%B8+%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7+2-%D0%B5+%D0%B8%D0%B7%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5 книги Кормена] (исчерпывающе). Желающие могут посмотреть [http://videolectures.net/mit6046jf05_leiserson_lec07/ лекцию]; | * Главы 11 [http://www.google.com/search?btnG=1&pws=0&q=%D0%BA%D0%BE%D1%80%D0%BC%D0%B5%D0%BD+%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B+%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5+%D0%B8+%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7+2-%D0%B5+%D0%B8%D0%B7%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5 книги Кормена] (исчерпывающе). Желающие могут посмотреть [http://videolectures.net/mit6046jf05_leiserson_lec07/ лекцию]; | ||
* Раздела 3.4 [http://www.google.com/search?btnG=1&pws=0&q=sedgewick+wayne+algorithms+4th+ed книги Седжвика] (очень подробно и с авторскими исследованиями; ознакомление лучше проводить с помощью [http://www.cs.princeton.edu/courses/archive/spring13/cos226/lectures/34HashTables.pdf слайдов] или [http://algs4.cs.princeton.edu/34hash/ сайта]); | * Раздела 3.4 [http://www.google.com/search?btnG=1&pws=0&q=sedgewick+wayne+algorithms+4th+ed книги Седжвика] (очень подробно и с авторскими исследованиями; ознакомление лучше проводить с помощью [http://www.cs.princeton.edu/courses/archive/spring13/cos226/lectures/34HashTables.pdf слайдов] или [http://algs4.cs.princeton.edu/34hash/ сайта]); | ||
| Строка 16: | Строка 14: | ||
* Новом издании [http://www.google.com/search?btnG=1&pws=0&q=josuttis+c%2B%2B+standard+library+2nd+ed книги Джосьютиса]. | * Новом издании [http://www.google.com/search?btnG=1&pws=0&q=josuttis+c%2B%2B+standard+library+2nd+ed книги Джосьютиса]. | ||
[[ | == Ссылки на задачи == | ||
* [http://acmp.ru/?main=task&id_task=505 ACMP #505 — Забор] | |||
[[Category:Базовые структуры и абстрактные типы данных]] | |||
== Ссылки == | |||
* [http://codeforces.com/blog/entry/62393 Codeforces — Blowing up unordered_map, and how to stop getting hacked on it] | |||
Текущая версия от 12:19, 28 января 2020
Редактирование этой статьи в ближайшее время не планируется.
Необходимую информацию о хешировании и хеш-таблицах можно получить из:
- Википедии (кратко, ёмко);
- Статьи RSDN (более подробно);
- Главы 11 книги Кормена (исчерпывающе). Желающие могут посмотреть лекцию;
- Раздела 3.4 книги Седжвика (очень подробно и с авторскими исследованиями; ознакомление лучше проводить с помощью слайдов или сайта);
- Раздела 3.7 и пункта 3.7.1 книги Скиены (две с половиной страницы), а также слайдов.
Реализация множеств и словарей на хеш-таблицах в STL появилась в стандарте C++11. Сведения о контейнерах unordered_set, unordered_multiset, unordered_map и unordered_multimap можно найти в:
- Материалах cplusplus.com [1], [2];
- Новом издании книги Джосьютиса.