how elements are stored in list of STL in C++

Question

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?

Answer 1

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;.

Answer 2

std::list<> is a sequence container, as are std::vector<>, std::deque. How they are implemented is implementation-dependent. But their behavior and required characteristics are defined by the standard.

Lists, for example, must have constant-time insertion. A vector does not require constant time insertion but does have other requirements (such as const-time random-access). Such requirements gravitate implementations to common algorithms (std::list is commonly a double-linked-list in the traditional-sense, for example).

Iterators "work" on containers such as std::list<> by attaching container-state to the iterator. A list iterator, for example, could know its iterating container and its "place" in the sequence enumeration via a pointer to the current node in the underlying implementation. Advancing the iterator simply means having it move through the internal node pointer to that pointer's "next".

Don't try to attach too much meaning to the implementation underneath the mandated behavior. So long as the behavioral requirements are met, the underlying implementation could quite-literally be anything.

Answer 3

List is not stored sequentially. You're looking for std::vector if that's what you want.

From documentation, "Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions. List containers are implemented as doubly-linked lists"