Scott Meyers wrote:

> I'm still confused about the high-level model that determines when
> iterators are or are not invalidated.  Consider:
>
>   list<int> list1;           // list1 is an empty list
>   list<int> list2(1);        // list2 is a list with one element
>
>   list<int>::iterator iter =
>     list2.begin();           // iter points to list2's only element
>
>   list1.swap(list2);         // per 23.1/10 (last bullet), iter remains
>                              // valid and now points to list1's only
>                              // element
>
> So a valid iterator that used to point into list2 now points into list1,
> but continues to be valid.
>
> Now consider the following, which is identical to the above, except that
> the call to swap has been replaced by a call to splice:
>
>   list<int> list1;           // list1 is an empty list
>   list<int> list2(1);        // list2 is a list with one element
>
>   list<int>::iterator iter =
>     list2.begin();           // iter points to list2's only element
>
>   list1.splice(list1.end(),  // per 23.2.2.4/4, iter is invalidated
>                list2);
>
> In both cases, we're moving a list node from list2 to list1.  If we move it
> via swap, an iterator pointing to that node remains valid.  If we move it
> via splice, an iterator pointing to that node is invalidated.  Why?
>

This is, of course, a bug in the standard. I have previously submitted a defect
report on it (issue 250), so hopefully it will be fixed in some future
technical corrigenda.
Having list invalidate its iterators on splice has to be a bug- the fact that
such node-based data structures allow one to splice nodes (in constant time)
between data structures whilst maintaining pointers and iterators to the moved
node (by essentially redefining them to be pointers and iterators into the
destination container) is a major motivation for their use and is required to
implement such self referential data structures as some types of graph. If it
was not guaranteed that std::list similarly moved its iterators on splice
without invalidating them, then std::list would (gratuitously) be made quite
useless for many uses traditionally needing a hand-crafted doubly-linked list.
My code certainly relies upon this and the SGI STL quite sensibly guarantees
it.

Ironically, the standard also has a second bug whereby swap is deemed to to
have splice-like semantics (i.e. not invalidating iterators) when its
traditional semantics should be value copy which should *not* move pointers and
iterators to the destination data structure but rather must invalidate them!
This is a relatively innocuous bug so I haven't submitted a defect report on it
(its major practical consequence is that it disallows some iterator validity
checks that a debug build could otherwise perform).
I suspect that the reason this splice-like semantics was given to swap was in
an attempt to have a simple wording to specify that the swap implementation
uses a constant-time pointer swap that can't throw an out-of-memory exception,
and the consequences of generalizing this requirement into a semantic notion on
iterators was not fully appreciated.

Brian Parker,
brianp@research.canon.com.au


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

I'm still confused about the high-level model that determines when
iterators are or are not invalidated.  Consider:

  list<int> list1;           // list1 is an empty list
  list<int> list2(1);        // list2 is a list with one element

  list<int>::iterator iter =
    list2.begin();           // iter points to list2's only element

  list1.swap(list2);         // per 23.1/10 (last bullet), iter remains
                             // valid and now points to list1's only
                             // element

So a valid iterator that used to point into list2 now points into list1,
but continues to be valid.

Now consider the following, which is identical to the above, except that
the call to swap has been replaced by a call to splice:

  list<int> list1;           // list1 is an empty list
  list<int> list2(1);        // list2 is a list with one element

  list<int>::iterator iter =
    list2.begin();           // iter points to list2's only element

  list1.splice(list1.end(),  // per 23.2.2.4/4, iter is invalidated
               list2);

In both cases, we're moving a list node from list2 to list1.  If we move it
via swap, an iterator pointing to that node remains valid.  If we move it
via splice, an iterator pointing to that node is invalidated.  Why?

On a note that I suspect is related, if I'd used a pointer instead of an
iterator, the pointer would remain valid in both cases.  But if I'd used a
reference, the results would be the same as for an iterator:  invalidated
via splice, but not via swap.

I'm so confused.  Can anybody make sense of this for me?

Thanks,

Scott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Scott Meyers wrote:
[...]
> In both cases, we're moving a list node from list2 to list1.  If we move it
> via swap, an iterator pointing to that node remains valid.  If we move it
> via splice, an iterator pointing to that node is invalidated.  Why?
>
> On a note that I suspect is related, if I'd used a pointer instead of an
> iterator, the pointer would remain valid in both cases.  But if I'd used a
> reference, the results would be the same as for an iterator:  invalidated
> via splice, but not via swap.
>
> I'm so confused.  Can anybody make sense of this for me?

Where did you get the idea that using splice would invalidate any iterator(s)?
CD2 does not seem to say that anywhere I could find.
SGI's online documentation for STL list
http://www.sgi.com/tech/stl/List.html
clearly states that splice does NOT invalidate any iterator(s).

Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here:
http://table.jps.net/~vert/

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Scott Meyers <smeyers@aristeia.com> writes:

> In both cases, we're moving a list node from list2 to list1.  If we
> move it via swap, an iterator pointing to that node remains valid.
> If we move it via splice, an iterator pointing to that node is
> invalidated.  Why?

SGI's documentation=B9 suggests that splice() doesn't invalidate any
iterators.

My first answer, despite SGI's contrary guarantee, is that
invalidating the iterators allows the implementation to not share nodes
among different lists. That is, the original node gets destroyed after
a new node get created in the target list and the value gets
copied. Dinkum's documentation=B2 suggests that such a sequence will
occur when the two lists' allocators differ.


Footnotes:=20
=B9 http://www.sgi.com/tech/stl/List.html
=B2 http://www.dinkum.com/htm_cpl/list.html#list::splice

--=20
Steven E. Harris        :: steven.harris@tenzing.com
Tenzing                 :: http://www.tenzing.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Fri,  9 Mar 2001 22:18:37 GMT, Dennis Yelle wrote:
> Where did you get the idea that using splice would invalidate any iterator(s)?

>From the standard.  I cited 23.2.2.4/4, which says:

  Effects: Inserts the contents of x before position and x becomes
  empty. Invalidates all iterators and references to the list x.

> CD2 does not seem to say that anywhere I could find.

CD2 doesn't count.

> SGI's online documentation for STL list
> http://www.sgi.com/tech/stl/List.html
> clearly states that splice does NOT invalidate any iterator(s).

SGI's documentation doesn't count.

Honestly, you really should spring for a copy of the Standard, especially
if you're going to contribute to this newsgroup.  Eighteen bucks just isn't
that much.

On Fri,  9 Mar 2001 22:19:15 GMT, Steven E. Harris wrote:
> My first answer, despite SGI's contrary guarantee, is that
> invalidating the iterators allows the implementation to not share nodes
> among different lists. That is, the original node gets destroyed after
> a new node get created in the target list and the value gets
> copied.

This is not a valid implementation, because 23.2.2.4/5 says that no
exceptions are thrown.  That means no user-defined copy constructor or
assignment operator can be called.

>Dinkum's documentation suggests that such a sequence will
>occur when the two lists' allocators differ.

If they're two lists of the same type (as they were in my example), this is
again an invalid implementation, and for the same reason.  If the lists are
of different types, e.g.,

  list<int, Allocator1<int> > L1;
  list<int, Allocator2<int> > L2;

then the standard has nothing to say about it, because there is no support
in the standard for splicing across list types.  Dinkum might offer it as
an extension, however.

Scott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Scott Meyers wrote:
[...]
> Honestly, you really should spring for a copy of the Standard, especially
> if you're going to contribute to this newsgroup.  Eighteen bucks just isn't
> that much.

If the only cost was 18 dollars, I would have a copy already.
My understanding is that one has to agree to some agreement in
order to buy it.  I don't agree to agreements to buy documents.
And I don't think anyone else should either.

Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here:
http://table.jps.net/~vert/

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Scott Meyers wrote:
...
> This is not a valid implementation, because 23.2.2.4/5 says that no
> exceptions are thrown.  That means no user-defined copy constructor or
> assignment operator can be called.

It should do this only when the allocators are inequivalent. Per
20.1.5p5, the semantics are implementation-defined in that case, so it's
not an invalid implementation.

...
> >Dinkum's documentation suggests that such a sequence will
> >occur when the two lists' allocators differ.
>
> If they're two lists of the same type (as they were in my example), this is
> again an invalid implementation, and for the same reason.  If the lists are

Incorrect. Section 20.1.5p4 does allow implementation of
standard-defined containers in a way that assumes that all allocators of
a given type compare equal. However, implementations are not required to
make that assumption. In fact, they're explicitly encouraged in the next
paragraph to support allocator types with inequivalent instances.

> If they're two lists of the same type (as they were in my example), this is
> again an invalid implementation, and for the same reason.  If the lists are
> of different types, e.g.,
>
>   list<int, Allocator1<int> > L1;
>   list<int, Allocator2<int> > L2;
>
> then the standard has nothing to say about it, because there is no support
> in the standard for splicing across list types.  Dinkum might offer it as
> an extension, however.

This isn't about allocators of different types, this is about
inequivalent allocators of the same type. Which is perfectly legal
(though not guaranteed to work with standard containers). Why would the
Allocator requirements require that operator==() be defined, if it were
never envisioned that it might return false?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Sat, 10 Mar 2001 13:20:03 GMT, James Kuyper Jr. wrote:
> It should do this only when the allocators are inequivalent. Per
> 20.1.5p5, the semantics are implementation-defined in that case, so it's
> not an invalid implementation.

Here's that paragraph:

  Implementors are encouraged to supply libraries that can accept
  allocators that encapsulate more general memory models and that support
  non-equal instances. In such implementations, any requirements imposed on
  allocators by containers beyond those requirements that appear in Table
  32, and the semantics of con-tainers and algorithms when allocator
  instances compare non-equal, are implementation-defined.

What exactly are the "semantics of containers"?  The standard has this to
say about one form of splice (23.2.2.4):

  void splice(iterator position, list<T,Allocator>& x);
  3 Requires: & x != this.
  4 Effects: Inserts the contents of x before position and x becomes
             empty. Invalidates all iterators and references to the list x.
  5 Throws: Nothing
  6 Complexity: Constant time.

When using this form of splice with inequivalent allocator objects, what
may the implementation change?
  - The signature (e.g., to add a throw specification)?
  - The requirements (e.g., to require that x.size() > 0)?
  - The effects (e.g., to invalidate nothing)?
  - The throw clause (e.g., to allow anything to be thrown)?
  - The complexity (e.g., to make the operation linear)?

Is an implementation permitted to change all of the above?

Scott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Fri,  9 Mar 2001 17:13:27 GMT, Scott Meyers <smeyers@aristeia.com>
wrote:

> I'm still confused about the high-level model that determines when
> iterators are or are not invalidated.  Consider:
>
>   list<int> list1;           // list1 is an empty list
>   list<int> list2(1);        // list2 is a list with one element
>
>   list<int>::iterator iter =
>     list2.begin();           // iter points to list2's only element
>
>   list1.swap(list2);         // per 23.1/10 (last bullet), iter remains
>                              // valid and now points to list1's only
>                              // element
>
> So a valid iterator that used to point into list2 now points into list1,
> but continues to be valid.

Now do

list2.erase(iter);

The iterator is obviously invalid.  You should submit a DR.

But

cout << *iter;

works fine.

> Now consider the following, which is identical to the above, except that
> the call to swap has been replaced by a call to splice:
>
>   list<int> list1;           // list1 is an empty list
>   list<int> list2(1);        // list2 is a list with one element
>
>   list<int>::iterator iter =
>     list2.begin();           // iter points to list2's only element
>
>   list1.splice(list1.end(),  // per 23.2.2.4/4, iter is invalidated
>                list2);

Now do

list1.erase(iter);

The iterator is obviously invalid.  This is right.

But

cout << *iter;

works fine.

> On a note that I suspect is related, if I'd used a pointer instead of an
> iterator, the pointer would remain valid in both cases.  But if I'd used a
> reference, the results would be the same as for an iterator:  invalidated
> via splice, but not via swap.

I don't think so.  I assume that all pointer questions default to
&reference.  If the reference is invalid, so is the pointer.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Scott Meyers wrote:
>
> On Sat, 10 Mar 2001 13:20:03 GMT, James Kuyper Jr. wrote:
> > It should do this only when the allocators are inequivalent. Per
> > 20.1.5p5, the semantics are implementation-defined in that case, so it's
> > not an invalid implementation.
>
> Here's that paragraph:
>
>   Implementors are encouraged to supply libraries that can accept
>   allocators that encapsulate more general memory models and that support
>   non-equal instances. In such implementations, any requirements imposed on
>   allocators by containers beyond those requirements that appear in Table
>   32, and the semantics of con-tainers and algorithms when allocator
>   instances compare non-equal, are implementation-defined.
>
> What exactly are the "semantics of containers"?  The standard has this to
> say about one form of splice (23.2.2.4):
>
>   void splice(iterator position, list<T,Allocator>& x);
>   3 Requires: & x != this.
>   4 Effects: Inserts the contents of x before position and x becomes
>              empty. Invalidates all iterators and references to the list x.
>   5 Throws: Nothing
>   6 Complexity: Constant time.
>
> When using this form of splice with inequivalent allocator objects, what
> may the implementation change?
>   - The signature (e.g., to add a throw specification)?
>   - The requirements (e.g., to require that x.size() > 0)?
>   - The effects (e.g., to invalidate nothing)?
>   - The throw clause (e.g., to allow anything to be thrown)?
>   - The complexity (e.g., to make the operation linear)?

The only requirements that are implementation-defined are ones that are
"imposed on allocators
by containers" and "beyond those in Table 32". The Table 32 requirements
still apply, as do those in the Containers clause. There's just a
possibility that there may be additional requirements. Syntax refers to
what your program says; semantics refers to what an implementation does
as a result of executing it. That covers the effects, throws, and
complexity clauses, I believe. The reason the standard allows
implementations so much freedom in this case is that no one had a lot of
experience with containers that allow inequivalent allocators. The
intent is to allow implementations the freedom they need to innovate
while gaining that experience. Therefore, if innovation translates as
"unacceptable risk" for your application, stay away from such
allocators.

The signature is a matter of the language syntax, not the semantics, so
this 20.1.5p5 isn't relevant there. The restrictions remain those of
17.4.4.3p2: "A call to a global function signature described in Clauses
18 through 27 behaves the same as if the implementation declares no
additional global function signatures." It says the same about member
function calls in 17.4.4.4p3.

However, keep in mind that the throw specification is NOT part of the
function signature - see 1.3.10. The rules on throw specifications are
given in section 17.4.4.8p1: "An implementation may strengthen the
_exception-specification_ for a function by removing listed exceptions."
For functions without a throw specification, p3 says "An implementation
may strengthen this implicit _exception-specification_ by adding an
explicit one". Other ways of strengthening a throw specification, such
as changing from a base class to a derived class, are apparently not
allowed. I'm not sure why. However, since very few standard library
functions have throw specifications, this isn't much of a restriction.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]