Tengo algunos datos que vienen con un índice entero. Continúo generando nuevos datos que deben agregarse a la recopilación de datos que tengo, ordenados por ese índice, al mismo tiempo quiero poder ir fácilmente al inicio de los datos e iterarlos. Esto suena como std :: multimap es justo lo que necesito.

Sin embargo, también necesito que los datos con el mismo índice se mantengan en el orden en que se insertaron, en este caso, lo que significa que cuando recorro los datos, obtengo los datos anteriores antes que los últimos.

¿Multimap hace esto?

No he encontrado ninguna garantía de que este sea el caso. En el manual de sgi, no vi ninguna mención de si. Lo probé en la implementación de gcc 4.3.4 y parecía ser cierto para algunos casos de prueba limitados, pero por supuesto me preguntaba si el estándar lo exige y puedo confiar en este hecho.

Editar: Para ser más claro en respuesta a algunas de las respuestas, quería que los datos se ordenaran primero por índice (no único) y luego por tiempo de inserción. Esperaba que tal vez la segunda parte fuera gratis con multimap, pero parece que no.