unordered_map 的有序版本?
在我的以下程序中,我当前使用 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 技术交流群。
发布评论
评论(3)
为了在插入时保持元素有序,您需要使用(有序)映射,它的设计具有渐进 log(N) 最坏情况插入复杂度,这是任何基于比较的排序算法的最佳结果。
为了提供对现有元素的快速(平均)访问,您可能可能想要使用无序(哈希)映射。
如果这两种情况都很重要,您可以手动使用两种映射,或者创建一些同时封装映射和有序映射的包装容器类。
然而,只有当读取操作(显着!)比写入操作更频繁时,此解决方案可能才有用,并且存在内存消耗等一些缺点(这可能会因缓存和页面交换问题而导致性能下降)。因此无论如何,这个解决方案都需要一些实验和分析。
另外,如果您的排序有一些细节,例如,您的元素是按小集合中的一些“速率”值(例如 1,2,...10)排序的,则特定排序算法可能比映射更好(因为这排序可能不需要基于比较)
[编辑](严格来说,我的最后一个按小范围值排序的示例与 std::map 的可能使用不兼容,因为对于大量元素它显然不会产生严格的弱秩序。我不会删除它,因为它在某些应用程序中有时可能很有用)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
只需使用常规的
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 ahash_map
, by the way. "Unordered" just captures the conceptual difference rather than the implementation difference, so it's a better name.