std::unordered_set 中带有自定义谓词的未定义行为

Question

我有一个 std::unordered_set 应该存储指向存储在 std::list 中的值的指针。这些值首先被添加到列表中，然后它们的指针被插入到集合中。该集合使用一个谓词来比较指针指向的值而不是地址。这会产生未定义的行为。

这是一个最小的工作示例：

#include <unordered_set>
#include <iostream>
#include <string>
#include <list>

using namespace std;

template<typename T> struct set_hash {
  size_t operator()(const T* p) const noexcept {
    return reinterpret_cast<uintptr_t>(p);
  }
};
template<typename T> struct set_eq {
  bool operator()(const T* a, const T* b) const noexcept {
    std::cout << "*a["<<*a<<"] == *b["<<*b<<"] "
              << boolalpha << (*a == *b) << std::endl;
    return *a == *b;
  }
};

template<typename T> using set_t =
  std::unordered_set<const T*, set_hash<T>, set_eq<T>>;

int main()
{
  set_t<string> set;
  list<string> list{"a", "b", "a", "c", "a", "d"};

  for (auto& str : list) {
    set.insert(&str);
    cout << str << ' ';
  }
  cout << endl;

  for (auto p : set) cout << *p << ' ';
  cout << endl;

  string c("c");
  cout << **set.find(&c) << endl;

  return 0;
}

在运行程序多次之后，我得到三种可能的输出：

a b a c a d 
d a c a b a 
Segmentation fault

a b a c a d 
d a c a b a 
*a[c] == *b[a] false
Segmentation fault

a b a c a d 
d a c a b a 
*a[c] == *b[c] true
c

我期望的输出是

a b a c a d 
a b c (not necessarily in this order)
c

有些行如 *a[c] == *b[c] true，具体取决于谓词被调用的次数。

我不明白是什么导致了未定义的行为。我用 gcc4.8.2、gcc4.9.1 和 gcc4.9.2 得到了相同的结果。

Answer 1

问题是散列函数对指针进行散列，而比较函数比较指针指向的值。因此，如果您有两个具有相同值的不同列表元素，哈希函数将给出不同的哈希值（来自指针），而比较函数将比较相等。

散列函数需要保持一致 -- 它需要散列值而不是指针。

std::unordered_set 中带有自定义谓词的未定义行为

Undefined behavior in std::unordered_set with custom predicate

c++

c++11

hash

predicate

unordered-set