使用STL的哈希列表-我可以将STL列表中的一个项指向另一个项吗?

Question

假设我有一个:

std::vector<std::list<Node> >

假设Node是:

class Node { 
    Node* next;
    int data;
};

向量单元格对应于快速查找的哈希函数值。其思想是将元素插入到vector中，但仍然将它们与Node-> next成员链接在一起。所以你有一个列表，其中的元素可以有效地通过键查找，使用哈希函数找到正确的向量单元开始。

不管怎样，把这些放在一边。我的问题是

我可以让我的Node::next指针指向列表中的其他节点(无论是同一节点，还是来自不同向量单元的另一个节点)而不会引起问题吗?我不确定列表的标准库实现是否允许这样做。我似乎遇到了问题(我的代码在这里无法访问)，我想看看这是否可能是原因。

Answer 1

如果您希望它指向列表中的其他节点，这是完全可行的，是的。然而，我将提出一种不同的设计:std::list<int>和std::unordered_map<int, std::list<int>::iterator>，它们都是类的成员，其唯一目的是保持两个容器同步。这应该比(我对)你目前计划的理解更容易、更安全、更快捷。

在两个列表中添加和删除对象是一件轻而易举的事:

std::unordered_map<int, std::list<int>::iterator> fast;
std::list<int> linked;
void add(int data) {
    fast[data] = linked.insert(linked.end(), data);
};
std::list<int>::iterator erase(std::list<int>::iterator iter) {
    fast.erase(*iter);
    return linked.erase(iter);        
}

Answer 2

STL列表是双重链接的，并且具有私有的previous和next指针。元素中的下一个指针与列表中的下一个指针无关，所以它可以是任何你想要的。你得自己处理这件事。看起来您正在实现一个带有哈希冲突链表的哈希(说clippy)。你看过地图容器了吗?