STL

The core reason for my re-implementing the standard containers is the Priority Queue (or namely Max Heap). It combines algorithms and fundamental data structures to create a sophisticated yet highly efficient data structure. My current focus on reinventing these containers has temporarily paused here. Similar containers, like flat_set, are slated for release in C++23. When they become available, I plan to continue this series by attempting to re-implement them. Description A priority queue is a container adapter offering constant time access to the largest (by default) element, albeit at the cost of logarithmic time insertion and extraction....

Description Both std::queue and std::stack are container adaptors that rely on an underlying container to provide specific functionality. For example: std::queue implements a First-In-First-Out (FIFO) flow, making it efficient to remove the front element. It can use std::deque (by default) or std::list as the underlying container. std::stack follows a Last-In-First-Out (LIFO) flow, where the back element needs efficient modification. By default, it uses std::deque but can also be based on std::list or std::vector....

Description The implementation of unordered containers rely on hashing techniques and utilize buckets for storing elements. Each bucket is essentially a vector containing a (singly) linked list. The following steps outline how elements are located, whether for finding, inserting, or erasing: Compute the hash value of the key. Determine the bucket index by taking the remainder of the hash value divided by the bucket size, e.g., index = {hash value} % {bucket size}....

Description Both std::set and std::map are underpinned by red-black trees (RBT). RBTs are self-balancing binary trees, albeit not perfectly balanced. In this structure, it’s ensured that the values (for std::set) or keys (for std::map) adhere to the following condition: node→left < node < node→right. Consequently, the RBT are considered ordered, so std::set and std::map are called ordered containers. RBT are characterized as follows: Property A node is either red or black....

Description STL indeed offers std::list and std::forward_list, which are essentially double-linked list and single-linked list, respectively. std::list provides operations like push_back/front, pop_back/front with a time complexity of O(1), and supports bidirectional iterators. On the other hand, std::forward_list only allows fronting operations with O(1) and insert/erase_after for backing operations, which have a time complexity of O(n); also, it only supports forward iterators. A valuable feature of lists is that they prohibit iterator invalidation compared to some other data structures....

Description std::deque extends the interfaces of std::vector with push_front, pop_front, etc., such that elements can be inserted or removed at the end or beginning at constant time. I’ve hardly ever incorporated std::deque in my own coding projects, and it’s a rarity in other people’s work as well. Code std::deque is essentially a sequence of individually allocated fixed-size arrays. The real challenge lies in the bookkeeping. Four variables are relied on to keep track of data:...

Array is allocated in stack memory Vector is allocated in heap memory. Its capacity is “pre-allocated”. #include <iostream> template<typename T> class Vector { private: T* data_; size_t size_; size_t capacity_; public: Vector(): data_(nullptr), size_(0), capacity_(0) {} Vector(size_t n_): size_(n_), capacity_(n_) { data_ = new T[n_]; } ~Vector() { delete [] data_; }; T& operator[] (size_t index) { return data_[index]; } const T& operator[] (size_t index) const { return data_[index]; } size_t size() const { return size_; } void push_back(const T& value) { if(size_ == capacity_) { capacity_ = size_ == 0?...

In my HPC-oriented programming, my go-to choices are typically limited to arrays and vectors because of their memory efficiency. Linked lists and hash maps, being non-contiguous in memory space, rarely find their way into my toolkit. These containers draw upon many classic algorithmic designs. Lately, as I’ve been revisiting fundamental graph algorithms, I’ve also decided to take on the tasks of re-implementing these containers in a simplified illustration. They are:...