Check if item is in queue

Question

I am using the Queue library in python and I want the entries in the queue to be unique.

As such, I want to check for “something” not yet in the queue before adding to it, essentially a function that works in the Queue library:

 queue = Queue.Queue() def in_queue(u): return u in queue 

Or should I use a different library / method to achieve this?

Answer 1

The standard Queue class cannot be repeated or otherwise verified.

However, it was created for expansion.

First, if you look at the source (which is associated with documents), there are hook methods _init , _qsize , _put and _get , which you can override to change the implementation. Look at the subclasses below the main class, and you can see how they do it.

So, one simple task is to replace the deque implementation with set :

 class SetQueue(Queue.Queue): def _init(self, maxsize): self.queue = set() def _put(self, item): self.queue.add(item) def _get(self): return self.queue.pop() 

(I did not implement _qsize , because by default return len(self.queue) is fine.)

Now you do not need to check, just add it to the queue and it will be ignored if it already exists.

Of course, this has the side that the queue is no longer streamlined. But you can solve this using an OrderedSet (similar to OrderedDict in collections ). There is a recipe that is associated with collections documents. When you have this:

 class OrderedSetQueue(Queue.Queue): def _init(self, maxsize): self.queue = OrderedSet() def _put(self, item): self.queue.add(item) def _get(self): return self.queue.pop() 

---

If you really want to check the values ​​in the queue, you can add a method for this:

 class CheckableQueue(Queue.Queue): # or OrderedSetQueue def __contains__(self, item): with self.mutex: return item in self.queue 

However, this causes race conditions in your code. For example, if you do this:

 if x not in my_queue: my_queue.put(x) 

It is always possible that x not in the queue when checking, but was in the queue when you called put . In fact, the only use of this function that would not be unsafe is some optimistic check (if the value is not in the queue now, do some expensive work, then try to add it, recognizing that the work is wasted if the value was added to the same time) - the same reason Queue.full() exists.

The only way to make it safe is to combine both operations under a lock:

 with my_queue.mutex: if x not in my_queue: my_queue.put(x) 

But at this point you defeat the goal of using Queue in the first place. (You also depend on the fact that Queue.mutex is a recursively-injected mutex.) It is better to add an operation as a method of your Queue subclass.

And if you always want to check and add first only if it is not, OrderedSetQueue is the best way to do this.