• Part of the C++ ISO Standard
• Heavily influenced by the Standard Template Library (STL)
• Provides
  • Generic container data types
  • Streams
  • Generic algorithms (syntax, semantics and performance)
  • Regular expressions, filesystem interaction, concurrency, ...
• C++ reference

Advantages

• Allows focusing on the project at hand
• Fulfills documented performance requirements
• Available with every common compiler: compiler support
• Continues to grow with every version of C++ (status)

std::array is a container that encapsulates fixed size arrays

template<class T, std::size_t N> struct array;

std::array<int, 3> a1{1, 2, 3};
std::array a2{1, 2, 3};  // requires C++17 or newer

Example: Standard Operations

#include <iterator>
#include <iostream>
#include <algorithm>
#include <array>
int main() {
  std::array<int, 5> a1{4, 2, 3, 1, 5};
  std::array a2{1.5, 2.0, 3.1};  // since C++17: clang++ -std=c++17
  // container operations are supported
  std::cout << "a1 has " << a1.size() << " elements" << std::endl;
  std::sort(a1.begin(), a1.end());
  std::copy(a1.begin(), a1.end(),
            std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  // range-based for loop is supported
  for(const auto& elem: a2)
    std::cout << elem << ' ';
  std::cout << std::endl;
}

Visualize execution

std::vector is a dynamic contiguous array - grows "automatically"

• Random access: constant $O(1)$
• Insertion or removal at the end: amortized constant $O(1)$
• Insertion or removal: linear in the distance to the end $O(n)$

More powerful and easier to use than array

template<class T, class Allocator = std::allocator<T>> class vector;

std::vector<int> v{3, 2, 1};

Example: Pass Vector to Function

#include <iostream>
#include <vector>

void print_vector(const std::vector<int>& v) {  // using a reference avoids copying
  std::cout << "{";
  for (auto it(v.cbegin()); it != v.cend(); ++it) {
    std::cout << *it;
    if (it + 1 != v.cend()) std::cout << ", ";
  }
  std::cout << "}" << std::endl;;
}
int main() {
  std::vector<int> v{7, 5, 16, 8};
  v.push_back(1);  // add element to end of vector
  v.push_back(3);
  print_vector(v);  // the "magic" of references
}

Visualize execution

For example

std::list elements have a pointer to next and previous element

• Random access: linear in the distance from head / tail $O(n)$
• Insertion or removal: constant $O(1)$

Memory is not contiguous

template<class T, class Allocator = std::allocator<T>> class list;

std::list<int> l{12, 99, 37};

Example: Fast Insertion to Middle of List

#include <algorithm>
#include <iostream>
#include <list>
int main() {
    std::list<int> l{7, 5, 16, 8};
    l.push_front(1);  // add to the front: O(1)
    l.push_back(3);  // add to the back: O(1)
    // Find iterator pointing to 8
    auto it = std::find(l.begin(), l.end(), 8);
    if (it != l.end())  // if found
        l.insert(it, 42);  // insert `42` before element `8`
    // Print out the list
    std::cout << "{";
    for (int n : l)
        std::cout << n << ", ";
    std::cout << "}" << std::endl;
}

Visualize execution

Map

std::map is a collection of key-value pairs with unique keys

• Search, removal, and insertion: logarithmic $O(\log n)$

Keys are sorted and maps are usually implemented as red-black trees

template<class Key, class T, class Compare = std::less<Key>,
         class Allocator = std::allocator<std::pair<const Key, T>>> class map;

std::map<std::string, std::string> m{ {"key1": "value1"}, {"key2": "value2"} };

Map

Example: Working with Maps

#include <iostream>
#include <map>
#include <string>

void print_map(const std::map<std::string, int>& m) {
  std::cout << "{";
  for (const auto& [key, value] : m)  // C++17
    std::cout << "\"" << key << "\": " << value << ", ";
//  for (const auto& e : m)  // C++ 11
//      std::cout << e.first << ": " << e.second << "; ";
  std::cout << "}" << std::endl;
}

int main() {
  std::map<std::string, int> m{ {"Henri", 3}, {"Leonie", 6}, {"Marie", 9} };
  print_map(m);
  m["Henri"] = 4;  // update an existing value
  m["Sue"] = 10;  // insert a new value
  print_map(m);
  // using operator[] with non-existent key always performs an insert
  std::cout << m["Louisa"] << std::endl;
  print_map(m);
  m.erase("Louisa");  // remove element
  print_map(m);
  std::cout << "m.size(): " << m.size() << std::endl;
  m.clear();
  std::cout << std::boolalpha << "Is map empty? " << m.empty() << std::endl;
}

std::set is a (sorted) collection of unique elements

• Search, removal, and insertion: logarithmic $O(\log n)$

std::set is useful wherever mathematical sets are useful

template<class Key, class Compare = std::less<Key>,
         class Allocator = std::allocator<Key>> class set;

std::set<int> s {1, 2, 3};

Theory - Intersection

Intersection of two sets $A$ and $B$, denoted by $A\cap B$ is the set containing all elements of $A$ that also belong to $B$

Theory - Union

Union (denoted by $\cup$) of a collection of sets is the set of all elements in the collection

Example: Working with Sets

#include <algorithm>
#include <iostream>
#include <set>

void print_set(std::set<int>& s) {
  std::cout << "{";
  for (auto i : s) std::cout << i << ", ";
  std::cout << "}" << std::endl;
}

int main() {
  std::set<int> s1 {1, 4, 5, 3, 1, 3, 5, 4, 3, 1, 3, 4};  // => {1, 3, 4, 5}
  s1.insert(2);  // insert 2 into the set
  s1.insert(5);  // no element will be inserted
  std::cout << "size: " << s1.size() << std::endl;
  std::set<int> s2 {7, 8, 3, 9, 2, 6};

  std::set<int> intersection;
  // O(n * log(m)) instead of O(n * m)
  std::ranges::set_intersection(s1, s2,
    std::inserter(intersection, intersection.begin()));
  print_set(intersection);

  std::set<int> union_;
  std::ranges::set_union(s1, s2,
    std::inserter(union_, union_.begin()));
  print_set(union_);

  return 0;
}

Standard library containers implement the copy constructor

#include <iostream>
#include <vector>
void print_vector(std::vector<int>& v) {
  for (int elem : v) std::cout << elem << " ";
  std::cout << std::endl;
}
int main() {
  std::vector<int> v1(5);  // create vector {0, 0, 0, 0, 0}
  std::vector<int> v2 = v1;  // this is copy assignment, not a reference
  std::vector<int>& v3 = v1;  // this is a reference
  v1[1] = 7;
  v2[3] = 2;
  v3[2] = 4;
  print_vector(v1);
  print_vector(v2);
  print_vector(v3);
}

std::vector<int> v1(5);  // create vector {0, 0, 0, 0, 0}
std::vector<int> v2 = v1;  // this is copy assignment, not a reference
std::vector<int>& v3 = v1;  // this is a reference
v1[1] = 7;
v2[3] = 2;
v3[2] = 4;

v1: 0 7 4 0 0
v2: 0 0 0 2 0
v3: 0 7 4 0 0