---
# System prepended metadata

title: Data Structures to Know (C++)

---


# Data Structures to Know (C++)

Remember:

- _Containers_ - hold things, stack, lists, maps, etc.
- _Iterators_ - connect algorithms to containers
- _Algorithms_ - do things, such as min, sort, transform, etc.
- _Rule of Zero_ - If a Data Structure defines something, and you have it as a member of another class (and you aren't working with pointers), leave all construction as default. 
  - This is far more efficient with the compiler, reduces chances of error, and is *good convention*.

# Containers

- Hold collections of objects, and usually implemented via templated arrays or linkedlists.
- **Two Kinds**:

  - Sequence Containers (ordered collections)
    - Array (C-array wrapper)
    - Vector (dynamic arraylist, push/pop_back)
    - list (doubly linked), forward_list (singly linked)
    - Deque (push/pop from front/back)
  - Associative Containers (sorted collections/hashmap access)
    - set, multiset
    - map, multimap
    - unordered map and set

- These can either be random-access, key-value, or linked. Essentially, non-random-access containers cannot be accessed directly by looking for a position or index.
- Examples of these include:
  - `set, map multiset, multimap` (and all their `unordered_` variants)
  - stack, queue, priority queue (built with multiple implementations, some including random-access containers, with that capability removed)
  - list, forward_list --> linked together

## std::string

- Standard String is a container that holds types of `const char*`, allowing you to abstract away the complexities of the C-string.

## std::vector

- Vector is a _random access_ container, that gives you the ability to access elements at any location.
- Access and Modification for `vector<T>`:
  - `at(int pos)` - get element with bounds check
  - `[]` - get element without bounds check
  - `front()` - get first element
  - `back()` - get last element
  - `begin()` - get iterator to first element
  - `end()` - get iterator just past last element
    - both of these can be prefaced with `r` (reverse) or `c` (const) or both
  - `empty()` - is empty or not
  - `size()` - get length
  - `clear()` - clear contents
  - `insert(iter, value)` - insert value at iter position
  - `push_back()` - add element to end
  - `pop_back()` - remove element from end

## std::set

- Sets are hash-tabled automatically-sorted containers that can't be accessed by direct index., with unique elements.
- Access and Modification for `std::set<T>`
  - `insert(value)` - add value to set
  - `insert({...values})` - add values to set
  - `erase(iterator)` - removes the value found at iterator
  - `find(value)` - returns an iterator to the pos of value
  - `count(value)` - 1 if value in set, 0 otherwise
  - `size()` - length of set
  - `empty()` - check if set is clear
  - `clear()` - clear the set

## std::map

- Map is a key-value `std::pair` set, which lets you treat it like a python dictionary.
- Access and Modification for `std::map<K, V>`:
  - `insert({key, value})` - insert key-value pair
  - `erase(key)` - delete key-value pair denoted by `key`
  - `find(key)` - return iterator to position of key, or `map->end()` if not
  - `operator[key]` - return value at `key`
  - `size(), empty(), clear()`

  
