ft_containers
============
This is a project about recreating a few of the C++98 STL containers and
learning what each one is meant for

The implementations have to be C++98 standard complaint. Meaning later features
musn't me implemented, and deprecated functions must be implemented.

mandatory part
============
Implement the following containers in their <container>.hpp files
  x vector (without vector<bool> specializiation
  x map
  x stack (it will use the custom vector implementation, but must still be
      compatible with other containers)
Also implement:
  x std::iterator_traits
  x std::reverse_iterator
  x std::enable_if (isn't C++98, but is required to discover SFINAE)
  x std::is_integral
  x std::equal and/or std::lexicographical_compare
  x std::pair
  x std::make_pair

bonus part 
============
Implement the set container with a red-black tree

result
============
I really liked this project, as I never really stood still by the fact that
exception safety is a thing, and that (at least in C++98) there are some weird
hacks you have to do to properly implement the containers. I think I also
learned how to (better) read and understand template errors and when to use
which container in my own projects.

My containers are, as far as I know, fully C++98 compliant if you ignore later
defect reports that were applied to the C++98 standard. Meaning they have the
exception safety and complexity guarantees as required by C++98.

My containers are also pretty fast compared to the ones installed on my system
(gcc12.2.0). Here are some results:

The data below was measured using the benchmarks in the benchmark/ directory

vector<T>
+-----------------------------------------------+------------+---------+
|                   function                    | system(ms) |  my(ms) |
+-----------------------------------------------+------------+---------+
| swap(vector)                                  |    0.00405 | 0.00146 |
| vector(InputIt, InputIt)                      |    0.06462 | 0.04502 |
| assign(size_type, value_type)                 |    0.08932 | 0.08412 |
| vector(size_type, value_type, allocator_type) |    0.08825 | 0.08548 |
| vector(vector)                                |    0.03764 | 0.03743 |
| insert(ForwardIt, ForwardIt)                  |    0.22229 | 0.27777 |
| push_back(value_type)                         |    0.01198 | 0.01790 |
| resize(size_type, value_type)                 |    0.09929 | 0.23234 |
+-----------------------------------------------+------------+---------+

set<T>
+-----------------------------------------------+------------+---------+
|         function                              | system(ms) | my(ms)  |
+-----------------------------------------------+------------+---------+
| count()                                       |    0.00199 | 0.00178 |
| find(key_type)                                |    0.00570 | 0.00529 |
| upper_bound(key_type)                         |    0.00197 | 0.00210 |
| lower_bound(key_type)                         |    0.00194 | 0.00212 |
| erase(key_type)                               |    0.00178 | 0.00209 |
| insert(value_type)                            |    0.03965 | 0.04766 |
| clear()                                       |    0.06644 | 0.08610 |
| erase(iterator, iterator)                     |    0.00035 | 0.00055 |
| equal_range(key_type)                         |    2.24509 | 3.83404 |
| erase(iterator)                               |    0.00086 | 0.00268 |
+-----------------------------------------------+------------+---------+

map<T, U>

+-----------------------------------------------+------------+---------+
|         function                              | system(ms) | my(ms)  |
+-----------------------------------------------+------------+---------+
| operator[](key_type)                          |    5.71076 | 5.24225 |
| find(key_type)                                |    5.50837 | 5.17741 |
| count(key_type)                               |    5.54869 | 5.21871 |
| lower_bound(key_type)                         |    2.09687 | 2.11234 |
| upper_bound(key_type)                         |    2.06051 | 2.07381 |
| clear()                                       |    0.09021 | 0.09198 |
| insert(value_type)                            |    0.04111 | 0.06012 |
| erase(iterator, iterator)                     |    0.00034 | 0.00058 |
| equal_range(key_type)                         |    2.20543 | 3.92549 |
| erase(key_type)                               |    0.00163 | 0.00316 |
| erase(iterator)                               |    0.00129 | 0.00265 |
+-----------------------------------------------+------------+---------+

(These tables were generated using Ozh's tool:
https://ozh.github.io/ascii-tables/)

improvements
============
There are quite some improvements that can still be implemented. For example,
equal_range for both map and set is currently implemented using lower_bound and
upper_bound, but this can be (probably) be optimized by starting the search for
the either lower_bound or upper_bound from eachother. Also currently
vector<T>::resize is currently implemented quite naively, which can be seen in
the data above. I also did not profile my code, so that's also something I
could do to find the bottlenecks and make it even faster. Lastly, I could
insert guidance on which branches are taken often or not, something that
EASTL (a STL impementation by EA which I used as reference) used heavily.


references
============
EASTL (https://github.com/electronicarts/EASTL)
LLVM libc++ (https://github.com/llvm/llvm-project)
GNU libc++ (https://github.com/llvm/llvm-project)

special thanks
============
Special thanks to mjoosten42 for helping me test my code
https://github.com/mjoosten42