Templated Binary Search Tree Documentation

In the following some brief descriptions of the classes involved in the project.

Description

A templated binary search tree implemented in C++ (compliant with the C++14 standard). The project is split into three files, each one of them contains the implementation of concept, and hence in each one of them we have a class declaration and definition.

Node.h

The implementation of the concept of a Node. A Node is templated on the type of the value, which in this project will be a std::pair with a key and a value, and must know its children and its parent. Therefore we have 4 data member. The pointers to the left and right child are unique_ptr, while the pointer to the parent is a raw pointer. If it were a unique_ptr, then we would end up with nodes that are pointed (uniquely) by more pointers, which is not correct.

Iterator.h

The class iterator is templated on the type 'T' of the Node, and on a boolean 'is_const', used to determine the const-ness of the iterator by exploiting std::conditional, a C++11 which determines at compile time the types of a member. The most important operator is the '++' (pre-increment), which allows to go the next (ordering by key) Node by returning a self-reference.

bst.h

This class contains the implementation of the Binary Search Tree. It's templated on the type of the key, on the type of the value, and on the type of the comparison operator, which is set to std::less by default. The data members are a std::unique_ptr to the head Node, and the comparison operator.