Maintaining insertion order is strictly a product of adding an additional list to whatever more efficient map you implement. Add something to a dict, push it onto the end of the list. When iterating over the keys, use the list instead of the dict structure.

It does come at a cost, but I think Python aims for ease of use over runtime speed and memory efficiency, so it seems perfect for them.