Standard Template Library

The C++ Standard Template Library conveniently implements many templated standard classes and algorithms for us. The containers library contains several data structures.

Why even use these? Implementing these structures is one thing, but optimising them for performance is another. There’s an enormous amount of research in C++ data structures alone (especially in hash maps)¹ that make them much more performance efficient compared to structures we implement.

for (auto& item: : numbers) is equivalent to for i in list in Python; this allows us to loop over an entire STL container.

Generally: if we want to check if something exists with find(search-val), we can check if it’s at end().

Included structures

• Vector (C++) — std::vector
• Sets — std::set
• Linked list
  • std::list implements a doubly linked list.
  • std::forward_list implements a singly linked list.
• Array — std::array
• Dictionary — std::map<type1, type2>
  • Implemented as a red-black tree; guaranteed $O(\log n)$ for find, insert, and erase.
• Hash table — std::unordered_map<type1, type2>
• Stack — std::queue
• Queue — std::queue
  • Priority queues — std::priority_queue
  • Deque — std::deque
• Thread, for multithreading

Resources

• CPlusPlus.com documentation
• cppreference.com documentation
• Problem Solving with C++ by Walter Savitch, chapter 18

Footnotes

1. This blog post on hash map benchmarking is pretty cool. ↩