Pointer/Reference 到 std::unordered_set 中的元素

Question

我使用 std::unordered_set 来存储我的数据对象。但是现在我想为他们创建一个pointer/reference，例如（没有散列函数...）：

struct Node
{
  Node* parent;
  ...
};
std::unordered_set<Node> list;

可以使用 std::unordered_set<Node>::const_iterator 吗？如果 （不删除元素！） 迭代器 "ordering" 发生变化，我不确定如何找出这些信息？

更新更多细节以便更好地理解：

我选择 std::unordered_set 因为查找时间不变。要提高我的 C++ 技能，最好知道要更改什么。

#include <iostream>
#include <string>
#include <stdint.h>
#include <vector>

#include <unordered_set>


struct Link;
struct Node
{
    uint32_t id;
    std::unordered_set<Link> link;

    Node(uint32_t id) : id(id)
    {
    };

    bool operator==(Node const& rhs)
    {
        return id == rhs.id;
    }
};

struct Link
{
    Node* parent;
    uint32_t param1; // ..... and more

    bool operator==(Link const& rhs)
    {
        return parent == parent.rhs && param1 == rhs.param1;
    }
}


namespace std
{
    template<> struct hash<Node>
    {
        size_t operator()(Node const& node) const
        {
            return hash<uint32_t>()(node.id);
        }
    };

    template<> struct hash<Link>
    {
        size_t operator()(Link const& link) const
        {
            return  hash<uint32_t>()(link.param1) ^ hash<Node>()(*link.parent);
        }
    };    
}

int main()
{
    std::unordered_set<Node> nodes;
    nodes.emplace( Node(1) );
    nodes.emplace( Node(2) );
    nodes.emplace( Node(3) );    
}

Answer 1

您可以在 unordered_set 中拥有指向 Node 对象的指针。但是这些指针必须是 Node const*（即 const）。

即使对 unordered_set 进行了插入，指针也不会失效。例如，您可以将这些指针存储在另一个 unordered_set<Node const*> 中，如：

std::unordered_set<Node, hasher> s{{1}, {2}, {3}};
std::unordered_set<Node const*> s_ptr;

for(auto &&i : s) {
  s_ptr.insert(&i);
}

Live Demo

Answer 2

无序容器中的迭代器在插入过程中发生重新散列时失效。我不会试图预测或避免重新散列。只要您不插入新项目，迭代器就会保持有效。您可以删除现有项目。

请注意，即使重新散列发生，值也不会移动。在您删除该特定项目之前，指针和引用不会失效。这意味着您可以执行 Node* parent 或类似的操作。

不清楚你的数据结构是什么。我假设您想将节点存储在 unordered_set（或几组）中，并且节点除此之外还具有 parent 关系。它适用于指针或引用而不是迭代器。您需要做的唯一更改是添加一个常量：const Node *parent。如果您需要在将 Node 插入集合后更改它，您可以通过指针（unique_ptr 等）存储它们，或者考虑将 unordered_map 以不可变部分作为键。

Pointer/Reference 到 std::unordered_set 中的元素

Pointer/Reference to element in std::unordered_set

c++

unordered-set

c++11