如何使用自定义比较器为三元组（“tuple”）声明/使用“unordered_set”？

如何声明/使用unordered_set对于三胞胎（tuple）使用自定义比较器？

我需要存储三元组float（处理为tuple）在一组中检查潜在的重复项。因为它是关于float，我想使用常规比较==不起作用，因此需要自定义比较。

这个最小的代码无法编译：

>> cat unordered_set_triplet.cpp 
#include <unordered_set>
#include <tuple>
#include <limits> // numeric_limits
#include <cmath> // fabs
#include <functional> // hash

using triplet = std::tuple<float, float, float>;
bool triplet_equal(triplet const & lhs, triplet const & rhs) {
  float const eps = std::numeric_limits<float>::epsilon();
  if (std::fabs(std::get<0>(lhs) - std::get<0>(rhs)) > eps) return false;
  if (std::fabs(std::get<1>(lhs) - std::get<1>(rhs)) > eps) return false;
  if (std::fabs(std::get<2>(lhs) - std::get<2>(rhs)) > eps) return false;
  return true;
}
using unordered_set_triplet = std::unordered_set<triplet,
                                                 std::hash<triplet>,
                                                 decltype(triplet_equal)>;

int main() {
  //unordered_set_triplet s; // Compilation: KO...
  unordered_set_triplet s(10, std::hash<triplet>, triplet_equal);
  s.insert({1.f, 2.f, 3.f});
}

I get:

>> g++ -std=c++20 -o unordered_set_triplet unordered_set_triplet.cpp 
In file included from /usr/include/c++/12/bits/hashtable.h:35,
                 from /usr/include/c++/12/unordered_set:46,
                 from unordered_set_triplet.cpp:1:
/usr/include/c++/12/bits/hashtable_policy.h: In instantiation of ‘struct std::__detail::_Hashtable_ebo_helper<0, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&), false>’:
/usr/include/c++/12/bits/hashtable_policy.h:1631:12:   required from ‘struct std::__detail::_Hashtable_base<std::tuple<float, float, float>, std::tuple<float, float, float>, std::__detail::_Identity, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&), std::hash<std::tuple<float, float, float> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, true, true> >’
/usr/include/c++/12/bits/hashtable.h:182:11:   required from ‘class std::_Hashtable<std::tuple<float, float, float>, std::tuple<float, float, float>, std::allocator<std::tuple<float, float, float> >, std::__detail::_Identity, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&), std::hash<std::tuple<float, float, float> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >’
/usr/include/c++/12/bits/unordered_set.h:100:18:   required from ‘class std::unordered_set<std::tuple<float, float, float>, std::hash<std::tuple<float, float, float> >, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&)>’
unordered_set_triplet.cpp:21:26:   required from here
/usr/include/c++/12/bits/hashtable_policy.h:1204:11: error: data member ‘std::__detail::_Hashtable_ebo_helper<0, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&), false>::_M_tp’ invalidly declared function type
 1204 |       _Tp _M_tp{};
      |           ^~~~~
/usr/include/c++/12/bits/hashtable.h: In instantiation of ‘class std::_Hashtable<std::tuple<float, float, float>, std::tuple<float, float, float>, std::allocator<std::tuple<float, float, float> >, std::__detail::_Identity, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&), std::hash<std::tuple<float, float, float> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >’:
/usr/include/c++/12/bits/unordered_set.h:100:18:   required from ‘class std::unordered_set<std::tuple<float, float, float>, std::hash<std::tuple<float, float, float> >, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&)>’
unordered_set_triplet.cpp:21:26:   required from here
/usr/include/c++/12/bits/hashtable.h:665:7: error: function returning a function
  665 |       key_eq() const
      |       ^~~~~~
In file included from /usr/include/c++/12/unordered_set:47:
/usr/include/c++/12/bits/unordered_set.h: In instantiation of ‘class std::unordered_set<std::tuple<float, float, float>, std::hash<std::tuple<float, float, float> >, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&)>’:
unordered_set_triplet.cpp:21:26:   required from here
/usr/include/c++/12/bits/unordered_set.h:632:7: error: function returning a function
  632 |       key_eq() const
      |       ^~~~~~
unordered_set_triplet.cpp: In function ‘int main()’:
unordered_set_triplet.cpp:21:49: error: expected primary-expression before ‘,’ token
   21 |   unordered_set_triplet s(10, std::hash<triplet>, triplet_equal);
      |                                                 ^

如何解决这个问题？

EDIT

使用（已订购）也不起作用set:

>> cat set_triplet.cpp 
#include <iostream>
#include <set>
#include <tuple>
#include <limits> // numeric_limits
#include <cmath> // fabs
#include <functional> // hash

using triplet = std::tuple<float, float, float>;
bool triplet_equal(triplet const & lhs, triplet const & rhs) {
  float const eps = std::numeric_limits<float>::epsilon();
  if (std::fabs(std::get<0>(lhs) - std::get<0>(rhs)) > eps) return false;
  if (std::fabs(std::get<1>(lhs) - std::get<1>(rhs)) > eps) return false;
  if (std::fabs(std::get<2>(lhs) - std::get<2>(rhs)) > eps) return false;
  return true;
}
using set_triplet = std::set<triplet, std::hash<triplet>, decltype(triplet_equal)>;

int main() {
  //set_triplet s; // Compilation: KO...
  set_triplet s(10, std::hash<triplet>, triplet_equal);
  s.insert({1.f, 2.f, 3.f});
  s.insert({1.0000001f, 2.0000001f, 3.0000001f});
  for (auto const & t : s) std::cout << std::get<0>(t) << ", " << std::get<1>(t) << ", " << std::get<2>(t) << std::endl;
}

什么容器适合使用？triplet可以看到 3D 点 (XYZ)：我需要处理/检测重复点。

解决方案：使用 SET（非无序集）和 INT（非浮点型）而不实现 Less

使用由整数组成的元组i这样建的i = (int) 1000000 * f来自浮动f并使用集合（如operator<乘以 1000000 后将遵守高达 6 位精度的严格排序）。

>> cat set_uint32_triplet.cpp 
#include <iostream>
#include <set>
#include <tuple>

using triplet_uint32 = std::tuple<uint32_t, uint32_t, uint32_t>;
using triplet_float = std::tuple<float, float, float>;
triplet_uint32 convert(triplet_float const & f) {
  uint32_t precision = 1000000; // Allow for 6-digit precision.
  uint32_t x = (uint32_t) (std::get<0>(f) * precision);
  uint32_t y = (uint32_t) (std::get<1>(f) * precision);
  uint32_t z = (uint32_t) (std::get<2>(f) * precision);
  return {x, y, z};
}

int main() {
  triplet_float pt1 = {1.f, 2.f, 3.f};
  triplet_float pt2 = {1.0000001f, 2.0000001f, 3.0000001f}; // Considered     duplicate with pt1.
  triplet_float pt3 = {1.000001f,  2.000001f,  3.000001f};  // Considered NOT duplicate with pt1.

  std::set<triplet_uint32> s;
  s.insert(convert(pt1));
  s.insert(convert(pt2));
  s.insert(convert(pt3));
  std::cout << "set size " << s.size() << std::endl;
  for (auto const & t : s) std::cout << "set item " << std::get<0>(t) << ", " << std::get<1>(t) << ", " << std::get<2>(t) << ", " << std::endl;
}

>> g++ -std=c++20 -o set_uint32_triplet set_uint32_triplet.cpp

>> ./set_uint32_triplet 
set size 2
set item 1000000, 2000000, 3000000, 
set item 1000000, 2000001, 3000001, 

解决方案：使用 SET（非无序集）和 INT（非浮点型）并实现 Less

>> cat set_uint32_triplet_less.cpp 
#include <iostream>
#include <set>
#include <tuple>

#define FLOAT_TO_INT(x) ((x)>=0?(int32_t)((x)+0.5):(int32_t)((x)-0.5))

using triplet_int32 = std::tuple<int32_t, int32_t, int32_t>;
using triplet_float = std::tuple<float, float, float>;
triplet_int32 convert(triplet_float const & f) {
  int32_t precision = 1000; // Allow for 3-digit precision.
  int32_t x = FLOAT_TO_INT(std::get<0>(f) * precision);
  int32_t y = FLOAT_TO_INT(std::get<1>(f) * precision);
  int32_t z = FLOAT_TO_INT(std::get<2>(f) * precision);
  //std::cout.precision(10);
  //std::cout << "convert: " << std::get<0>(f) << ", " << std::get<1>(f) << ", " << std::get<2>(f);
  //std::cout << " - " << std::get<0>(f) * precision << ", " << std::get<1>(f) * precision << ", " << std::get<2>(f) * precision;
  //std::cout << " - " << FLOAT_TO_INT(std::get<0>(f) * precision) << ", " << FLOAT_TO_INT(std::get<1>(f) * precision) << ", " << FLOAT_TO_INT(std::get<2>(f) * precision);
  //std::cout << " - " << x << ", " << y << ", " << z << std::endl;
  return {x, y, z};
}
struct less {
  bool operator()(triplet_int32 const & lhs,
                  triplet_int32 const & rhs) const {
    bool res = true; // lhs < rhs.
    if      (std::get<0>(lhs) >= std::get<0>(rhs)) res = false;
    else if (std::get<1>(lhs) >= std::get<1>(rhs)) res = false;
    else if (std::get<2>(lhs) >= std::get<2>(rhs)) res = false;
    //std::cout << "  less: " << std::get<0>(lhs) << ", " << std::get<1>(lhs) << ", " << std::get<2>(lhs);
    //std::cout <<    " - " << std::get<0>(rhs) << ", " << std::get<1>(rhs) << ", " << std::get<2>(rhs);
    //std::cout << " - res " << res << std::endl;
    return res; // lhs < rhs.
  }
};

int main() {
  triplet_float pt1 = {1.f, 2.f, 3.f};
  triplet_float pt2 = {1.0001f, 2.0001f, 3.0001f}; // Considered     duplicate with pt1.
  triplet_float pt3 = {1.001f,  2.001f,  3.001f};  // Considered NOT duplicate with pt1.

  std::set<triplet_int32, less> s;
  s.insert(convert(pt1));
  s.insert(convert(pt2));
  s.insert(convert(pt3));
  std::cout << "set size " << s.size() << std::endl;
  for (auto const & t : s) std::cout << "set item " << std::get<0>(t) << ", " << std::get<1>(t) << ", " << std::get<2>(t) << ", " << std::endl;
}
>> g++ -std=c++20 -o set_uint32_triplet_less set_uint32_triplet_less.cpp
>> ./set_uint32_triplet_less 
set size 2
set item 1000, 2000, 3000, 
set item 1001, 2001, 3001, 

这可能不是您想要的答案，但它为您提供了已接受答案的传递性问题的解决方案。

Use std::tuple<int, int, int>并通过将浮点数乘以某个常数（例如 10000）并向下舍入来量化浮点数。比例因子将取决于您的域。

如果需要保留原始值，请使用 unordered_map。使用 int 元组作为键，并添加一个 float 元组作为值。 然后，当您搜索给定的三元组时，您可以在三个值中的每个值中查找相邻元组。

这更复杂，工作量更大，但这是一种更正确的方法，并且可以避免由于传递性问题而导致的 UB。