Всем привет.

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

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