como o multimap do stl insere ordens de respeito?

Eu tenho alguns dados que vêm com um índice inteiro. Eu estou continuamente gerando novos dados que precisam ser adicionados à coleção de dados que eu tenho, classificados por esse índice, ao mesmo tempo eu quero ser capaz de ir facilmente ao início dos dados e iterar através dele. Isso soa como std :: multimap é exatamente o que eu preciso.

No entanto, também preciso que os dados com o mesmo índice sejam mantidos na ordem em que foram inseridos, significando que, quando eu percorrer os dados, chego aos dados anteriores antes dos dados posteriores.

O multimap faz isso?

Eu não encontrei nenhuma garantia de que este é o caso. No manual do sgi, não vi nenhuma menção sobre se. Eu tentei na implementação do gcc 4.3.4 e pareceu ser verdade para alguns casos de teste limitados, mas é claro que eu estava me perguntando se o padrão exige isso e eu posso confiar nesse fato.

Editar: Para ser mais claro em resposta a algumas das respostas, eu queria que os dados fossem classificados primeiro pelo índice (não exclusivo) e segundo pelo tempo de inserção. Eu esperava que talvez a segunda parte viesse de graça com multimap, mas parece que não.