Gabriel Dos Reis wrote:
> AlbertoBarbati@libero.it (Alberto Ganesh Barbati) writes:

> | kanze wrote:

> | > Finally, what about something like:

> | >     copy( l.begin(), l.end(), back_inserter( l ) ) ;

> | > I think that, realistically, this will generally result in
> | > an endless loop.  And yet, it requires quite a stretch of
> | > the imagination to say that back_inserter( l ) is in the
> | > range of [l.begin(),l.end()).

> | It doesn't result in an endless loop, because l.end() is not
> | re-evaluated during the execution of copy.

> the "because" part is irrelevant.  See below.

> And James' claim that the l.end() is invalidated is bogus.

Agreed.  I was thinking of something else.

The results of a v.end(), where v is a vector or a deque, are
invalidated by dereferencing a back_inserter.  The results of
l.end(), where l is a list, aren't.

(Intuitively, I find it convenient to imagine that the iterator
returned by end() points to a virtual element, which is always
behind all of the real elements in the list.  And that the rules
concerning invalidation of iterators apply to it in exactly the
same way they apply to iterators designating real objects.)

> | The value which is passed as the "last" parameter remains a
> | valid iterator which keeps pointing to the same element for
> | the whole execution of the algorithm. Therefore the
> | statement will effectively just append a entire copy of l at
> | the end of l itself.

> Consider this:

>     p = l.end();
>     l.push_back(8);
>     q = l.end();
>     assert (p == q);

Guaranteed, I believe.

There are subtle issues concerning the copy function above.  I
would normally presume that something like:

    while ( begin != end ) {
        *dest ++ = *begin ++ ;
    }

would be a legal implementation of std::copy.  As would be:

    while ( begin != end ) {
        *dest = *begin ;
        ++ dest ;
        ++ begin ;
    }

It's interesting to note, however, that they have different
behavior in the case above.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Alberto Ganesh Barbati wrote:

> back_inserter can be used only for vector, deque, list and string.

AFAICT back_inserter requires a container that supports push_back().
Nothing in the standard prevents you (or anyone else) from writing
their own containers, and I suspect that someone has done so by now.

> Only
> vector and string invalidates iterators after a push_back, while both
> deque and list don't.

Guess again.  23.2.1.3/1 "... An insert at either end of the deque
invalidates all the iterators to the deque ..."

It is possible to implement deque (vector and string also) so that
push_back does not invalidate iterators, but I'm not aware of
widely-used implementations that do so.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Alberto Ganesh Barbati wrote:
> Gabriel Dos Reis wrote:

    [...]
> > Consider this:

> >     p = l.end();
> >     l.push_back(8);
> >     q = l.end();
> >     assert (p == q);

> That might happen for some (probably most) implementations of
> std::list, but I could find no statement in the standard that
> provides such guarantee. If you think such guarantee is
> provided, I will be glad to have a precise reference in the
> standard. Without an explicit or implicit guarantee you cannot
> assume that the expression in the assert always true for all
> conformant implementations of std::list.

   23.2.23/1, in the decription of insert, push_front and
push_back: "Does not affect the validity of iterators and
references."

I don't find an exact definition in the standard as to what it
means by validity, but from the actual use, I think it means
that the iterator continues to designate the same element (or in
the case of end(), it continues to designate an element one past
the end).

Note that this guarantee only applies to std::list.  The other
containers offer differents sets of guarantees, and none of the
other containers guarantee the validity of an end iterator after
an insertion.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Alberto Ganesh Barbati wrote:
> kanze wrote:
> > Alberto Ganesh Barbati wrote:

> >>Gabriel Dos Reis wrote:

> >     [...]

> >>>Consider this:

> >>>    p = l.end();
> >>>    l.push_back(8);
> >>>    q = l.end();
> >>>    assert (p == q);

> >>That might happen for some (probably most) implementations
> >>of std::list, but I could find no statement in the standard
> >>that provides such guarantee. If you think such guarantee is
> >>provided, I will be glad to have a precise reference in the
> >>standard. Without an explicit or implicit guarantee you
> >>cannot assume that the expression in the assert always true
> >>for all conformant implementations of std::list.

> >    23.2.23/1, in the decription of insert, push_front and
> > push_back: "Does not affect the validity of iterators and
> > references."

> > I don't find an exact definition in the standard as to what
> > it means by validity, but from the actual use, I think it
> > means that the iterator continues to designate the same
> > element (or in the case of end(), it continues to designate
> > an element one past the end).

> I agree that the statement means that a valid past-the-end
> iterator remains valid after a push_back, but it's not obvious
> to me that it should remain a past-the-end iterator. One could
> implement a past-the-end iterator in such a way that, after a
> push_back, it points to (newly added) last element and I don't
> see how such implementation would be violating the
> standard. Of course I may be missing something.

I think it is the standard which is missing something, but I may
have just missed it.  What is missing is the definition of what
it means for an iterator to remaind valid.  Given the total set
of specifications as to when an iterator remains valid, and when
it doesn't, I think that the definition is that an iterator
remains valid if and only if it can still be used AND still
designates the same element (with one past the end being
considered a "virtual" element).

If we assume only the first part of this requirement, of course,
vector<>::erase whould only invalidate the last n iterators
(where n is the number of elements begin erased), and not all of
the iterators past the point of erase.  And vector::insert would
only invalid iterators if reallocation occured; a correctly
dimensionned reserve could guarantee that it never invalided an
iterator.

I am exterpolating this definition from the total set of the
validity specifications, however, and it would be much nicer if
the standard said it explicitly.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Marc Schoolderman wrote:
> kanze wrote:

> > Finally, what about something like:
> >     copy( l.begin(), l.end(), back_inserter( l ) ) ;
> > I think that, realistically, this will generally result in
> > an endless loop.  And yet, it requires quite a stretch of
> > the imagination to say that back_inserter( l ) is in the
> > range of [l.begin(),l.end()).

> I think this example is different from the others, since the
> input and output ranges don't strictly overlap, yet assigning
> through the output iterator has the side effect of increasing
> the input range.  This also means the complexity requirement
> of copy() gets violated since it will do more than "exactly
> last - first assignments" -- unless it measures "last - first"
> before it enteres the copy loop, but that would be inefficient
> for bidirectional iterators.

Quite.  Something has to break, somewhere.

> > Globally, I think that the wording of the requires clause
> > for copy needs work.  But I can't really think of any
> > reasonable way to formulate what common sense tells me
> > should be the restrictions.

> Perhaps the requirement should be that the output iterator
> should not produce any side effects in the range [first,
> last)? This seems similar to the requirement that predicates
> should be side-effect free and I think covers all of your
> examples.

I think there are two important points.  The first is, as you
say, that of side effects (including those resulting from
dereferencing the iterator on the left side of an assignment).
The second is that any restrictions must apply to all values
that the output iterator will take, and not just the value
passed to the function.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]