containers

Reimplementation of Standard Template Library's containers.

Contents

• Installation
• Introduction to STL
  • Containers
    • Sequence Containers
    • Associative Containers
    • Unordered Associative Containers
    • Container Adaptors
  • Algorithms
• Red-Black Tree
• Iterators
  • What is it?
  • Types
    • Input/Output
    • Forward
    • Bidirectional
    • Random Access
    • Contiguous
• Sequence Containers
  • Vector
  • Deque
  • List
    • Forward list
  • Array
• Associative Containers
  • Balanced Binary Search Trees
  • Red Black Tree Implementation
  • Set
  • Map
  • Multiset
  • Multimap
• Unordered Associative Containers
  • Hash tables
  • Unordered set
  • Unordered map
  • Unordered multiset
  • Unordered multimap
• Container Adaptors
  • Stack
  • Queue
  • Priority queue

Installation

Install and run tests:

git clone https://github.com/georghegel/containers.git && cd containers
make test

Check for memory leaks:

make leaks

Usage:

#include "containers.h"

int main(){
    
    s21::set a = {1,2,3,4,5};   // creates the set (1,2,3,4,5)
    a.insert(6);                // adds 6 to it (1,2,3,4,5,6)
    a.erase(5);                 // removes 5 from the set (1,2,3,4,6)
    a.insert(6);                // does nothing because we already have 6 (1,2,3,4,6)
    size_t sz = a.size();       // returns set's size: 5
    auto bg = a.begin();        // returns begin iterator
    auto it = a.find(3);        // returns an iterator to the found element, otherwise nullptr
}

Introduction to STL

Containers

The Standard Template Library (STL) in C++ provides a variety of containers, each designed to handle different types of data storage and access patterns efficiently. Here is a list of the main STL containers along with a brief description of each:

As of 07.07.2024 I've only implemented set and map. Will implement other ones in the future

Sequence Containers

1. std::vector
2. std::deque
3. std::list
4. std::forward_list
5. std::array

Associative Containers

1. std::set
2. std::multiset
3. std::map
4. std::multimap

Unordered Associative Containers

1. std::unordered_set
2. std::unordered_multiset
3. std::unordered_map
4. std::unordered_multimap

Container Adaptors

1. std::stack
2. std::queue
3. std::priority_queue

Algorithms

Red-Black Tree

Under the set and the map containers we have data structure that will contain our data. For computational efficiency both of these containers have Red-Black Tree as a data structure.
In worst case for insertion and deletion we have: $$\color{black}O(\log(n))$$

By Cormen et al. book we have next properties of the RBT:

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either $${\color{red}RED}$$ or $${\color{black}BLACK}$$
By constraining the way nodes can be colored on any path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.
Each node of the tree now contains the fields color, key, left, right, and p. If a child or the parent of a node
does not exist, the corresponding pointer field of the node contains the value NIL.
We shall regard these NIL'S as being pointers to external nodes (leaves) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree.
A binary search tree is a red-black tree if it satisfies the following red-black properties:

1. Every node is either red or black.
2. Every leaf (NIL) is black.
3. If a node is red, then both its children are black.
4. Every simple path from a node to a descendant leaf contains the same number of black nodes

For the full understanding:

1. Wikipedia
2. Cormen et al.

Iterators

We will not invent the wheel and will define iterators as it defined in a C++ Standard:

1.
Iterators are a generalization of pointers that allow a C++ program to work with different data structures
(for example, containers and ranges) in a uniform manner. To be able to construct template algorithms
that work correctly and efficiently on different types of data structures, the library formalizes not just the
interfaces but also the semantics and complexity assumptions of iterators. An input iterator i supports the
expression *i, resulting in a value of some object type T, called the value type of the iterator. An output
iterator i has a non-empty set of types that are indirectly_writable to the iterator; for each such type T,
the expression *i = o is valid where o is a value of type T. For every iterator type X, there is a corresponding
signed integer-like type (23.3.4.4) called the difference type of the iterator.
        
2.
Since iterators are an abstraction of pointers, their semantics are a generalization of most of the semantics of
pointers in C++. This ensures that every function template that takes iterators works as well with regular
pointers. This document defines six categories of iterators, according to the operations defined on them: input
iterators, output iterators, forward iterators, bidirectional iterators, random access iterators, and contiguous
iterators, as shown in Table 83.

Table 83: Relations among iterator categories [tab:iterators.relations]

Types

Each higher level iterator contains all properties of the previous levels.
For example, Bidirectional iterator has the properties of the Forward, which has all properties of the I/O.

Picture should make it clear:

Input/Output

The input_iterator concept defines requirements for a type whose referenced values can be read (from the requirement for indirectly_readable (23.3.4.2)) and which can be both pre- and post-incremented.

Means that we can iterate over ++a and a++ operators.
And also can read the values by "*" operator.

The output_iterator concept defines requirements for a type that can be used to write values (from the requirement for indirectly_writable (23.3.4.3)) and which can be both pre- and post-incremented.

Same as above + we can write in it.

Forward

The forward_iterator concept adds copyability, equality comparison, and the multi-pass guarantee.

Added equality comparison (multi-pass guarantee I haven't researched yet)

Use cases: forward_list

Bidirectional

The bidirectional_iterator concept adds the ability to move an iterator backward as well as forward.

Added: --a and a--

Use cases: set, map, multiset, multimap, list, queue

Random Access

The random_access_iterator concept adds support for constant-time advancement with +=, +, -=, and -, as well as the computation of distance in constant time with -. Random access iterators also support array notation via subscripting.

New properties and operations are given below:

template<class I>
    concept random_access_iterator =
        bidirectional_iterator<I> &&
        derived_from<ITER_CONCEPT(I), random_access_iterator_tag> &&
        totally_ordered<I> &&
        sized_sentinel_for<I, I> &&
        requires(I i, const I j, const iter_difference_t<I> n) {
            { i += n } -> same_as<I&>;
            { j + n } -> same_as<I>;
            { n + j } -> same_as<I>;
            { i -= n } -> same_as<I&>;
            { j - n } -> same_as<I>;
            { j[n] } -> same_as<iter_reference_t<I>>;
        };

Use cases: vector, deque

Contiguous

The contiguous_iterator concept provides a guarantee that the denoted elements are stored contiguously in memory.

Haven't learned yet

Use cases: array

Sequence Containers Detailed

Vector

Deque

List

Forward list

Array

Associative Containers Detailed

Balanced Binary Search Trees

Red Black Tree Implementation

Set

Map

Multiset

Multimap

Unordered Associative Containers Detailed

Hash Tables

Unordered set

Unordered map

Unordered multiset

Unordered multimap

Container Adaptors Detailed

Stack

Queue

Priority Queue

References

[1] Standard Template Library
[2] Algorithms
[3] Iterators
[4] Red Black Tree
[5] C++ Standard