in c++, How std::deque works internally

Now a question rises how high deque is able to give good performance for insertion and deletion at both ends?To know the answer we need to know little internal implementation of dequeue.

A deque is generally implemented as a collection of memory blocks. These memory blocks contains the elements at contiguous locations.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/1954fe37-b299-4138-aa7d-72174dc7f5b2/image.png

Consider deque as a linked list of vectors

python deque

import collections

# Create a deque

DoubleEnded = collections.deque(["Mon","Tue","Wed"])

print (DoubleEnded)

# Append to the right

print("Adding to the right: ")

DoubleEnded.append("Thu")

print (DoubleEnded)

# append to the left

print("Adding to the left: ")

DoubleEnded.appendleft("Sun")

print (DoubleEnded)

# Remove from the right

print("Removing from the right: ")

DoubleEnded.pop()

print (DoubleEnded)

# Remove from the left

print("Removing from the left: ")

DoubleEnded.popleft()

print (DoubleEnded)

# Reverse the dequeue

print("Reversing the deque: ")

DoubleEnded.reverse()

print (DoubleEnded)