How to maintain deque with quick lookup?

Question

I need to build a circular buffer as a deque in python with efficient search (not O(n) el in deque, but O(1) like in set())

from collections import deque 
deque = deque(maxlen=10) # in my case maxlen=1000
for i in range(20):
    deque.append(i)
deque 
Out[1]: deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
10 in deque # but it takes O(n), I need O(1)
Out[1]: True

I guess I need to maintain a separate dictionary for lookup and remove from it once deque is full, but don't understand how. I don't need to remove from the middle of deque, just to append as deque did it and quick lookup.

Answer 1

As you said, I guess you have to create a data structure with deque to insert/remove and set to look up O(1), like this:

from collections import deque

class CircularBuffer:
    def __init__(self, capacity):
        self.queue = deque()
        self.capacity = capacity
        self.value_set = set()

    def add(self, value):
        if self.contains(value):
            return
        if len(self.queue) >= self.capacity:
            self.value_set.remove(self.queue.popleft())
        self.queue.append(value)
        self.value_set.add(value)

    def contains(self, value):
        return value in self.value_set

test & output

cb = CircularBuffer(10)

for i in range(20):
    cb.add(i)

print(cb.queue)
print(cb.contains(10))

# deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
# True

It is a similar idea to implement a simple LRU Cache, dict + double linked list.
Hope that helps you, and comment if you have further questions. : )