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

M>>Сложность всё равно константная.

TB>В среднем да, в худшем случае нет

Скорее всего, ТСу нужна средняя сложность, вряд ли он делает систему жесткого реального времени. А резервирование/рехеширование можно делать по мере необходимости при вставке, или настроить max_load_factor, чтобы рехеши пореже происходили

Практические рекомендации

Всегда используйте reserve(), если знаете примерный размер

Оптимальный max_load_factor зависит от использования:

Для частых поисков: 0.7-0.8

Для экономии памяти: 1.0-1.5

Для минимизации рехеширования: 2.0-3.0

Профилируйте для нахождения оптимальных параметров

Рассмотрите альтернативные контейнеры, если рехеширование критично