Many problems can be solved with arrays and their dynamic version. In Python, you can use the builtin list. In C++, you use vector. But the drawback is that these dynamic array is terrible at insertion and deletion at the front due to shifting. Deque is created to solve this problem!

#Introduction

Deque, or doubly-ended queue, is a data structure created to solve the critical problem that dynamic arrays have: working with the front element.

As a reminder, dynamic arrays are great at inserting and deleting the last element in the array, thanks to the size property: appending new elements will increase the size. Assume there is no reallocation happening, the time complexity of this operation is constant.

However, inserting or deleting an element at some arbitary position will take linear time, $O(N)$ where $N$ is the distance between the position on which the operation performs and the position of the last element. This means working with the first element always yields the worst runtime. (Psst. I have a post about about this)

This is where deque comes in to "save the world"!

#What deque can do

What deque proposes and tries to solve is support insertion and deletion at the front of a container. You might wonder: "Has linked list already solved this problem?". That is correct. Insertion/deleteion at the front can be done with linked lists.

However, the problem with linked lists is that accessing elements takes linear time. The beauty of a deque is that it also supports constant access time (random access), just like a vector can do.

With these useful traits, deque can be used as the underlying data structure for both stack (first-in last-out) and queue (first-in first out).

#Implementation

This article will focus heavily on the implementation on std::deque<T>, and a bit from collections.deque.

A deque maintains an array of fix-sized arrays. This data structure is often referred as a map. Initially, the map has an arbitary initial number of slots. In C++, this initial number is 8. In Python, it does not have an initial size as the implementation uses a doubly-linked list.

Each element in this map points to a block of elements. These blocks often have a fixed number of elements. In Python, the block length is set to 64, which means each block will contain 64 elements of a type. In C++, the block length is determined in bytes, which is 512. For example, C++ integer type int is 4 bytes, then the block length will be 512 / 4 = 128 elements in total. The bigger the size of a type is, the shorter the block is.

If the size of a type exceeds 512, C++ deque allocates only one object of that type, which means there is one element in a block.

#Deque iterator

The core functionalities rely on the implementation of its iterator.

An iterator is an interface on how you can access the underlying elements without knowing too much the internal implementation. More detail about C++ iterator here.

In C++, a deque iterator contains 4 essential member fields:

1. map_node: Map pointer that points to a block.
2. start: Block pointer that points to the first element.
3. finish: Block pointer that points to the end of the block.
4. curr: Block pointer that points to the last element.

Each deque object contains two iterators. One is used to mark the first range and one is used to mark the second range in the deque. The first pointer will grow backward, which means appending new elements will decrease the start iterator. Meanwhile, the second pointer will grow forward, which means appending new elements will increase the finish iterator.

If we re-arrange this illustration so that all blocks look continous:

In the second illustration, you have a better picture how the appending to front and to back works. Appending to the back will use the finish iterator and increase its internal _curr so that the deque can grow to the right. Appending to the front will use the start iterator and decrease its internal _curr so the the deque can grow to the left.

#Reallocation

You might wonder how deque handles reallocation when there is not enough space. Well, the beauty in deque's implementation does not stop there.

An inituitive thought is that you might copy allocate a completely new map, allocate all the nodes and start to copy everything from the old deque to the newly-created one.

If that's what you think, you are partly correct. To accomodate more space for new elements, we need to allocate a new map. However, you do not need to allocate new nodes and copy element by element.

Instead, the deque can just move the address of those nodes from the old deque to the new one. This will make the reallocation would be significantly less expensive.

#To use or not to use?

Deque is a great container that supports many useful functionalities to end users like us. They're widely used to solve problems that require efficient inserting at the front.

One of the most used case of deque in Python and C++ is probably to apply the queue data structure to solve problems. For example, Breadth-first search (BFS) requires using a queue to keep track of what node will be traversed next.

from collections import deque

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

def bfs(root):
  if root is None:
    return root

  q = deque()
  q.append(root)

  while len(q) != 0:
    node = q.popleft()
    print(node.val)

    if node.left:
      q.append(node.left)

    if node.right:
      q.append(node.right)

One more good reason to use deque is that deque can handle a large data set with constant insertion. As we know from the Reallocation, deque only allocates a new map; it doesn't copy the actual elements when reallocation happens.

Now, when and why you should not use deque. Deque has a large initial cost due to its internal implementation. So, if you have a small dataset and you really need to preserve memory, deque might be not a good option.

A niche aspect of considering not use deque is the contiguity of the storage. This refers to spatial locality. In a nutshell, a spatial locality means that your CPU grabs the element and its neighbors and store those in a cache with super fast access time. This requires the storage to be contiguous (like vector and array).

Whereas, deque does have a contiguous memory storage. The elements are scattered in memory, which does not utilize the spatial locality that your computer offers.

We can do a small test in C++ to demonstrate this comparison:

#include <chrono>
#include <deque>
#include <iostream>
#include <vector>

#define ONE_MILLION 1e6

// Simple test - assign the range [1..999999] to both vector and deque
// with pre-allocated size.
int main(void) {
  // Avoid timing reallocation
  std::vector<int> v(ONE_MILLION);
  std::deque<int> d(ONE_MILLION);

  using namespace std::chrono;

  steady_clock::time_point begin;
  steady_clock::time_point end;

  begin = steady_clock::now();

  for (size_t i = 0; i < v.size(); ++i)
    v[i] = i;

  end = steady_clock::now();
  std::cout << "Elapsed time (vector): "
            << duration_cast<microseconds>(end - begin).count() << "ms"
            << std::endl;

  begin = steady_clock::now();

  for (size_t i = 0; i < d.size(); ++i)
    d[i] = i;

  end = steady_clock::now();
  std::cout << "Elapsed time (deque):  "
            << duration_cast<microseconds>(end - begin).count() << "ms"
            << std::endl;

  return 0;
}

Elapsed time (vector): 7689 ms
Elapsed time (deque): 62380 ms

You re-run the program multiple times. The elapsed time of vector is still significantly smaller than of deque. This is because vector utilizes the spatial locality better than deque does.

The last thing you should consider not using a deque is when you constantly need to insert in the middle of the container. Due to deque's special traits, inserting/deleting in the middle takes an expensive amount of time to accomplish. It needs to determine which one of the two iterators should perform such a operation, locate the correct position in the node and do the shifting.

#Conclusion

Deque is a greate container and it can solve many problems efficiently. People often compare it with its sister, vector, and cause some questions whether you should use deque over vector. This article will give you some ideas about the advantages of using deque, and the internal implementation to explain those advantages.

A good way to start from here is to implement a simplified version of the deque container. You would realize how complicate deque is.

Feel free to discuss the article on Twitter.