Me gustaría almacenar un mapeo de uninteger clave para unfloat valor en memoria.

Tengo aproximadamente 130 millones de llaves (y, en consecuencia, 130 millones de valores).

Mi enfoque está en el rendimiento de búsqueda, tengo que hacer muchos, muchos millones de búsquedas.

La librería STL de C ++ tiene unamap Clase para matrices asociativas de este tipo. Tengo varias preguntas sobremap.

¿Cuál es la sobrecarga de almacenamiento demap para un conjunto de datos del tamaño mencionado anteriormente? ¿Cómo escala de gastos generales de almacenamiento, en general, conmap?

Parece que la estructura de datos subyacente paramap Es un árbol binario equilibrado rojo-negro. Suena como el mundo real.actuación porque esto esO(log n) Para la inserción y recuperación.

Se mencionaO(1) para una inserción insinuada. Mi entrada está pre-ordenada, por lo que creo que debería poder proporcionar una sugerencia para los eventos de inserción. ¿Cómo puedo proporcionar esta sugerencia, utilizando los métodos enumerados?aquí?

¿Hay un contenedor STL que proporcione un mejor rendimiento de búsqueda?

¿Existen otros marcos de código abierto de acceso público con una clase de matriz asociada que use una estructura de datos subyacente que funcionaría mejor que STL?map?

Si escribir mi propia clase contenedora proporcionaría un mejor rendimiento de búsqueda, ¿qué estructuras de datos podría investigar?

Estoy usando GCC 4 para esta tarea, ejecutando bajo Linux o Mac OS X.

Pido disculpas por adelantado si estas son preguntas tontas. Gracias por tu consejo.