# 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()`