[VHRanger]

You can implement the sorted vector of keys with a hash function instead of a coindexed vector of values. It still keeps most of the properties we like, especially if doing the coindex-sort operation is too expensive for some reason.

[obstinate]

> You can implement the sorted vector of keys with a hash function instead of a coindexed vector of values

So you're saying you're going to hash the keys, then sort them according to the hash, with tie breaking on the key itself? I'm not aware of any sorted table that does this, but I'm sure some exist. I suppose you'd get something of a win if N was large, and the keys had long common prefixes, and you didn't care about the ordering property.

But in that case you'd probably use an actual hash table, not the algorithm you just described. Unless there's something I'm missing.

[VHRanger]

Sorry I misspoke. Lookup is always O(1) in a hash table. But this could be a "weak dict" that is you don't actually store the keys, as long as you can reference a key through a hash you can lookup.

In the proper "data structure", we usually store the key and the value -- iteration through keys and/or values and/or pairs are probably supported operations.

Finding a key in the structure (either with binary tree search, or binary search on a sorted array, or linear lookup on an array) varies. So does iteration and most other operations.