Всем привет.

Не знаю, зачем я начал делать этот велосипед, но тем не менее
он получился с рядом интересных звоночков и свисточков.

Что получилось:
Узловой ассоциативный контейнер с 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).
ну так огласи результаты

Здравствуйте, rm822, Вы писали:

EX>>Сравниваются std::map, hashtree, кондовая реализация hash table для char* ключей и unordered_map из boost при
EX>>наличии такового (-DHAVE_BOOST).
R>ну так огласи результаты
Результат разный для разных платформ, компиляторов, тестов и ключей.

В среднем hash tree чуть-чуть медленнее hash table и umap,
но сильно быстрее чем std::map. Это на строковых ключах.
Итерирование по этой реализации hash tree на порядок быстрее остальных использованных контейнеров.

На opteron-ах при компиляции сановским компилятором hash tree оказывается быстрее всех.

Здравствуйте, 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>имхо бенчмарк лучше было делать на шаблонах а не на интерфейсах. Я не помню чтобы контейнер кто-то заворачивал в интерфейс — тест вносит искажение по сравнению с реальным использованием.
С другой стороны, обращение к контейнерам нередко происходит из виртуальных методов.