Splice() on Std::List and Iterator Invalidation

C++11 std::list iterator invalidation after splicing

list iterators point to elements. By splicing a range of elements, you've changed which container those iterators point into. The element is no longer an element of A; it is an element of B. Iterators are preserved across spliceing, so p and p_copy will still point to those elements.

They're just iterators into different containers now.

std::list::splice invalidates iterators. Rationale?

In C++11 splice does not invalidate the iterators, but make them refer to the appropriate elements in the *this container. This is all described in 23.3.5.5.

STL list::splice - iterator validity

It's only a guess, but they might have written that to imply that it is now "invalid" in the sense that it is no longer a valid iterator of mylist1, but instead becomes a valid iterator of mylist2.

But still, and I guess you already knew that, it is a valid iterator, so the wording is misleading. You need to be careful, though, as it means that after the second splice-operation, for example, you can no longer do:

std::distance( mylist1.begin(), it );

but need to use

std::distance( mylist2.begin(), it );

as the first would be illegal.

The standard clearly defines it that way in:

23.3.5.5 list operations [list.ops]

void splice(const_iterator position, list& x, const_iterator i);
void splice(const_iterator position, list&& x, const_iterator i);

⁷ Effects: Inserts an element pointed to by i from list x before position and removes the element from x. The result is unchanged if position == i or position == ++i. Pointers and references to *i continue to refer to this same element but as a member of *this. Iterators to *i (including i itself) continue to refer to the same element, but now behave as iterators into *this, not into x.

So, if your compiler/STL invalidates the iterator, this is clearly a bug.

std::list - are the iterators invalidated on move?

For containers in general, only swap guarantees that iterators remain valid (and point into the swapped containers).

For std::list, the special member function splice() guarantees that iterators retain their expected meaning.

In general, constructing a container from an rvalue doesn't make guarantees about iterators; the only general requirement is that the new container has the "same value" as the container it was constructed from had originally.

(You can imagine debug iterator implementations that store a reference to the container, and that reference would become dangling after a move.)

I can move elements within the std::list without invalidating iterators nor references, but how?

But how may I arbitrarily swap the positions of two elements while preserving the values of all iterators?

As suggested by @cpplearner, use .splice().

It can operate on individual elements or ranges. It can also transfer elements across lists.

Here's a simple example demonstrating how to move a single element.

std::list<int> list{1,2,3,4,5};

// This element will be moved
auto source = std::find(list.begin(), list.end(), 4);

// It will be inserted before this element
auto destination = std::find(list.begin(), list.end(), 2);

list.splice(destination, list, source);
// ^                      ^
// |                      `- A list to move from
// `- A list to move to   

// Prints `1 4 2 3 5`.
for (int it : list) std::cout << it << ' ';

---

Related Topics