Добрый день.

В конце декабря-начале января я писал прототип отдельного сервиса на C++, чтобы вынести из Java-кода Codeforces тяжелые данные в С++. Давненько я не писал на C++, испытал забавные ощущения погружения в другой мир.

С удивлением обнаружил отсутствие в C++ хэш-мэпа с открытой адресацией в стандартной библиотеке, как впрочем и в boost-e, как впрочем и других нормальных библиотеках. Даже странно как-то, ведь правда же довольно часто открытая адресация будет делать разрешение коллизий цепочками как по времени, так и по памяти. А так как я предполагаю хранить мелкие объекты, то и наверняка.

Я быстренько набросал прототип, который в самом деле показывает, что открытая адресация в раза 2-3 работает быстрее стандартного unordered_map, так что такой контейнер, наверняка, имеет смысл. Вот вывод бенчмарка на моём ноуте:

std::map takes 15779 ms
std::unordered_map takes 4698 ms
oaht::hash_map takes 1473 ms

Мне кажется, что нормальной реализации в stl-стиле с поддержкой С++11 (move semantics) нет. Может кто-то покажет, но я не нашел.

Вот мой прототип на github: https://github.com/MikeMirzayanov/open_addressing_hash_table К сожалению, я не крутой эксперт C++, и со временем у меня совсем не круто, так что довести до ума такой контейнер в обозримом будущем не получится.

С другой стороны, на Codeforces регулярно поднимается обсуждение C++ и, кажется, есть много участников, понимающих современный С++. Алгоритмы же — это вообще вода и воздух Codeforces. У меня есть надежда, что вселенский разум Codeforces и прямые руки кого-то из сообщества поможет довести до ума такой контейнер. Конечно, хочется максимальной совместимости с unordered_map, чтобы API и семантика были максимально эквивалентны (где можно, конечно). Вот примерный список фич, что хочется видеть:

1. One more template type parameter class Pred = std::equal_to<Key>
2. Member function at
3. Member function clear
4. Member function empty
5. Member function insert
6. Member function equal_range
7. Member function swap
8. Member function operator=
9. Member functions load_factor, max_load_factor, rehash, reserve
10. Constant members
11. Member types: difference_type, hasher, key_type, mapped_type, reference, size_type, value_type, pointer, const_reference, key_equal
12. Iterators: member types iterator, const_iterator, member functions begin, end, cbegin, cend
13. Member function emplace
14. Member function emplace_hint
15. Relational operators
16. Non-member function overload: swap
17. Move semantics

Кроме того, хочется сохранить работоспособность на основных реализациях C++11: g++, Visual Studio 13+, clang. Пожалуйста, постарайтесь следовать принципам форматирования oaht.h, чтобы не нарушить единообразие.

Я с удовольствием передам управление этим проектом кому-то, у кого есть энтузиазм, знания C++ и зарекомендованный опыт в задачах. Доброволец, найдись! С меня футболка и +5 к уважению.

P.S. На выходе хочется иметь приличную реализацию, а не абы что, так что есть желание вливать в проект только правильный и красивый код.