I am programming for class LinkedList, but I don't know what is the correct way to implement iterator end(). In case of begin(), I can simply pass the Head, but end() points to one-past-the-last element. This means that I can't pass Tail directly and iterate like Tail = Tail->prev.
Which is the correct way to implement iterator end() function?
Should a memory be allocated as a dummy node or should some conditions be implemented in operator++ and operator--?
How does std::list do this?
In all node-based containers that model ReversibleContainer, including std::list, the end() sentinel must be a valid past-the-end position on which a decrement operation can be performed through the iterator interface. If it were simply represented by any sentinel value, such as a null pointer, it would not be possible to perform the aforementioned operation to move to the previous node. One way to solve this issue is the use of a "dummy node".
The dummy node is dynamically allocated. As the container is constructed, a full node is allocated through the provided allocator and all member attributes, except the value, are constructed. In this way, the type T is guaranteed not to be initialized.
This design allows to implement the move constructor, move assignment operator and swap() member function in an easy way, since it is sufficient to work on the pointer that refers to the dynamically-allocated node. On the other hand, it requires to perform an allocate operation for the instantiation of the dummy node, which makes the default constructor potentially-throwing.
However, the most important draw effect is another: the space occupied by the dummy node is not limited by the number of pointers, which are the only member attributes required to allow linkage with the other nodes, but is proportional to the type T size.
The dummy node is statically allocated in order that it is present in the container throughout the lifetime of the object. This allows to avoid any allocate operation, making the construction of the node non-throwing.
To solve the issue with the occupied space, the implementation exploits two structures: the base node, which contains only pointers; the full node, which inherits from the previous one and adds a member attribute for the value type.
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;
};
The base node is used only to construct the dummy node, while all elements are allocated as full modes. Furthermore, the inter-operability between pointers to the base and full nodes is guaranteed by the inheritance, even if it may require some explicit conversions.
To reduce the memory overhead, it is also used a trick: since the container requires to keep track of the first node, the next pointer of the sentinel node can be exploited to handle it. This creates a circular-linked list, where the sentinel node represents both the before-the-beginning and past-the-end positions. As a result, all insert and erase operations can be performed on both the first and last elements as in any other position.
Both designs have pros and cons, but the latter is more suitable to implement a linked-list container with a minimal memory overhead.
Provided that the class contain a base node as member attribute _head and define the types iterator and const_iterator, the begin() and end() member functions can be implemented in the following way.
iterator begin()
{ return iterator{this->_head.next}; }
const_iterator begin() const
{ return const_iterator{this->_head.next}; }
iterator end()
{ return iterator{&this->_head}; }
const_iterator end() const
{ return const_iterator{&this->_head}; }