STL Containers – Deep Dive

on

 

Vector, Pair, List, Stack, Queue & Deque

In the previous blog, we introduced the C++ Standard Template Library (STL) and understood why it is important for DSA and coding interviews.

Now it’s time to go deeper.

In this article, we will going to explore some of the most commonly used STL containers:

  • Vector (Dynamic Array)
  • Pair
  • List
  • Deque
  • Stack

Understanding when and why to use these containers can significantly improve your problem-solving skills in interviews and competitive programming.

What is a container adaptor?

It is a wrapper over an existing container (like deque by default) that restricts operations to provide specific behavior.

LIKE:

  • stack → uses deque internally

But it can also use:

  • vector
  • list

1. Vector (Dynamic Array) (Link)

The vector is the most commonly used STL container. It is a dynamic array that automatically resizes itself when elements are added or removed. Unlike normal arrays, you don’t need to worry about size limitations. It is homogeneous and allows contiguous memory allocation. You can also create custom data types within a vector as per your requirements, such as: vector<vector<int>>, vector<pair<int,int>>, vector<vector<string>>, etc.

Why use Vector?

  • Fast random access (O(1))
  • Automatically resizes
  • Works smoothly with STL algorithms like sort()
  • Memory efficient and cache friendly
  • Allows indexing

Key Member Function:

  • push_back(value)
  • pop_back()
  • insert(position, value)
  • erase(position)
  • clear()
  • assign()
  • front()
  • back()
  • at(index)
  • size()
  • empty()

Example:




Time Complexity:

  • Access: O(1)
  • Insertion at end: O(1) (amortized)
  • Insertion in middle: O(n)
  • Deletion: O(n)

Application:

  • You need fast access using index.
  • Storing data when you don't know the final count [Dynamic List].
  • Most insertions are at the end.
  • Allows using in-build functions [size(), puch_back(), back(), pop_back() etc.]
  • Allows creating flexible matrices

2. Pair  (Link)

In C++ Pair is a simple container that stores two value together as a [key, value] or [value, value] pair. It is generic means we can use any data type as per the problem requirements.

It is commonly used when:

  • Storing coordinates (x, y)
  • Storing value and index
  • Returning two values from a function
  • Performing operations using 2 params.

How You can create, store and access elements from Pair?

CREATE: pair<datatype, dataType> p;

STORE: p.make_pair(a,b);

ACCESS:

  • p.first → (a)
  • p.second → (b)

Example:



Applications:

Use pair when you need to store two related pieces of information together without creating a separate class or struct.

It is heavily used in sorting problems and graph problems.

3. List (Link)

In C++, a list is a sequence container that implements a doubly linked list, allowing for efficient insertions and deletions anywhere in the sequence. It is part of the Standard Template Library (STL) and is defined in the <list> header file.

Unlike vector, elements are not stored in contiguous memory.

Why use List?

  • Fast insertion anywhere (O(1))
  • Fast deletion anywhere (O(1))
  • No shifting of elements required

Example:




Time Complexity:

  • Access: O(n)
  • Insertion: O(1)
  • Deletion: O(1)

Applications:

  • Frequent insertions and deletions are required
  • You do not need random access using index.

However, in most interview problems, vector is preferred unless specifically required.

4. QUEUE (Link)

A queue in C++ is a sequence container that operates on the First-In, First-Out (FIFO) principle, similar to a real-world waiting line. Elements are inserted at one end, the back (or rear), and removed from the other end, the front (or head).

It can grow or shrink in size automatically as elements are added or removed, without you needing to manage memory manually.

Key Member Functions:

  • push()
  • pop()
  • front()
  • back()
  • size()
  • empty()

Time Complexity:

  • Insert: O(1)
  • Delete: O(1)
  • Access: O(1)

Example:



Applications:

  • CPU scheduling and disk scheduling in operating systems.
  • Handling interrupts in real-time systems.
  • Breadth-First Search (BFS) algorithm in graphs and trees.
  • Printer spooling, where print jobs are processed in the order they are received.

5. Deque (Double Ended Queue) (Link) 

A deque (double-ended queue) in C++ is a dynamic sequence container that allows efficient insertion and deletion of elements at both the front and back ends, unlike a standard queue or vector. It is part of the C++ Standard Template Library (STL) and can also provide constant time access to elements by index.

You can think of it as a combination of vector and queue.

Key Member Functions:

Element Access:

  • push_back(value)
  • push_front(value)
  • pop_back()
  • pop_front()
  • insert(position, value)
  • erase()
  • front(), back(), size(), empty()

Iterator: begin(), end(), rbegin(), rend()


Example:



Time Complexity:

  • Access: O(1)
  • Insertion at front/back: O(1)
  • Insertion in middle: O(n)

Applicatins:

  • You need efficient operations at both front and back.
  • Problems like sliding window maximum.
  • Implementing Task Scheduling algorithms.
  • Used in 'Undo' and 'Redo' operations & Web Browser History.

6. Stack (Link)

In the C++ Standard Template Library (STL), a stack is a container adaptor that follows the LIFO (Last In, First Out) principle, meaning the last element added is the first one removed—much like a stack of plates. It is a generic data structure, allowing it to store any data type or custom structure depending on your requirements; for example, you can store pairs of integers using std::stack<std::pair<char, int>> stk;

Key Member Function:

  • push(x) => Insert element at the top
  • pop() => Remove top element
  • top() => Access top element
  • empty() => Check if the stack is empty
  • size() => Get the stack size

Example:


Time Complexity:

  • Insertion: O(1) Time
  • Deletion: O(1) Time
  • View Top Element: O(1) Time
  • Get Size: O(n)
  • Empty: O(1)

Application:

  • Backbone of recursion, backtracking, and many graph algorithm problems.
  • Used for navigation or revisiting previously visited pages.
  • Used to evaluate mathematical expressions.

QUICK RECAP

Time Complexity Comparison

  • Vector → Fast access, slow middle insertion
  • List → Slow access, fast insertion and deletion
  • Deque → Fast front and back operations
  • Pair → Used for storing two values together
  • Stack → Allows performing operations in constant time (fast read, write, and access).
  • Queue → Insertion and deletion take constant time.

When to Use Which Container?

  • Use Vector when fast index access is needed.
  • Use List when frequent insertions/deletions are required.
  • Use Deque when operations are needed from both ends.
  • Use Pair when storing two related values together.
  • Use Stack when the application requires LIFO format.
  • Use Queue when the application requires FIFO format.

Choosing the correct container depends entirely on the problem requirements.

Conclusion

STL containers reduce implementation complexity and allow you to focus more on logic rather than low-level data structure implementation.

Mastering vector, pair, list, stack, queue and deque will make your DSA journey smoother and more efficient.

In the next part, we will explore associative containers like set, unordered_set, multiset, map, unordered_map, and understand their real-world DSA applications.

   Article Contributor: Arijit Chowdhury

Location: Barasat, Kolkata, West Bengal, India

Comments

Post a Comment