README.md

ft_containers

42/Codam deep dive into standard C++ containers.

Description

Reimplementing STL containers: vector, stack, map, and set.
This includes all member and non-member functions and overloads, and also iterator systems.
Inner data structures should be appropriate to the container.
I therefore also reimplemented a Red-Black tree class (complete with iterator and nodes) for use with map and set, as is done by the STL.

Red-Black Tree

I followed the implementation of Red-Black Trees as described in "Introduction to Algorithms" (3rd ed.) by Cormen et al.
A RB tree differs from a regular binary search tree by having 1 extra attribute in its nodes: colour, which is either red or black.
This property and the constraints surrounding it ensure that a RB tree is approximately balanced and require less rotations (compared to say AVL trees).

My RB tree also makes use of a single sentinel node instead of a nullptr to simplify handling of last and root nodes (as we can treat the sentinel node like a normal node).

The tree is therefore somewhat circular, as both the root's parent and the leaves child points to the single sentinel.

(a) conventional RB tree (b) RB tree using single sentinel node

Compilation

I've included extensive test files that compare my implementation of the containers against the STL ones.
Each function of the containers is tested against its STL version.
I also apply "stress tests" that utilize large container sizes to test complexity.
The compilation commands below will create 2 binaries - one compiled with my library "ft" and one compiled with the STL.

Build
Run make in the root directory to compile the test files with the container library headers.
This will compile with stress tests included (see above).
Binaries ft_bin and std_bin may then be executed to see behaviour of respective libraries.

For compiling without stress tests:
make quick

Quick Build-n-Run

make run    # runs simple output comparison using diff, ignores performance
make compare    # detailed comparison program that shows output and performance differences
make qcompare    # same as above but without stress test, faster

Output of binary compiled by make	Output of make qcompare

Resources

General:

• C++ Primer

Vector:

• How a vector grows exponentially

SFINAE:

• Explanation of enable-if and SFINAE from More C++ Idioms

Red-Black Tree:

• Introduction to RB Trees
• Explanation of Insertion with Diagrams
• Breakdown of insert/delete/rebalance algorithms
• Chapter 13 of Introduction to Algorithms, 3rd edition
• RB iterator in/decrement source code

Sentinel nodes in binary search trees:

• Introduction to Algorithms, page 309

Rebind:

• What does template rebind do
• Using rebind for node allocation