On Mon, 17 Jul 2000 02:56:15 CST, hinnant@anti-spam_metrowerks.com
(Howard Hinnant) wrote:

>In article <8knhc3$lca$1@nnrp1.deja.com>, Dietmar Kuehl
><dietmar_kuehl@yahoo.com> wrote:
>
>| Of course, this is plain ridiculous and clearly a programming bug but
>| you want implementations to provide reasonable behavior to this code.
>
>Such as?  Or was that your point?
>
>| I agree, however, that all references to elements in either list should
>| remain valid.
>
>But 20.1.5/5 is encouraging vendors to be able to deal with instances of
>allocators that do not compare equal.  To be able to handle that situation
>I think splice will have to invalidate the reference.

I don't see how using different allocators would require either
iterators or references to become invalid. Surely, once a list node is
allocated it just becomes a part of the linear address space until it
is deallocated.

Could you give some more details on the problem here?

Thanks,
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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <3975aea4.5241146@news.ozemail.com.au>,
brianjparker@ozemail.com.au (Brian Parker) wrote:

| >But 20.1.5/5 is encouraging vendors to be able to deal with instances of
| >allocators that do not compare equal.  To be able to handle that situation
| >I think splice will have to invalidate the reference.
|
| I don't see how using different allocators would require either
| iterators or references to become invalid. Surely, once a list node is
| allocated it just becomes a part of the linear address space until it
| is deallocated.
|
| Could you give some more details on the problem here?

Given two allocators: a1 and a2, if a1 != a2 then that means that a1 can
not deallocate pointers allocated by a2 and vice versa.  Consider an
element e1 which is a member of list l1 (having allocator instance a1).
The memory for e1 was allocated using a1.  If e1 is spliced into l2
(having allocator a2), then a2 is now responsible for deallocating e1.  It
can do this only if a1 == a2.

20.1.5 / 4 says that:

| Implementations of containers described in this International
| Standard are permitted to assume that their Allocator template
| parameter meets the following two additional requirements beyond
| those in (the table):
|
|        All instances of a given allocator type are required
|        to be interchangeable and always compare equal to
|        each other.

But then the next paragraph encourages vendors to ignore this paragraph. :-)

If a1 != a2 in my example above, (and if the implementor indeed wanted to
support this senario), then l2 would need to allocate a new node using a2
and copy e1 into it (instead of just fixing up the linked list pointers).
Then l1 would use a1 to deallocate the original e1 node.

-Howard

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Howard Hinnant wrote:

> In article <3975aea4.5241146@news.ozemail.com.au>,
> brianjparker@ozemail.com.au (Brian Parker) wrote:
>
> | >But 20.1.5/5 is encouraging vendors to be able to deal with instances of
> | >allocators that do not compare equal.  To be able to handle that situation
> | >I think splice will have to invalidate the reference.
> |
> | I don't see how using different allocators would require either
> | iterators or references to become invalid. Surely, once a list node is
> | allocated it just becomes a part of the linear address space until it
> | is deallocated.
> |
> | Could you give some more details on the problem here?
>
> Given two allocators: a1 and a2, if a1 != a2 then that means that a1 can
> not deallocate pointers allocated by a2 and vice versa.  Consider an
> element e1 which is a member of list l1 (having allocator instance a1).
> The memory for e1 was allocated using a1.  If e1 is spliced into l2
> (having allocator a2), then a2 is now responsible for deallocating e1.  It
> can do this only if a1 == a2.
>
> 20.1.5 / 4 says that:
>
> | Implementations of containers described in this International
> | Standard are permitted to assume that their Allocator template
> | parameter meets the following two additional requirements beyond
> | those in (the table):
> |
> |        All instances of a given allocator type are required
> |        to be interchangeable and always compare equal to
> |        each other.
>
> But then the next paragraph encourages vendors to ignore this paragraph. :-)
>
> If a1 != a2 in my example above, (and if the implementor indeed wanted to
> support this senario), then l2 would need to allocate a new node using a2
> and copy e1 into it (instead of just fixing up the linked list pointers).
> Then l1 would use a1 to deallocate the original e1 node.
>

But if you can't just fix up the linked list pointers then you can't implement a
constant time splice. Allocating new nodes and copying values would not be a
correct implementation of a constant-time splice and would defeat the whole point
of it.

To paraphrase, you are really saying that if, as encouraged by the standard in
20.1.5/5, an implementation provided lists that dealt with instances of
allocators that did not compare equal, then that implementation would need to
document the resulting implementation-defined semantics i.e. that splice could
not be supported- this is not simply a problem of iterator invalidation but goes
much deeper.

,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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <8knhc3$lca$1@nnrp1.deja.com>, Dietmar Kuehl
<dietmar_kuehl@yahoo.com> wrote:

| Of course, this is plain ridiculous and clearly a programming bug but
| you want implementations to provide reasonable behavior to this code.

Such as?  Or was that your point?

| I agree, however, that all references to elements in either list should
| remain valid.

But 20.1.5/5 is encouraging vendors to be able to deal with instances of
allocators that do not compare equal.  To be able to handle that situation
I think splice will have to invalidate the reference.

-Howard

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Sat, 15 Jul 2000 03:13:57 CST, Dietmar Kuehl
<dietmar_kuehl@yahoo.com> wrote:

>Hi,
>In article <396E9390.3EBDA542@research.canon.com.au>,
>  Brian Parker <brianp@research.canon.com.au> wrote:
>> I think that this clause (and the other splice clauses) should be
>> reworded to-
>> "all iterators and references remain valid, including iterators that
>> point to elements of x."
>
>This does not appropriately cover the semantics of the following
>program which would be considered well-defined under the rules you are
>giving:
>  #include <list>
>  #include <algorithm>
>  #include <iterator>
>  #include <iostream>
>
>  int main()
>  {
>    std::list<int> l1;
>    l1.push_back(17);
>    std::list<int>::iterator it = l1.begin();
>    std::list<int> l2;
>    l2.splice(l2.begin(), l1);
>
>    std::copy(it, l1.end(),
>              std::ostream_iterator<int>(std::cout, "\n"));
>  }
>
>Of course, this is plain ridiculous and clearly a programming bug but
>you want implementations to provide reasonable behavior to this code.
>I agree, however, that all references to elements in either list should
>remain valid.

No, your example is undefined under the suggested wording.

For a demonstration of this we need to use the following two facts.

(1)  At any given time an element is owned by a particular container
and so when one speaks of a valid iterator to an element, that implies
that one is actually speaking of a valid iterator into a particular
container.

(2) It is important to note the semantics of splice  is not that of
simple value copying- it is a destructive move of elements from one
list to another i.e. the moved element's owning container changes
after a splice.

Now, to analyse your example:

>    std::list<int> l1;
>    l1.push_back(17);
>    std::list<int>::iterator it = l1.begin();

it is now a valid pointer into l1

>    std::list<int> l2;
>    l2.splice(l2.begin(), l1);

The elements previously owned by l1 are now owned by l2, by the
definition of splice [2]. Therefore, any iterator that was into l1
that is now classed as valid must now, by definition [1], be
considered to be a valid iterator *into l2*.

Also, l1 is the empty list.

>    std::copy(it, l1.end(),
>              std::ostream_iterator<int>(std::cout, "\n"));
>  }

So, from the previous discussion, it is now a valid iterator into l2
and l1.end() is a valid iterator into l1 and so std::copy is undefined
as it needs an iterator range into a single container (and this should
in fact give an assert on a debugging implementation of copy).

QED.

By the way, this is not just some theoretical issue- splice is pretty
useless without it as if one is separately processing two lists then
one can't do a constant time splice of the two lists if one needs to
(redundantly) traverse the new combined list to update the iterators
into it. I for one currently rely upon the correct full semantics as
specified in the SGI STL in my algorithms.

I still think that this is bug in the standard's documentation of
list::splice.

Thanks for you comments,
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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Sat, 15 Jul 2000 07:01:31 CST, "Bill Wade" <bill.wade@stoner.com>
wrote:

>
>"Dietmar Kuehl" <dietmar_kuehl@yahoo.com> wrote
>>   Brian Parker <brianp@research.canon.com.au> wrote:
>> > I think that this clause (and the other splice clauses) should be
>> > reworded to-
>> > "all iterators and references remain valid, including iterators that
>> > point to elements of x."
>>
>> This does not appropriately cover the semantics of the following
>> program [ snip ]
>
>You have to be careful about what you read into invalid/valid.  A container
>class's iterator is valid if it points into some container's [begin,end]
>range.

Yes, the key point here being that when one speaks of a valid iterator
one is implicitly speaking of a valid iterator *into a specified
container* (it is always well-defined which container the iterator
currently points into as it is induced by the owning container of the
element pointed to).

>
>If I change your example to use swap instead of splice, the standard says
>that the iterator is valid, but your program still has the same problem.

The current definition of swap is another bug in the standard. The
irony here is that for swap which (properly) does *not* have the
semantics of destructive move of elements (unlike splice) but instead
should, of course, have the visible semantics of element copying, the
standard does specify that iterators remain valid !!

So, when we say

int a, b;
int* ap = &a;
int* bp = &b;
swap(a, b);

by the semantics of swap we expect only the values of a and b to be
exchanged, but not the pointers to the elements, by the definition of
value sematics swap.

And if we extend this usual value sematics definition of swap to a
vector of ints, then after a swap the *visible* sematics should be
that only the values of the elements have changed and *not* the owning
container of the elements.

If a particular implementation of swap can not maintain these usual
semantics of the element's owner remaining unchanged (e.g. an
optimised constant time pointer exchanging swap() ) then the correct
approach is to consider all iterators to be invalid after the swap-
the question of whether they might, by some implementation artifact,
actually now point into some other container is irrelevant.

But this does not hold for swap(std::vector<T>&, std::vector<T>&) as
currently defined as it specifies an optimised swap and it specifies
that all iterators remain valid after the swap, which implies
splice-like member moving sematics for swap.

The standard has given splice-like sematics to swap and taken them
from splice (perhaps we could just swap these two clauses in the
standard, but then any cross-references to them  would probably remain
pointing at the old definitions :-) )

The problem with swap(std::vector&, std::vector&)  is pretty innocuous
in that no-one would actually rely upon the splice-like iterator
semantics as (1) it will vary among other container classes depending
on the implementation method, and (2) it is a basically useless
semantics that could be emulated by using and swapping pointers to
containers instead. Its main practical effect is that it rules out
debugging implementations of vector picking up what would undoubtedly
be a bug in a real program.

But in the case of list::splice, the current wording of the standard
definitely should be fixed, in my opinion, as it unnecessarily limits
the functionality of splice in real algorithms.

,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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Section 23.2.2.4 list operations states that
void splice(iteratoror position, list<T, Allocator>& x);
*invalidates* all iterators and references to list x.

This is unnecessary and defeats an important feature of splice. In fact,
the SGI STL guarantees that iterators to x remain valid after splice.

I think that this clause (and the other splice clauses) should be
reworded to-
"all iterators and references remain valid, including iterators that
point to elements of x."

,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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,
In article <396E9390.3EBDA542@research.canon.com.au>,
  Brian Parker <brianp@research.canon.com.au> wrote:
> I think that this clause (and the other splice clauses) should be
> reworded to-
> "all iterators and references remain valid, including iterators that
> point to elements of x."

This does not appropriately cover the semantics of the following
program which would be considered well-defined under the rules you are
giving:
  #include <list>
  #include <algorithm>
  #include <iterator>
  #include <iostream>

  int main()
  {
    std::list<int> l1;
    l1.push_back(17);
    std::list<int>::iterator it = l1.begin();
    std::list<int> l2;
    l2.splice(l2.begin(), l1);

    std::copy(it, l1.end(),
              std::ostream_iterator<int>(std::cout, "\n"));
  }

Of course, this is plain ridiculous and clearly a programming bug but
you want implementations to provide reasonable behavior to this code.
I agree, however, that all references to elements in either list should
remain valid.
--
<mailto:dietmar_kuehl@yahoo.com>
<http://www.dietmar-kuehl.de/>


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Dietmar Kuehl" <dietmar_kuehl@yahoo.com> wrote
>   Brian Parker <brianp@research.canon.com.au> wrote:
> > I think that this clause (and the other splice clauses) should be
> > reworded to-
> > "all iterators and references remain valid, including iterators that
> > point to elements of x."
>
> This does not appropriately cover the semantics of the following
> program [ snip ]

You have to be careful about what you read into invalid/valid.  A container
class's iterator is valid if it points into some container's [begin,end]
range.

If I change your example to use swap instead of splice, the standard says
that the iterator is valid, but your program still has the same problem.



---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]