So, let's review what we have in terms of data structures:
Structure Stable Unique Python type
Multiset no no - Set no yes set Map no yes dict List yes no list, tuple Ordered set yes yes - Ordered map yes yes collections.OrderedDict
where "stable" means that input order is retained.
<slightly off topic>
And where do Multimaps fit in? And Ordered Mulitmaps? Example of an Ordered Multimap in the wild: the headers of an email message, where multiple values may be attached to a single key, and the ordering of key-value pairs is important (and not all key-value pairs with the same key are necessarily adjacent). But basically it is anything that behaves like a sequence of key-value pairs. Come to think of it, 'headers' in lots of network protocols are like this.
(ps: +0 on adding ordered sets)