Стоит задача быстрого нахождения элемента по ключу. Использую stl. Для реальной задачи он должен быть достаточно большой.

Стоит ли делать такой большой ключ или лучше сделать хэш-таблицу для этого случая, или map, где в качестве значения список c разными id. Тут надо сказать, что различных id планируется немного, а в большинстве случаев это будет массив нулей. Мне кажется, что в большом ключе страшного ничего нет, если значения в общей массе будут различаться в начале области памяти, a less делать каким-нибудь memcmp.

+ Еще такой вопрос: как сыграет на производительности, если сделать в качестве ключа структуру с двумя конструкторами - ну очень уж удобно. Я пока не понимаю как это все в памяти лежит, где указатели на методы и т.п. Читаю ABI, но пока понимая нет.

Спасибо.

Хэш таблица нужна тогда, когда количество элементов в контейнере довольно большое. Если у тебя десяток элементов, то скорее всего, ты получишь замедление, по сравнению с обычным map.

Количество конструкторов и других методов не влияет на скорость. Ключи сравниваются с помощью less. Другие операции к ним не применяются. Конструкторы вызываются лишь один раз при создании элемента (ты, надеюсь, контейнеры целиком не копируешь?).

Количество элементов не больше 65535. 

Это да. Если нет полиморфизма, то размер ключа будет размер величине данных, так?  
Это я все думаю о размере и как он будет влиять на сложность поиска и вставки.

Думаю, что фактически размер ключа влияет только на скорость сравнения элементов. Следовательно, если я буду сравнивать до первого расхождения и данные ключа расположить по степени редкости этого расхождения, то вполне можно оставить map с таким ключом. 

Максимальное количество не сильно интересно. Скорей интересно среднее-взвешенное (с вероятностью 80% количество элементов будет от 10-20 или от 10000 до 20000).
не забывай о выравнивании. Но в целом да (только тут не полиморфизм, а всего-лишь наличие виртуальных функций).
скорость поиска зависит от метода поиска, скорости сравнения и количества элементов. Если ты сравниваешь через memcmp, то да, скорость будет зависеть от размера ключа.
memcmp именно так и работает - до первого расхождения.

А вот и не так. 
Для составных ключей, если мне память не изменяет, есть не map, а multimap.
А иначе получится такая вещь. Для контейнеров существуют свои алгоритмы поиска и так далее по списку. В случае если вы закидываете в стандартный контейнер некую структуру с дополнительными условиями сортировки и поиска, для которого используете свой алгоритм (у которого есть примерный показатель затратности опреаций поиска и сортировки), это всё может наложиться на сопутствующие действия контейнера  и привести к довольно неожиданным для разработчика результатам.

ну не совсем . если std::map позволяет держать асоциацию один к одному, то std::multimap - один ко многим, один ключ - много значений. 

скорость вставки и поиска в std::map зависит от алгоритма сравнение обьектов типа, который используется для ключа.

Это сообщение отредактировал(а) SenkraD - 20.8.2013, 15:06

Во-во, а то я уже обрадовался, что что-то знаю)