In libstdc++ and libc++ the internal nodes for lists (e.g. list and forward_list) and other trees are constructed in (at least) two parts: a node base class; and the node class itself. For example, rather than:
struct sl_full_node {
sl_full_node *p;
int value;
};
...we would see something like:
struct sl_node_base {
sl_node_base *p;
};
struct sl_node : sl_node_base {
int value;
};
A simple, self-contained example of this idiom can be found in the singly linked list proposal from 2008 here. What are the benefits of this approach?
All STL containers require to provide an end() sentinel. This means that, if bidirectional iteration is supported, there must be a valid past-the-end position on which a decrement operation can be performed through the iterator interface. In this part, only node-based containers that allow bidirectional iteration will be treated, and therefore the std::forward_list container will be momentarily ignored.
If the end() sentinel were simply represented by any sentinel value, such as a null pointer, it would not be possible to perform the aforementioned decrement operation in order to move to the previous node. One way to solve this issue is the use of a "dummy node".
In the libstdc++ and libc++ implementations, this node is statically allocated in order that it is present in the container throughout the lifetime of the object and allows for a valid past-the-end position even if the sequence is completely empty. It is important to note that the word "sequence" is used to refer to the in-order iteration of all values in the container, regardless of whether the nodes are arranged linearly or structured in a more complex graph (std::set).
If the result were achieved by allocating a complete node, this would result in two side effects:
T size;T is stored directly in the node, when the object is constructed, a method should be found to avoid the T object construction.The last issue can be solved by replacing the type T with an aligned storage, but this would not solve the issue of occupied space. This situation makes it necessary to introduce a specific structure for the dummy node, which contain only pointers. However, the creation of such a structure would lead to an inter-operability problem because a pointer to node can not be converted to a pointer to dummy node and vice versa.
A solution consists of deriving the complete node from the dummy node, to which the data attribute, or an aligned storage, is added.
Example:
struct _List_node_base
{
_List_node_base* _M_next;
_List_node_base* _M_prev;
};
template <typename _Tp>
struct _List_node : public _List_node_base
{
_Tp _M_data;
};
Similar reasoning can be applied to the std::forward_list container, which, however, requires a before_begin() sentinel on which an increment operation can be performed through the iterator interface.