In this project, I implements my own version of some containers from the Standard Template Library (STL) using C++98. The following containers have been implemented:
- vector
- map
- stack
The implementation aims to reproduce the behavior and features of the STL containers while following the standard constraints and requirements.
To run this program, you will need:
A Unix-like operating system (Linux, macOS)
g++ compiler
1- Clone the repository: git clone https://github.com/Clivassy/ft_containers
2- cd ft_containers
3- Compile the code using the provided Makefile: make
4- Run test for one container : ./container (by default it will launch vector test)
NB : to test other containers :
-> Open Makefile
-> Decomment the test you want in this part :
The usage of the implemented containers is similar to that of the STL containers.
For instance, to create a vector of integers and add some elements to it.
You can refer to the "tests" directory to find many tests on each container.
The code is organized in the following directory structure:
.
├── ft_vector.hpp
├── ft_map.hpp
├── ft_stack.hpp
├── ...
└── Makefile
Each header file contains the implementation of a specific container.
The implementation is splited into two main sections: the container class definition and the container iterator definition.
- here talk about how to begin the project
- here insist on iterators + types traits + spécificités du vector
To my mind, the important part of this project, and the real capital gain, is the implementation of the Red black Tree.
So I won't go into detail about vector and stack implementation and I will focus my advices on map and set.
Here are the steps I followed to understand step by step Red Black Trees. At the end, I will provide you THE ONE AND ONLY youtube perfect teacher who helped me so much in understanding Red Black Trees and Data Structure in general.
First of all, you need to understand the basic structure of a tree.
A tree is a widely used data structure that resembles a hierarchical tree structure with a set of nodes connected by edges or branches.
Each node in the tree can have zero or more child nodes, except for the root node, which has no parent.
Trees are a really useful way to organize data in a hierarchy.
They're used all the time in computer science and software engineering for things like file systems, sorting algorithms, and web page structures.
There are lots of different types of trees to choose from, like:
- Binary trees
- AVL trees
- Red-black trees
The type you choose depends on what you're trying to do and how fast you need it to be.
Have a look to this schemas to have a better understanding :
A binary tree is a type of tree data structure in which each node can have at most two children. The two children are commonly referred to as the left child and the right child. The structure of a binary tree is hierarchical, where each node is connected to its children nodes.
Here are important rules to know about Binary Search Trees :
→ Each node can have at most 2 children
→ The left subtree of any node will have at least less than the parent and root.
→ The right subtree of any node will have at least more than the parent.
Deletion in a binary search tree is crucial for maintaining the integrity and efficiency of the tree.
When a node is deleted from a binary search tree, the tree structure needs to be adjusted to preserve the binary search tree property.
The binary search tree property states that for every node, all nodes in its left subtree have values less than the node's value, and all nodes in its right subtree have values greater than the node's value.
WHen you delete a node, you can face 3 cases:
1) Node has 0 child :
→ Simply delete the node.
2) Node has 1 child:
→ Simply link the parent to the child of the node we delete.
3) Node has 2 children (two choices):
→ Replace the node being deleted with its in-order predecessor.
Note that :
In-order predecessor = largest element from the left subtree of the node we want to delete.
→ Replace the node being deleted with its in-order successor.
In-order successor = smallest element from the right subtree of the node we want to delete.
An AVL tree is a self-balancing binary search tree that maintains balance by performing rotations.
It ensures that the heights of the left and right subtrees of each node differ by at most one.
When balance is violated, rotations are used to restore it.
This guarantees efficient operations with a worst-case time complexity of O(log n).
Red Black Tree guarantees the time complexity will be log(n^2) since it is a balanced tree.
Properties of Red Black Trees:
→ It is a self balancing BST.
→ Every node is either Black or Red.
→ Root is always Black.
→ Every leaf which is nil is Black.
→ If node is Red, then its children are Black.
→ Every path from a node to any of its descendent NIL node hase same number of Black nodes.