The difference between python dict and tr1::unordered_map in C++

Question

I have a question related to understanding of how python dictionaries work.

I remember reading somewhere strings in python are immutable to allow hashing, and it is the same reason why one cannot directly use lists as keys, i.e. the lists are mutable (by supporting .append) and hence they cannot be used as dictionary keys.

I wanted to know how does implementation of unordered_map in C++ handles these cases. (since strings in C++ are mutable)

Behka

Wish I could edit posts, so I could edit away the "'" in "dict's"... ;-) (Yes, I'm in a snarky mood ;-) – Impaste

Answer 1

Keys in all C++ map/set containers are const and thus immutable (after added to the container).

Notice that C++ containers are not specific to string keys, you can use any objects, but the constness will prevent modifications after the key is copied to the container.

Slumlord

What will happen if someone uses const_cast to mess around with keys. Thanks – Behka

Reference: sgi.com/tech/stl/Map.html -- value_type is defined as "The type of object, pair<const key_type, data_type>, stored in the map." Note the const. – Dayledaylight

@Akshay: if someone does that, they get what they deserve :) std::map is implemented using a red-black tree. Changing a key would invalidate the tree. unordered_map is implemented using a hash table. Changing a key would mean you likely would never find that item again, because it would probably be in the wrong hash bucket for its new key. – Dayledaylight

@Akshay @Dan: More specifically, modifying a const object through a const_cast leads to undefined behavior. – Aronson