[Python-ideas] Indexable dict and set (was: OrderedDict.peekitem())

[Grant Jenks]

>>> On Mon, Jul 6, 2015 at 3:30 PM, Neil Girdhar <mistersheik at gmail.com>
>>> wrote:
>>> SortedDict
>>> (http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html)
>>> manages to support indexing.  Can OrderedDict do the same thing?
>>
>> On Mon, Jul 6, 2015 at 5:59 PM, Eric Snow <ericsnowcurrently at gmail.com>
>> wrote:
>>
>> Don't forget that, as the docs describe, an "OrderedDict is a dict
>> that remembers the order that keys were first inserted".  While
>> obviously there's an implicit sequence for that order, the focus is
>> still on dict-ness with the sequence exposed through the normal
>> mapping approach (iteration).  If you want to get sequence semantics
>> then first unpack the order into a sequence type like list or tuple.
>> Or use some other type than OrderedDict.
>
> On Mon, Jul 6, 2015 at 3:04 PM, Neil Girdhar <mistersheik at gmail.com> wrote:
> You can do indexing, insertion, and removal all in logarithmic time (which
> is basically constant) by using a B-tree as the underlying data structure.
> (See e.g. the blist package.)

If you want a `dict` or `set` that is indexable, it's quite easy using
the sortedcontainers module. Just use the hash function as the key:

```python
from sortedcontainers import SortedDict, SortedSet

class DictWithIndex(SortedDict):
    def __init__(self, *args, **kwargs):
        super(DictWithIndex, self).__init__(hash, *args, **kwargs)

class SetWithIndex(SortedSet):
    def __init__(self, *args, **kwargs):
        super(SetWithIndex, self).__init__(*args, key=hash, **kwargs)

```

The ordering can be quasi-random but the indexing can still be useful.
Example usage:

```
In [2]: d = DictWithIndex(enumerate('abcde'))

In [3]: d.iloc[4]
Out[3]: 4

In [4]: d.iloc[-2]
Out[4]: 3

In [5]: s = SetWithIndex('abcde')

In [6]: s[4]
Out[6]: 'e'

In [7]: s[-2]
Out[7]: 'd'
```

The likelihood that the hash collides is low and when it does so, the
order will be based on insertion order.