STL - Sequence Containers & Adaptors

Tags: cpp stl

Sequence Containers

array - Static arrays
vector - Dynamic arrays
forward_list - Singly linked-list
list - Doubly linked-list
deque - Double-ended queue

Common member functions in sequential containers:

.begin() - Returns an iterator pointing to the start of the container
.end() - Returns an iterator pointing to the address next to the last element in the container
.empty() - Returns whether the container is empty
.clear() - Clear all contents present inside the container
.size() - Returns number of items present inside the container (absent in forward_list)
.max_size() - Returns theoretical maximum number of elements that the container can hold
.swap(other) - Swap content of current container with similar other container
.resize(n), resize(n,val) - Resize container to contain n elements. Can also pass default value val to set newly created elements as

Note: The *emplace* member functions perform insertions a bit faster than *push* or *insert* functions as they construct the new element in-place (instead of creating and then copying them)

Adaptors for Sequence Containers

They provide a wrapper interface for Sequential containers

stack - provides Stack (LIFO)
queue - provides Queue (FIFO)
priority_queue - provides Heap (Max-Heap by default)

Singly Linked-List

Declaration: forward_list<Type> ll;
Supports O(1) insertion/deletion if location specified (only links updated)
Operations at the start are O(1) and O(N) elsewhere.
Random access NOT present. Only the start (i.e. head) accessible
Uni-directional access to only forward adjacent element: next(pos)
CPP Reference: forward_list

Element Access:

.front() - Access first element in the list

Iterators:

.before_begin()

Returns an iterator pointing to a placeholder element before the first element in the list
Trying to access it results in undefined behaviour
Generally used with: .insert_after() , .emplace_after() , .erase_after() etc.
Incrementing this iterator gives .begin()

Note: The list goes in only one direction i.e. forward. So, we can only do itr++ , but NOT itr-- (where itr is an iterator pointing to some element in the list)

Capacity: Note that .size() function is NOT provided

Modifiers:

.pop_front() - Remove first element from the list
.push_front(item) , .emplace_front(item) - Insert element item at start of the list
.insert_after(): Insertion takes O(1) per entry in these operations
- .insert_after(pos,val) - Insert element item after the position pos
- .insert_after(pos,count,item) - Insert count copies of item after position pos
- .insert(pos,start,end) - Insert all elements within [start,end) after position pos
.emplace_after(pos,...args) - Construct element in-place after position pos

forward_list demo

void printList(forward_list<int> &ll) {
  for (auto &num : ll) {
    cout << num << " -> ";
  }
  cout << "X" << endl;
}

int main() {
  forward_list<int> ll{7, 1, 3, 5};
  printList(ll);
  // 7 -> 1 -> 3 -> 5 -> X

  cout << "First element: " << ll.front() << endl;
  // First element: 7

  ll.push_front(10), ll.push_front(20);
  printList(ll);
  // 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> X

  ll.emplace_front(11), ll.emplace_front(22);
  printList(ll);
  // 22 -> 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> X

  ll.pop_front();
  printList(ll);
  // 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> X

  // same as ll.push_front(420)
  ll.insert_after(ll.before_begin(), 420);
  printList(ll);
  // 420 -> 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> X

  ll.insert_after(ll.begin(), 111);
  printList(ll);
  // 420 -> 111 -> 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> X

  // Inserting at end of list: O(N) time
  // Step 1: Finding location of last element
  auto itr = ll.before_begin(); // handles empty list case
  while (next(itr) != ll.end()) {
    itr++;
  }
  cout << "Last element: " << *itr << endl;
  // Last element: 5
  // Step 2: Insert after the last element
  ll.insert_after(itr, 999);
  printList(ll);
  // 420 -> 111 -> 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> 999 -> X

  // same as ll.pop_front()
  ll.erase_after(ll.before_begin());
  printList(ll);
  // 111 -> 11 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> 999 -> X

  ll.erase_after(ll.begin());
  printList(ll);
  // 111 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> 999 -> X

  // Deleting from end of list: O(N) time
  // Step 1: Find location of second-last element
  itr = ll.before_begin();
  while (next(next(itr)) != ll.end()) {
    itr++;
  }
  cout << "Second-last element: " << *itr << endl;
  // Step 2: Delete the element after second-last element
  ll.erase_after(itr);
  printList(ll);

  // insert_after(pos, count, val)
  ll.insert_after(ll.before_begin(), 3, 69);
  printList(ll);
  // 69 -> 69 -> 69 -> 111 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> X

  vector<int> v1{-5, -2, -8};
  // insert(pos, start, end)
  ll.insert_after(ll.before_begin(), v1.begin(), v1.end());
  printList(ll);
  // -5 -> -2 -> -8 -> 69 -> 69 -> 69 -> 111 -> 20 -> 10 -> 7 -> 1 -> 3 -> 5 -> X

  ll.clear();
  ll.emplace_front(101);
  ll.emplace_after(ll.begin(), 512);
  printList(ll);
  // 101 -> 512 -> X

  return 0;
}

Doubly-Linked List

Declaration: list<Type> dll;
Supports O(1) insertion/deletion if location specified (only links updated)
Operations at the start and end are O(1), but O(N) elsewhere
Random access NOT present. Only the start and end is accessible
Bidirectional access to both forward & backward adjacent elements: next(pos) , prev(pos)
CPP Reference: list

Element Access:

.front() - Returns reference to first element in the list
.back() - Returns reference to last element in the list

Iterators: .begin() , .end() , .rbegin(), .rend()

Note: The list goes in both directions. So, we can only do itr++ as well as itr-- (where itr is an iterator pointing to some element in the list)

Capacity: .size() function provided

Modifiers:

.push_front(item) , .emplace_front(item) - Insert element item at start of the list
.push_back(item) , .emplace_back(item) - Insert element item at end of the list
.pop_front() - Remove first element from the list
.pop_back() - Remove last element from the list
.insert(): Insertion takes O(1) per entry in these operations
- .insert(pos,item) - Insert element item at position pos
- .insert(pos,count,item) - Insert count copies of item at position pos
- .insert(pos,start,end) - Insert all elements within [start,end) at position pos
.emplace(pos,...args) - Construct element in-place at position pos
.erase(pos) - Removes element at pos position

list demo

void printList(list<int> &dl) {
  cout << "X <-> ";
  for (auto &num : dl) {
    cout << num << " <-> ";
  }
  cout << "X" << endl;
}

int main() {
  list<int> dl{7, 1, 4, 3, 5};
  printList(dl);
  // X <-> 7 <-> 1 <-> 4 <-> 3 <-> 5 <-> X

  cout << "First element: " << dl.front() << endl;
  // First element: 7
  cout << "Last element: " << dl.back() << endl;
  // Last element: 5

  cout << "Reverse: ";
  // Reverse traversal
  for (auto itr = dl.rbegin(); itr != dl.rend(); itr++) {
    cout << *itr << ", ";
  }
  cout << endl;
  // Reverse: 5, 3, 4, 1, 7,

  dl.push_front(10);
  dl.emplace_front(20);
  printList(dl);
  // X <-> 20 <-> 10 <-> 7 <-> 1 <-> 4 <-> 3 <-> 5 <-> X

  dl.push_back(100);
  dl.emplace_back(200);
  printList(dl);
  // X <-> 20 <-> 10 <-> 7 <-> 1 <-> 4 <-> 3 <-> 5 <-> 100 <-> 200 <-> X

  dl.pop_front();
  printList(dl);
  // X <-> 10 <-> 7 <-> 1 <-> 4 <-> 3 <-> 5 <-> 100 <-> 200 <-> X

  dl.pop_back();
  printList(dl);
  // X <-> 10 <-> 7 <-> 1 <-> 4 <-> 3 <-> 5 <-> 100 <-> X

  auto thirdPosition = next(next(dl.begin()));
  dl.insert(thirdPosition, 55);
  printList(dl);
  // X <-> 10 <-> 7 <-> 55 <-> 1 <-> 4 <-> 3 <-> 5 <-> 100 <-> X

  auto secondLastPosition = prev(prev(dl.end()));
  dl.insert(secondLastPosition, 77);
  printList(dl);
  // X <-> 10 <-> 7 <-> 55 <-> 1 <-> 4 <-> 3 <-> 77 <-> 5 <-> 100 <-> X

  // insert(pos,count,val)
  dl.insert(dl.begin(), 3, -8);
  printList(dl);
  // X <-> -8 <-> -8 <-> -8 <-> 10 <-> 7 <-> 55 <-> 1 <-> 4 <-> 3 <-> 77 <-> 5 <-> 100 <-> X

  vector<int> v1{128, 64, 256};
  // insert(pos,start,end)
  dl.insert(dl.begin(), v1.begin(), v1.end());
  printList(dl);
  // X <-> 128 <-> 64 <-> 256 <-> -8 <-> -8 <-> -8 <-> 10 <-> 7 <-> 55 <-> 1 <-> 4 <-> 3 <-> 77 <-> 5 <-> 100 <-> X

  dl.erase(dl.begin());
  // above line same as dl.pop_front();
  printList(dl);
  // X <-> 64 <-> 256 <-> -8 <-> -8 <-> -8 <-> 10 <-> 7 <-> 55 <-> 1 <-> 4 <-> 3 <-> 77 <-> 5 <-> 100 <-> X

  return 0;
}

Double-ended Queue

Declaration: deque<Type> dq;
Operations at the start and end are O(1), but O(N) elsewhere
Random access is supported in O(1) time
How is deque different from vector ?
- Unlike vector, the elements are not stored contiguously
- Indexed access to deque must perform two pointer dereferences, compared to only one in indexed access of vector
- Expansion is cheaper than expansion of vector because it does not involve copying existing elements to new memory location
See this answer for difference between deque and list
Most implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping. They can also expand/contract as needed on both the ends. They also have a large minimal memory cost for allocating the individual arrays
CPP Reference: deque

Element Access:

.at(idx) - Access element at idx index, with bounds-checking
[idx] - Access element at idx index
.front() - Access first element
.back() - Access last element

Iterators: .begin() , .end() , .rbegin(), .rend()

Capacity: .size() provided, .shrink_to_fit() (free ununsed space)

Modifiers:

.push_front(item) , .emplace_front(item) - Insert element item at start of the list
.push_back(item) , .emplace_back(item) - Insert element item at end of the list
.pop_front() - Remove first element from the list
.pop_back() - Remove last element from the list
.insert(): Insertion element(s) at given postition
- .insert(pos,item) - Insert element item at position pos
- .insert(pos,count,item) - Insert count copies of item at position pos
- .insert(pos,start,end) - Insert all elements within [start,end) at position pos
.emplace(pos,...items) - Construct element in-place at position pos

Stack

The stack adaptor provides a Stack data structure wrapper to the container, which has the property of Last-in First-out i.e. LIFO (also called first-in last-out)
Supports operations ONLY at the top of Stack, which take O(1) time each

It’s defined as:

template<
    class T,
    class Container = deque<T>
> class stack;

Declaration: stack<Type> stk;
CPP Reference: stack

Element Access: .top() returns reference to first i.e. top-most element

Capacity: .size() , .empty()

Iterators: NONE provided

Modifiers:

.pop() - Remove element present at the top
.push(val) - Insert element at the top
.emplace(...args) - Construct element in-place at the top

Queue

The queue adaptor provides a Queue data structure wrapper to the container, which has the property of First-in First-out i.e. FIFO (also called last-in last-out)
Insertion occurs at the back and Deletion at the front, both taking O(1) time

It’s defined as:

template<
  class T,
  class Container = deque<T>
> class queue;

Declaration: queue<Type> q;
CPP Reference: queue

Element Access:

.front() - returns reference to first i.e. starting element
.back() - returns reference to last i.e. ending element

Capacity: .size() , .empty()

Iterators: NONE provided

Modifiers:

.pop() - Remove the first i.e. starting element
.push(val) - Insert element at the end
.emplace(...args) - Construct element in-place at the end

Heap

The priority_queue adaptor provides a Heap data structure wrapper to the container
Fast lookup of highest-priority element in O(1) time
Insertion/Deletions take upto O(logN) time

It’s defined as:

template<
  class T,
  class Container = vector<T>,
  class Compare = less<typename Container::value_type>
> class priority_queue;

The default ordering is to keep the lexicographically larger element at the top i.e. a Max-heap, but you can also provide a custom Compare function to determine the ordering
CPP Reference: priority_queue
Declaration:
- Max-heap: priority_queue< int > maxHp;
- Min-heap: priority_queue< int, vector<int>, greater<int> > minHp;

Element Access: .top() returns reference to the highest priority element (stored topmost at the root of Heap tree)

Capacity: .size() , .empty()

Iterators: NONE provided

Modifiers:

.pop() - Remove the topmost element from the heap
.push(val) - Insert element into the heap
.emplace(...args) - Construct element in-place and insert into the heap

Note: After each insertion/deletion, to maintain the sorted Heap property, the elements are re-organized internally by the adaptor itself.

Also refer: is_heap() , make_heap(), push_heap() , pop_heap() , sort_heap()

Can also use keyboard characters ← , → , ↔ as arrows in display functions