Vector and Deque
=============================================

Vectors are the go-to choice when you need a sequence of elements whose size might change during your program's execution.  Here's what makes them special:

- Contiguous Storage:  A vector stores its elements in a single, continuous block of memory. This provides lightning-fast random access to elements using their index. Think of it like a neatly organized bookshelf where you can instantly locate any book by its position.

- Growth and Shrinkage: Vectors automatically expand or shrink as you add (push_back) or remove (pop_back) elements. This dynamic nature eliminates the need to manually pre-allocate or resize arrays.

- Efficiency at the End: Adding or removing elements from the end of a vector is extremely fast, usually taking constant time :math:`O(1)`.

Many data structure and algorithms can be implemented with vector. The related algorithms include **sorting**, **binary search**, **two pointers**. There are non-sequential data structures flattened as vectors, like **disjoint set** (union find), **heap tree**, **segment tree**, **binary index tree**, **flat map**, **flat interval tree** etc.


.. note::

    - **Array Replacement**: If you need an array-like structure that can grow and shrink, vectors are an ideal replacement for traditional C-style arrays.
    - **Fast Back-End Operations**: When you frequently add or remove elements from the back of your sequence, vectors excel.

----

Deques (pronounced "decks") are double-ended queues. You can efficiently insert and remove elements from **both the front and the back**, offering more flexibility than traditional stacks or queues. It is normally implemented by vector under the hood [#]_.

Adaptable Structure: Internally, a deque may be represented as multiple smaller chunks of memory. This gives it flexibility but makes random access by index slightly slower than vectors.

Front and Back Agility:  The defining feature of deques is their efficiency in adding (push_front, push_back) and removing (pop_front, pop_back) elements from either end. These operations maintain constant time complexity :math:`O(1)`.

.. note::

    - **Queues and Stacks**: Deques are the natural choice when implementing queues (first-in, first-out) or stacks (last-in, first-out) in your program.
    - **Flexibility Needed**: If you need to frequently manipulate **both the beginning and end** of your sequence, deques offer an advantage over vectors.

.. rubric:: Footnotes

.. [#] Deque is typically implemented as a vector of arrays (a linked-list of arrays can't give constant time random access). The size of the arrays is implementation dependent, commonly a constant size in bytes (4096 for libc++, 512 for libstdc++, 16 for MS STL).

In the following sections, we will discussion some algorithms related to vector and deque.

.. toctree::
   :maxdepth: 3

   sorting
   two_pointers
   cumsum
   sliding_window
   meeting_room
   interval
   questions