You're not going to find a basic data structure that does this; the goals you're looking for rule out all of them. You might find an more esoteric one that'll do it, but the easiest approach is to use a compound data structure, maintaining two data structures in parallel.
That's what collections.OrderedDict does under the hood, in fact. That's not what you want, though: since it's not designed to support indexing, it uses a linked list under the hood for preserving order. Linked lists can't do indexing--short of a slow, linear scan, which you usually want to avoid since it tends to turn O(n^2) on you if used in a loop.
Here's a simple implementation. It maintains two data structures: a list, preserving the order of items as they're set, and a dict, for quick lookup by key. Both hold the value, and both hold the other's key: the dict holds the index within the list, and the list holds the key within the dict. This makes it easy to reference each data structure from the other, so it can handle both assignment and iteration efficiently.
Note that this doesn't implement every operation, just the basic ones: dict-style assignment a['x'] = 1, dict-style lookup a['x'], list-style assignment a.set_value_by_index(0, 1) and list-style lookup a.get_value_by_index(0).
Also note carefully: this doesn't use the same syntax for dict-style and list-style operations. That's confusing and evil, and will bite you badly sooner or later. This doesn't turn a[0] into a list-style lookup; if that's what you want, be explicit and use get_value_by_index. Don't be magic and try to guess based on the parameter type.
Finally, it provides simple dict-style iteration, yielding the keys as a dict does. Implementing things like iteritems and itervalues or Python3 views are obvious extensions.
class IndexableUniqueList(object):
"""
>>> a = IndexableUniqueList()
>>> a['x'] = 1
>>> a['x']
1
>>> a['y'] = 2
>>> a['y']
2
>>> a.get_key_by_index(0)
'x'
>>> a.get_value_by_index(0)
1
>>> a.get_key_by_index(1)
'y'
>>> a.get_value_by_index(1)
2
>>> a['x'] = 3
>>> a.get_key_by_index(0)
'x'
>>> a.get_value_by_index(0)
3
>>> a.set_value_by_index(0, 4)
>>> a['x']
4
>>> [val for val in a]
['x', 'y']
"""
def __init__(self):
self.items_by_index = []
self.items_by_key = {}
def __getitem__(self, key):
return self.items_by_key[key][1]
def __setitem__(self, key, value):
if key in self.items_by_key:
idx, old_value = self.items_by_key[key]
self.items_by_key[key] = (idx, value)
self.items_by_index[idx] = (key, value)
return
idx = len(self.items_by_index)
self.items_by_key[key] = (idx, value)
self.items_by_index.append((key, value))
def get_key_by_index(self, idx):
return self.items_by_index[idx][0]
def get_value_by_index(self, idx):
key = self.get_key_by_index(idx)
return self.items_by_key[key][1]
def set_value_by_index(self, idx, value):
key = self.items_by_index[idx][0]
self[key] = value
def __iter__(self):
for key, value in self.items_by_index:
yield key
data.items()[123]?