Winnipuh,

Map не имеет порядка, элементы в map не упорядочены.
Если тебе нужен порядок, используй другой контейнер, другую коллекцию.
Порядок поддерживают списки и вектора.
Если тебе при этом надо ещё и быстро искать по ключу map-ы, то храни две коллекции,
map и плюс к этому ещё и vector или list. При этом в одно структуре можно хранить
элементы по значению, в другой -- в виде ссылок.

Например,
std::vector< MyStruct > xxx;
и
std::map< key, MyStruct* > xxx;