unordered_map 的有序版本?

发布于 11-27 18:57 字数 2461 浏览 0 评论 0原文

在我的以下程序中,我当前使用 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;
   }
}

编辑:

我之前使用过 std::map ,但我有大量的项目(以百万计)。因此,即使商品数量如此之大,如果我想订购的话,你们都会推荐 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 ?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

栩栩如生2024-12-04 18:57:06

只需使用常规的 std::map 即可。请注意,这意味着您需要排序而不是散列。

顺便说一句,unordered_map 一个hash_map。 “无序”只是捕获了概念上的差异,而不是实现上的差异,所以它是一个更好的名称。

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.

且行且努力2024-12-04 18:57:06

如果您足够频繁地需要排序顺序,那么我建议切换到 map 这是一个有序容器。插入和查找现在的复杂性是对数的,但容器默认情况下是排序的。

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.

度的依靠╰つ2024-12-04 18:57:06

为了在插入时保持元素有序,您需要使用(有序)映射,它的设计具有渐进 log(N) 最坏情况插入复杂度,这是任何基于比较的排序算法的最佳结果。

为了提供对现有元素的快速(平均)访问,您可能可能想要使用无序(哈希)映射。

如果这两种情况都很重要,您可以手动使用两种映射,或者创建一些同时封装映射和有序映射的包装容器类。

然而,只有当读取操作(显着!)比写入操作更频繁时,此解决方案可能才有用,并且存在内存消耗等一些缺点(这可能会因缓存和页面交换问题而导致性能下降)。因此无论如何,这个解决方案都需要一些实验和分析。

另外,如果您的排序有一些细节,例如,您的元素是按小集合中的一些“速率”值(例如 1,2,...10)排序的,则特定排序算法可能比映射更好(因为这排序可能不需要基于比较)

[编辑](严格来说,我的最后一个按小范围值排序的示例与 std::map 的可能使用不兼容,因为对于大量元素它显然不会产生严格的弱秩序。我不会删除它,因为它在某些应用程序中有时可能很有用)

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)

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文