Множество и словарь. Реализация на хеш-таблицах: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «<span style="color: red;">'''Редактирование данной статьи ещё не завершено.'''</span> Редактирование это…»)
 
Нет описания правки
 
(не показано 8 промежуточных версий этого же участника)
Строка 1: Строка 1:
<span style="color: red;">'''Редактирование данной статьи ещё не завершено.'''</span>
Редактирование этой статьи в ближайшее время не планируется.
Редактирование этой статьи в ближайшее время не планируется.


Строка 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 статьи RDSN] (более подробно);
* [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/ сайта]);
* Раздела 3.7 и пункта 3.7.1 [http://www.google.com/search?btnG=1&pws=0&q=%D1%81%D0%BA%D0%B8%D0%B5%D0%BD%D0%B0+%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B+%D1%80%D1%83%D0%BA%D0%BE%D0%B2%D0%BE%D0%B4%D1%81%D1%82%D0%B2%D0%BE+%D0%BF%D0%BE+%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B5+2-%D0%B5+%D0%B8%D0%B7%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5 книги Скиены] (две с половиной страницы), а также [http://www.cs.sunysb.edu/~algorith/video-lectures/2007/lecture6.pdf слайдов].
* Раздела 3.7 и пункта 3.7.1 [http://www.google.com/search?btnG=1&pws=0&q=%D1%81%D0%BA%D0%B8%D0%B5%D0%BD%D0%B0+%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B+%D1%80%D1%83%D0%BA%D0%BE%D0%B2%D0%BE%D0%B4%D1%81%D1%82%D0%B2%D0%BE+%D0%BF%D0%BE+%D1%80%D0%B0%D0%B7%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B5+2-%D0%B5+%D0%B8%D0%B7%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5 книги Скиены] (две с половиной страницы), а также [http://www.cs.sunysb.edu/~algorith/video-lectures/2007/lecture6.pdf слайдов].


Реализация множеств и словарей на хеш-таблицацх в STL появилась в стандарте C++11. Сведения о контейнерах <tt>unordered_set</tt>, <tt>unordered_multiset</tt>, <tt>unordered_map</tt> и <tt>unordered_multimap</tt> можно найти в:
Реализация множеств и словарей на хеш-таблицах в STL появилась в стандарте C++11. Сведения о контейнерах <tt>unordered_set</tt>, <tt>unordered_multiset</tt>, <tt>unordered_map</tt> и <tt>unordered_multimap</tt> можно найти в:


* Материалах cplusplus.com [http://www.cplusplus.com/reference/unordered_map/], [http://www.cplusplus.com/reference/unordered_set/];
* Материалах cplusplus.com [http://www.cplusplus.com/reference/unordered_map/], [http://www.cplusplus.com/reference/unordered_set/];
* Новом издании [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 &mdash; Забор]
 
[[Category:Базовые структуры и абстрактные типы данных]]
 
== Ссылки ==
* [http://codeforces.com/blog/entry/62393 Codeforces — Blowing up unordered_map, and how to stop getting hacked on it]

Текущая версия от 12:19, 28 января 2020

Редактирование этой статьи в ближайшее время не планируется.

Необходимую информацию о хешировании и хеш-таблицах можно получить из:

Реализация множеств и словарей на хеш-таблицах в STL появилась в стандарте C++11. Сведения о контейнерах unordered_set, unordered_multiset, unordered_map и unordered_multimap можно найти в:

Ссылки на задачи

Ссылки