I was reading about lists in Standard Template library in C++. I read elements can not be accessed using index. Can any one please let me know how the lists are stored in memory? Is it sequential? I know how linked lists are implemented. Are the lists in STL are also implemented in same fashion? i.e. a pointer will be having address of next element?
If that is the case, how increment of iterator is able to point to the next element in the list? Is the increment operator on iterator is overloaded?
std::list is usually implemented as a linked list, each node storing a list element and pointers to previous and next nodes. It is common to implement linked lists with bounding fake nodes in the very beginning of the list and at the end of it (it makes the implementation a bit simpler and more beautiful). In gcc implementation they use only one node both for the starting and ending fake nodes, so the list is actually cyclic. This fake node does not contain any list element (if it contained, it would be a problem by many reasons). This node has a non-template type (lets say basic_node) which looks like this:
struct basic_node
{
basic_node * prev, * next;
};
Other, value-containing, nodes are templated:
template <typename T>
struct node : basic_node
{
T value;
};
std::list::iterator stores a pointer to basic_node. This gives the following advantage: most of the iterator's code is independent of the template parameter. For example, to increment the iterator, we can just do something like node_ptr = node_ptr->next;, where node_ptr has type basic_node.
When dereferencing, std::list<T>::iterator can cast the pointer to node to appropriate templated node: return static_cast<node<T> *>(node_ptr)->value;.