2

我正在尝试散列一个 Edge 结构，以便我可以拥有一个具有唯一边缘的 unordered_set。在我的情况下，如果在之前的集合中没有遇到它的两个端点的组合，则认为一条边是唯一的。

虽然我的代码适用于仅包含 Edge 类型的 unordered_set，但我无法让它适用于指向 Edge 类型的指针。请在下面查看我有些冗长的代码。非常感谢任何帮助。

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <unordered_set>

struct Vector3
{
    float x, y, z;

    Vector3() {}

    Vector3(float xx, float yy, float zz)
    {
        x = xx, y = yy, z = zz;
    }

    inline bool operator==(const Vector3& other) const
    {
        return x == other.x && y == other.y && z == other.z;
    }

    friend std::ostream& operator<<(std::ostream& stream, const Vector3& vector);
};

std::ostream& operator<<(std::ostream& stream, const Vector3& vector)
{
    return stream 
        << "(" 
        << std::setw(2) << std::setfill(' ') << vector.x << ", " 
        << std::setw(2) << std::setfill(' ') << vector.y << ", " 
        << std::setw(2) << std::setfill(' ') << vector.z 
        << ")";
}

struct Edge
{
    Vector3 EndPoints[2];

    Edge() {}

    Edge(Vector3 p, Vector3 q)
    {
        EndPoints[0] = p;
        EndPoints[1] = q;
    }

    inline bool operator==(const Edge& other) const
    {
        return  (EndPoints[0] == other.EndPoints[0] || EndPoints[0] == other.EndPoints[1]) && 
                (EndPoints[1] == other.EndPoints[1] || EndPoints[1] == other.EndPoints[0]);
    }

    inline bool operator==(const Edge* other) const
    {
        return  (EndPoints[0] == other->EndPoints[0] || EndPoints[0] == other->EndPoints[1]) && 
                (EndPoints[1] == other->EndPoints[1] || EndPoints[1] == other->EndPoints[0]);
    }

    friend std::ostream& operator<<(std::ostream& stream, const Edge& vector);
    friend std::ostream& operator<<(std::ostream& stream, const Edge* vector);
};

std::ostream& operator<<(std::ostream& stream, const Edge& edge)
{
    return stream << edge.EndPoints[0] << " -- " << edge.EndPoints[1];
}

std::ostream& operator<<(std::ostream& stream, const Edge* edge)
{
    return stream << edge->EndPoints[0] << " -- " << edge->EndPoints[1];
}


namespace std
{
    template <>
    struct hash<Edge>
    {
        std::size_t operator()(const Edge& edge) const
        {
            Vector3 p0 = edge.EndPoints[0];
            Vector3 p1 = edge.EndPoints[1];

            if (p1.x < p0.x) std::swap(p0.x, p1.x);
            if (p1.y < p0.y) std::swap(p0.y, p1.y);
            if (p1.z < p0.z) std::swap(p0.z, p1.z);

            unsigned hash0 = (int(p0.x*73856093) ^ int(p0.y*19349663) ^ int(p0.z*83492791)) % 1024;
            unsigned hash1 = (int(p1.x*73856093) ^ int(p1.y*19349663) ^ int(p1.z*83492791)) % 1024;

            return hash0 ^ (hash1 << 3);
        }
    };

    template <>
    struct hash<Edge*>
    {
        std::size_t operator()(const Edge* edge) const
        {
            Vector3 p0 = edge->EndPoints[0];
            Vector3 p1 = edge->EndPoints[1];

            if (p1.x < p0.x) std::swap(p0.x, p1.x);
            if (p1.y < p0.y) std::swap(p0.y, p1.y);
            if (p1.z < p0.z) std::swap(p0.z, p1.z);

            unsigned hash0 = (int(p0.x*73856093) ^ int(p0.y*19349663) ^ int(p0.z*83492791)) % 1024;
            unsigned hash1 = (int(p1.x*73856093) ^ int(p1.y*19349663) ^ int(p1.z*83492791)) % 1024;

            std::size_t key = hash0 ^ (hash1 << 3);
            return key;
        }
    };
}


void add_edge(std::unordered_set<Edge>& table, Edge edge)
{
    std::unordered_set<Edge>::const_iterator it = table.find(edge);
    if (it == table.end()) table.insert(edge);
    else std::cout << "Table already contains edge " << edge << std::endl;
}

void add_edge(std::unordered_set<Edge*>& table, Edge* edge)
{
    std::unordered_set<Edge*>::const_iterator it = table.find(edge);
    if (it == table.end()) table.insert(edge);
    else std::cout << "Table already contains edge " << edge << std::endl;
}


void print_table(std::unordered_set<Edge>& table)
{
    std::cout << std::endl;
    std::cout << "Table has " << table.size() << " elements:" << std::endl;

    for (auto it = table.begin(); it != table.end(); ++it)
        std::cout << *it << std::endl;

    std::cout << std::endl;
}

void print_table(std::unordered_set<Edge*>& table)
{
    std::cout << std::endl;
    std::cout << "Table has " << table.size() << " elements:" << std::endl;

    for (auto it = table.begin(); it != table.end(); ++it)
        std::cout << *(*it) << std::endl;

    std::cout << std::endl;
}


int main()
{
    std::unordered_set<Edge> table;
    std::unordered_set<Edge*> ptable;

    Edge e0(Vector3( 1.f,  0.f,  0.f), Vector3(-1.f,  0.f,  0.f));
    Edge e1(Vector3(-1.f,  0.f,  0.f), Vector3( 1.f,  0.f,  0.f));

    add_edge(table, e0);
    add_edge(table, e1);

    print_table(table);

    add_edge(ptable, &e0);
    add_edge(ptable, &e1);

    print_table(ptable);

    return 0;
}

这是输出：

1>  Table already contains edge (-1,  0,  0) -- ( 1,  0,  0)
1>  
1>  Table has 1 elements:
1>  ( 1,  0,  0) -- (-1,  0,  0)
1>  
1>  Table has 2 elements:
1>  (-1,  0,  0) -- ( 1,  0,  0)
1>  ( 1,  0,  0) -- (-1,  0,  0)

所以我的问题是：为什么将第二个元素添加到第二个表中？我检查了哈希函数，但它为两个条目返回相同的键，所以这似乎不是罪魁祸首，但我不确定它可能是什么。

编辑：

我现在发现inline bool operator==(const Edge* other) const没有调用，但我不知道为什么。

4

2 回答 2

3

Angew 指出了真正的问题。

还有其他问题。似乎您希望 Edges 始终是双向的，因此 Edge(a,b) == Edge(b,a)。

旁注Edge实现此目的的最佳方法（IMO）是在构建过程中以确定的顺序对端点进行排序以后不用考虑了。这被称为不变量，并且消除了在所有其余代码中检查边的“等效性”的负担。

但是，您的哈希函数没有正确实现

你的hash<>::operator()阅读：

    std::size_t operator()(const Edge& edge) const
    {
        Vector3 p0 = edge.EndPoints[0];
        Vector3 p1 = edge.EndPoints[1];

        if (p1.x < p0.x) std::swap(p0.x, p1.x);
        if (p1.y < p0.y) std::swap(p0.y, p1.y);
        if (p1.z < p0.z) std::swap(p0.z, p1.z);

        unsigned hash0 = (int(p0.x*73856093) ^ int(p0.y*19349663) ^ int(p0.z*83492791)) % 1024;
        unsigned hash1 = (int(p1.x*73856093) ^ int(p1.y*19349663) ^ int(p1.z*83492791)) % 1024;

        return hash0 ^ (hash1 << 3);
    }

这种交换逻辑有效地构成了虚假端点。

Edge(ep[3,1,2], ep[1,2,3])变成Edge(ep[1,1,2], ep[3,2,3])你可能想要的地方Edge(ep[1,2,3], ep[3,1,2])。

修复它会交换整个端点，而不是单个向量元素：

if (std::tie(p1.x, p1.y, p1.z) < std::tie(p0.x, p0.y, p0.z)) {
    using std::swap;
    swap(p0, p1);
}

通过删除（全部）不必要的重复代码来修复您的哈希函数：

template <> struct hash<Edge>
{
    std::size_t operator()(const Edge& edge) const {
        Vector3 p0 = edge.EndPoints[0];
        Vector3 p1 = edge.EndPoints[1];

        if (std::tie(p0.x, p0.y, p0.z) < 
            std::tie(p1.x, p1.y, p1.z))  // consider`Vector3::operator<`
        {
            using std::swap;
            swap(p0, p1);
        }

        auto hash_p = [](Vector3 const& p) { return (unsigned(p.x*73856093u) ^ unsigned(p.y*19349663u) ^ unsigned(p.z*83492791u)) % 1024u; };

        return hash_p(p0) ^ (hash_p(p1) << 3);
    }
};

并且指针哈希变成了单纯的转发：

template <> struct hash<Edge*> {
    std::size_t operator()(const Edge* edge) const { 
        return hash<Edge>()(*edge); 
    }
};

考虑将比较移至Vector3::operator<

固定测试程序

实现上述内容，并修复 Edge* 缺少的平等比较器：

也可以在 IdeOne 上看到它

#include <iostream>
#include <iomanip>
#include <unordered_set>
#include <cassert>
#include <tuple>

struct Vector3
{
    float x, y, z;

    Vector3() {}

    Vector3(float xx, float yy, float zz)
    {
        x = xx, y = yy, z = zz;
    }

    inline bool operator==(const Vector3& other) const
    {
        return x == other.x && y == other.y && z == other.z;
    }

    inline bool operator<(const Vector3& other) const
    {
        return std::tie(x, y, z) < std::tie(other.x, other.y, other.z);
    }

    friend std::ostream& operator<<(std::ostream& stream, const Vector3& vector);
};

std::ostream& operator<<(std::ostream& stream, const Vector3& vector)
{
    return stream 
        << "(" 
        << std::setw(2) << std::setfill(' ') << vector.x << ", " 
        << std::setw(2) << std::setfill(' ') << vector.y << ", " 
        << std::setw(2) << std::setfill(' ') << vector.z 
        << ")";
}

struct Edge
{
    Vector3 EndPoints[2];

    Edge() {}

    Edge(Vector3 p, Vector3 q)
    {
        // swap order
        if (q < p) { using std::swap; swap(p, q); } // the invariant
        EndPoints[0] = p;
        EndPoints[1] = q;
    }

    inline bool operator==(const Edge& other) const {
        return std::tie(EndPoints[0], EndPoints[1]) == std::tie(other.EndPoints[0], other.EndPoints[1]);
    }

    friend std::ostream& operator<<(std::ostream& stream, const Edge& vector);
    friend std::ostream& operator<<(std::ostream& stream, const Edge* vector);
};

std::ostream& operator<<(std::ostream& stream, const Edge& edge)
{
    return stream << edge.EndPoints[0] << " -- " << edge.EndPoints[1];
}

std::ostream& operator<<(std::ostream& stream, const Edge* edge)
{
    return stream << edge->EndPoints[0] << " -- " << edge->EndPoints[1];
}


namespace std
{
    template <> struct hash<Edge>
    {
        std::size_t operator()(const Edge& edge) const {
            assert(edge.EndPoints[0] < edge.EndPoints[1]); // the invariant

            auto hash_p = [](Vector3 const& p) { return (unsigned(p.x*73856093u) ^ unsigned(p.y*19349663u) ^ unsigned(p.z*83492791u)) % 1024u; };

            return hash_p(edge.EndPoints[0]) ^ (hash_p(edge.EndPoints[1]) << 3);
        }
    };

    template <> struct hash<Edge*> {
        std::size_t operator()(const Edge* edge) const { 
            return hash<Edge>()(*edge); 
        }
    };
}

struct EdgePtrEqual {
    bool operator()(Edge const* a, Edge const* b) const {
        return *a == *b;
    }
};

using EdgeSet    = std::unordered_set<Edge,  std::hash<Edge>>;
using EdgePtrSet = std::unordered_set<Edge*, std::hash<Edge*>, EdgePtrEqual>;

void add_edge(EdgeSet& table, Edge edge)
{
    EdgeSet::const_iterator it = table.find(edge);
    if (it == table.end()) table.insert(edge);
    else std::cout << "Table already contains edge " << edge << std::endl;
}

void add_edge(EdgePtrSet& table, Edge* edge)
{
    EdgePtrSet::const_iterator it = table.find(edge);
    if (it == table.end()) table.insert(edge);
    else std::cout << "Table already contains edge " << edge << std::endl;
}


void print_table(EdgeSet& table)
{
    std::cout << std::endl;
    std::cout << "Table has " << table.size() << " elements:" << std::endl;

    for (auto it = table.begin(); it != table.end(); ++it)
        std::cout << *it << std::endl;

    std::cout << std::endl;
}

void print_table(EdgePtrSet& table)
{
    std::cout << std::endl;
    std::cout << "Table has " << table.size() << " elements:" << std::endl;

    for (auto it = table.begin(); it != table.end(); ++it)
        std::cout << *(*it) << std::endl;

    std::cout << std::endl;
}


int main()
{
    EdgeSet table;
    EdgePtrSet ptable;

    Edge e0(Vector3( 1.f,  0.f,  0.f), Vector3(-1.f,  0.f,  0.f));
    Edge e1(Vector3(-1.f,  0.f,  0.f), Vector3( 1.f,  0.f,  0.f));

    add_edge(table, e0);
    add_edge(table, e1);

    print_table(table);

    add_edge(ptable, &e0);
    add_edge(ptable, &e1);

    print_table(ptable);

    return 0;
}
于 2013-09-05T12:24:49.127 回答
2

添加专门化的std::hash<Edge*>使哈希与相等比较不一致。因为集合中的元素是指针，所以它们使用正常的指针相等性进行比较。你的不平衡operator==(const Edge*)只会被要求比较 anEdge和 an Edge*（这绝对不是你想要的）。

您需要提供与您的哈希一致的比较器。默认比较器是std::equal_to<Key>. 我认为您不能（或不想）专门std::equal_to<Edge*>化 ，因此您应该只提供自己的比较器作为unordered_set.

不相关的提示：如果您像这样实现指针散列器，它将需要更少的维护：

template <>
struct hash<Edge*>
{
    std::size_t operator()(const Edge* edge) const
    {
        std::hash<Edge> h;
        return h(*edge);
    }
};
于 2013-09-05T12:06:51.063 回答