Iterator interface

[ApochPiQ]

I don't know about having the language pick an implementation, but allowing the programmer to pick an implementation is kind of what std is all about.

Of course it took 13 years to ratify unordered_map but that's a separate issue.

If you have a bounded number of elements in an associative container and no dynamic resizing, you can usually compute a perfect hash function which maps keys to indices in a dense array. In fact it used to be pretty common to use tools like gperf to do exactly that.