c++ - 带有 STL 的哈希列表 - 我可以将 STL 列表中的一个项目指向另一个项目吗？

Question

假设我有一个:

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

假设 Node 是:

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

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

不管怎样，抛开这些。我的问题是:

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

Answer 1

如果你想让它指向列表中的其他节点，那是完全可行的，是的。但是，我会提出一个不同的设计:a 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);        
}