def __iter__(self):
    return (k for k, _ in self._list)

def __contains__(self, k):
    i = bisect.bisect_left(self._list, (k, None))
return i < len(self._list) and self._list[i][0] == k

def __len__(self):
    return len(self._list)

def __getitem__(self, k):
    i = bisect.bisect_left(self._list, (k, None))
if i >= len(self._list):
    raise KeyError(k)
return self._list[i][1]
Словарь Python - бинарный поиск ключа?