title: How is std::map implemented so it can require its key_type to be comparable?
body: <p>This is my implementation of the Box class:</p>
  
  <pre><code>class Box {
      friend ostream&amp; operator&lt;&lt;(ostream &amp;os, const Box &amp;b);
      friend bool operator&lt;(const Box &amp;left, const Box &amp;right);
  public:
      Box(int i, double d);
      ~Box();
  private:
      int i;
      double d;
  };
  
  Box::Box(int _i, double _d):i(_i), d(_d) {}
  
  Box::~Box() {}
  
  bool operator&lt;(const Box &amp;left, const Box &amp;right)
  {
      return (left.i &lt; right.i);
  }
  
  ostream&amp; operator&lt;&lt;(ostream &amp;os, const Box &amp;b)
  {
      os &lt;&lt; b.d;
      return os;
  }
  </code></pre>
  
  <p>This the test code:</p>
  
  <pre><code>int main()
  {
      Box b1(3,2), b2(2,1), b3(0, 9);
      map&lt;Box, int&gt; bmap;
      bmap.insert(pair&lt;Box,int&gt;(b1, 10));
      bmap.insert(pair&lt;Box,int&gt;(b2, 10));
      bmap.insert(pair&lt;Box,int&gt;(b3, 10));
      for (map&lt;Box,int&gt;::iterator iter = bmap.begin(); iter != bmap.end(); ++iter)
      {
          cout &lt;&lt; iter-&gt;first &lt;&lt; " ";
      }
      cout &lt;&lt; endl;
      return 0;
  }
  </code></pre>
  
  <p>If I remove the definition of operator&lt; on the Box class, the compiler will complain (an error) if I try to insert a Box object into std::map.</p>
  
  <p>I have some experience with Java and I know in similar cases I just have to let Box implement Comarable. And Java compiler will check this contract at compile time, because Map in Java requires its key type conform to Comparable.</p>
  
  <p>And if I want to define my own map type in Java, I just need to write:</p>
  
  <pre class="lang-java prettyprint-override"><code>public class MyMap&lt;K extends Comparable&lt;K&gt;, V&gt;
  </code></pre>
  
  <p>So my question is, if I want to implement my own map type (say, MyMap) in C++, how to define MyMap so that the compiler knows at compile time that "MyMap requires its key_type has its own overloaded definition of operator&lt;"?</p>