This repository contains one of my projects of the core curriculum at 42 Heilbronn.
The project ft_containers is about some of the container class templates from the C++ standard template library (STL). As with all C++ projects at 42 Heilbronn, the code has to be written according to the C++98 standard.
The task in this project is to reimplement some of the container types from the C++ STL:
Further, some additional features are required:
The structure of each standard container has to be taken as reference. As the solution has to comply with the C++98 standard, every C++98 feature (even deprecated ones) is expected. Any later feature of the containers must not be implemented. If the container has an iterator system, then this has to be implemented as well.
Apart from implementing set, the bonus part is to use a red-black tree as internal data structure for map and set.
My general approach was to follow the original implementation rather closely, so I read a lot of source code of the STL. A good overview over the required member functions, their actions, and parameters was provided by cplusplus.com.
I decided to implement a red-black tree for map and set.
For this, I used the excellent guide provided in Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.
To check that my own containers (namespace ft) work as the original ones (namespace std), some tests are included.
The Makefile rule all compiles my tests into two binaries, ft and std, using the containers from the respective namespace.
Running them shows the test output, including the time from a small benchmark.
Further, the rb_tree rule produces a binary of the same name.
This program will display a small visualization of the insertion and deletion process of the red-black tree.
A small script test.sh is also included.
It automates the comparison between the ft and the std containers and saves the result in a file result.diff.
Ideally, this file should only contain the benchmark times.
Apart from my own tests, I also used the following testers:
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, Third Edition
- CodesDope: Red-Black Trees