Jag använder en std::map för att spara data. Nu vill jag skriva ut datan i mappen i en loop och undrar om jag kan vara säker på att datan skrivs ut i samma ordning varje gång programmet körs?

I princip blir det nog med 99% sannolikhet så, men det finns så vitt jag vet inte (och bör inte finnas) något krav på det i standarden.

Exakt hur det lagras är en implementationsdetalj, och om man sparar det som ett binärt träd är det inget man gärna håller på och sorterar hur mycket som helst.

Du kan ju om inte annat ta ut grejerna i en vektor och sortera den istället, när du väl behöver?

en std::map är garanterad att vara sorterad efter den "<" relation som du anger.

dvs ordningen blir densamma varje gång och är oberoende av i vilken ordning elementen stoppas in.

Ja, se på jävlars. Jag tänkte nog på set, men det är nog vid närmare eftertanke så där också.
Standarden kräver ju faktiskt operationerna utan att man egentligen behöver dem för definitionen av behållarna.