Python 3でOrderedDictの挿入を実装する方法

Question

OrderedDictに特定の位置に項目を挿入したいとします。だから私はそれは、Pythonで動作しないという問題がある答えるgistthisのを使用して 3.

これは、実装が

ld = ListDict([(1,1), (2,2), (3,3)]) 
ld.insert_before(2, (1.5, 1.5)) 

が

を与える

のようにそれを使用して

from collections import OrderedDict 

class ListDict(OrderedDict): 

    def __init__(self, *args, **kwargs): 
     super(ListDict, self).__init__(*args, **kwargs) 

    def __insertion(self, link_prev, key_value): 
     key, value = key_value 
     if link_prev[2] != key: 
      if key in self: 
       del self[key] 
      link_next = link_prev[1] 
      self._OrderedDict__map[key] = link_prev[1] = link_next[0] = [link_prev, link_next, key] 
     dict.__setitem__(self, key, value) 

    def insert_after(self, existing_key, key_value): 
     self.__insertion(self._OrderedDict__map[existing_key], key_value) 

    def insert_before(self, existing_key, key_value): 
     self.__insertion(self._OrderedDict__map[existing_key][0], key_value) 

を使用しています

File "...", line 35, in insert_before 
    self.__insertion(self._OrderedDict__map[existing_key][0], key_value) 
AttributeError: 'ListDict' object has no attribute '_OrderedDict__map' 

wi thのPython 2.7。 Python 3で失敗する理由は何ですか？ OrderedDictのソースコードを確認すると、self._OrderedDict__mapの代わりにself.__mapが使用されています。コードをself.__mapに変更すると、

AttributeError: 'ListDict' object has no attribute '_ListDict__map' 

どのようになりますか？そして、私はこの作品をPython 3で作ることができますか？ OrderedDictは内部の__map属性を使用して、二重リンクリストを格納します。だから私はこの属性に正しくアクセスできますか？

Answer 1

私はあなたがより良い自分のコード内の別のリストと辞書に追いついて提供されることはないわからないんだけど、ここではそのようなオブジェクトの純粋なPython実装で刺しています。これは、私のコメントhas been rewritten in Cで指摘したように、実際のP​​ython 3.5のOrderedDictよりも遅くなります。

""" 
A list/dict hybrid; like OrderedDict with insert_before and insert_after 
""" 
import collections.abc 


class MutableOrderingDict(collections.abc.MutableMapping): 
    def __init__(self, iterable_or_mapping=None, **kw): 
     # This mimics dict's initialization and accepts the same arguments 
     # Of course, you have to pass an ordered iterable or mapping unless you 
     # want the order to be arbitrary. Garbage in, garbage out and all :) 
     self.__data = {} 
     self.__keys = [] 
     if iterable_or_mapping is not None: 
      try: 
       iterable = iterable_or_mapping.items() 
      except AttributeError: 
       iterable = iterable_or_mapping 
      for key, value in iterable: 
       self.__keys.append(key) 
       self.__data[key] = value 
     for key, value in kw.items(): 
      self.__keys.append(key) 
      self.__data[key] = value 

    def insert_before(self, key, new_key, value): 
     try: 
      self.__keys.insert(self.__keys.index(key), new_key) 
     except ValueError: 
      raise KeyError(key) from ValueError 
     else: 
      self.__data[new_key] = value 

    def insert_after(self, key, new_key, value): 
     try: 
      self.__keys.insert(self.__keys.index(key) + 1, new_key) 
     except ValueError: 
      raise KeyError(key) from ValueError 
     else: 
      self.__data[new_key] = value 

    def __getitem__(self, key): 
     return self.__data[key] 

    def __setitem__(self, key, value): 
     self.__keys.append(key) 
     self.__data[key] = value 

    def __delitem__(self, key): 
     del self.__data[key] 
     self.__keys.remove(key) 

    def __iter__(self): 
     return iter(self.__keys) 

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

    def __contains__(self, key): 
     return key in self.__keys 

    def __eq__(self, other): 
     try: 
      return (self.__data == dict(other.items()) and 
        self.__keys == list(other.keys())) 
     except AttributeError: 
      return False 

    def keys(self): 
     for key in self.__keys: 
      yield key 

    def items(self): 
     for key in self.__keys: 
      yield key, self.__data[key] 

    def values(self): 
     for key in self.__keys: 
      yield self.__data[key] 

    def get(self, key, default=None): 
     try: 
      return self.__data[key] 
     except KeyError: 
      return default 

    def pop(self, key, default=None): 
     value = self.get(key, default) 
     self.__delitem__(key) 
     return value 

    def popitem(self): 
     try: 
      return self.__data.pop(self.__keys.pop()) 
     except IndexError: 
      raise KeyError('%s is empty' % self.__class__.__name__) 


    def clear(self): 
     self.__keys = [] 
     self.__data = {} 

    def update(self, mapping): 
     for key, value in mapping.items(): 
      self.__keys.append(key) 
      self.__data[key] = value 

    def setdefault(self, key, default): 
     try: 
      return self[key] 
     except KeyError: 
      self[key] = default 
      return self[key] 

    def __repr__(self): 
     return 'MutableOrderingDict(%s)' % ', '.join(('%r: %r' % (k, v) 
                 for k, v in self.items())) 

私は方法のどれもが非常に長くなかったので、全体collections.abc.MutableMapping契約を実装することになったが、あなたはおそらく、それらのすべてを使用することはありません。特に、__eq__およびpopitemは少し恣意的です。私はinsert_*メソッドのあなたの署名を、少し自然な感じの4引数に変更しました。最後の注意：Python 3.5でのみテストされています。 Python 2ではいくつかの変更（マイナーな変更なし）では動作しません。

Answer 2

from collections import OrderedDict 

od1 = OrderedDict([ 
    ('a', 1), 
    ('b', 2), 
    ('d', 4), 
]) 

items = od1.items() 
items.insert(2, ('c', 3)) 
od2 = OrderedDict(items) 

print(od2) # OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)]) 

Answer 3

で、Python 3.2、move_to_endを使用して項目を移動することができます。次のコードは、指定されたインデックスの後ろのすべてのアイテムを最後まで移動することによってinsert機能を実装します。

これはあまり効率的ではないため、まったく使用しないでください。

def ordered_dict_insert(ordered_dict, index, key, value): 
    if key in ordered_dict: 
     raise KeyError("Key already exists") 
    if index < 0 or index > len(ordered_dict): 
     raise IndexError("Index out of range") 

    keys = list(ordered_dict.keys())[index:] 
    ordered_dict[key] = value 
    for k in keys: 
     ordered_dict.move_to_end(k) 

明白な最適化と改善がありますが、これは一般的な考えです。