It amazes me how easily _bad_ (really bad) ideas catches on. No flak intended towards alan w as he pointed out it was a bad idea. You spend years trying to convince people why std::vector is good or why std::string is good or why CString is good (I prefer std::string but CString >> C-style strings). Sometimes it feels like one don't succeed at all at getting the point through.

But as soon as someone presents a _bad_ idea that breaks neat classes such as std::map it seems people jumps on that bandwagon without much thought.

Just an observation.

PS. To the OP: Why not copy the elements into a std::vector and do an inplace shuffle? If you're worried about memory it's worth to consider that std::map uses a lot more memory than std::vector (to achive O(log n) lookups.