Daniel Phillips
by Daniel Phillips

Categories

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;
}