title: One-to-one relation in STL terms
body: <p>As I know there is no biunivocal mapping datastruct/ADT in C++ (STL) and even C++1y. But I need a sorted associative container that allows me to map key set into value set and vice versa.</p>
  
  <p>What is the best approach or existant solution?</p>
  
  <p>My proposal is:</p>
  
  <pre><code>#!/usr/bin/env bash -vex
  # cls ; bash self.bash 2&gt;&amp;1 | tee self.log | less
  WARN="-W -Wall -Wextra -Werror"
  g++ -x c++ - -std=gnu++1y $WARN -Ofast -o a &lt;&lt;__EOF &amp;&amp; ./a &amp;&amp; echo -e "\e[1;32msucceeded\e[0m" || echo -e "\e[1;31mfailed\e[0m"
  #include &lt;list&gt;
  #include &lt;tuple&gt;
  #include &lt;map&gt;
  #include &lt;functional&gt;
  
  #include &lt;string&gt;
  
  #include &lt;cstdlib&gt;
  #include &lt;cassert&gt;
  
  template&lt; typename A, typename B &gt;
  class bijection
  {
  
      using data_type = std::list&lt; std::tuple&lt; A const, B const &gt; &gt;;
  
  public :
  
      using iterator = typename data_type::iterator;
      using const_iterator = typename data_type::const_iterator;
  
  private :
  
      using direct_mapping_type = std::map&lt; std::reference_wrapper&lt; A const &gt;, iterator, std::less&lt; A const &amp; &gt; &gt; ;
      using inverse_mapping_type = std::map&lt; std::reference_wrapper&lt; B const &gt;, iterator, std::less&lt; B const &amp; &gt; &gt;;
      using direct_iterator = typename direct_mapping_type::iterator;
      using inverse_iterator = typename inverse_mapping_type::iterator;
  
  public :
  
      auto size() const { return data_.size(); }
  
      iterator find(A const &amp; a)
      {
          auto const direct = direct_mapping_.find(a);
          if (direct == direct_mapping_.end()) {
              return data_.end();
          } else {
              return direct-&gt;second;
          }
      }
  
      iterator find(B const &amp; b)
      {
          auto const inverse = inverse_mapping_.find(b);
          if (inverse == inverse_mapping_.end()) {
              return data_.end();
          } else {
              return inverse-&gt;second;
          }
      }
  
      auto erase(iterator pos)
      {
          auto const &amp; element = *pos;
          direct_mapping_.erase(std::get&lt; 0 &gt;(element));
          inverse_mapping_.erase(std::get&lt; 1 &gt;(element));
          return data_.erase(pos);
      }
  
      template&lt; typename X, typename Y &gt;
      std::tuple&lt; iterator, bool, bool &gt; insert(X &amp;&amp; x, Y &amp;&amp; y)
      {
          direct_iterator direct = direct_mapping_.find(x);
          inverse_iterator inverse = inverse_mapping_.find(y);
          bool const d = (direct != direct_mapping_.end());
          bool const i = (inverse != inverse_mapping_.end());
          if (d &amp;&amp; i) {
              iterator ix = inverse-&gt;second;
              iterator iy = direct-&gt;second;
              inverse_mapping_.erase(inverse);
              direct_mapping_.erase(direct);
              if (ix != iy) {
                  inverse_mapping_.erase(std::get&lt; 1 &gt;(*iy));
                  direct_mapping_.erase(std::get&lt; 0 &gt;(*ix));
                  data_.erase(iy);
                  data_.erase(ix);
              } else {
                  data_.erase(ix); // iy
              }
          } else if (d) {
              iterator iy = direct-&gt;second;
              direct_mapping_.erase(direct);
              inverse_mapping_.erase(std::get&lt; 1 &gt;(*iy));
              data_.erase(iy);
          } else if (i) {
              iterator ix = inverse-&gt;second;
              inverse_mapping_.erase(inverse);
              direct_mapping_.erase(std::get&lt; 0 &gt;(*ix));
              data_.erase(ix);
          }
          data_.emplace_back(std::forward&lt; X &gt;(x), std::forward&lt; Y &gt;(y));
          auto const &amp; element = data_.back();
          iterator it = --data_.end();
          direct_mapping_.emplace(std::get&lt; 0 &gt;(element), it);
          inverse_mapping_.emplace(std::get&lt; 1 &gt;(element), it);
          return std::make_tuple(it, d, i);
      }
  
  private :
  
      data_type data_;
      direct_mapping_type direct_mapping_;
      inverse_mapping_type inverse_mapping_;
  
  };
  
  int main()
  {
      using A = std::size_t;
      using B = std::string;
      using M = bijection&lt; A, B &gt;;
      M m;
      assert(1 == (m.insert(A(111), B("111")), m.size()));
      assert(1 == (m.insert(A(111), B("111")), m.size()));
      assert(2 == (m.insert(A(222), B("222")), m.size()));
      assert(3 == (m.insert(A(333), B("333")), m.size()));
      assert(2 == (m.insert(A(222), B("111")), m.size()));
      assert(3 == (m.insert(A(111), B("222")), m.size()));
      assert(2 == (m.insert(A(111), B("111")), m.size()));
      assert(1 == (m.insert(A(333), B("111")), m.size()));
      assert(1 == (m.insert(A(333), B("333")), m.size()));
      assert(1 == (m.insert(A(111), B("333")), m.size()));
      assert(0 == (m.erase(m.find(A(111))), m.size()));
      return EXIT_SUCCESS;
  }
  __EOF
  </code></pre>