插入自定义哈希函数的unordered_set

问题描述 投票:17回答:2

我有以下的代码,以使一个unordered_set<Interval>。编译没有问题。

struct Interval {
  unsigned int begin;
  unsigned int end;
  bool updated;   //true if concat.  initially false
  int patternIndex;  //pattern index. valid for single pattern
  int proteinIndex;   //protein index.  for retrieving the pattern
};

struct Hash {
  size_t operator()(const Interval &interval);
};

size_t Hash::operator()(const Interval &interval){
  string temp = to_string(interval.begin) + to_string(interval.end) + to_string(interval.proteinIndex);
  return hash<string>()(temp);
}

unordered_set<Interval, string, Hash> test;

然而,当我尝试使用此代码插入我不能编译:

for(list<Interval>::iterator i = concat.begin(); i != concat.end(); ++i){
  test.insert((*i));
}

此外,我也不能确定是什么问题,从错误消息,例如:

note: candidate is:
note: size_t Hash::operator()(const Interval&)
note:   candidate expects 1 argument, 2 provided  

我想我只是提供1种说法...

什么是我的插入代码的问题?


这里是新的实例代码:unordered_set<Interval, Hash> test;但是,我仍然收到错误消息的转换,例如:

note: candidate is:
note: size_t Hash::operator()(const Interval&) <near match>
note:   no known conversion for implicit ‘this’ parameter from ‘const Hash*’ to ‘Hash*’
c++ c++11 unordered-set
2个回答
36
投票

第一个问题:

你逝去的string作为您的unordered_set<>类模板实例化的第二个模板参数。 The second argument should be the type of your hasher functorstd::string不是一个可调用对象。

也许意味着这样写:

unordered_set<Interval, /* string */ Hash> test;
//                      ^^^^^^^^^^^^
//                      Why this?

此外,我会建议使用比beginend您(成员)变量等名称,这是因为它们的C ++标准库的算法名称。

第二个问题:

你应该记住,that the hasher function should be qualified as const,所以你的仿函数应该是:

struct Hash {
   size_t operator() (const Interval &interval) const {
   //                                           ^^^^^
   //                                           Don't forget this!
     string temp = to_string(interval.b) + 
                   to_string(interval.e) + 
                   to_string(interval.proteinIndex);
     return (temp.length());
   }
};

第三个问题:

最后,如果你想std::unordered_set能够与类型Interval的对象的工作,你需要定义一个平等的运营商,你的哈希函数相一致。默认情况下,如果不指定任何类型的参数作为std::unordered_set类模板的第三个参数,operator ==将被使用。

您目前没有operator ==为你的类Interval的任何超载,所以你应该提供一个。例如:

inline bool operator == (Interval const& lhs, Interval const& rhs)
{
    return (lhs.b == rhs.b) && 
           (lhs.e == rhs.e) && 
           (lhs.proteinIndex == rhs.proteinIndex); 
}

结论:

上述所有的修改后,你可以看到你的代码在这个live example编制。


0
投票

我想,安迪四处寻觅完美地与你的代码fixed the problems。不过,我想下面的成员函数添加到您的Interval,这说明什么使得两个区间相同的:

std::string getID() const { return std::to_string(b) + " " + std::to_string(e) + " " + std::to_string(proteinIndex); }

请注意,我也跟着安迪四处寻觅的建议,并改名为成员beginbende。接下来,你可以很容易地通过使用lambda expressions定义散列和比较函数。其结果是,你可以如下定义unordered_set

auto hash = [](const Interval& i){ return std::hash<std::string>()(i.getID()); };
auto equal = [](const Interval& i1, const Interval& i2){ return i1.getID() == i2.getID(); };
std::unordered_set<Interval, decltype(hash), decltype(equal)> test(8, hash, equal);

最后,可读性的原因,我转换了您for环路成基于范围的for循环:

std::list<Interval> concat {{1, 2, false, 3, 4}, {2, 3, false, 4, 5}, {1, 2, true, 7, 4}};

for (auto const &i : concat)
    test.insert(i);

for (auto const &i : test)
    std::cout << i.b << ", " << i.e << ", " << i.updated << std::endl;

输出(I刚刚打印每个Interval的前三个成员):

2, 3, 0 1, 2, 0

正如你所看到的,只有两个打印间隔。第三个({1, 2, true, 7, 4})未插入至concat,因为其beproteinIndexare等于第一间隔({1, 2, false, 3, 4})的。

Code on Ideone

© www.soinside.com 2019 - 2024. All rights reserved.