Skip to content

C++ Data Structures

Table of Contents

Others

Iterators <iterator>

container.begin() and container.end()

  • container.begin() - returns an iterator pointing to the first element of the container.
  • container.end() - returns an iterator pointing to the past-the-end element of the container. This element acts as a placeholder and does not contain a valid value. It is used to indicate the end of the container when iterating through it.

container.rbegin() and container.rend()

  • container.rbegin() - returns a reverse iterator pointing to the last element of the container (the first element in reverse order).
  • container.rend() - returns a reverse iterator pointing to the past-the-end element of the container in reverse order. This element acts as a placeholder and does not contain a valid value. It is used to indicate the end of the container when iterating through it in reverse.

container.cbegin() and container.cend()

  • container.cbegin() - returns a constant iterator pointing to the first element of the container. It cannot be used to modify the elements it points to.
  • container.cend() - returns a constant iterator pointing to the past-the-end element of the container. It cannot be used to modify the elements it points to. This is used to indicate the end of the container when iterating through it with constant iterators.

std::advance and std::next

  • std::advance(it, n) - advances the existing iterator it by n
  • std::next(it, n) - returns a new iterator that is advanced by n from it, without modifying it itself.

std::prev

  • std::prev(it, n) - returns a new iterator that is moved backward by n from it, without modifying it itself.

std::distance

  • std::distance(first, last) - returns the number of elements between the range defined

Linear Data Structures

container::find

  • std::find(container.begin(), container.end(), value) - returns an iterator to the first occurrence of value in the container, or container.end() if value is not found. This function is part of the <algorithm> header and can be used with any container that supports iterators.
  • std::find_if(container.begin(), container.end(), predicate) - returns an iterator to the first element in the container that satisfies the given predicate, or container.end() if no such element is found. The predicate is a function or function object that takes an element as an argument and returns a boolean value indicating whether the element meets the condition.

Array

  • Fixed-size contiguous memory
  • O(1) access, O(n) insertion/deletion

Vector

  • Dynamic array in STL
  • std::vector<T>

Linked List/List

  • Node-based linear structure
  • std::list<T>, std::forward_list<T>

std::list::splice

  1. list1.splice(pos, list2) - moves all elements from list2 to list1 at the position pos (list 1 iterator).
  2. list1.splice(pos, list2, it) - moves the element pointed to by it from list2 to list1 at the position pos.
  3. list1.splice(pos, list2, first, last) - moves the range of elements from first to last (exclusive) from list2 to list1 at the position pos.

Time complexity: O(1) for all splice operations, as they only involve pointer manipulations without copying elements.

std::list<int> list1 = {1, 2, 3};
list1.splice(next(list1.begin(), 1), list1, list1.end());

this will move the last element in the list 1 (3) to the position after the second element (so the 1 next to the first element, which is 2). the resulting list will be: 1, 3, 2

list<int> l1 = {1, 5, 8};
list<int> l2 = {4, 6};

// Transfer range of elements from l2 to l1
l1.splice(l1.end(), l2, l2.begin(), l2.end());

this will move all elements from list 2 to the end of list 1. the resulting list will be: 1, 5, 8, 4, 6. list 2 will be empty after this operation.

std::list::erase

- list.erase(pos) - removes the element at the position pos (list iterator).

std::list::push_front and std::list::push_back

  • list.push_front(value) - adds an element to the front of the list.
  • list.push_back(value) - adds an element to the back of the list.

std::list::front and std::list::back

  • list.front() - returns a reference to the first element in the list.
  • list.back() - returns a reference to the last element in the list.

std::list::size

  • list.size() - returns the number of elements in the list.
  • Note: std::list does not have random access iterators, so accessing elements by index is not efficient. Use std::advance to move an iterator to a specific position if needed.

std::list::empty

  • list.empty() - returns true if the list is empty, otherwise returns false.

std::list::clear

  • list.clear() - removes all elements from the list, leaving it empty.

Stack

  • LIFO (Last In First Out)
  • std::stack<T>

Queue

  • FIFO (First In First Out)
  • std::queue<T>, std::deque<T>

Tree Data Structures

Binary Search Tree

  • Ordered hierarchical structure
  • std::set<T>, std::map<K,V>

Balanced Trees

  • AVL, Red-Black trees
  • std::multiset<T>, std::multimap<K,V>

Heap

  • Priority-based structure
  • std::priority_queue<T>

Graph Data Structures

Adjacency List

  • Node-edge representation

Adjacency Matrix

  • Matrix representation

Hash-Based Structures

unordered::erase

  • unordered_set.erase(key) - removes the element with the specified key from the unordered set. Returns the number of elements removed (0 or 1).
  • unordered_map.erase(key) - removes the element with the specified key from the unordered map. Returns the number of elements removed (0 or 1).

std::unordered_set<T>

  • Unordered collection of unique elements
  • Implemented as a hash table, provides average O(1) time complexity for insertions, deletions, and lookups.

std::unordered_map<K,V>

unordered_map::find

  • unordered_map.find(key) - returns an iterator to the element with the specified key, or unordered_map.end() if the key is not found. The iterator points to a pair of key and value (std::pair<const K, V>).

unordered_map::insert

  • unordered_map.insert({key, value}) - inserts a key-value pair into the unordered map. If the key already exists, the insertion will fail and the map will remain unchanged. Returns a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a boolean indicating whether the insertion took place.

Hash Multimap

  • std::unordered_multimap<K,V>