405 lines
30 KiB
HTML
405 lines
30 KiB
HTML
|
||
<!DOCTYPE html>
|
||
<html lang="en">
|
||
<head>
|
||
<meta charset="utf-8">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
||
<meta name="color-scheme" content="light dark">
|
||
<title>PEP 372 – Adding an ordered dictionary to collections | peps.python.org</title>
|
||
<link rel="shortcut icon" href="../_static/py.png">
|
||
<link rel="canonical" href="https://peps.python.org/pep-0372/">
|
||
<link rel="stylesheet" href="../_static/style.css" type="text/css">
|
||
<link rel="stylesheet" href="../_static/mq.css" type="text/css">
|
||
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" media="(prefers-color-scheme: light)" id="pyg-light">
|
||
<link rel="stylesheet" href="../_static/pygments_dark.css" type="text/css" media="(prefers-color-scheme: dark)" id="pyg-dark">
|
||
<link rel="alternate" type="application/rss+xml" title="Latest PEPs" href="https://peps.python.org/peps.rss">
|
||
<meta property="og:title" content='PEP 372 – Adding an ordered dictionary to collections | peps.python.org'>
|
||
<meta property="og:description" content="This PEP proposes an ordered dictionary as a new data structure for the collections module, called “OrderedDict” in this PEP. The proposed API incorporates the experiences gained from working with similar implementations that exist in various real-worl...">
|
||
<meta property="og:type" content="website">
|
||
<meta property="og:url" content="https://peps.python.org/pep-0372/">
|
||
<meta property="og:site_name" content="Python Enhancement Proposals (PEPs)">
|
||
<meta property="og:image" content="https://peps.python.org/_static/og-image.png">
|
||
<meta property="og:image:alt" content="Python PEPs">
|
||
<meta property="og:image:width" content="200">
|
||
<meta property="og:image:height" content="200">
|
||
<meta name="description" content="This PEP proposes an ordered dictionary as a new data structure for the collections module, called “OrderedDict” in this PEP. The proposed API incorporates the experiences gained from working with similar implementations that exist in various real-worl...">
|
||
<meta name="theme-color" content="#3776ab">
|
||
</head>
|
||
<body>
|
||
|
||
<svg xmlns="http://www.w3.org/2000/svg" style="display: none;">
|
||
<symbol id="svg-sun-half" viewBox="0 0 24 24" pointer-events="all">
|
||
<title>Following system colour scheme</title>
|
||
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" fill="none"
|
||
stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round">
|
||
<circle cx="12" cy="12" r="9"></circle>
|
||
<path d="M12 3v18m0-12l4.65-4.65M12 14.3l7.37-7.37M12 19.6l8.85-8.85"></path>
|
||
</svg>
|
||
</symbol>
|
||
<symbol id="svg-moon" viewBox="0 0 24 24" pointer-events="all">
|
||
<title>Selected dark colour scheme</title>
|
||
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" fill="none"
|
||
stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round">
|
||
<path stroke="none" d="M0 0h24v24H0z" fill="none"></path>
|
||
<path d="M12 3c.132 0 .263 0 .393 0a7.5 7.5 0 0 0 7.92 12.446a9 9 0 1 1 -8.313 -12.454z"></path>
|
||
</svg>
|
||
</symbol>
|
||
<symbol id="svg-sun" viewBox="0 0 24 24" pointer-events="all">
|
||
<title>Selected light colour scheme</title>
|
||
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" fill="none"
|
||
stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round">
|
||
<circle cx="12" cy="12" r="5"></circle>
|
||
<line x1="12" y1="1" x2="12" y2="3"></line>
|
||
<line x1="12" y1="21" x2="12" y2="23"></line>
|
||
<line x1="4.22" y1="4.22" x2="5.64" y2="5.64"></line>
|
||
<line x1="18.36" y1="18.36" x2="19.78" y2="19.78"></line>
|
||
<line x1="1" y1="12" x2="3" y2="12"></line>
|
||
<line x1="21" y1="12" x2="23" y2="12"></line>
|
||
<line x1="4.22" y1="19.78" x2="5.64" y2="18.36"></line>
|
||
<line x1="18.36" y1="5.64" x2="19.78" y2="4.22"></line>
|
||
</svg>
|
||
</symbol>
|
||
</svg>
|
||
<script>
|
||
|
||
document.documentElement.dataset.colour_scheme = localStorage.getItem("colour_scheme") || "auto"
|
||
</script>
|
||
<section id="pep-page-section">
|
||
<header>
|
||
<h1>Python Enhancement Proposals</h1>
|
||
<ul class="breadcrumbs">
|
||
<li><a href="https://www.python.org/" title="The Python Programming Language">Python</a> » </li>
|
||
<li><a href="../pep-0000/">PEP Index</a> » </li>
|
||
<li>PEP 372</li>
|
||
</ul>
|
||
<button id="colour-scheme-cycler" onClick="setColourScheme(nextColourScheme())">
|
||
<svg aria-hidden="true" class="colour-scheme-icon-when-auto"><use href="#svg-sun-half"></use></svg>
|
||
<svg aria-hidden="true" class="colour-scheme-icon-when-dark"><use href="#svg-moon"></use></svg>
|
||
<svg aria-hidden="true" class="colour-scheme-icon-when-light"><use href="#svg-sun"></use></svg>
|
||
<span class="visually-hidden">Toggle light / dark / auto colour theme</span>
|
||
</button>
|
||
</header>
|
||
<article>
|
||
<section id="pep-content">
|
||
<h1 class="page-title">PEP 372 – Adding an ordered dictionary to collections</h1>
|
||
<dl class="rfc2822 field-list simple">
|
||
<dt class="field-odd">Author<span class="colon">:</span></dt>
|
||
<dd class="field-odd">Armin Ronacher <armin.ronacher at active-4.com>,
|
||
Raymond Hettinger <python at rcn.com></dd>
|
||
<dt class="field-even">Status<span class="colon">:</span></dt>
|
||
<dd class="field-even"><abbr title="Accepted and implementation complete, or no longer active">Final</abbr></dd>
|
||
<dt class="field-odd">Type<span class="colon">:</span></dt>
|
||
<dd class="field-odd"><abbr title="Normative PEP with a new feature for Python, implementation change for CPython or interoperability standard for the ecosystem">Standards Track</abbr></dd>
|
||
<dt class="field-even">Created<span class="colon">:</span></dt>
|
||
<dd class="field-even">15-Jun-2008</dd>
|
||
<dt class="field-odd">Python-Version<span class="colon">:</span></dt>
|
||
<dd class="field-odd">2.7, 3.1</dd>
|
||
<dt class="field-even">Post-History<span class="colon">:</span></dt>
|
||
<dd class="field-even"><p></p></dd>
|
||
</dl>
|
||
<hr class="docutils" />
|
||
<section id="contents">
|
||
<details><summary>Table of Contents</summary><ul class="simple">
|
||
<li><a class="reference internal" href="#abstract">Abstract</a></li>
|
||
<li><a class="reference internal" href="#patch">Patch</a></li>
|
||
<li><a class="reference internal" href="#rationale">Rationale</a></li>
|
||
<li><a class="reference internal" href="#ordered-dict-api">Ordered Dict API</a></li>
|
||
<li><a class="reference internal" href="#questions-and-answers">Questions and Answers</a></li>
|
||
<li><a class="reference internal" href="#reference-implementation">Reference Implementation</a></li>
|
||
<li><a class="reference internal" href="#future-directions">Future Directions</a></li>
|
||
<li><a class="reference internal" href="#references">References</a></li>
|
||
<li><a class="reference internal" href="#copyright">Copyright</a></li>
|
||
</ul>
|
||
</details></section>
|
||
<section id="abstract">
|
||
<h2><a class="toc-backref" href="#abstract" role="doc-backlink">Abstract</a></h2>
|
||
<p>This PEP proposes an ordered dictionary as a new data structure for
|
||
the <code class="docutils literal notranslate"><span class="pre">collections</span></code> module, called “OrderedDict” in this PEP. The
|
||
proposed API incorporates the experiences gained from working with
|
||
similar implementations that exist in various real-world applications
|
||
and other programming languages.</p>
|
||
</section>
|
||
<section id="patch">
|
||
<h2><a class="toc-backref" href="#patch" role="doc-backlink">Patch</a></h2>
|
||
<p>A working Py3.1 patch including tests and documentation is at:</p>
|
||
<blockquote>
|
||
<div><a class="reference external" href="https://github.com/python/cpython/issues/49647">OrderedDict patch</a></div></blockquote>
|
||
<p>The check-in was in revisions: 70101 and 70102</p>
|
||
</section>
|
||
<section id="rationale">
|
||
<h2><a class="toc-backref" href="#rationale" role="doc-backlink">Rationale</a></h2>
|
||
<p>In current Python versions, the widely used built-in dict type does
|
||
not specify an order for the key/value pairs stored. This makes it
|
||
hard to use dictionaries as data storage for some specific use cases.</p>
|
||
<p>Some dynamic programming languages like PHP and Ruby 1.9 guarantee a
|
||
certain order on iteration. In those languages, and existing Python
|
||
ordered-dict implementations, the ordering of items is defined by the
|
||
time of insertion of the key. New keys are appended at the end, but
|
||
keys that are overwritten are not moved to the end.</p>
|
||
<p>The following example shows the behavior for simple assignments:</p>
|
||
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">d</span> <span class="o">=</span> <span class="n">OrderedDict</span><span class="p">()</span>
|
||
<span class="gp">>>> </span><span class="n">d</span><span class="p">[</span><span class="s1">'parrot'</span><span class="p">]</span> <span class="o">=</span> <span class="s1">'dead'</span>
|
||
<span class="gp">>>> </span><span class="n">d</span><span class="p">[</span><span class="s1">'penguin'</span><span class="p">]</span> <span class="o">=</span> <span class="s1">'exploded'</span>
|
||
<span class="gp">>>> </span><span class="n">d</span><span class="o">.</span><span class="n">items</span><span class="p">()</span>
|
||
<span class="go">[('parrot', 'dead'), ('penguin', 'exploded')]</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>That the ordering is preserved makes an OrderedDict useful for a couple of
|
||
situations:</p>
|
||
<ul>
|
||
<li>XML/HTML processing libraries currently drop the ordering of
|
||
attributes, use a list instead of a dict which makes filtering
|
||
cumbersome, or implement their own ordered dictionary. This affects
|
||
ElementTree, html5lib, Genshi and many more libraries.</li>
|
||
<li>There are many ordered dict implementations in various libraries
|
||
and applications, most of them subtly incompatible with each other.
|
||
Furthermore, subclassing dict is a non-trivial task and many
|
||
implementations don’t override all the methods properly which can
|
||
lead to unexpected results.<p>Additionally, many ordered dicts are implemented in an inefficient
|
||
way, making many operations more complex then they have to be.</p>
|
||
</li>
|
||
<li><a class="pep reference internal" href="../pep-3115/" title="PEP 3115 – Metaclasses in Python 3000">PEP 3115</a> allows metaclasses to change the mapping object used for
|
||
the class body. An ordered dict could be used to create ordered
|
||
member declarations similar to C structs. This could be useful, for
|
||
example, for future <code class="docutils literal notranslate"><span class="pre">ctypes</span></code> releases as well as ORMs that define
|
||
database tables as classes, like the one the Django framework ships.
|
||
Django currently uses an ugly hack to restore the ordering of
|
||
members in database models.</li>
|
||
<li>The RawConfigParser class accepts a <code class="docutils literal notranslate"><span class="pre">dict_type</span></code> argument that
|
||
allows an application to set the type of dictionary used internally.
|
||
The motivation for this addition was expressly to allow users to
|
||
provide an ordered dictionary. <a class="footnote-reference brackets" href="#id3" id="id1">[1]</a></li>
|
||
<li>Code ported from other programming languages such as PHP often
|
||
depends on an ordered dict. Having an implementation of an
|
||
ordering-preserving dictionary in the standard library could ease
|
||
the transition and improve the compatibility of different libraries.</li>
|
||
</ul>
|
||
</section>
|
||
<section id="ordered-dict-api">
|
||
<h2><a class="toc-backref" href="#ordered-dict-api" role="doc-backlink">Ordered Dict API</a></h2>
|
||
<p>The ordered dict API would be mostly compatible with dict and existing
|
||
ordered dicts. Note: this PEP refers to the 2.7 and 3.0 dictionary
|
||
API as described in collections.Mapping abstract base class.</p>
|
||
<p>The constructor and <code class="docutils literal notranslate"><span class="pre">update()</span></code> both accept iterables of tuples as
|
||
well as mappings like a dict does. Unlike a regular dictionary,
|
||
the insertion order is preserved.</p>
|
||
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">d</span> <span class="o">=</span> <span class="n">OrderedDict</span><span class="p">([(</span><span class="s1">'a'</span><span class="p">,</span> <span class="s1">'b'</span><span class="p">),</span> <span class="p">(</span><span class="s1">'c'</span><span class="p">,</span> <span class="s1">'d'</span><span class="p">)])</span>
|
||
<span class="gp">>>> </span><span class="n">d</span><span class="o">.</span><span class="n">update</span><span class="p">({</span><span class="s1">'foo'</span><span class="p">:</span> <span class="s1">'bar'</span><span class="p">})</span>
|
||
<span class="gp">>>> </span><span class="n">d</span>
|
||
<span class="go">collections.OrderedDict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>If ordered dicts are updated from regular dicts, the ordering of new
|
||
keys is of course undefined.</p>
|
||
<p>All iteration methods as well as <code class="docutils literal notranslate"><span class="pre">keys()</span></code>, <code class="docutils literal notranslate"><span class="pre">values()</span></code> and
|
||
<code class="docutils literal notranslate"><span class="pre">items()</span></code> return the values ordered by the time the key was
|
||
first inserted:</p>
|
||
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">d</span><span class="p">[</span><span class="s1">'spam'</span><span class="p">]</span> <span class="o">=</span> <span class="s1">'eggs'</span>
|
||
<span class="gp">>>> </span><span class="n">d</span><span class="o">.</span><span class="n">keys</span><span class="p">()</span>
|
||
<span class="go">['a', 'c', 'foo', 'spam']</span>
|
||
<span class="gp">>>> </span><span class="n">d</span><span class="o">.</span><span class="n">values</span><span class="p">()</span>
|
||
<span class="go">['b', 'd', 'bar', 'eggs']</span>
|
||
<span class="gp">>>> </span><span class="n">d</span><span class="o">.</span><span class="n">items</span><span class="p">()</span>
|
||
<span class="go">[('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', 'eggs')]</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>New methods not available on dict:</p>
|
||
<dl class="simple">
|
||
<dt><code class="docutils literal notranslate"><span class="pre">OrderedDict.__reversed__()</span></code></dt><dd>Supports reverse iteration by key.</dd>
|
||
</dl>
|
||
</section>
|
||
<section id="questions-and-answers">
|
||
<h2><a class="toc-backref" href="#questions-and-answers" role="doc-backlink">Questions and Answers</a></h2>
|
||
<p>What happens if an existing key is reassigned?</p>
|
||
<blockquote>
|
||
<div>The key is not moved but assigned a new value in place. This is
|
||
consistent with existing implementations.</div></blockquote>
|
||
<p>What happens if keys appear multiple times in the list passed to the
|
||
constructor?</p>
|
||
<blockquote>
|
||
<div>The same as for regular dicts – the latter item overrides the
|
||
former. This has the side-effect that the position of the first
|
||
key is used because only the value is actually overwritten:<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">OrderedDict</span><span class="p">([(</span><span class="s1">'a'</span><span class="p">,</span> <span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="s1">'b'</span><span class="p">,</span> <span class="mi">2</span><span class="p">),</span> <span class="p">(</span><span class="s1">'a'</span><span class="p">,</span> <span class="mi">3</span><span class="p">)])</span>
|
||
<span class="go">collections.OrderedDict([('a', 3), ('b', 2)])</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>This behavior is consistent with existing implementations in
|
||
Python, the PHP array and the hashmap in Ruby 1.9.</p>
|
||
</div></blockquote>
|
||
<p>Is the ordered dict a dict subclass? Why?</p>
|
||
<blockquote>
|
||
<div>Yes. Like <code class="docutils literal notranslate"><span class="pre">defaultdict</span></code>, an ordered dictionary subclasses <code class="docutils literal notranslate"><span class="pre">dict</span></code>.
|
||
Being a dict subclass make some of the methods faster (like
|
||
<code class="docutils literal notranslate"><span class="pre">__getitem__</span></code> and <code class="docutils literal notranslate"><span class="pre">__len__</span></code>). More importantly, being a dict
|
||
subclass lets ordered dictionaries be usable with tools like json that
|
||
insist on having dict inputs by testing isinstance(d, dict).</div></blockquote>
|
||
<p>Do any limitations arise from subclassing dict?</p>
|
||
<blockquote>
|
||
<div>Yes. Since the API for dicts is different in Py2.x and Py3.x, the
|
||
OrderedDict API must also be different. So, the Py2.7 version will need
|
||
to override iterkeys, itervalues, and iteritems.</div></blockquote>
|
||
<p>Does <code class="docutils literal notranslate"><span class="pre">OrderedDict.popitem()</span></code> return a particular key/value pair?</p>
|
||
<blockquote>
|
||
<div>Yes. It pops-off the most recently inserted new key and its
|
||
corresponding value. This corresponds to the usual LIFO behavior
|
||
exhibited by traditional push/pop pairs. It is semantically
|
||
equivalent to <code class="docutils literal notranslate"><span class="pre">k=list(od)[-1];</span> <span class="pre">v=od[k];</span> <span class="pre">del</span> <span class="pre">od[k];</span> <span class="pre">return</span> <span class="pre">(k,v)</span></code>.
|
||
The actual implementation is more efficient and pops directly
|
||
from a sorted list of keys.</div></blockquote>
|
||
<p>Does OrderedDict support indexing, slicing, and whatnot?</p>
|
||
<blockquote>
|
||
<div>As a matter of fact, <code class="docutils literal notranslate"><span class="pre">OrderedDict</span></code> does not implement the <code class="docutils literal notranslate"><span class="pre">Sequence</span></code>
|
||
interface. Rather, it is a <code class="docutils literal notranslate"><span class="pre">MutableMapping</span></code> that remembers
|
||
the order of key insertion. The only sequence-like addition is
|
||
support for <code class="docutils literal notranslate"><span class="pre">reversed</span></code>.<p>A further advantage of not allowing indexing is that it leaves open
|
||
the possibility of a fast C implementation using linked lists.</p>
|
||
</div></blockquote>
|
||
<p>Does OrderedDict support alternate sort orders such as alphabetical?</p>
|
||
<blockquote>
|
||
<div>No. Those wanting different sort orders really need to be using another
|
||
technique. The OrderedDict is all about recording insertion order. If any
|
||
other order is of interest, then another structure (like an in-memory
|
||
dbm) is likely a better fit.</div></blockquote>
|
||
<p>How well does OrderedDict work with the json module, PyYAML, and ConfigParser?</p>
|
||
<blockquote>
|
||
<div>For json, the good news is that json’s encoder respects OrderedDict’s iteration order:<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">items</span> <span class="o">=</span> <span class="p">[(</span><span class="s1">'one'</span><span class="p">,</span> <span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="s1">'two'</span><span class="p">,</span> <span class="mi">2</span><span class="p">),</span> <span class="p">(</span><span class="s1">'three'</span><span class="p">,</span><span class="mi">3</span><span class="p">),</span> <span class="p">(</span><span class="s1">'four'</span><span class="p">,</span><span class="mi">4</span><span class="p">),</span> <span class="p">(</span><span class="s1">'five'</span><span class="p">,</span><span class="mi">5</span><span class="p">)]</span>
|
||
<span class="gp">>>> </span><span class="n">json</span><span class="o">.</span><span class="n">dumps</span><span class="p">(</span><span class="n">OrderedDict</span><span class="p">(</span><span class="n">items</span><span class="p">))</span>
|
||
<span class="go">'{"one": 1, "two": 2, "three": 3, "four": 4, "five": 5}'</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>In Py2.6, the object_hook for json decoders passes-in an already built
|
||
dictionary so order is lost before the object hook sees it. This
|
||
problem is being fixed for Python 2.7/3.1 by adding a new hook that
|
||
preserves order (see <a class="reference external" href="https://github.com/python/cpython/issues/49631">https://github.com/python/cpython/issues/49631</a> ).
|
||
With the new hook, order can be preserved:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">jtext</span> <span class="o">=</span> <span class="s1">'{"one": 1, "two": 2, "three": 3, "four": 4, "five": 5}'</span>
|
||
<span class="gp">>>> </span><span class="n">json</span><span class="o">.</span><span class="n">loads</span><span class="p">(</span><span class="n">jtext</span><span class="p">,</span> <span class="n">object_pairs_hook</span><span class="o">=</span><span class="n">OrderedDict</span><span class="p">)</span>
|
||
<span class="go">OrderedDict({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5})</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>For PyYAML, a full round-trip is problem free:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">ytext</span> <span class="o">=</span> <span class="n">yaml</span><span class="o">.</span><span class="n">dump</span><span class="p">(</span><span class="n">OrderedDict</span><span class="p">(</span><span class="n">items</span><span class="p">))</span>
|
||
<span class="gp">>>> </span><span class="nb">print</span> <span class="n">ytext</span>
|
||
<span class="go">!!python/object/apply:collections.OrderedDict</span>
|
||
<span class="go">- - [one, 1]</span>
|
||
<span class="go"> - [two, 2]</span>
|
||
<span class="go"> - [three, 3]</span>
|
||
<span class="go"> - [four, 4]</span>
|
||
<span class="go"> - [five, 5]</span>
|
||
|
||
<span class="gp">>>> </span><span class="n">yaml</span><span class="o">.</span><span class="n">load</span><span class="p">(</span><span class="n">ytext</span><span class="p">)</span>
|
||
<span class="go">OrderedDict({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5})</span>
|
||
</pre></div>
|
||
</div>
|
||
<p>For the ConfigParser module, round-tripping is also problem free. Custom
|
||
dicts were added in Py2.6 specifically to support ordered dictionaries:</p>
|
||
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">config</span> <span class="o">=</span> <span class="n">ConfigParser</span><span class="p">(</span><span class="n">dict_type</span><span class="o">=</span><span class="n">OrderedDict</span><span class="p">)</span>
|
||
<span class="gp">>>> </span><span class="n">config</span><span class="o">.</span><span class="n">read</span><span class="p">(</span><span class="s1">'myconfig.ini'</span><span class="p">)</span>
|
||
<span class="gp">>>> </span><span class="n">config</span><span class="o">.</span><span class="n">remove_option</span><span class="p">(</span><span class="s1">'Log'</span><span class="p">,</span> <span class="s1">'error'</span><span class="p">)</span>
|
||
<span class="gp">>>> </span><span class="n">config</span><span class="o">.</span><span class="n">write</span><span class="p">(</span><span class="nb">open</span><span class="p">(</span><span class="s1">'myconfig.ini'</span><span class="p">,</span> <span class="s1">'w'</span><span class="p">))</span>
|
||
</pre></div>
|
||
</div>
|
||
</div></blockquote>
|
||
<p>How does OrderedDict handle equality testing?</p>
|
||
<blockquote>
|
||
<div>Comparing two ordered dictionaries implies that the test will be
|
||
order-sensitive so that list <code class="docutils literal notranslate"><span class="pre">(od1.items())==list(od2.items())</span></code>.<p>When ordered dicts are compared with other Mappings, their order
|
||
insensitive comparison is used. This allows ordered dictionaries
|
||
to be substituted anywhere regular dictionaries are used.</p>
|
||
</div></blockquote>
|
||
<p>How __repr__ format will maintain order during a repr/eval round-trip?</p>
|
||
<blockquote>
|
||
<div>OrderedDict([(‘a’, 1), (‘b’, 2)])</div></blockquote>
|
||
<p>What are the trade-offs of the possible underlying data structures?</p>
|
||
<blockquote>
|
||
<div><ul class="simple">
|
||
<li>Keeping a sorted list of keys is fast for all operations except
|
||
__delitem__() which becomes an O(n) exercise. This data structure leads
|
||
to very simple code and little wasted space.</li>
|
||
<li>Keeping a separate dictionary to record insertion sequence numbers makes
|
||
the code a little bit more complex. All of the basic operations are O(1)
|
||
but the constant factor is increased for __setitem__() and __delitem__()
|
||
meaning that every use case will have to pay for this speedup (since all
|
||
buildup go through __setitem__). Also, the first traversal incurs a
|
||
one-time <code class="docutils literal notranslate"><span class="pre">O(n</span> <span class="pre">log</span> <span class="pre">n)</span></code> sorting cost. The storage costs are double that
|
||
for the sorted-list-of-keys approach.</li>
|
||
<li>A version written in C could use a linked list. The code would be more
|
||
complex than the other two approaches but it would conserve space and
|
||
would keep the same big-oh performance as regular dictionaries. It is
|
||
the fastest and most space efficient.</li>
|
||
</ul>
|
||
</div></blockquote>
|
||
</section>
|
||
<section id="reference-implementation">
|
||
<h2><a class="toc-backref" href="#reference-implementation" role="doc-backlink">Reference Implementation</a></h2>
|
||
<p>An implementation with tests and documentation is at:</p>
|
||
<blockquote>
|
||
<div><a class="reference external" href="https://github.com/python/cpython/issues/49647">OrderedDict patch</a></div></blockquote>
|
||
<p>The proposed version has several merits:</p>
|
||
<ul class="simple">
|
||
<li>Strict compliance with the MutableMapping API and no new methods
|
||
so that the learning curve is near zero. It is simply a dictionary
|
||
that remembers insertion order.</li>
|
||
<li>Generally good performance. The big-oh times are the same as regular
|
||
dictionaries except that key deletion is O(n).</li>
|
||
</ul>
|
||
<p>Other implementations of ordered dicts in various Python projects or
|
||
standalone libraries, that inspired the API proposed here, are:</p>
|
||
<ul class="simple">
|
||
<li><a class="reference external" href="http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py">odict in Python</a></li>
|
||
<li><a class="reference external" href="http://babel.edgewall.org/browser/trunk/babel/util.py?rev=374#L178">odict in Babel</a></li>
|
||
<li><a class="reference external" href="http://code.djangoproject.com/browser/django/trunk/django/utils/datastructures.py?rev=7140#L53">OrderedDict in Django</a></li>
|
||
<li><a class="reference external" href="http://www.voidspace.org.uk/python/odict.html">The odict module</a></li>
|
||
<li><a class="reference external" href="http://www.xs4all.nl/~anthon/Python/ordereddict/">ordereddict</a> (a C implementation of the odict module)</li>
|
||
<li><a class="reference external" href="http://pypi.python.org/pypi/StableDict/0.2">StableDict</a></li>
|
||
<li><a class="reference external" href="http://codespeak.net/svn/user/arigo/hack/pyfuse/OrderedDict.py">Armin Rigo’s OrderedDict</a></li>
|
||
</ul>
|
||
</section>
|
||
<section id="future-directions">
|
||
<h2><a class="toc-backref" href="#future-directions" role="doc-backlink">Future Directions</a></h2>
|
||
<p>With the availability of an ordered dict in the standard library,
|
||
other libraries may take advantage of that. For example, ElementTree
|
||
could return odicts in the future that retain the attribute ordering
|
||
of the source file.</p>
|
||
</section>
|
||
<section id="references">
|
||
<h2><a class="toc-backref" href="#references" role="doc-backlink">References</a></h2>
|
||
<aside class="footnote-list brackets">
|
||
<aside class="footnote brackets" id="id3" role="doc-footnote">
|
||
<dt class="label" id="id3">[<a href="#id1">1</a>]</dt>
|
||
<dd><a class="reference external" href="https://github.com/python/cpython/issues/42649">https://github.com/python/cpython/issues/42649</a></aside>
|
||
</aside>
|
||
</section>
|
||
<section id="copyright">
|
||
<h2><a class="toc-backref" href="#copyright" role="doc-backlink">Copyright</a></h2>
|
||
<p>This document has been placed in the public domain.</p>
|
||
</section>
|
||
</section>
|
||
<hr class="docutils" />
|
||
<p>Source: <a class="reference external" href="https://github.com/python/peps/blob/main/peps/pep-0372.rst">https://github.com/python/peps/blob/main/peps/pep-0372.rst</a></p>
|
||
<p>Last modified: <a class="reference external" href="https://github.com/python/peps/commits/main/peps/pep-0372.rst">2023-09-09 17:39:29 GMT</a></p>
|
||
|
||
</article>
|
||
<nav id="pep-sidebar">
|
||
<h2>Contents</h2>
|
||
<ul>
|
||
<li><a class="reference internal" href="#abstract">Abstract</a></li>
|
||
<li><a class="reference internal" href="#patch">Patch</a></li>
|
||
<li><a class="reference internal" href="#rationale">Rationale</a></li>
|
||
<li><a class="reference internal" href="#ordered-dict-api">Ordered Dict API</a></li>
|
||
<li><a class="reference internal" href="#questions-and-answers">Questions and Answers</a></li>
|
||
<li><a class="reference internal" href="#reference-implementation">Reference Implementation</a></li>
|
||
<li><a class="reference internal" href="#future-directions">Future Directions</a></li>
|
||
<li><a class="reference internal" href="#references">References</a></li>
|
||
<li><a class="reference internal" href="#copyright">Copyright</a></li>
|
||
</ul>
|
||
|
||
<br>
|
||
<a id="source" href="https://github.com/python/peps/blob/main/peps/pep-0372.rst">Page Source (GitHub)</a>
|
||
</nav>
|
||
</section>
|
||
<script src="../_static/colour_scheme.js"></script>
|
||
<script src="../_static/wrap_tables.js"></script>
|
||
<script src="../_static/sticky_banner.js"></script>
|
||
</body>
|
||
</html> |