如何基于相等谓词删除向量中的重复项？
How to remove duplicates in a vector based on an equality predicate?
我有一个 struct 大致是这样的：
struct vec3
{
int x;
int y;
int z;
constexpr bool operator==(const vec3& v) const
{
return (x == v.x) && (y == v.y) && (z == v.z);
}
constexpr vec3 operator-() const
{
return {-x, -y, -z};
}
};
然后我生成一个 std::vector of vec3，每个坐标都有随机值。
使用它的函数要求该向量中没有一对值 {v1, v2} 填充 v1 == -v2。我显然需要在代码的其他地方定义 operator== ，否则这个问题就微不足道了。
我首先尝试 std::set 和 std::sort + std::unique，但找不到任何方法来为该申请 struct 提交 named requirements Compare（这两种方法都需要）。
我该如何继续？
Note:
This is somewhat different from Removing duplicates from a non-sortable vector in which pointers are sorted, and also from C++ how to remove duplicates from vector of Class type? in which the elements are sortable according to some criteria (I think).
我相信最简单的方法是使用 std::unordered_set 并利用它的第二个和第三个 template 参数。
方法
- 定义一个散列函数
这一步的目标是提供一个“pre-filtering”步骤，根据上下文中的含义消除明显的重复（所以这里，v1并且 -v1 应该具有相同的散列）。
这应该是 per-class 基础上的 。没有办法想出通用的 performant 散列函数，尽管 non-performant 关键应用程序可能会使用下面的第一个散列器（但我不会再推荐了）。
一个。 不好的哈希器
这是我最初提出的，在考虑@axnsan and @François Andrieux 的评论之前。
我能想到的最简单的哈希器如下所示：
struct bad_hasher
{
std::size_t operator()(const value_type&) const
{
return 0;
}
};
它使所有散列发生冲突并强制std::unordered_set 使用KeyEqual 来确定对象是否相等。
因此，确实 有效 ，但这并不是一个好的选择。 @axnsan and @François Andrieux 在下面的评论中指出了以下缺点：
- "它将其性能特征更改为 O(n^2)（它必须在每次查找时遍历所有元素）"(- @axnsan)
- [它将集合转换为一个简单的未排序链表。每个元素都会与其他元素发生冲突，看起来典型的实现使用 collision chaining". (- @François Andrieux)
换句话说，这使得 std::unordered_set 与 std::vector + std::remove_if 相同。
b。 更好 哈希器
@axnsan 建议针对此特定应用程序使用以下散列器：
struct better_hasher
{
std::size_t operator()(const vec3& v) const
{
return static_cast<std::size_t>(std::abs(v.x) + std::abs(v.y) + std::abs(v.z));
}
};
满足以下要求：
better_hasher(v) == better_hasher(-v).v1 != v2 => better_hasher(v1) != better_hasher(v2) 在大多数情况下（例如(1, 0, 1)会与(1, 1, 0)发生碰撞）- 并不是所有的散列都会发生冲突。
- 删除明显的重复项。
这可能接近我们希望在此配置中达到的最佳状态。
然后我们需要删除由于哈希冲突而导致的那些“误报”。
- 定义一个键相等谓词
此处的目标是删除哈希器未检测到的重复项（此处通常是 (1, 0, 1) / (1, 1, 0) 或溢出等向量）。
声明一个谓词 struct 大致如下所示：
struct key_equal
{
bool operator()(const value_type& a, const value_type& b) const
{
return (a == b) || <...>;
}
};
其中 <...> 是在当前上下文中使两个值相同的任何东西（因此这里 a == b) || -a == b 例如）。
请注意，这需要 operator== 才能实现。
- 删除重复项
声明一个删除重复项的 std::unordered_set：
const std::unordered_set<value_type, hasher, key_equal> s(container.begin(), container.end());
container.assign(s.begin(), s.end());
- (alt) 删除重复项（并在容器中保留原始顺序）
基本相同，但这里检查是否可以在 std::unordered_set 中插入一个元素，如果不能，则将其删除。改编自 @yury's answer in What's the most efficient way to erase duplicates and sort a vector?.
std::unordered_set<value_type, hasher, comparator> s;
const auto predicate = [&s](const value_type& value){return !s.insert(value).second;};
container.erase(std::remove_if(container.begin(), container.end(), predicate), container.end());
通用（container-independent）模板函数：
template<typename key_equal_t, typename hasher_t, bool order_conservative, typename container_t>
void remove_duplicates(container_t& container)
{
using value_type = typename container_t::value_type;
if constexpr(order_conservative)
{
std::unordered_set<value_type, hasher_t, key_equal_t> s;
const auto predicate = [&s](const value_type& value){return !s.insert(value).second;};
container.erase(std::remove_if(container.begin(), container.end(), predicate), container.end());
}
else
{
const std::unordered_set<value_type, hasher, key_equal_t> s(container.begin(), container.end());
container.assign(s.begin(), s.end());
}
}
预计会提供 key_equal_t 和 hasher_t（以及一个 bool 已知的编译时间，表明您是否关心元素是否保持相同的顺序）。我没有对这个函数中的两个分支中的任何一个进行基准测试，所以我不知道一个是否明显优于另一个，尽管 this answer 似乎显示手动插入可能更快。
此用例中的示例：
/// "Predicate" indicating if two values are considered duplicates or not
struct key_equal
{
bool operator()(const vec3& a, const vec3& b) const
{
// Remove identical vectors and their opposite
return (a == b) || (-a == b);
}
};
/// Hashes a vec3 by adding absolute values of its components.
struct hasher
{
std::size_t operator()(const vec3& v) const
{
return static_cast<std::size_t>(std::abs(v.x) + std::abs(v.y) + std::abs(v.z));
}
};
remove_duplicates<key_equal, hasher, order_conservative>(vec);
测试数据：
vec3 v1{1, 1, 0}; // Keep
vec3 v2{0, 1, 0}; // Keep
vec3 v3{1, -1, 0}; // Keep
vec3 v4{-1, -1, 0}; // Remove
vec3 v5{1, 1, 0}; // Remove
std::vector vec{v1, v2, v3, v4, v5};
测试 1：non-order-conservative：
// ...<print vec values>
remove_duplicates<key_equal, hasher, false>(vec);
// ... <print vec values>
输出（之前/之后）：
(1, 1, 0) (0, 1, 0) (1, -1, 0) (-1, -1, 0) (1, 1, 0)
(1, -1, 0) (0, 1, 0) (1, 1, 0)
测试 2：order-conservative：
// ... <print vec values>
remove_duplicates<key_equal, hasher, true>(vec);
// ... <print vec values>
输出（之前/之后）：
(1, 1, 0) (0, 1, 0) (1, -1, 0) (-1, -1, 0) (1, 1, 0)
(1, 1, 0) (0, 1, 0) (1, -1, 0)
The function in which it is used requires that no couple of values {v1, v2} in that vector fills v1 == -v2
but could not find any way to have a struct filing named requirements Compare for that application (which is needed for both approaches).
在我看来，您正在尝试解决 X，但这是您 XY-problem 中的 Y。
实现满足 -v == v 等式的有序比较器相当简单。简单比较绝对值：
struct vec3
{
int x;
int y;
int z;
// normal comparison that treats -x != x
friend auto operator<=>(const vec3&, const vec3&) = default;
};
// declare in same namespace as vec3 for ADL
vec3 abs(const vec3& v) {
return {std::abs(v.x), std::abs(v.y), std::abs(v.z)};
}
struct abs_less {
template< class T, class U>
constexpr auto operator()( T&& lhs, U&& rhs ) const
-> decltype(std::forward<T>(lhs) < std::forward<U>(rhs))
{
using std::abs; // for integers
return abs(lhs) < abs(rhs); // this implementation assumes normal comparison operator
// you can implement logic directly here if that's not possible
}
};
此比较器适用于 std::set 和 std::sort + std::unique。集合示例：
std::set<vec3, abs_less> example;
当然，您可以直接重载 operator< 并使用 std::less，但通常我建议不要使用具有异常行为的 non-defaulted 运算符重载。
我有一个 struct 大致是这样的：
struct vec3
{
int x;
int y;
int z;
constexpr bool operator==(const vec3& v) const
{
return (x == v.x) && (y == v.y) && (z == v.z);
}
constexpr vec3 operator-() const
{
return {-x, -y, -z};
}
};
然后我生成一个 std::vector of vec3，每个坐标都有随机值。
使用它的函数要求该向量中没有一对值 {v1, v2} 填充 v1 == -v2。我显然需要在代码的其他地方定义 operator== ，否则这个问题就微不足道了。
我首先尝试 std::set 和 std::sort + std::unique，但找不到任何方法来为该申请 struct 提交 named requirements Compare（这两种方法都需要）。
我该如何继续？
Note:
This is somewhat different from Removing duplicates from a non-sortable vector in which pointers are sorted, and also from C++ how to remove duplicates from vector of Class type? in which the elements are sortable according to some criteria (I think).
我相信最简单的方法是使用 std::unordered_set 并利用它的第二个和第三个 template 参数。
方法
- 定义一个散列函数
这一步的目标是提供一个“pre-filtering”步骤，根据上下文中的含义消除明显的重复（所以这里，v1并且 -v1 应该具有相同的散列）。
这应该是 per-class 基础上的 。没有办法想出通用的 performant 散列函数，尽管 non-performant 关键应用程序可能会使用下面的第一个散列器（但我不会再推荐了）。
一个。 不好的哈希器
这是我最初提出的，在考虑@axnsan and @François Andrieux 的评论之前。
我能想到的最简单的哈希器如下所示：
struct bad_hasher
{
std::size_t operator()(const value_type&) const
{
return 0;
}
};
它使所有散列发生冲突并强制std::unordered_set 使用KeyEqual 来确定对象是否相等。
因此，确实 有效 ，但这并不是一个好的选择。 @axnsan and @François Andrieux 在下面的评论中指出了以下缺点：
- "它将其性能特征更改为 O(n^2)（它必须在每次查找时遍历所有元素）"(- @axnsan)
- [它将集合转换为一个简单的未排序链表。每个元素都会与其他元素发生冲突，看起来典型的实现使用 collision chaining". (- @François Andrieux)
换句话说，这使得 std::unordered_set 与 std::vector + std::remove_if 相同。
b。 更好 哈希器
@axnsan 建议针对此特定应用程序使用以下散列器：
struct better_hasher
{
std::size_t operator()(const vec3& v) const
{
return static_cast<std::size_t>(std::abs(v.x) + std::abs(v.y) + std::abs(v.z));
}
};
满足以下要求：
better_hasher(v) == better_hasher(-v).v1 != v2=>better_hasher(v1) != better_hasher(v2)在大多数情况下（例如(1, 0, 1)会与(1, 1, 0)发生碰撞）- 并不是所有的散列都会发生冲突。
- 删除明显的重复项。
这可能接近我们希望在此配置中达到的最佳状态。
然后我们需要删除由于哈希冲突而导致的那些“误报”。
- 定义一个键相等谓词
此处的目标是删除哈希器未检测到的重复项（此处通常是 (1, 0, 1) / (1, 1, 0) 或溢出等向量）。
声明一个谓词 struct 大致如下所示：
struct key_equal
{
bool operator()(const value_type& a, const value_type& b) const
{
return (a == b) || <...>;
}
};
其中 <...> 是在当前上下文中使两个值相同的任何东西（因此这里 a == b) || -a == b 例如）。
请注意，这需要 operator== 才能实现。
- 删除重复项
声明一个删除重复项的 std::unordered_set：
const std::unordered_set<value_type, hasher, key_equal> s(container.begin(), container.end());
container.assign(s.begin(), s.end());
- (alt) 删除重复项（并在容器中保留原始顺序）
基本相同，但这里检查是否可以在 std::unordered_set 中插入一个元素，如果不能，则将其删除。改编自 @yury's answer in What's the most efficient way to erase duplicates and sort a vector?.
std::unordered_set<value_type, hasher, comparator> s;
const auto predicate = [&s](const value_type& value){return !s.insert(value).second;};
container.erase(std::remove_if(container.begin(), container.end(), predicate), container.end());
通用（container-independent）模板函数：
template<typename key_equal_t, typename hasher_t, bool order_conservative, typename container_t>
void remove_duplicates(container_t& container)
{
using value_type = typename container_t::value_type;
if constexpr(order_conservative)
{
std::unordered_set<value_type, hasher_t, key_equal_t> s;
const auto predicate = [&s](const value_type& value){return !s.insert(value).second;};
container.erase(std::remove_if(container.begin(), container.end(), predicate), container.end());
}
else
{
const std::unordered_set<value_type, hasher, key_equal_t> s(container.begin(), container.end());
container.assign(s.begin(), s.end());
}
}
预计会提供 key_equal_t 和 hasher_t（以及一个 bool 已知的编译时间，表明您是否关心元素是否保持相同的顺序）。我没有对这个函数中的两个分支中的任何一个进行基准测试，所以我不知道一个是否明显优于另一个，尽管 this answer 似乎显示手动插入可能更快。
此用例中的示例：
/// "Predicate" indicating if two values are considered duplicates or not
struct key_equal
{
bool operator()(const vec3& a, const vec3& b) const
{
// Remove identical vectors and their opposite
return (a == b) || (-a == b);
}
};
/// Hashes a vec3 by adding absolute values of its components.
struct hasher
{
std::size_t operator()(const vec3& v) const
{
return static_cast<std::size_t>(std::abs(v.x) + std::abs(v.y) + std::abs(v.z));
}
};
remove_duplicates<key_equal, hasher, order_conservative>(vec);
测试数据：
vec3 v1{1, 1, 0}; // Keep
vec3 v2{0, 1, 0}; // Keep
vec3 v3{1, -1, 0}; // Keep
vec3 v4{-1, -1, 0}; // Remove
vec3 v5{1, 1, 0}; // Remove
std::vector vec{v1, v2, v3, v4, v5};
测试 1：non-order-conservative：
// ...<print vec values>
remove_duplicates<key_equal, hasher, false>(vec);
// ... <print vec values>
输出（之前/之后）：
(1, 1, 0) (0, 1, 0) (1, -1, 0) (-1, -1, 0) (1, 1, 0)
(1, -1, 0) (0, 1, 0) (1, 1, 0)
测试 2：order-conservative：
// ... <print vec values>
remove_duplicates<key_equal, hasher, true>(vec);
// ... <print vec values>
输出（之前/之后）：
(1, 1, 0) (0, 1, 0) (1, -1, 0) (-1, -1, 0) (1, 1, 0)
(1, 1, 0) (0, 1, 0) (1, -1, 0)
The function in which it is used requires that no couple of values {v1, v2} in that vector fills v1 == -v2
but could not find any way to have a struct filing named requirements Compare for that application (which is needed for both approaches).
在我看来，您正在尝试解决 X，但这是您 XY-problem 中的 Y。
实现满足 -v == v 等式的有序比较器相当简单。简单比较绝对值：
struct vec3
{
int x;
int y;
int z;
// normal comparison that treats -x != x
friend auto operator<=>(const vec3&, const vec3&) = default;
};
// declare in same namespace as vec3 for ADL
vec3 abs(const vec3& v) {
return {std::abs(v.x), std::abs(v.y), std::abs(v.z)};
}
struct abs_less {
template< class T, class U>
constexpr auto operator()( T&& lhs, U&& rhs ) const
-> decltype(std::forward<T>(lhs) < std::forward<U>(rhs))
{
using std::abs; // for integers
return abs(lhs) < abs(rhs); // this implementation assumes normal comparison operator
// you can implement logic directly here if that's not possible
}
};
此比较器适用于 std::set 和 std::sort + std::unique。集合示例：
std::set<vec3, abs_less> example;
当然，您可以直接重载 operator< 并使用 std::less，但通常我建议不要使用具有异常行为的 non-defaulted 运算符重载。