...

...

On Mon, Jul 6, 2015 at 3:30 PM, Neil Girdhar <mistersheik@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@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@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.