在下面的程序中,我有一个typedef map
。我要做的是实现一个哈希表。我尝试使用unordered_map
,因为我听说它是最有效的,因为它需要O(1)时间。我在主程序(我正在开发的另一个程序)中到处使用typedef map
,所以我不想改变这一点。我想在其中一个函数中实现哈希表,我想弄清楚如何将映射的内容插入哈希表中,然后再搜索键。我在遇到问题的两个地方插入了评论。请帮助。
#include <iostream>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;
typedef vector<int> v_t;
typedef set<int> s_t;
typedef map<s_t, v_t> m_t;
typedef m_t::iterator m_it;
typedef std::unordered_map<s_t, v_t> Mymap;
int main(){
m_t sample;
for (int i = 0; i < 100; i = i+2) {
v_t v;
for(int k = 100 ; k<=105 ; ++k)
v.push_back(k);
s_t k;
k.insert(i);
sample.insert(sample.end(), make_pair(k, v));
}
//---------Debug--------------------
for( m_it it(sample.begin()) ; it!=sample.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<double>(cout," "));
cout << endl;
}
//---------------------------------
Mymap c1;
for( m_it it(sample.begin()) ; it!=sample.end(); ++it) {
c1.insert(Mymap::value_type(it->first,it->second)); // how to do this ?
}
s_t s;
s.insert(72);
if(c1.find(s)!=c1.end()) // does this work ?
cout << "Success" << endl;
return 0;
}
感谢大家的帮助和意见。
阅读Jason的评论后,我明白了为什么我不能使用std::set
作为unordered_map
中的键,所以我试图使用std::string
作为键,但find
函数不起作用。你能帮帮我吗?
Mymap c1;
for( m_it it(sample.begin()) ; it!=sample.end(); ++it) {
v_t v1;
std::string key;
key.insert(key.begin(),it->first.begin(),it->first.end());
copy(it->second.begin(), it->second.end(),std::back_inserter(v1));
c1.insert(Mymap::value_type(std::make_pair(key,v1)));
}
string s = "72";
if((c1.find(s) != c1.end()) == true)
cout << "Success" << endl;
return 0;
要完成此工作,您缺少的基本元素是为您的std::set
定义一个散列函数,将其用作键。STL已经为std::set
定义了相等性和字典顺序,因此您可以将其用作std::map
原样中的键值,而不会出现任何问题。但是,它没有定义散列函数,因此,您需要通过重载std::hash来实现这一点。这相当直接,可以通过定义以下函数来完成:
namespace std
{
template<>
struct hash<std::set<int> > : public std::unary_function<std::set<int>, size_t>
{
size_t operator()(const std::set<int>& my_set) const
{
//insert hash algorithm that returns integral type
}
};
}
上面的函子对象将返回size_t
整型,并接受std::set
作为实参。您必须在namespace std
中定义它,以便std::unordered_map
能够识别它。一个"简单"的算法可以是简单地将元素相加,因为你有一个类型为int
的集合。有更复杂的算法可以减少碰撞的数量,这样一个简单的算法会以牺牲哈希时间为代价。一旦你定义了这个,你应该没有任何问题插入你的std::set
键值到unordered_map
,以及创建新的键值和在哈希表中找到它们。
您可以在http://ideone.com/DZ5jm
看到源代码工作的示例。编辑:Jason的代码放在这里供参考:
#include <iostream>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;
namespace std
{
template<>
struct hash<set<int> > : public unary_function<set<int>, size_t>
{
size_t operator()(const std::set<int>& my_set) const
{
set<int>::iterator iter = my_set.begin();
int total = 0;
for (; iter != my_set.end(); iter++)
{
total += *iter;
}
return total;
}
};
}
typedef vector<int> v_t;
typedef set<int> s_t;
typedef map<s_t, v_t> m_t;
typedef m_t::iterator m_it;
typedef std::unordered_map<s_t, v_t> Mymap;
int main(){
m_t sample;
for (int i = 0; i < 100; i = i+2) {
v_t v;
for(int k = 100 ; k<=105 ; ++k)
v.push_back(k);
s_t k;
k.insert(i);
sample.insert(sample.end(), make_pair(k, v));
}
//---------Debug--------------------
for( m_it it(sample.begin()) ; it!=sample.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<double>(cout," "));
cout << endl;
}
//---------------------------------
Mymap c1;
for( m_it it(sample.begin()) ; it!=sample.end(); ++it) {
c1.insert(Mymap::value_type(it->first,it->second)); // how to do this ?
}
s_t s;
s.insert(72);
if(c1.find(s)!=c1.end()) // does this work ?
cout << "Success" << endl;
return 0;
}