博士

ロボ子、Pythonの辞書って、バージョン3.7から挿入順序が保証されるようになったのじゃな。知っておるか？

ロボ子

はい、博士。それまでは`collections.OrderedDict`を使っていましたね。

博士

`collections.OrderedDict`は今でも標準ライブラリに残っておるんじゃ。なぜか分かるか？

ロボ子

後方互換性の維持と、キーの順序を等価性の要素として扱う点が通常の辞書と異なるから、でしたっけ。

博士

その通り！それに、`move_to_end`みたいな追加機能もあるからの。

ロボ子

`OrderedDict`の実装って、どうなっているんでしょう？

博士

`dict`を継承して、キーと値のペアを格納するのは当然として、キーの順序を追跡するために外部データ構造を追加しておるんじゃ。

ロボ子

双方向連結リストと別の辞書を組み合わせているんでしたね。双方向連結リストはO(1)でノードの挿入と削除をサポートするんでしたか。

博士

そうじゃ！各ノードは`OrderedDict`のキーを格納しておる。そして、別の辞書は連結リスト内のノードをO(1)で検索できるのじゃ。

ロボ子

`__setitem__`メソッドは、キーと値のペアを書き込む際に、連結リストのノードを作成して`self.__map`に格納するんですね。

博士

`__delitem__()`や`pop()`も同じように、辞書と連結リストを更新するのじゃ。

ロボ子

`OrderedDict`は`__iter__`をカスタマイズして、順序を維持したイテレーションを実現しているんですね。

博士

そう！双方向連結リストと辞書インデックスの組み合わせは、メモリを少し消費する代わりに、予測可能なイテレーションを実現しておるのじゃ。

ロボ子

`weakref`モジュールを使って参照カウントによる循環参照を回避しているのも興味深いですね。

博士

`pop`メソッドでキーが存在しない場合のデフォルト値として`object()`を使用しているのはなぜか分かるか？

ロボ子

`object()`はユーザーデータに現れないことが保証されているため、キーが存在するかどうかを正確に区別できるから、でしたっけ。

博士

その通り！しかし、`OrderedDict`って、ちょっとメモリ食い虫じゃな。まるで、私の冷蔵庫みたいだぞ。

ロボ子

博士の冷蔵庫は、いつも面白いものでいっぱいですからね。