C++ | Data structures

About the project

The containers in C++ all have a very different usage.
To make sure I understand them all, let's re-implement them!
I had to implement using C++98 and with the help of this reference the following containers :

  • List
  • Vector
  • Map
  • Stack
  • Queue

I also made so bonus containers:

  • Set
  • Multiset
  • Multimap

Of course, STL (standard template library) is forbidden.
However STD (standard) library was allowed.

What I learned

A bunch of data structures

Before this project, the only data structure that I experimented with was singly linked list.

Singly linked list

In order to implement the List container, I had to learn about doubly circular linked list.

Circular doubly linked list

For the Map container , binary trees and more specifically red black trees.

Red black tree


Re-implementing containers and their iterators demystified the STL and really increased my expertise in C++.

Test driven development

I made a lot of unit tests as there was a bunch of functions to test and tried my best to follow TDD practices.
Unfortunately, it was forbidden in this project to use a C++ testing library, so in order to run my tests I had to use assert which made the whole process really redundant (and painful).


Re-implementing existing containers wasn't meaningful to me so I found it to be boring sometimes.
However, I really enjoyed researching, learning about data structures and making TDD.