Given Node in Tree container:
#include <iostream>
template <class T>
class Tree {
struct Node {
Node(T val) : left(new Node()), right(new Node()), val(val) { /* value node */ }
Node() : left(nullptr), right(nullptr) { /* sentinal node */ }
Node *left, *right;
T val;
};
public:
T insert(T val) {
Node node(val);
return node.val;
}
};
int main() {
Tree<int> tree;
std::cout << tree.insert(42);
}
When I create a sentinel node using new Node() it initializes the val member using the default constructor T(). However, T, might not have a default constructor.
How can I create a sentinel node without calling the default constructor of T?
To prevent the value type from being initialized, you can replace the type T with an aligned storage. For simplicity, it is exploited a standard type trait, std::aligned_storage. In this way, the object can be constructed explicitly only.
template <typename T>
struct Node
{
std::aligned_storage_t<sizeof(T), alignof(T)> storage;
Node* left;
Node* right;
};
However, this design has a side effect: the construct operation of the node requires to manipulate the bits of the aligned storage to allow the construction of the value object. This increases the complexity of the implementation and requires introducing other components, either standard or created from scratch, to handle the bit manipulation.
An alternative involves keeping the original value type, but do not initialize it. Specifically, the class is allocated as a raw memory and then all member attributes, except the value attribute, are constructed. This technique is used by the MSVC library for the implementation of all node-based containers.
template <typename T>
struct Node
{
T value = std::declval<T>();
Node* left;
Node* right;
};
Although this design may seem effective, both of the above approaches have an important side effect: the space that is occupied by the sentinel node is not limited by the number of pointers, which are the only member attributes required to allow linkage with other nodes, but becomes proportional to the type T size. This means that, if the user specifies a value type whose size is particularly large, the sentinel node will require a significant amount of space to be instantiated, leading the container object to consume the same amount of memory as a full node even if the sequence is completely empty. Furthermore, if the sentinel node is instantiated directly in the container object, the memory usage may become intolerable.
The only way to solve the problem is to divide the node interface into two classes, the NodeBase class, which contains only the pointers, and the Node class, which inherits from the former and introduces the value attribute. Thus, the sentinel node is an instance of the base class, which can be embedded in the container or dynamically allocated at construction time, while all other nodes are instances of the derived class.
struct NodeBase
{
NodeBase* left;
NodeBase* right;
};
template <typename T>
struct Node
: public NodeBase
{
T value;
};
This saves a large amount of space for the sentinel node and does not require workarounds to prevent initialization of the value type. The only difficulty is the need to convert the NodeBase* pointer to a Node<T>* pointer and vice versa. Since the first type conversion is implicit, only the second case requires to be handled by the implementation.