list::splice and iterator invalidation

[Mark P]

What should be the output of the following program? The SGI STL docs
say that all iterators remain valid during a splice operation. The
dinkumware library reference says that iterators to spliced elts. may be
invalidated. I have one system (Linux gcc) which outputs:

0
3

and another (HP aCC) which outputs:

0
2

Any clarification would be most appreciated.

Thanks,
Mark

// pasted code

#include <iostream>

using namespace std;

struct S
{
S(int i) : i(i) {}
int i;
};

typedef list<S> sl;
typedef sl::iterator sli;

void print(sl& l)
{
for (sli it = l.begin(); it != l.end(); ++it)
cout << it->i << endl;
}

int main()
{

sl a;
a.push_back(0);
sl b;
b.push_back(1);

sli bi = b.begin();
*bi = 2;

a.splice(a.end(),b);
*bi = 3;

print(a);
}

 

[Alf P. Steinbach]

* Mark P:

The SGI STL docs
say that all iterators remain valid during a splice operation. The
dinkumware library reference says that iterators to spliced elts. may be
invalidated.

The standard says, for the two-argument version of splice, "Invalidates all
iterators and references to the list x", where x is the second argument, and
where presumably "to the list" means "to elements of the list", not to the
list itself.

This unclarity is to my mind an obvious defect in the standard, as is also the
inclusion of references in the things to be invalidated: constant time means
no copying, just pointer shuffling, and so raw pointers and references to
elements should not, as I see it, be invalidated, and _if_ references are
invalidated, then also raw pointers should be invalidated. But anyway,
iterators are certainly invalidated. Unless the whole paragraph is botched.

Thus you have Undefined Behavior, and both implementations you tried are
Right.

 

[John Harrison]

* Mark P:



The standard says, for the two-argument version of splice, "Invalidates all
iterators and references to the list x", where x is the second argument, and
where presumably "to the list" means "to elements of the list", not to the
list itself.

This unclarity is to my mind an obvious defect in the standard, as is also the
inclusion of references in the things to be invalidated: constant time means
no copying, just pointer shuffling, and so raw pointers and references to
elements should not, as I see it, be invalidated, and _if_ references are
invalidated, then also raw pointers should be invalidated. But anyway,
iterators are certainly invalidated. Unless the whole paragraph is botched.

Thus you have Undefined Behavior, and both implementations you tried are
Right.

This is a known defect

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#250

and

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#278

john