list: node stability, splice, and locality

Constant time assumes you already have the position

list provides bidirectional iterators and no random-access subscript. Given an iterator, inserting one element and erasing that element are constant time; walking from the beginning to the k-th position still takes a linear number of steps. "Middle-of-list erasure is fast" therefore omits the cost of finding the position and cannot be used as-is to judge a complete business operation.

Insertion does not invalidate iterators and references to existing elements. Erasure invalidates only handles to the erased element. Typical implementations are independent nodes with predecessor and successor links. Pointer chasing, node allocation, and weaker locality during a scan can cost more than moving small objects. The standard specifies operation semantics and complexity; it does not specify node layout or cache behavior on a particular processor.

splice transfers element identity

dst.splice(pos, src, it) places one element before the target position without copying or moving that element object. Its references and iterators keep pointing at the same object; only the owning list changes. That property fits to-do queues, grouping, or recency order when you already hold node handles and do not want to reconstruct objects.

Transfer of a whole list and transfer of a single element are constant time. Range transfer is constant time inside the same list and linear time across two lists; do not ignore the standard complexity because "only a few links change." Allocators must compare equal. The whole-list overload cannot take the destination list as its own source. The range overload requires that the target position not lie inside the transferred range.

Prefer member operations that use the node structure

std::sort requires random-access iterators and cannot be used on list. Use list::sort, which provides a stable sort and keeps element iterators. list::remove_if actually erases nodes, whereas generic std::remove_if only packs the logical range by move assignment: it does not change the container size and does not use the advantage of list nodes.

The example moves one item from a pending list into a running list and checks address, contents, and the visible order of both lists. After the transfer, do not pass that iterator to erase on the source list; ownership has already changed. If the application only reads a batch of numbers and sorts them, vector is usually the simpler default. Choose list when node stability or frequent splicing is genuinely required, not because a textbook called the structure a linked list.

Pitfalls

• Before splicing across two lists, the allocators must compare equal. Lists that use different pmr resources cannot be spliced merely because their element types match.
• Iterator stability on list is not ownership stability: an iterator that was spliced belongs with the destination list, not with the source.

Minimum C++11 · complete program · Download .cpp

#include <cassert>
#include <iostream>
#include <iterator>
#include <list>
#include <string>

int main() {
    std::list<std::string> pending{"parse", "compile", "link"};
    std::list<std::string> running{"fetch"};
    auto job = std::next(pending.begin());
    const std::string* address = &*job;
    running.splice(running.end(), pending, job);
    assert(&*job == address && *job == "compile");
    assert((pending == std::list<std::string>{"parse", "link"}));
    assert((running == std::list<std::string>{"fetch", "compile"}));
    running.splice(running.begin(), running, job);
    assert(running.front() == "compile");
    auto next = running.erase(job);
    assert(next != running.end() && *next == "fetch");
    std::cout << pending.size() << ' ' << running.front() << '\n';
}

Compile locally

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-list.cpp -o example && ./example

Expected result

2 fetch

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

You already hold an iterator hit to an element in a list and need that element to become the first one, while keeping external references valid. Give the operation and explain its cost.

Check the sources

• Working draft [list.ops]: splice, remove, and sort

Drafts and official chapters change. The version mark is only the example’s minimum.