如何根据平等谓词在向量中删除重复物？

Question

我有一个 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 的 vec3 ，每个坐标的随机值。 使用的功能要求在该向量中，没有几个值 {v1，v2} 验证 v1 == -v2 。显然，我需要 operator == （上图中的一个）的定义，否则该问题是微不足道的。

我首先尝试 std :: set 和 std :: sort + std :: unique ，但找不到任何方法来拥有 struct fileing 命名的要求比较两种方法都需要）。

我该如何继续？

注意：

这与对指针进行排序，也来自 c ++如何从类类型的向量中删除重复项？根据某些标准可以分类元素（我认为）。

Answer 1

使用的函数要求在该向量填充V1 == -v2

中没有几个值{v1，v2}

，但找不到任何方法来使该应用程序的结构归档命名要求（两种方法都需要）。

在我看来，您正在尝试解决X，但这是您 xy-problem 。

实现满足 -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;

当然，您可以直接超载操作员并使用 std :: Less Liest ，但是通常我会建议针对具有不寻常行为的非违约操作员过载。

Answer 2

我相信最简单的方法是使用 std :: Unordered_set 并利用其第二和第三模板参数。

方法

1. 定义哈希函数

此步骤目标是提供“预滤波”步骤，该步骤根据上下文中的含义消除了明显的重复（因此，在这里， V1 和 -v1 应该具有相同的哈希）。

这是应该按 每类基础上的东西 。尽管不表现的关键应用程序可能会在下面使用第一个哈瑟，但无法提出通用 perforant 哈希功能（但我不再建议这样做）。

一个。 bad hasher

这是我最初提出的，然后在 @ in Count。

和 @ françoisAndrieux 那就是：

struct bad_hasher
{
    std::size_t operator()(const value_type&) const
    {
        return 0;
    }
};

它使所有哈希碰撞和强制 std :: unordered_set 使用 keyequal 来确定对象等效。
因此，确实有效，但这并不是一个不错的选择。 @ axnsan and @a href =“ https://stackover.com/users/7359094/fran%c3%A7oiisa7oiisa7oiisa7oiisa7oiis a -andrieux“>françoisAndrieux在下面的评论中指出了以下缺点：

• “它将其性能特征更改为o（n^2）（它将必须通过每个查找中的所有元素迭代）”（ - @<<< a href =“ https://stackoverflow.com/users/3194671/axnsan”> axnsan ）
• ” [它将集合]设置为一个简单的无分数链接列表。每个元素都会碰撞其他元素，看起来典型的实现使用＆nbsp; 碰撞链接”。 （ - @françoisAndrieux

） /代码>与 std :: vector + std :: remove_if 相同。

b。 更好的 hasher

@ 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）== etport_hasher（-v）。
• v1！= V2 =＆gt; better_hasher（v1）！= better_hasher（v2） 在大多数情况下（（1，0，1）将与碰撞（1 ，1，0））
• 并非所有哈希相撞。
• 删除明显的重复。

在这种配置中，这可能是我们可以希望的最好的。

然后，由于哈希碰撞，我们需要删除那些“误报”。

2. 定义关键平等谓词< / strong>

此处的目标是删除没有被藏机检测到的重复（通常是（1，1，0，1） /（1，1，1，0）的向量）或溢出）。

声明一个谓词 struct ，该大致看起来像：

struct key_equal
{
    bool operator()(const value_type& a, const value_type& b) const
    {
        
        return (a == b) || <...>;
    }
};

其中＆lt; ...＆gt; 在当前上下文中的两个值相同（因此，这里 a ========== b）|| -a == b 例如）。

请注意，这将期望实现 operator == 。

3. 删除重复项

声明 std :: unordered_set 删除重复的重复：

const std::unordered_set<value_type, hasher, key_equal> s(container.begin(), container.end());
container.assign(s.begin(), s.end());

3. （alt）删除重复（并保存在容器中的原始顺序）

基本上是相同的，但是这检查是否可以将元素插入 std :: Unordered_set 以及是否可以插入不删除它。 Adapted from @yury's answer in

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());

通用（独立于容器的）模板函数：

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 已知的编译时间，如果您关心是否关心，则元素以相同的顺序保留）。我没有在此功能中的两个分支中的任何一个基准测试，所以我不知道一个分支是否比另一个分支机构明显好，尽管这个答案似乎显示手动插入可能更快。

在此用例中的示例：

/// "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：非订单保存：

// ...<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：订单保守词：输出：

// ... <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)