Всем привет.
Не знаю, зачем я начал делать этот велосипед, но тем не менее
он получился с рядом интересных звоночков и свисточков.
Что получилось:
Узловой ассоциативный контейнер с modification stable итератором.
Ключ должен быть copy constructable, иметь operator== и
для него должна быть хэш функция возвращающая 32-битный хэш код.
Сложность вставки, поиска и удаления относительно операций с ключом — O(1).
При отсутствии коллизий не более одной операции сравнения.
В отличии от hash table у hash tree менее жесткие требования
на хэш функцию. Главное, что б hash code отличался.
Коллизия возникнет только при полном совпадении 32-битного хэш кода.
В качестве бонуса моя реализаци контейнера обладает fifo семантикой.
Прототип с benchmark можно скачать тут:
https://sites.google.com/site/hashtree2011/download
Сравниваются std::map, hashtree, кондовая реализация hash table для char* ключей и unordered_map из boost при
наличии такового (-DHAVE_BOOST).
EX>Сравниваются std::map, hashtree, кондовая реализация hash table для char* ключей и unordered_map из boost при
EX>наличии такового (-DHAVE_BOOST).
ну так огласи результаты
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Здравствуйте, e-Xecutor, Вы писали:
EX>Прототип с benchmark можно скачать тут: https://sites.google.com/site/hashtree2011/download
имхо бенчмарк лучше было делать на шаблонах а не на интерфейсах. Я не помню чтобы контейнер кто-то заворачивал в интерфейс — тест вносит искажение по сравнению с реальным использованием.
Здравствуйте, SleepyDrago, Вы писали:
SD>Здравствуйте, e-Xecutor, Вы писали:
EX>>Прототип с benchmark можно скачать тут: https://sites.google.com/site/hashtree2011/download
SD>имхо бенчмарк лучше было делать на шаблонах а не на интерфейсах. Я не помню чтобы контейнер кто-то заворачивал в интерфейс — тест вносит искажение по сравнению с реальным использованием.
С другой стороны, обращение к контейнерам нередко происходит из виртуальных методов.