Wednesday, January 7, 2015

Behaviour of std::list::splice in the 2003 and 2011 C++ standards

There's an interesting corner case in the behaviour of std::list::splice. In the C++98/C++03 standards it is defined such that iterators referring to the spliced element(s) are invalidated. This behaviour changes in the C++11 standard, where iterators remain valid.

The text of the 2003 standard (section 23.2.2.4, p2, p7, p12) describes the splice operation as "destructively" moving elements from one list to another. If one list is spliced into another, then all iterators and references to that list become invalid. If an element is spliced into a list, then any iterators and references to that element become invalid, similarly if a range of elements is spliced then iterators and references to those elements become invalid.

This is changed in the 2011 standard (section 23.3.5.5, p2, p4, p7, p12) where the operation is still described as being destructive, but all the iterators and references to the spliced element(s) remain valid.

The following code demonstrates the problem:

#include <list>
#include <iostream>

int main()
{
  std::list<int> list;
  std::list<int>::iterator i;

  i=list.begin();
  list.insert(i,5);
  list.insert(i,10);
  list.insert(i,3);
  list.insert(i,4); // i points to end
  // list contains 5 10 3 4
  i--; // i points to 4
  i--; // i points to 3
  i--; // i points to 10

  std::cout << " List contains: ";
  for (std::list<int>::iterator l=list.begin(); l!=list.end(); l++)
  {
    std::cout << " >" << *l << "< ";
  }
  std::cout << "\n element at i = " << *i << "\n";

  std::list<int>::iterator element;
  element = list.begin();
  element++; // points to 10
  element++; // points to 3
  std::cout << " element at element = " << *element << "\n";

  list.splice(i,list,element); // Swap 10 and 3

  std::cout << " List contains :";
  for (std::list<int>::iterator l=list.begin(); l!=list.end(); l++)
  {
    std::cout << " >" << *l << "< ";
  }

  std::cout << "\n element at element = " << *element << '\n';
  element++; // C++03, access to invalid iterator
  std::cout << " element at element = " << *element << '\n';
}

When compiled to the 2011 standard the code is expected to work and produce output like:

 List contains:  >5<  >10<  >3<  >4<
 element at i = 10
 element at element = 3
 List contains : >5<  >3<  >10<  >4<
 element at element = 3
 element at element = 10

However, the behaviour when compiled to the 2003 standard is indeterminate. It might work - if the iterator happens to remain valid, but it could also fail:

 List contains:  >5<  >10<  >3<  >4<
 element at i = 10
 element at element = 3
 List contains : >5<  >3<  >10<  >4<
 element at element = 3
 element at element = Segmentation Fault (core dumped)