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)1 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
andstd::unordered_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 for find, insert, and erase.
- Hash table —
std::map<T1, T2>
andstd::unordered_map<type1, type2>
- Stack —
std::queue
- Queue —
std::queue
- Priority queues —
std::priority_queue
- Deque —
std::deque
- Priority queues —
- Thread, for multithreading
Resources
- CPlusPlus.com documentation
- cppreference.com documentation
- Problem Solving with C++ by Walter Savitch, chapter 18