Geek Answers Handbook

An ordered version of unordered_map?

In my next program, I'm currently unordered_maponly using it because I need O (1) to 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 what hash_mapdoes the work, but the articles I read are very confusing or rather difficult for me to understand. What is the complexity of the insert / search hash_mapand is it really ordered? If so, is it defined in C ++ 0x and how to implement it? If not what else can I use? Thank.

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:

std::map , ( ). , , map, , ?

+5
3

std::map. , , , .

An unordered_map - hash_map, . "Unordered" , , .

+9

, map, . , .

+1

, () , (N) , .

() , , (-).

, - .

, (!) , , ( - ). , , , .

, , , "" (, 1,2,... 10), , ( )

[edit] (My last example, ordering by small range values, strictly speaking, is incompatible with the possible use of std :: map, since for a large number of elements it does not seem to create strict weak order. I do not delete it, since this may be sometimes useful in some applications)

0
source

More articles:


All Articles