title: What data structure best mixes strengths of dictionary and list
body: <p>A <a href="https://stackoverflow.com/questions/6430973/access-a-dictionary-as-a-list">question</a> I asked recently left me wondering about the following:</p>
  
  <p>What is the data structure to store a collection (key, value) pairs such that:</p>
  
  <ul>
  <li>its elements are ordered</li>
  <li><code>d[key] -&gt; val</code> has complexity <code>O(dict)</code></li>
  <li><code>d(index) -&gt; (key, val)</code> has complexity <code>O(list)</code></li>
  <li>provides reverse lookup <code>d{val} -&gt; (index, key)</code> with complexity <code>O(dict)</code></li>
  <li>uses the least possible storage</li>
  </ul>
  
  <p>When I type <code>O(type)</code> I mean the same complexity for the operation as data structure <code>type</code>.</p>
  
  <p>For instance, if the ordered collection is:</p>
  
  <pre><code>c = {key_1:val_1, key_2:val_2, key_3:val_3}
  </code></pre>
  
  <p>I'd like to obtain</p>
  
  <pre><code> c[key_1] # returns val_1, as in a dictionary
   c(1)     # returns val_2, as in a list
   c{val_3} # returns (2, key_3) as in a sort of "indexed dictionary"
  </code></pre>