STL Data Structures

Learn about basic STL data structures

Vector

A vector is a dynamic array. It works like a normal array, but it can grow and shrink automatically.

Basic operations:

• Declare: vector<int> v or vector<int> v(n) or vector<int> v(n, value)
• Size: v.size()
• Access: v[i]
• Add to end: v.push_back(x)
• Remove last: v.pop_back()
• Last element: v.back()
• Check if empty: v.empty()
• Clear all: v.clear()

Example: reading $n$ numbers and printing them in reverse:

Queue

A queue is a First In First Out (FIFO) structure. The first element added is the first element removed, like a line of people.

Basic operations:

• Declare: queue<int> q
• Add element to the end: q.push(x)
• Remove element from the front: q.pop()
• Access front element: q.front()
• Access last element: q.back()
• Check if empty: q.empty()
• Size: q.size()

Example: process tasks in the order they arrive.

Deque

A deque (double ended queue) allows pushing and popping from both front and back in $O(1)$ time. It combines some features of both queue and vector.

Basic operations:

• Declare: deque<int> d
• Add to front: d.push_front(x)
• Add to back: d.push_back(x)
• Remove from front: d.pop_front()
• Remove from back: d.pop_back()