Tak, w std::map przy iterowaniu iteratorem będziesz dostawał wartości posortowane według klucza. Dla std::multimap jeśli klucze są identyczne, kolejność będzie zgodna z kolejnością wstawienia.
(no i nie chodzi o to że "sama się sortuje", tylko sama natura tego jak jest zaimplementowana - drzewem czerwono-czarnym - sprawia że elemeny będą "posortowane".)
Jak sama nazwa wskazuje, std::unordered_map i std::unordered_set nie mają żadnej konkretnej kolejności elementów.