查找一个项目是否已经存在于STL队列中

问题描述

我使用STL队列在图上实现BFS（宽度优先搜索）。如果该节点已经不在队列中，我需要推送队列中的一个节点。但是，STL队列的，因此我不能使用STL查找功能。

我可以使用每个节点的标志来标记它们，当它们被访问时，只有在标志为false时才会推送它们，但是，我需要多次运行BFS，每次我将不得不重置所有的标志，所以我最终使用了一个计数器，而不是一个标志，但我仍然想知道是否有一个标准的方式找到一个队列中的项目。

解决方案

我假设你在BFS中实现了封闭集合的概念？这样做的标准方法是简单地维护单独的 std :: set 或 std :: unordered_set 元素遇到。这样，你可以得到O（lg em n）或者O（1）查找，如果它被支持的话，通过一个队列迭代会花费O（ n ）时间。

I am using an STL queue to implement a BFS (breadth first search) on a graph. I need to push a node in the queue if that node already doesn't exist in the queue. However, STL queue does not allow iteration through its elements and hence I cannot use the STL find function.

I could use a flag for each node to mark them when they are visited and push them only when the flag is false, however, I need to run BFS multiple times and after each time I will have to reset all the flags, so I ended up using a counter instead of a flag, but I still would like to know if there is a standard way of finding an item in a queue.

解决方案

I assume you're implementing the concept of a "closed set" in your BFS? The standard way of doing that is to simply maintain a separate std::set or std::unordered_set of elements already encountered. That way, you get O(lg n) or O(1) lookup, while iterating through a queue, if it were supported, would take O(n) time.

这篇关于查找一个项目是否已经存在于STL队列中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！