在图形类中，我需要处理具有整数值(主要是 1-1000)的节点。在每一步中，我都想从图中删除一个节点及其所有邻居。另外，我想始终从最小值的节点开始。我想了很久如何以最快的方式做到这一点，并决定执行以下操作:
- 图表使用邻接列表存储
- 有一个巨大的数组
std::vector<Node*> bucket[1000]按其值存储节点 - 始终存储并跟踪最低非空桶的索引
- 通过选择该索引的随机元素，或者如果桶已经空了则增加索引，我可以非常快速地找到最小值节点
- 从存储桶中删除选定的节点显然可以在 O(1) 中完成，问题是为了删除邻居，我需要首先在存储桶 Bucket[neighbor 的值] 中搜索所有邻居节点，这并不是很快。
是否有更有效的方法？
我想使用类似 std::list<Node*> bucket[1000] 的东西，并为每个节点分配一个指向其“列表元素”的指针，这样我就可以在 O(1) 时间内从列表中删除该节点。这对于 STL 列表是否可能，显然可以通过我可以手动实现的普通双链表来完成？
最佳答案
我最近为使用存储桶的优先级队列实现做了类似的事情。
我所做的是使用哈希表(unordered_map)，这样，您不需要存储 1000 个空 vector ，并且仍然可以获得 O(1) 随机访问(一般情况，不能保证)。现在，如果您只需要存储/创建该图形类一次，那可能并不重要。就我而言，我需要每秒创建数十/数百次优先级队列，并且使用 HashMap 产生了巨大的差异(因为事实上，当我实际上拥有该优先级的元素时，我只创建了 unordered_sets ，所以不需要初始化 1000 个空哈希集)。哈希集和映射是 C++11 中的新功能，但在 std::tr1 中已经可用一段时间了，或者您可以使用 Boost 库。
我可以看到您和我的用例之间的唯一区别是您还需要能够删除相邻节点。我假设每个节点都包含指向其邻居的指针列表。如果是这样，删除邻居应该采取 k * O(1)与 k邻居的数量(同样，一般来说，O(1)，不能保证，最坏情况是 unordered_map/set 中的 O(n))。您只需检查每个相邻节点，获取其优先级，即可为您提供 HashMap 中的正确索引。然后你在哈希集中找到优先级映射到的指针，这个搜索通常是O(1)，而删除元素通常又是O(1)。
总而言之，我认为您非常清楚该怎么做，但我相信使用 HashMap /集将大大加快您的代码速度(当然取决于具体的用法)。对我来说，使用 unordered_map<int, unordered_set> 实现的速度得到了提高与 vector<set>大约是 50 倍。
关于c++ - 快速桶实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9618204/