In working on upsolving https://mirror.codeforces.com/contest/1513/problem/D, I ran into this weird aspect of c++ I need some help explaining:

Part of the solution involved iterating over a sorted ordering, which I initially achieved by inserting everything into a map (not hashmap). I understand that iteration over a map in c++ should produce elements in sorted order. However, this produced a WA result, like in this submission: https://mirror.codeforces.com/contest/1513/submission/112967965.

On replacing the map with an array and then manually sorting that array however, the solution was accepted, like here:https://mirror.codeforces.com/contest/1513/submission/112968002

The only difference between the two submissions is changing the map to a sorted array. To me the logic seems equivalent; iterating over a map should produce an equivalent sorted ordering to the one if you manually sorted an array, however it seems like thats not the case. I was wondering if anyone had any insight on why?

Thanks!