title: Is there a more efficient implementation for a bidirectional map?
body: <p>I created a simple <strong>bidirectional map</strong> class that works by internally storing two <code>std::map</code> instances, with opposite key/value types, and providing an user-friendly interface:</p>
  
  <pre><code>template&lt;class T1, class T2&gt; class Bimap
  {
      std::map&lt;T1, T2&gt; map1;
      std::map&lt;T2, T1&gt; map2;
      // ...
  };
  </code></pre>
  
  <ul>
  <li><p>Is there a more efficient method of implementing a bidirectional map that doesn't require twice the memory?</p></li>
  <li><p>How is a bimap usually implemented?</p></li>
  </ul>
  
  <hr>
  
  <p><em>EDIT:</em></p>
  
  <ul>
  <li><p>Should bimap element be mutable or immutable? <em>(Changing one element in <code>map1</code> should change the key in <code>map2</code>, but keys are const and that's impossible - what's the solution?)</em></p></li>
  <li><p>Ownership of elements is also another problem: when an user inserts a key-value pair in the bimap, the bimap should make a copy of that key-value pair and store it, then the internal second map (with inverted key/value) should not copy but point to the original pair. How can this be achieved?</p></li>
  </ul>
  
  <hr>
  
  <p><em>EDIT 2:</em> </p>
  
  <p><a href="https://codereview.stackexchange.com/questions/42427/bidirectional-map-based-on-memory-manipulation-c11">I've posted a possible implementation I made on Code Review.</a></p>