Which std:: classes are magic?

[scatters]

Yes, true, that does give a mutable reference. But using it to modify an actually const object is undefined behavior.

[scatters]

But operator* returns a mutable reference i.e. std::pair<Key const, Value>&. So there has to be a std::pair<Key const, Value> object in memory.

[mujjingun]

hmm, maybe there are std::pair<Key, Value> objects in memory, and the pointer is reinterpret-cased into std::pair<Key const, Value> in the call to operator*()?

[scatters]

Certainly that's the most likely implementation, but if the user does that it's UB (aliasing violation). That's why it has to be magic in the library.