упорядоченная версия unordered_map?

Question

В моей следующей программе я сейчас использую unordered_map только потому, что мне нужно O (1) время поиска / вставки. Но теперь я хотел, чтобы товары были заказаны. Сортировка каждый раз очень неэффективна. Каковы мои альтернативы? Я читал, что hash_map делает работу, но статьи, которые я читаю, очень запутаны или довольно сложны для понимания. Какова сложность вставки / поиска для hash_map и действительно ли она упорядочена? Если так, определено ли это в C ++ 0x и как я могу это реализовать? Если нет, что еще я могу использовать? Спасибо.

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, если я хочу заказать его?

Answer 1

Просто используйте обычный std::map.Обратите внимание, что это означает, что вам нужно упорядочить вместо хеширования.

unordered_map это, кстати, a hash_map.«Неупорядоченный» просто отражает концептуальное различие, а не различие в реализации, так что это лучшее имя.

Answer 2

Если вам нужен отсортированный заказ достаточно часто, то я бы предложил переключиться на map, который является заказанным контейнером.Вставка и поиск теперь логарифмически сложны, но контейнер сортируется по умолчанию.

Answer 3

Чтобы упорядочить элементы при вставке, вам нужно использовать (упорядоченную) карту, она разработана с асимптотически логарифмической (N) сложностью вставки в худшем случае, лучший результат для любых алгоритмов упорядочения на основе сравнения.

Чтобы обеспечить быстрый (средний) доступ к существующим элементам, вы можете , вероятно, хотеть использовать неупорядоченную (хэш) карту.

Если оба случая являются значительными, вы можете использовать обе карты, вручную или одновременно создавая некоторую карту класса-оболочки, инкапсулирующую карту и упорядоченную карту.

Однако это решение может быть полезно только в том случае, если операции чтения (значительно!) Выполняются чаще, чем операции записи, и имеют некоторые недостатки, такие как потребление памяти (что может привести к снижению производительности из-за проблем с кешем и подкачкой страниц). Так что в любом случае с этим решением нужно было провести некоторые эксперименты и профилирование.

Кроме того, если ваш порядок имеет некоторые особенности, например, ваши элементы упорядочены по некоторым значениям «скорости» из небольшого набора (скажем, 1,2, ... 10), определенные алгоритмы упорядочения могут быть лучше, чем map (поскольку этот порядок может не основываться на сравнении)

[править] (Мой последний пример с упорядочением по небольшим значениям диапазона, строго говоря, несовместим с возможным использованием std :: map, так как для большого количества элементов он явно не производит строго слабый порядок. Я не удаляю его, так как это может быть иногда полезно в некоторых приложениях)