Я хотел бы сохранить сопоставление ключа integer
со значением float
в памяти.
У меня примерно 130 миллионов ключей (и, соответственно, 130 миллионов значений).
Мое внимание сосредоточено на производительности поиска - мне нужно много, много миллионов поисков.
Библиотека С++ STL имеет класс map
для ассоциативных массивов такого типа. У меня есть несколько вопросов о map
.
Что такое накладные расходы на хранение map
для набора данных указанного выше размера? Как накладные расходы на хранение, в общем, с map
?
Похоже, что базовая структура данных для map
- это красно-черное сбалансированное двоичное дерево. Это звучит как реальная производительность для этого O(log n)
для вставки и извлечения.
Он упоминает O(1)
для намеченной вставки. Мой ввод предварительно отсортирован, поэтому я считаю, что должен быть в состоянии дать подсказку о событиях вставки. Как бы я дал эту подсказку, используя перечисленные методы здесь?
Есть ли контейнер STL, который обеспечивает лучшую производительность поиска?
Существуют ли другие общедоступные структуры с открытым исходным кодом с классом ассоциированных массивов, который использует базовую структуру данных, которая будет работать лучше, чем STL map
?
Если запись собственного класса контейнера обеспечит лучшую производительность поиска, какие структуры данных я могу исследовать?
Я использую GCC 4 для этой задачи, работая под Linux или Mac OS X.
Я извиняюсь заранее, если это глупые вопросы. Благодарим вас за советы.