SystemsJune 8, 202630 min read

Reimplementing the C++ STL — The Ultimate Guide

A from-scratch tour of the C++ STL internals: exception safety & RAII, SFINAE, type traits, iterators, allocators, and building vector, stack, and a red-black tree.

chamil (1)

let’s talk about some essential concepts before diving into the actual implementation of containers :

disclaimer: there are some oversimplifications that might alter the meaning of some details please refer to the resources for more deep understanding

1 - exception safety and RAII

so what is exception safety?

before I answer that I should first introduce to you an important concept which is stack unwinding

stack unwinding :

when a function is called, information about that routine gets stacked up on the call stack inside a frame. Each function(subroutine) gets its own frame with whatever information instruction needs the CPU to execute that function.
now when the function finishes its execution, its frame gets destroyed and the CPU executes the next function in a FILO order
When an exception occurs while a function is in progress on the stack, it returns to the call stack by finding the catch block, it just keeps returning through the execution path. resulting in the destruction of the function frame.
if there is any memory allocated before the exception throw, memory leaks will occur
exception
Screen Shot 2022 10 26 at 9.17.17 AM
C++
void f3() {
	int *c = new int[100]; // will be leak
	std::string s = "this is stack... would be destroyed";
	throw "exception!";
}

void f2() { f3() }

void f1() { try { f2() } catch (...) { std::cout << "back to here!\n"; } }

• f1->f2->f3Stacks are stacked in f3->f2->f1order, and stacks are released in order.

RAII (Resource Acquisition Is Initialization)

Resource Acquisition is Initialization is a c++ technique that ensures that the allocated resources will be released

it consists of creating an object that will encapsulate and manage the resource Acquisition/allocation in the constructor. ****and release that resource in the destructor.

- Functors (Function Objects):

C++
struct Add{
	Add(int toAdd) : _toAdd(toAdd) {}
	int operator()(int x){
		return x + _toAdd;
	}
	private:
	int _toAdd;
};

int main(){
	Add add_42(42); // state
	Add add_13(13);
	int result_42 = add_42(2);
	int result_13 = add_13(2);
	std::vector<int> v(10, 10);
	std::transform(v.begin(), v.end(), v.begin(), add_42);
}

Classification of functors

functor vs function

functor vs function pointer

function vs lambda expression (c++11)

Both can be inlined and lambda expression defaults to inline.

2- SFINAE

- SFINAE (Substitution Failure Is Not An Error)

before we define what SFINAE really is, let's first see how the compiler chooses the right function overload to call.

in c++, the compiler goes through a process in order for it to find the right function overload.

these steps are:

4 • template argument substitution

Specifically, when creating a candidate set for overload resolution, some (or all) candidates of that set may be the result of instantiated templates with (potentially deduced) template arguments substituted for the corresponding template parameters. If an error occurs during the substitution of a set of arguments for any given template, the compiler removes the potential overload from the candidate set instead of stopping with a compilation error, provided the substitution error is one the C++ standard grants such treatment.[2] If one or more candidates remain and overload resolution succeeds, the invocation is well-formed.

in the next section, we will see how we can use SFINAE to our advantage, through type traits, and tag dispatching ….

3- Type Traits / Tag dispatching …

Type Traits :

so what are type traits?

let's start with what is a trait.

a trait is "a particular characteristic that can produce a particular type of behavior". Or simply "a characteristic, especially of a personality".
we can think about type traits as properties of a type .

you'd often need the information on what kind of types are accepted by a template, and what types are supported by certain operations. While concepts are much superior in terms of expressiveness or usability, with type traits you could already introduce compile-time conditions on what should be accepted as valid code and what not.

Though type traits can help with even more. With their help, you can also add or remove the const specifier, you can turn a pointer or a reference into a value, and so on….

Type traits are a clever technique used in C++ template metaprogramming that gives you the ability to inspect and transform the properties of types.
For example, given a generic type T — it could be int, bool, std::vector, or whatever you want — with type traits you can ask the compiler some questions: is it an integer? Is it a function? Is it a pointer? Or maybe a class? Does it have a destructor? Can you copy it? Will it throw exceptions? ... and so on. This is extremely useful in conditional compilation, where you instruct the compiler to pick the right path according to the type in input. We will see an example shortly.

Tag Dispatching :

sometimes in metaprogramming, we want our template function to behave differently depending on the types given as parameters

we can achieve that in different means :

Tag-dispatching is a metaprogramming technique to overload a function using different tag parameters. The right overload is chosen by a compiler at compile time

by creating several tags (so several types), we can use them to route the execution through various overloads of a function.

C++

template<class It>
It plus2_impl(It it, std::forward_iterator_tag) 
{
    ++it; ++it;
    return it;
}

template<class It>
It plus2_impl(It it, std::random_access_iterator_tag) 
{
    return it + 2;
}

template<class It>
It plus2(It it) 
{
    using Tag = typename std::iterator_traits<It>::iterator_category;
    return plus2_impl(it, Tag{});
}

- is_integral :

template <class T> struct is_integral;

Screen Shot 2022 10 31 at 5.10.31 PM

is_integral is a Trait class that identifies whether T is an integral type.

it inherits from the class integral_constant either TRUE or FALSE depending on the type is it an integral type or not

here are the integral types :
C++
bool , char ,char16_t , char32_t  , wchar_t , signed char,short int, int
long int,long long int , unsigned char , unsigned short int , unsigned int
unsigned long int, unsigned long long int

- enable_if :

The enable_if trait is a technique to control the application of SFINAE.

In C++ metaprogramming, std::enable_if is an important function to enable certain types for template specialization via some predicates known at the compile time. Using types that are not enabled by std::enable_if for template specialization will result in a compile-time error.

std::enable_if can be used in many forms, including:

implementation of enable_if :

C++
template<bool B, class T = void>
struct enable_if {};
 
template<class T>
struct enable_if<true, T> { typedef T type; };

- **lexicographical_compare :**

lexicographical comparison is the kind of comparison generally used to sort words alphabetically in dictionaries; It involves comparing sequentially the elements that have the same position in both ranges against each other until one element is not equivalent to the other. The result of comparing these first non-matching elements is the result of the lexicographical comparison.
C++

template <class InputIterator1, class InputIterator2>
  bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2)
{
  while (first1!=last1)
  {
    if (first2==last2 || *first2<*first1) return false;
    else if (*first1<*first2) return true;
    ++first1; ++first2;
  }
  return (first2!=last2);
}

- std::pair **:**

the pair is pretty strait forward This class couples together a pair of values, which may be of different types (T1 and T2). The individual values can be accessed through its public members first  and second.

3- Iterators :

An iterator  is an object (like a pointer) that points to an element inside the container. We can use iterators to move through the contents of the container. They can be visualized as something similar to a pointer pointing to some location and we can access the content at that particular location using them. Iterators play a critical role in connecting algorithms with containers along with the manipulation of data stored inside the containers.
in c++ there are 5 categories of iterators, each with its own properties that we should know in order to work with them efficiently
iterator traits

- Iterator Traits :

Generic code that uses iterators, such as the STL algorithms which use them intensely, needs information about them. For example, it needs the type of object that the iterators refer to.
so how does it gets this information?
Another example of the required information is the capabilities of the iterator: is it just an input iterator, that supports ++  but should not be read twice? Or a forward iterator that can be read several times? Or a bidirectional that can also do --? Or a random access iterator, that can jump around with +=, +, -=, and -? Or an output iterator?
This piece of information is useful for some algorithms that would be more or less efficient depending on those capabilities. Such an algorithm typically has several implementations and chooses one to route to depending on the category of the iterator.

Iterator Traits is a class trait that provides specific information about the iterator that stl::algorithms needs

member description
difference_type Type to express the result of subtracting one iterator from another. it gets stored in type able to represent the result of any valid pointer subtraction operation(ptrdiff_t)
value_type The type of element the iterator can point to.
pointer The type of a pointer to an element the iterator can point to.
reference The type of reference to an element the iterator can point to.
iterator_category The iterator category. It can be one of these:
• input_iterator_tag
• output_iterator_tag
• forward_iterator_tag
• bidirectional_iterator_tag
• random_access_iterator_tag
The iterator_traits class template comes with a default definition that obtains these types from the iterator type itself (iterator class). It is also specialized for pointers (T*) and pointers to const (const T*).Note that any custom class will have a valid instantiation of iterator_traits if it publicly inherits the base class std::iterator.

Member types

member generic definition T* specialization const T* specialization
difference_type Iterator::difference_type ptrdiff_t ptrdiff_t
value_type Iterator::value_type T T
pointer Iterator::pointer T* const T*
reference Iterator::reference T& const T&
iterator_category Iterator::iterator_category random_access_iterator_tag random_access_iterator_tag

- the Iterator Class :

std::iterator is a helper to define the iterator traits of an iterator.

std::iterator is a template, that takes 5 template parameters:

C++
template<
    typename Category,
    typename T,
    typename Distance = std::ptrdiff_t,
    typename Pointer = T*,
    typename Reference = T&
> struct iterator;

Those 5 names sound familiar, right? Those template types correspond to the 5 types required by the STL on iterators.

The job of std::iterator is to expose those types. Here is one possible implementation of std::iterator:

C++
template<
    typename Category,
    typename T,
    typename Distance = std::ptrdiff_t,
    typename Pointer = T*,
    typename Reference = T&
> struct iterator
{
    using iterator_category = Category;
    using value_type = T;
    using difference_type = Distance;
    using pointer = Pointer;
    using reference = Reference;
};

std::iterator allows an iterator to define these 5 types, by inheriting from std::iterator and passing it those types (at least the first 2 since the other 3 have default values):

C++
class MyIterator : public std::iterator<std::random_access_iterator, int>
{
    // ...
};

By inheriting from std::iterator,  MyIterator also exposes the 5 types.

4 - Allocator :

an Allocator is an object that’s responsible for encapsulating memory management
every stl container except (std::array, to std::shared_ptr and std::function)
has an allocator that Encapsulates memory allocation and deallocation strategy.

if you are coming from a c language background you may ask why not malloc or alloc instead of new and delete? , so let’s first answer this

malloc() is a library function of stdlib.h and it was used in C language to allocate memory for N blocks at run time, it can also be used in C++ programming language. Whenever a program needs memory to declare at run time we can use this function.
while new is an operator in C++ programming language, it is also used to declare memory for N blocks at run time.
here are some differences between malloc and new :

now time to answer why using an allocator and not new and delete :

the std::allocator was not created to replace new and delete.

in fact, the allocator uses new and delete in its internals.

what’s so special about the allocator is that it separates the allocation and construction, deallocation and destruction.

for general programming using new and delete is more than enough, but when creating a container it's a must to take control of these things.

here is an example :

C++
std::vector<X> v;
v.reserve(4);        // (1)
v.push_back( X{} );  // (2)
v.push_back( X{} );  // (3)
v.clear();           // (4)

- allocator_traits :

just like the iterator, the std::allocator needs to have some information about the container in order for it to work properly.

The allocator_traits  the class template provides a standardized way to access various properties of allocators. The standard containers and other standard library components access allocators through this template, which makes it possible to use any class type as an allocator, as long as the user-provided specialization of allocator_traits  implements all required functionality.

The default, non-specialized, allocator_traits  contains the following members:

Member types

Type Definition
allocator_type Alloc
value_type Alloc::value_type
pointer Alloc::pointer if present, otherwise value_type*
const_pointer Alloc::const_pointer if present, otherwise std::pointer_traits::rebind
void_pointer Alloc::void_pointer if present, otherwise std::pointer_traits::rebind
const_void_pointer Alloc::const_void_pointer if present, otherwise std::pointer_traits::rebind
difference_type Alloc::difference_type if present, otherwise std::pointer_traits::difference_type
size_type Alloc::size_type if present, otherwise std::make_unsigned::type
propagate_on_container_copy_assignment Alloc::propagate_on_container_copy_assignment if present, otherwise std::false_type
propagate_on_container_move_assignment Alloc::propagate_on_container_move_assignment if present, otherwise std::false_type
propagate_on_container_swap Alloc::propagate_on_container_swap if present, otherwise std::false_type
is_always_equal(since C++17) Alloc::is_always_equal if present, otherwise std::is_empty
the template std::allocator_traits  supplies the default implementations for all optional requirements, and all standard library containers and other allocator-aware classes access the allocator through std::allocator_traits , not directly.

Member functions

allocate [static] allocates uninitialized storage using the allocator(public static member function)
deallocate [static] deallocates storage using the allocator(public static member function)
construct [static] constructs an object in the allocated storage(function template)
destroy [static] destructs an object stored in the allocated storage(function template)
max_size [static] returns the maximum object size supported by the allocator(public static member function)
select_on_container_copy_construction [static] obtains the allocator to use after copying a standard container(public static member function)
with this in mind, I think we have enough knowledge to try and deep dive into the
re-implementation of the containers.

FT_VECTOR :

The iterators of vector are of the “random access” category:
→ Random-access iterators are iterators that can be used to access elements at an arbitrary offset position relative to the element they point to, offering the same functionality as pointers.
→ Random-access iterators are the most complete iterators in terms of functionality. All pointer types are also valid random-access iterators.

Member types

Member type Definition
value_type T
allocator_type Allocator
size_type Unsigned integer type (usually std::size_t)
difference_type Signed integer type (usually std::ptrdiff_t)
reference value_type&
const_reference const value_type&
pointer Allocator::pointer(until C++11)std::allocator_traits::pointer(since C++11)
const_pointer Allocator::const_pointer(until C++11)std::allocator_traits::const_pointer(since C++11)
iterator LegacyRandomAccessIterator and LegacyContiguousIterator to value_type(until C++20)LegacyRandomAccessIterator, contiguous_iterator, and ConstexprIterator to value_type(since C++20)
const_iterator LegacyRandomAccessIterator and LegacyContiguousIterator to const value_type(until C++20)LegacyRandomAccessIterator, contiguous_iterator, and ConstexprIterator to const value_type(since C++20)
reverse_iterator std::reverse_iterator
const_reverse_iterator std::reverse_iterator

Member functions

(constructor) constructs the vector(public member function)
(destructor) destructs the vector(public member function)
operator= assigns values to the container(public member function)
assign assigns values to the container(public member function)
get_allocator returns the associated allocator(public member function)
Element access
at access specified element with bounds checking(public member function)
operator[] access specified element(public member function)
front access the first element(public member function)
back access the last element(public member function)
data direct access to the underlying array(public member function)
Iterators
begin cbegin(C++11) returns an iterator to the beginning(public member function)
endcend(C++11) returns an iterator to the end(public member function)
begin crbegin(C++11) returns a reverse iterator to the beginning(public member function)
rend crend(C++11) returns a reverse iterator to the end(public member function)
Capacity
empty checks whether the container is empty(public member function)
size returns the number of elements(public member function)
max_size returns the maximum possible number of elements(public member function)
reserve reserves storage(public member function)
capacity returns the number of elements that can be held in currently allocated storage(public member function)
Modifiers
clear clears the contents(public member function)
insert inserts elements(public member function)
erase erases elements(public member function)
push_back adds an element to the end(public member function)
pop_back removes the last element(public member function)
resize changes the number of elements stored(public member function)
swap swaps the contents(public member function)

Non-member functions

operator==operator!=operator<operator<=operator>operator>=operator<=> lexicographically compares the values in the vector(function template)
std::swap(std::vector) specializes the std::swap algorithm(function template)

FT_STACK :

The std::stack class is a container adapter. Container objects hold data of a similar data type. You can create a stack from various sequence containers. If no container is provided, the deque contains will be used by default. Container adapters don’t support iterators, so they can’t be used to manipulate data.
the std::stack is built on top of the std::vector as an underlying container
so most of its member functions are just a call to the underlying container’s member functions

Member types

Member type Definition
container_type Container
value_type Container::value_type
size_type Container::size_type
reference Container::reference
const_reference Container::const_reference

Member functions

(constructor) constructs the stack(public member function)
(destructor) destructs the stack(public member function)
operator= assigns values to the container adaptor(public member function)
Element access
top accesses the top element(public member function)
Capacity
empty checks whether the underlying container is empty(public member function)
size returns the number of elements(public member function)
Modifiers
push inserts element at the top(public member function)
pop removes the top element(public member function)
swap(C++11) swaps the contents(public member function)

Member objects

Container c the underlying container(protected member object)

Non-member functions

operator==operator!=operator<operator<=operator>operator>=operator<=> lexicographically compares the values in the stack(function template)
std::swap(std::stack) specializes the std::swap algorithm(function template)

RED-BLACK-TREE

0 ilyr9n3l4OGhjdk9

Problems with Binary Search Tree :

For Binary Search Tree, although the average time complexity for the search, insertion and deletion are all O(log n), where n is the number of nodes in the tree, the time complexity becomes O(n) in the worst case - BST is not balanced.

bst

We can guarantee O(log⁡n) time for all three operations by using a balanced tree - a tree that always has height log(n).

so, what is a red-black tree?

A red-black tree is a self-balancing binary search tree, that is, a binary search tree that automatically maintains some balance.
Red-black trees are an evolution of binary search trees that aim to keep the tree balanced without affecting the complexity of the primitive operations. This is done by coloring each node in the tree with either red or black and preserving a set of properties that guarantee that the deepest path in the tree is not longer than twice the shortest one.

Red-Black Tree Properties

The following rules enforce the red-black tree balance:

  1. Each node is either red or black.
  2. (The root is black.)
  3. All NIL leaves are black.
  4. A red node must not have red children.
  5. All paths from a node to the leaves below contain the same number of black nodes.

upper_bound/lower_bound:

The names already have an intuitive but different meaning in mathematics. Given the mathematical meanings, it seems weird that in a big set or map, upper_bound and lower_bound are actually the same or adjacent elements.

the basic rules you have to remember:

predecessor and successor:

When you do the in-order traversal of a binary tree, the neighbors of a given node are called Predecessor(the node lies behind of given node) and Successor (the node lies ahead of the given node).

here’s an example :

Inorder Predecessor and Successor in Binary Search Tree

Approach:

Say you have to find the in-order predecessor and successor node 15.

pseudocode :

C++
if (root != null) {
          if (root.data == val) {
                // go to the right most element in the left subtree, it will the
                // predecessor.
                if (root.left != null) {
                    Node t = root.left;
                    while (t.right != null) {
                        t = t.right;
                    }
                    predecessor = t.data;
                }
                if (root.right != null) {
                    // go to the left most element in the right subtree, it will
                    // the successor.
                    Node t = root.right;
                    while (t.left != null) {
                        t = t.left;
                    }
                    successor = t.data;
                }
            } else if (root.data > val) {
                // we make the root as successor because we might have a
                // situation when value matches with the root, it wont have
                // right subtree to find the successor, in that case we need
                // parent to be the successor
                successor = root.data;
                successorPredecessor(root.left, val);
            } else if (root.data < val) {
                // we make the root as predecessor because we might have a
                // situation when value matches with the root, it wont have
                // left subtree to find the predecessor, in that case we need
                // parent to be the predecessor.
                predecessor = root.data;
                successorPredecessor(root.right, val);
            }
        }
    }

red-black tree iterator :

Iterators for tree-based data structures can be more complicated than those for linear structures.

For arrays (and vectors and deques and other array-like structures) and linked lists, a single pointer can implement an iterator:

listarit

Iterating over Trees:

look at this binary search tree, and suppose that you were implementing tree iterators as a single pointer. Let’s see if we can “think” our way through the process of traversing this tree, one step at a time, without needing to keep a whole stack of unfinished recursive calls around.
bst1
We’re going to try to visit the nodes in the same order we would process them during an “in-order” traversal, which, for a BST, means that we will visit the data in ascending order.
It’s not immediately obvious what our data structure for storing our “current position” (i.e., an iterator) will be. We might suspect that a pointer to a tree node will be part or the whole of that data structure, in only because that worked for us with iterators over linked lists. With that in mind, …

begin(),end():

operator++:

Suppose you are still trying to implement iterators using a single pointer, you have one such pointer named current as shown in the figure.

Question: How would you implement ++current?

Well, we know that we should wind up at node 50. But how can we get there?

bstiter
We can’t, not with just a pointer to the node and all the nodes pointing only to their children. The only place you can go within this tree is down, and there is no “down” from our current position.
In a binary tree, to do operator++ :
• We need to know not only where we are, • but also how we got here.
One way to do that is to implement the iterator as a stack of pointers containing the path to the current node. In essence, we would use the stack to simulate the activation stack during a recursive traversal. But that’s pretty clumsy. Iterators tend to get assigned (copied) a lot, and we’d really like that to be an O(1) operation. Having to copy an entire stack of pointers just isn’t very attractive.

now let’s try to figure out just what our code should do :

biniter

Question: Suppose that we are currently at node A. What is the in-order successor (the node that comes next during an in-order traversal) of A?

Answer: F is the in-order successor of A. If we are at A during an in-order traversal, we have already visited all of A’s left descendants. So the answer has to be C or one of its descendants. It’s tempting to pick C because it’s only one step away from A. But, remember, during an in-order traversal, we visit a node only after visiting all of its left descendants and before visiting any of its right descendants. We have not yet visited C’s left descendants. So have to run down from C to the left as far as we can go.

This suggests that, if a node has any right descendants, we should

• Take a step down to the right, then • Run as far down to the left as we can.

You can see how this would take us from A to F. And, for that matter, it would take us from E to G as well. So both of our prior examples are satisfied.

biniter 1

To summarize : • If the current node has a non-null right child, ◦ Take a step down to the right ◦ Then run down to the left as far as possible • If the current node has a null right child, ◦ move up the tree until we have moved over a left child link

with that in mind lets move to pseudocode :

C++

  if (nodePtr == nullptr)
    {
      // ++ from end(). get the root of the tree
      nodePtr = tree->root;
      
      // error! ++ requested for an empty tree
      if (nodePtr == nullptr)
        throw UnderflowException { };
      
      // move to the smallest value in the tree,
      // which is the first node inorder
      while (nodePtr->left != nullptr) {
        nodePtr = nodePtr->left;
      }
    }
  else
    if (nodePtr->right != nullptr)
      {
        // successor is the farthest left node of
        // right subtree
        nodePtr = nodePtr->right;
        
        while (nodePtr->left != nullptr) {
          nodePtr = nodePtr->left;
        }
      }
    else
      {
        // have already processed the left subtree, and
        // there is no right subtree. move up the tree,
        // looking for a parent for which nodePtr is a left child,
        // stopping if the parent becomes NULL. a non-NULL parent
        // is the successor. if parent is NULL, the original node
        // was the last node inorder, and its successor
        // is the end of the list
        p = nodePtr->parent;
        while (p != nullptr && nodePtr == p->right)
          {
            nodePtr = p;
            p = p->parent;
          }
        
        // if we were previously at the right-most node in
        // the tree, nodePtr = nullptr, and the iterator specifies
        // the end of the list
        nodePtr = p;
      }
  
  return *this;

rotation :

color-flipping :

insertion :

insertion strategy: 1 - insert the node and color it RED 2 - check what is the violation 3 - repair the violation either by color flipping, rotating, or both

1 - first of all we insert the node in the binary search way, and we color it RED, the reason for that is to not violate rule 5

2- after that if there are 2 consecutive RED nodes, we will fix it depending on the 2 cases that may occur:

C++
INSERT(T, n)
  y = T.NIL
  temp = T.root

  while temp != T.NIL
      y = temp
      if n.data < temp.data
          temp = temp.left
      else
          temp = temp.right
  n.parent = y
  if y==T.NIL
      T.root = n
  else if n.data < y.data
      y.left = n
  else
      y.right = n

  n.left = T.NIL
  n.right = T.NIL
  n.color = RED
  INSERT_FIXUP(T, n)

cases:

  1. if the uncle is red, we color flip color flipping is simple :make the parent red and the children black <aside> 💡 if the parent is the root, then we force the color to be black </aside>
  2. if the uncle is black, we rotate : there are 4 cases when we are rotating the same applies if the parent is the grandparent’s right but in reverse
  3. if the parent is the grandparent left and the child is the parent’s left
  4. then we right rotate
  5. if the parent is the grandparent’s left and the child is the parent’s right
  6. then we need to left-right rotate
C++
INSERT_FIXUP(T, z)
  while z.parent.color == red

      if z.parent == z.parent.parent.left //z.parent is left child
          y = z.parent.parent.right //uncle of z

          if y.color == red //case 1
              z.parent.color = black
              y.color = black
              z.parent.parent.color = red
              z = z.parent.parent

          else //case 2 or 3
              if z == z.parent.right //case 2
                  z = z.parent //marked z.parent as new z
                  LEFT_ROTATE(T, z) //rotated parent of orignal z

              //case 3
              z.parent.color = black // made parent black
              z.parent.parent.color = red // made grandparent red
              RIGHT_ROTATE(T, z.parent.parent) // right rotation on grandparent

      else // z.parent is right child
          code will be symmetric
  T.root.color = black

Deletion :

The deletion process in a red-black tree is also similar to the deletion process of a normal binary search tree. Similar to the insertion process, we will make a separate function to fix any violations of the properties of the red-black tree.

Just go through the DELETE function of binary search trees because we are going to develop the code for deletion on the basis of that only. After that, we will develop the code to fix the violations.

On the basis of the TRANSPLANT function of a normal binary search tree, we can develop the code for the transplant process for red-black trees as:

C++
RB-TRANSPLANT(T, u, v)
  if u.parent == T.NIL // u is root
      T.root = v
  elseif u == u.parent.left //u is left child
      u.parent.left = v
  else // u is right child
      u.parent.right = v
  v.parent = u.parent

this is the pseudocode for the deletion of the binary search tree:

C++

RB-DELETE(T, z)
  y = z
  y_orignal_color = y.color
  if z.left == T.NIL //no children or only right
      x = z.right
      RB-TRANSPLANT(T, z, z.right)
  else if z.right == T.NIL // only left child
      x = z.left
      RB-TRANSPLANT(T, z, z.left)
  else // both children
      y = MINIMUM(z.right)
      y_orignal_color = y.color
      x = y.right
      if y.parent == z // y is direct child of z
          x.parent = y
      else
          RB-TRANSPLANT(T, y, y.right)
          y.right = z.right
          y.right.parent = y
      RB-TRANSPLANT(T, z, y)
      y.left = z.left
      y.left.parent = y
      y.color = z.color
  if y_orignal_color == black
      RB-DELETE-FIXUP(T, x)

Fixing Violation of Red-Black Tree in Deletion

The violation of property 5 (change in black height) is our main concern. We are going to deal it with in a bit different way. We are going to say that property 5 has not been violated and node x  which is now occupying y 's original position has an "extra black" in it. In this way, the property of black height is not violated but the property 1 i.e., every node should be either black or red is violated because the node x  is now either "double black" (if it was black) or red and black (if it was red).

With this thinking, we can say that either properties 1, 2, or 4 can be violated.

If x is red and black, we can simply color it black and this will fix the violation of property 1 without causing any other violation. This will also solve the violation of property 4.

If x is the root, we can simply remove the one extra black and thus, fix the violation of property 1.

With the above two mentioned cases, violations of properties 2 and 4 are entirely solved and now we can focus only on solving the violation of property 1.

There can be 4 cases (w is x's sibling):

let’s explain each case for fixup on its own

Screen Shot 2022 11 27 at 12.39.23 PM
Screen Shot 2022 11 27 at 12.40.08 PM

Take note that by doing this, we haven't caused any new violations.

Also if we have entered case 2 from case 1, the parent must be red and now red and black, so it will be simply fixed by coloring it black.

Screen Shot 2022 11 27 at 12.55.53 PM
Screen Shot 2022 11 27 at 12.57.47 PM

We first colored w the same as the parent of x and then colored the parent of x  black. After this, we colored the right child of w  black and then left rotated the parent of x. At last, we removed the extra black from x  without violating any properties.

pseudo-code for the fixup delete :
C++
RB-DELETE-FIXUP(T, x)
  while x!= T.root and x.color == black
      if x == x.parent.left
          w = x.parent.right
          if w.color == red //case 1
              w.color = black
              x.parent.color = red
              LEFT-ROTATE(T, x.parent)
              w = x.parent.right
          if w.left.color == black and w.right.color == black //case 2
              w.color = red
              x = x.parent
          else //case 3 or 4
              if w.right.color == black //case 3
                  w.left.color = black
                  w.color = red
                  RIGHT-ROTATE(T, w)
                  w = x.parent.right
              //case 4
              w.color = x.parent.color
              x.parent.color = black
              w.right.color = black
              LEFT-ROTATE(T, x.parent)
              x = T.root
      else
          code will be symmetric
  x.color = black

5 - FT_MAP

now that we have a working red-black tree, map is almost free. a std::map is an ordered associative container: keys are unique, kept sorted by Compare, and each key maps to a value. under the hood that is exactly a balanced BST keyed on the .first of each pair.

the only real trick is the comparator. the tree compares whole value_types, but map only cares about the key. so we wrap the user's comparator into a value_compare that reaches into .first:

C++
template <class Key, class T, class Compare = std::less<Key> >
class map {
public:
    typedef ft::pair<const Key, T> value_type;

    // adapt: order two value_types by their keys only
    class value_compare {
        Compare _comp;
    public:
        value_compare(Compare c) : _comp(c) {}
        bool operator()(const value_type& a, const value_type& b) const {
            return _comp(a.first, b.first);
        }
    };

private:
    typedef ft::RBTree<value_type, value_compare> tree_type;
    tree_type _tree;
};

operator[]

the famous one. m[key] inserts a default-constructed value if the key is missing, then hands back a reference to it:

C++
T& operator[](const Key& key) {
    return _tree.insert(ft::make_pair(key, T())).first->second;
}

notice it can't be const — it may insert. that is why there is no const overload (in c++11 you reach for .at() instead, which throws rather than inserts).

iterators come for free

because the tree already exposes in-order iterators, map::begin()/end() just forward to the tree. in-order traversal of a BST keyed on .first visits pairs sorted by key — which is precisely map's contract. you wrote the hard part once, in the tree, and every ordered container inherits it.

6 - FT_SET

set is map with the value taken away — the key is the value. same red-black tree, but value_type == Key and the comparator orders keys directly.

one rule from the standard catches people out: set iterators are always const. you can't mutate an element in place, because changing it would silently break the tree's ordering invariant. so iterator and const_iterator are the same type — mutation has to go through erase + insert.

C++
template <class T, class Compare = std::less<T> >
class set {
    typedef ft::RBTree<const T, Compare> tree_type;
    // iterator == const_iterator, by design
};

7 - reverse_iterator

every container also owes you rbegin() and rend(). instead of writing reversed traversal by hand, the STL gives you an adapter: reverse_iterator wraps any bidirectional iterator and flips its direction.

the subtle bit is the off-by-one. a reverse iterator stores a base iterator and dereferences the element before it. that single indirection is what lets rbegin() (base = end()) point at the last real element, and rend() (base = begin()) sit one before the first:

C++
template <class Iter>
class reverse_iterator {
    Iter _base;
public:
    explicit reverse_iterator(Iter it) : _base(it) {}

    reference operator*() const { Iter tmp = _base; return *--tmp; }
    reverse_iterator& operator++() { --_base; return *this; }
    reverse_iterator& operator--() { ++_base; return *this; }
    Iter base() const { return _base; }
};

write the adapter once and every container gets reverse iteration for free — the same leverage as iterator traits and allocators. that repetition is the whole point: the STL is small because each piece does one job and composes with the rest.

what reimplementing the STL actually teaches you

the headline lesson is that there is no magic. vector is a pointer, a size, and a capacity, with a careful dance around std::allocator and exception safety. map is a red-black tree wearing a comparator. iterators are just a typed cursor with five typedefs that let algorithms ask "what are you?" at compile time. once you've built them, you stop treating the standard library as a black box and start seeing the moving parts.

the second lesson is harder won: the difficulty was never the data structures — it was the contracts. strong exception safety on insert. iterator invalidation rules. const-correctness that the type system enforces for you. the rebalancing case analysis in red-black deletion. these are the invisible promises every STL container keeps, and you only really feel their weight when you're the one who has to keep them.

and that is exactly why the exercise is worth it. you come out reading other people's code differently — you see the allocation behind the convenience, the template substitution behind the overload, the syscall behind the abstraction. the same way writing an HTTP server from the socket up taught me what every framework quietly does on my behalf, rebuilding the STL taught me what every std:: quietly does on mine.

build the boring machinery yourself, once. then trust it — because now you know exactly what it's doing.

← All field notes