title: ordered version of unordered_map?
body: <p>In my following program I'm currently using <code>unordered_map</code> just because I wanted O(1) search/insert time. But now I wanted the items to be ordered. Sorting it every time is very inefficient. What are my alternatives ? I read that <code>hash_map</code> does the job but the articles i read are very confusing or rather complicated for me to understand. What is the complexity of insert/search for <code>hash_map</code> and is it really ordered ? If so, is it defined in C++0x and how can I implement it ? If not what else can I use ? Thanks.</p>
  
  <pre><code>include &lt;iostream&gt;
  #include &lt;iterator&gt;
  #include &lt;set&gt;
  #include &lt;vector&gt;
  #include &lt;unordered_map&gt;
  
  using namespace std;
  
  
  template &lt;class T&gt;
  inline void hash_combine(std::size_t &amp; seed, const T &amp; v)
  {
    std::hash&lt;T&gt; hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed &lt;&lt; 6) + (seed &gt;&gt; 2);
  }
  
  template &lt;typename C&gt; struct ContainerHasher
  {
    typedef typename C::value_type value_type;
    inline size_t operator()(const C &amp; c) const
    {
      size_t seed = 0;
      for (typename C::const_iterator it = c.begin(), end = c.end(); it != end; ++it)
      {
        hash_combine&lt;value_type&gt;(seed, *it);
      }
      return seed;
    }
  };
  
  
  typedef std::set&lt;int&gt; my_set;
  typedef std::vector&lt;int&gt; my_vector;
  typedef std::unordered_map&lt;my_set, my_vector, ContainerHasher&lt;std::set&lt;int&gt;&gt;&gt; my_map;
  typedef my_map::iterator m_it;
  
  void print(my_map&amp; data)
  {
          for( m_it it(data.begin()) ; it!=data.end(); ++it)
          {
                  cout &lt;&lt; "Key : ";
                  copy(it-&gt;first.begin(), it-&gt;first.end(), ostream_iterator&lt;int&gt;(cout, " "));
                  cout &lt;&lt; " =&gt; Value: ";
                  copy (it-&gt;second.begin(),it-&gt;second.end(),ostream_iterator&lt;int&gt;(cout," "));
                  cout &lt;&lt; endl;
          }
          cout &lt;&lt; "---------------------------------------------------------------\n";
  }
  
  int main()
  {
     my_vector v1,v2,v3;
    for(int i = 1; i&lt;=10; ++i)
     {
        v1.push_back(i);
        v2.push_back(i+10);
        v3.push_back(i+20);
     }
  
     my_set s1(v3.begin(),v3.begin()+3);
     my_set s2(v1.begin(),v1.begin()+3);
     my_set s3(v2.begin(),v2.begin()+3);
  
     my_map m1;
  
     m1.insert(make_pair(s1,v1));
     m1.insert(make_pair(s2,v2));
     m1.insert(make_pair(s3,v3));
  
     print(m1);
     my_set s4(v3.begin(),v3.begin()+3);
  
     m_it it = m1.find(s4);
  
     if(it != m1.end())
     {
        cout &lt;&lt; endl &lt;&lt; "found" &lt;&lt; endl;
     }
     else
     {
        cout &lt;&lt; endl &lt;&lt; "Not found" &lt;&lt; endl;
     }
  }
  </code></pre>
  
  <p>EDIT:</p>
  
  <p>I was using <code>std::map</code> before but I have large number of items (in millions). So even if the number of items are so large do you all recommend <code>map</code> if I want it ordered ? </p>