Я хотел бы сохранить отображениеinteger ключ кfloat значение в памяти.

У меня примерно 130 миллионов ключей (и, соответственно, 130 миллионов значений).

Я сосредоточен на производительности поиска - мне нужно сделать много, много миллионов поисков.

Библиотека C ++ STL имеетmap класс для ассоциативных массивов такого рода. У меня есть несколько вопросов оmap.

Что такое накладные расходы на хранениеmap для набора данных указанного выше размера? Как масштабируется общий объем хранилищаmap?

Похоже, что основная структура данных дляmap является красно-черным, сбалансированным бинарным деревом. Звучит как в реальном мирепредставление для этогоO(log n) для вставки и поиска.

Это упоминаетO(1) для намека на вставку. Мои входные данные предварительно отсортированы, поэтому я считаю, что должен быть в состоянии предоставить подсказку для событий вставки. Как бы я дал эту подсказку, используя методы, перечисленныеВот?

Есть ли контейнер STL, который обеспечивает лучшую производительность поиска?

Существуют ли другие общедоступные платформы с открытым исходным кодом с классом связанного массива, который использует базовую структуру данных, которая будет работать лучше, чем STLmap?

Если написание моего собственного класса контейнера обеспечит лучшую производительность поиска, какие структуры данных я могу исследовать?

Для этой задачи я использую GCC 4, работающий под Linux или Mac OS X.

Я заранее прошу прощения, если это глупые вопросы. Спасибо за совет.