Find if an item already exists in the STL queue

Question

I use the STL queue to implement BFS (width first search) on a chart. I need to click the node in the queue if that node no longer exists in the queue. However, the STL queue does not allow iteration through its elements , and therefore I cannot use the STL lookup function.

I can use the flag for each node to mark them when they are visited, and only click them when the flag is false, however I need to run BFS several times and after each time I will have to reset all the flags, so I used the counter instead flag, but I still would like to know if there is a standard way to search for an item in the queue.

Answer 1

I assume that you are implementing the concept of "private set" in your BFS? The standard way to do this is to simply maintain a separate std::set or std::unordered_set elements that have already been encountered. This way you get an O (log n) or O (1) search, while iterating through the queue, if supported, will take O (n) time.