List Object Structure

The std::list in C++ Standard Template Library is implemented as a doubly-linked circular list. Each node in the list inherits from a common base class called _List_node_base.

The list container itself contains a single header node, which is allocated on the stack. Individual elements are dynamically allocated on the heap through the new operator.

std::list<int> l;

The size of a list object itself is fixed at 24 bytes on most implementations (when using GCC 13.1), which corresponds to the size of its internal header structure. This header contains pointers to manage the linked list structure.

One key characteristic of list is that insertions and deletions can be performed in constant time when an iterator to the position is available. However, due to its non-contiguous memory layout, random access is not supported efficiently.

List Iterators

Implementation Details

Since list elements are not stored contiguously, its iterators cannot be implemented as simple pointers like in vector. Instead, they are implemented as bidirectional iterators with the following capabilities:

The iterator is essentially a wrapper around a _List_node_base* pointer. Here's a simplified representation:

template<typename T>
struct ListIterator {
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;

    __detail::_List_node_base* node_ptr;
};

Iterator Construction

Common operations for obtaining iterators:

// Get begin iterator (first element)
iterator begin() {
    return iterator(this->_M_impl._M_node._M_next);
}

// Get end iterator (past-the-end)
iterator end() {
    return iterator(&this->_M_impl._M_node);
}

Dereferencing and Navigation

Key operations for accessing elements and moving through the list:

// Dereference operator
reference operator*() const {
    return *static_cast<_Node*>(node_ptr)->_M_valptr();
}

// Member access operator
pointer operator->() const {
    return static_cast<_Node*>(node_ptr)->_M_valptr();
}

// Pre-increment
ListIterator& operator++() {
    node_ptr = node_ptr->_M_next;
    return *this;
}

// Post-increment
ListIterator operator++(int) {
    ListIterator tmp = *this;
    node_ptr = node_ptr->_M_next;
    return tmp;
}

// Pre-decrement
ListIterator& operator--() {
    node_ptr = node_ptr->_M_prev;
    return *this;
}

// Post-decrement
ListIterator operator--(int) {
    ListIterator tmp = *this;
    node_ptr = node_ptr->_M_prev;
    return tmp;
}

Comparison Operators

friend bool operator==(const ListIterator& a, const ListIterator& b) {
    return a.node_ptr == b.node_ptr;
}

friend bool operator!=(const ListIterator& a, const ListIterator& b) {
    return a.node_ptr != b.node_ptr;
}

Iterator Invalidation

List iterators have differant invalidation rules compared to vector:

• Inserting elements doesn't invalidate existing iterators
• Deleting an element only invalidates iterators pointing to that specific element
• Other elements remain unaffected due to the linked list structure

This makes list more suitable for algorithms requiring stable iterators to elements that aren't being modified.