As I work through a bunch of algorithm problems in C++, I thought it would be useful to create a summary of the collection classes built into the standard library.

Common features

In general, most collections support:

Getting the number of elements in the collection with size().
Iteration with begin() and end().
Checking if the collection is empty with empty().

Overview

std::array	std::vector	std::deque
std::forward_list	std::list	std::set
std::unordered_set	std::multiset	std::unordered_multiset
std::map	std::unordered_map	std::stack
std::queue	std::priority_queue

std::array

A fixed size array with all elements of the same type. \(O(1)\) to access an element.

#include <iostream>
#include <array>

int main() {
    std::array<int, 5> a = {1, 2, 3, 4, 5};
    for (auto i : a) {
        std::cout << i << std::endl;
    }
    
    // not range checked
    std::cout << a[4] << std::endl;
    
    // range checked
    std::cout << a.at(4) << std::endl;
}

std::vector

A variable sized array. \(O(1)\) to access an element, and \(O(1)\) amortized for adding an element at the end.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    a.push_back(10);
    
    for (auto i : a) {
        std::cout << i << std::endl;
    }
    
    a.clear();
    std::cout << a.size() << std::endl;
}

std::deque

An indexed sequence container that allows fast deletion and insertion at the beginning and end of the sequence.

\(O(1)\) to access an element.
\(O(1)\) to insert or remove an element at the start or end of the array.
\(O(n)\) to insert or remove elements at other locations.

#include <iostream>
#include <deque>

int main() {
    std::deque<int> a = {1, 2, 3, 4, 5};
    a.push_back(6);
    a.push_front(12);
    
    for (auto i : a) {
        std::cout << i << std::endl;
    }
    
    std::cout << a[2] << std::endl;
    
    a.clear();
    std::cout << a.size() << std::endl;
}

std::forward_list

A singly-linked list.

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> list;
    
    auto next = list.insert_after(list.before_begin(), 10);
    next = list.insert_after(next, 12);
    list.push_front(20);
    
    for (auto i : list) {
        std::cout << i << std::endl;
    }
}

std::list

A doubly-linked list.

#include <iostream>
#include <list>

int main() {
    std::list<int> list;
    
    auto next = list.insert(list.begin(), 10);
    next = list.insert(next, 12);
    list.push_front(20);
    
    for (auto i : list) {
        std::cout << i << std::endl;
    }
}

std::set and std::unordered_set

A set of unique elements. set is \(O(\log{n})\) for insertion, removal and search and provides elements in sorted order, whereas unordered_set is \(O(1)\) and uses hashing to store elements.

#include <iostream>
#include <set>
#include <unordered_set>

int main() {
    std::set<int> s = { 2, 7, 3, 1, 6 };
    std::unordered_set<int> u = { 2, 7, 3, 1, 6 };
    
    // returns 1 2 3 6 7
    for (auto i : s) {
        std::cout << i << std::endl;
    }
    // returns 6 1 3 7 2
    for (auto i : u) {
        std::cout << i << std::endl;
    }
    
    bool contains_8 = s.find(8) == s.end();
}

std::multiset and std::unordered_multiset

A set of elements that supports adding duplicate elements. multiset is \(O(\log{n})\) for insertion, removal and search and provides elements in sorted order, whereas unordered_multiset is \(O(1)\) and uses hashing to store elements.

#include <iostream>
#include <set>
#include <unordered_set>

int main() {
    std::multiset<int> s = { 2, 7, 3, 1, 2, 6, 2 };
    std::unordered_multiset<int> u = { 2, 7, 3, 1, 2, 6, 2 };
    
    // returns 1 2 2 2 3 6 7
    for (auto i : s) {
        std::cout << i << std::endl;
    }
    // returns 6 1 3 7 2 2 2
    for (auto i : u) {
        std::cout << i << std::endl;
    }
    
    const auto pair = s.equal_range(2);
    const int count = std::distance(pair.first, pair.second);
    // Item count: 3
    std::cout << "Item count: " << count << std::endl;
}

std::map and std::unordered_map

Associative containers that hold key-value pairs. map is \(O(\log{n})\) for insertion, removal and search and provides elements in sorted order, whereas unordered_map has \(O(1)\) and uses hashing to store keys.

#include <iostream>
#include <map>
#include <unordered_map>

template<typename Key, typename Value>
void print_pair(const std::pair<Key, Value>& pair) {
    std::cout << "(" << pair.first << ", " << pair.second
        << ")" << std::endl;
}

int main() {
    std::map<std::string, int> m = {
        { "d", 10 }, { "a", 25 }, { "c", 13 }
    };
    std::unordered_map<std::string, int> u = {
        { "d", 10 }, { "a", 25 }, { "c", 13 }
    };
    
    // (a, 25) (c, 13) (d, 10)
    for (auto pair : m) {
        print_pair(pair);
    }
    // (c, 13) (a, 25) (d, 10)
    for (auto pair : u) {
        print_pair(pair);
    }
    
    // 13
    std::cout << m["c"] << std::endl;
}

As with set, there also exists multimap and unordered_multimap which allow multiple keys with the same value.

std::stack

A container wrapper that provides stack (LIFO) functionality.

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    
    s.push(10);
    s.push(12);
    s.push(6);
    
    // 6
    std::cout << s.top() << std::endl;
    
    s.pop();
    // 12
    std::cout << s.top() << std::endl;
}

std::queue

A container wrapper that provides queue (FIFO) functionality.

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;
    
    q.push(10);
    q.push(12);
    q.push(6);
    
    // 6
    std::cout << q.front() << std::endl;
    
    q.pop();
    // 12
    std::cout << q.front() << std::endl;
}

std::priority_queue

Heap data structure that provides \(O(1)\) lookup of the largest (by default) element, but \(O(\log{n})\) insertion and removal.

#include <iostream>
#include <queue>

int main() {
    std::vector<int> elements = { 5, 1, 54, 100 };
    std::priority_queue<int> max_heap(elements.begin(), elements.end());
    
    // 100
    std::cout << max_heap.top() << std::endl;
    
    using min_priority = std::priority_queue<int, std::vector<int>, std::greater<int>>;
    min_priority min_heap(elements.begin(), elements.end());
    
    // 1
    std::cout << min_heap.top() << std::endl;
}

C++ collection classes: a summary

Categories