ordered version of unordered_map?

Question

In my following program I'm currently using unordered_map 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 hash_map 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 hash_map 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.

include <iostream>
#include <iterator>
#include <set>
#include <vector>
#include <unordered_map>

using namespace std;


template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

template <typename C> struct ContainerHasher
{
  typedef typename C::value_type value_type;
  inline size_t operator()(const C & c) const
  {
    size_t seed = 0;
    for (typename C::const_iterator it = c.begin(), end = c.end(); it != end; ++it)
    {
      hash_combine<value_type>(seed, *it);
    }
    return seed;
  }
};


typedef std::set<int> my_set;
typedef std::vector<int> my_vector;
typedef std::unordered_map<my_set, my_vector, ContainerHasher<std::set<int>>> my_map;
typedef my_map::iterator m_it;

void print(my_map& data)
{
        for( m_it it(data.begin()) ; it!=data.end(); ++it)
        {
                cout << "Key : ";
                copy(it->first.begin(), it->first.end(), ostream_iterator<int>(cout, " "));
                cout << " => Value: ";
                copy (it->second.begin(),it->second.end(),ostream_iterator<int>(cout," "));
                cout << endl;
        }
        cout << "---------------------------------------------------------------\n";
}

int main()
{
   my_vector v1,v2,v3;
  for(int i = 1; i<=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 << endl << "found" << endl;
   }
   else
   {
      cout << endl << "Not found" << endl;
   }
}

EDIT:

I was using std::map before but I have large number of items (in millions). So even if the number of items are so large do you all recommend map if I want it ordered ?

Answer 1

Just use a regular std::map. Note this means you need ordering instead of hashing.

An unordered_map is a hash_map, by the way. "Unordered" just captures the conceptual difference rather than the implementation difference, so it's a better name.

Answer 2

IF you need the sorted order frequently enough, then I'd suggest switching to map which is an ordered container. Insert and find are now logarithmic in complexity but the container comes sorted by default.