ordered version of unordered_map?

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 ? 开发者_StackOverflow社区

---

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.

---

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.

---

To keep elements ordered while inserting, you need to use (ordered) map, it is designed with asymptotically log(N) worst case insertion complexity, the best result for any comparison-based ordering algorithms.

To provide fast (average) access to existing elements you may probably want to use unordered (hash) map.

If both cases are significant, you may use both maps, manually or creating some wrapper container class incapsulating map and ordered map simultaniously.

However, this solution may be useful only if read operations are (significantly!) more frequent than write ones, and has some drawbacks as memory consumption (which may lead to performance degradation due to cache and page swapping problems). So some experiments and profiling needed with this solution anyway.

Also, if your ordering has some specifics, for instance, your elements are ordered by some "rate" values from a small set (say, 1,2,...10), specific ordering algorithms may be better than map (as this ordering may not need to be comparison-based)

[edit] (My last example with ordering by small range values, strictly speaking, is incompatable with possible using of std::map since for large amount of elements it apparently doesn't produce strict weak order. I don't remove it as it may be sometimes useful case in some applications)