On Mon, Aug 31, 2020 at 9:30 PM <junknenopok@gmail.com> wrote:
I have a use case which relates to this request: iterating over a dict starting from a given key. I would like to achieve this without having to pay the full O(n) cost if I'm going to be iterating over only a few items. My understanding is that this should be achievable without needing to iterate through the entire dict, since the dict's internal key lookup points to a particular index of dk_entries anyway.
[snip]
Doing this efficiently would require either the addition of indexing to dicts as well as some sort of get_key_index operation, or else could be done without knowing indices if an iter_from_key operation were introduced (which used the internal dk_indices to know where to start iterating over dk_entries). I think this thread touches on the same sorts of debates however so I'm mentioning this here.
Note that proposed index access is O(n), not O(1). So `get_key_index` doesn't match your use case. On the other hand, iter_from_key is possible idea. Another API idea is `d.next_item(key)` and `d.prev_item(key)`. They return None if the key is left/right end. They raise KeyError if key not found. Other wise, they return (key, item) pair.
I also think that even if adding new features to the built-in dict is undesirable, adding a collections.IndexableDict would be very useful (sortedcollections.IndexableDict exists but sorting is not acceptable for many use cases).
Maybe, OrderedDict can have od.next_item(key) and od.prev_item(key). Regards, -- Inada Naoki <songofacandy@gmail.com>