std::list

std::list<T> is a doubly-linked list: each element lives in its own heap-allocated node, with prev and next pointers wiring the nodes together. It gives up random access entirely and in exchange offers true O(1) insertion and erasure at any position you can name with an iterator. This chapter covers the internal structure, the operations a list supports, the splice family of constant-time list operations, iterator stability, and the question of when (if ever) you should actually pick a list in modern C++.