Home

C++ Data Structures, Iterators, and Algorithms

Data Structures

Operation Speed
Reading Fast
Inserting Slow
Appending Fast
Getting size Done at compiler time
Data Type Stack/Heap Fast reading/writing Fast inserting/removal
Array Stack Fast Slow
Vector Heap Fast Slow
Linked List Heap Slow Fast

array

std::array<type, size> is used to store a block of continuous memory. This has advantages over the regular C style arrays because it supports iterators, error handing for reading/writing out of bounds, and allows you to easily get the size(size is calculated at compile time).

vector

std::vector<type> is an array that can grow in size. First a fixed size array is stored in the heap. If an insert would overflow the array, a new larger fixed size array is created else where in the heap, and all the contents of the smaller array are moved to the larger array.

Method Description
.at(size_type n) Get reference to element at n index
.size() Get how many elements are in the vector
.empty() Checks if the vector is empty or not
.clear() Removes all the elements
.push_back(const T& x) Adds new element to end of vector
.erase(iterator pos) Removes element. Higher elements are shifted back to fill gap.
.insert(iterator pos, const T& x) Copies x to element at pos. Higher elements are shifted over.
.begin() Returns an iterator to the first element.
.end() Returns an iterator to one past the last element.

.pop_back() .resize() .reserve() .capacity() - returns the number of elements that the vector can hold before needing to allocate more memory .data() vs &vec[0]?

.begin() vs .front() .end() vs .back()

list

std::list<type> is a doubly linked list stored in the heap.

// Get each element of the linked list
ListNode* currNode = _head;
while (currNode != nullptr) {
	// So something with currNode
	currNode = currNode->nextNode();
}

pair

queue

deque

std::deque<type> is a linked list of arrays. This sort of mixes the advantages and disadvantages of a list and vector.

.push_back .push_front

set

std::set<type> and std::unordered_set<type> are used to store a list of unique elements. Set automatically sorts the elements as they go in, but unordered doesn’t.

.insert() .find()

map

std::map<keyType, valueType> and std::unordered_map<keyType, valueType> are used to store a list of key value pairs.

mp["key"] = value;

template<typename T>
void printElems(const T& v) {
	for (typename T::iterator pos = v.begin(); pos != v.end(); pos++) {
		std::cout << *pos << "\n";
	}
}

Constant iterators

Different types of iterators

back_inserter

If you just had an iterator, and you wen to the next element, but you were at the end of the memory, you couldn’t insert any more. The back_insterter automatically does a push_back to expenand the memeory.

std::back_insert(data structure)

int square(int in) {
	return in * in;
}

std::list<int> list = {1, 2, 3, 4, 5};
std::vector<int> vec; // empty

// Runtime error because transform writes into unavailable data
std::transform(list.begin(), list.end(),
							 vec.begin(),
							 square)

// Doesn't give an error because back insert automatically extends the size of vec
std::transform(list.begin(), list.end(),
							 std::back_insert(vec),
							 square)

Algorithms

#include <algorithms>

Usage Description
sort(v.begin(), v.end()) Sorts a list in O(nlogn). Tends to use introsort algorithm(quicksort + heap sort)
sort(v.begin(), v.end(), func) You can also sort with a function which takes in 2 args and returns the element you want
stable_sort Same as sort, but equivalent elements are guaranteed to keep the same order
binary_search(v.begin(), v.end(), search) O(logn). Returns true if the value is in the sorted list.
binary_search(v.begin(), v.end(), search, func) When list is sorted differently. func can be greater for reverse sorted lists.
lower_bound Like binary_search, but returns the first equal to or the next greatest element
upper_bound Same, but just gives the next greatest element
reverse() O(n) will reverse a list
`reverse  

Sort