Problems interpreting requirement for std::copy (§25.2.1) - C++ language, library and standards

C++Talk.NET
C++ language newsgroups

Archives

FAQ

Memberlist

Usergroups

Profile

Problems interpreting requirement for std::copy (§25.2.1)

C++Talk.NET Forum Index -> C++ language, library and standards

View previous topic :: View next topic

Author

Message

kanze
Guest

Posted: Sat Sep 10, 2005 5:34 am Post subject: Problems interpreting requirement for std::copy (§25.2.1)

std::copy has a requirement that:
result shall not be in the range [first,last).

What does this mean if the iterators are not the same type?

(In the following, consider that any variable v has a type
std::vector, and any variable l a type std::list.)

If the InputIterator is C::const_iterator, and the
OutputIterator C::iterator, I think that the meaning is pretty
clear. What about if InputIterator is C::const_iterator, and
OutputIterator is C::reverse_iterator? I would expect that
something like:
copy( v.begin() + 3, v.begin() + 8, v.rbegin() + 5 ) ;
is also undefined behavior.

As a first approach, I would expect that something like result
refers to the same object as any of the iterators in the range
[begin, end). But suppose something like:

struct Toggle
{
bool value ;
Toogle() : value( false ) {}
bool operator() { value = ! value ; return value ; }
} ;

typedef boost::filter_iterator< Toggle,
std::vector< int >::const_iterator

Quote:

I ;

copy( I( v.begin() , v.begin() + 10 ), I(), v.begin() + 4 ) ;

In this case, v.begin() + 4 refers to an element which is not
designated by any iterator in the range [begin,end) passed to
copy -- unless I've made a mistake in my code, the range
[begin,end) includes the elements with indexes 1, 3, 5, 7 and 9.
not index 4. On the other hand, with every implementation I
know, copy will assign index 3 to index 5 before reading index 5
to assign it to 6. I rather suspect that it was not intended to
support this, although the arguments to copy are conform to the
Requires clause in §25.2.1.

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()).

(Note that for containers other than list, dereferencing
back_inserter(l) will invalidate the results of an earlier
l.end(). Although I'm not sure where it says so in the
standard, common sense says that doing anything which will
invalidate any iterator in the range [begin,end) makes the
behavior of the function undefined.)

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. (FWIW, I suspect that other functions are
concerned as well. I just happened to look at copy as a result
of some postings in fr.comp.lang.c++.)

--
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
Guest

Posted: Sun Sep 11, 2005 3:41 pm Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

kanze wrote:

Quote:

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.

Quote:

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.

~Marc.

---
[ 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 ]

Gabriel Dos Reis
Guest

Posted: Tue Sep 13, 2005 4:20 am Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

[email]squell (AT) alumina (DOT) nl[/email] (Marc Schoolderman) writes:

Quote:

Indeed, this example -- which I originally posted to
news:fr.comp.lang.c++ -- is fundamentally different from the
vector::iterator case.

In the vector::iterator, it is not hard to offer a definition of
"overlap" that meets common sense such that the assumptions made by
std::copy is violated.

Quote:

output ranges don't strictly overlap, yet assigning through the output
iterator has the side effect of increasing the input range.

Right, that is the crux of the issue. Furthermore, back_inserter(l)
does not even belond to the same category as the input.

Quote:

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.

I think "last - first" is flawed because the inputs are InputIterators
for which we do not have such notion.

Quote:

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)?

Completely agreed -- and it is the suggestion I made on
news:fr.comp.lang.c++. It would suffice to make the code duplicate the
content of the list; but it would not suffice to ensure that general
termination, let alone "last - first" assignments.

---
[ 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
Guest

Posted: Tue Sep 13, 2005 4:20 am Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

kanze wrote:

Quote:

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 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.

Quote:

(Note that for containers other than list, dereferencing
back_inserter(l) will invalidate the results of an earlier
l.end().

back_inserter can be used only for vector, deque, list and string. Only
vector and string invalidates iterators after a push_back, while both
deque and list don't.

Alberto

---
[ 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 ]

kanze
Guest

Posted: Tue Sep 13, 2005 4:30 am Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

Marc Schoolderman wrote:

Quote:

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.

Quote:

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 ]

Gabriel Dos Reis
Guest

Posted: Tue Sep 13, 2005 5:30 am Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

[email]AlbertoBarbati (AT) libero (DOT) it[/email] (Alberto Ganesh Barbati) writes:

Quote:

the "because" part is irrelevant. See below.

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

Quote:

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( Cool

;
q = l.end();
assert (p == q);

---
[ 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 ]

kanze
Guest

Posted: Wed Sep 14, 2005 5:10 am Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

Gabriel Dos Reis wrote:

Quote:

AlbertoBarbati (AT) libero (DOT) 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.)

Quote:

| 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( Cool

;
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
Guest

Posted: Wed Sep 14, 2005 5:32 am Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

Gabriel Dos Reis wrote:

Quote:

AlbertoBarbati (AT) libero (DOT) 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.

I think it is, see below.

Quote:

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

| 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( Cool

;
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.

Alberto

---
[ 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 ]

wade@stoner.com
Guest

Posted: Wed Sep 14, 2005 5:40 am Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

Alberto Ganesh Barbati wrote:

Quote:

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.

Quote:

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 ]

Gabriel Dos Reis
Guest

Posted: Wed Sep 14, 2005 2:30 pm Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

[email]AlbertoBarbati (AT) libero (DOT) it[/email] (Alberto Ganesh Barbati) writes:

Quote:

;
q = l.end();
assert (p == q);

That might happen for some (probably most) implementations of std::list,

I'm not talking of a particular implementation artifact. The
assertion is based on the semantics of insert().

---
[ 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 ]

kanze
Guest

Posted: Wed Sep 14, 2005 2:40 pm Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

Alberto Ganesh Barbati wrote:

Quote:

Gabriel Dos Reis wrote:

[...]

Quote:

Consider this:

p = l.end();
l.push_back( Cool

§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
Guest

Posted: Wed Sep 14, 2005 11:23 pm Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

kanze wrote:

Quote:

Alberto Ganesh Barbati wrote:

Gabriel Dos Reis wrote:

[...]

Consider this:

p = l.end();
l.push_back( Cool

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.

Quote:

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.

Correct, I was mistaken to say that it applies to std::deque also,
because push_back invalidate all iterators, in that case.

Alberto

---
[ 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 ]

John Potter
Guest

Posted: Fri Sep 16, 2005 2:26 am Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

On Wed, 14 Sep 2005 23:23:03 GMT, [email]AlbertoBarbati (AT) libero (DOT) it[/email] (Alberto
Ganesh Barbati) wrote:

Quote:

kanze wrote:
§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.

A look at vector may help. With size less than capacity, push_back is
the same as insert end and invalidates any end iterator. The old
iterator will point to the newly added element unless the
implementation goes out of its way to modify the old iterator, but it
is invalid. For list, it is still valid. Conclusion, it is still an
end iterator.

For validity amusement:

vector<int> v(3, 42);
v.reserve(10);
vector<int>::iterator b(v.begin()), m(b + 1), l(m + 1), p(l + 1);
v.insert(l, 24);
// l and p are now invalid
// b and m are still valid
v.push_back(13);
// b and m are still valid
rotate(m, v.end() - 1, v.end());
// b and m are still valid

The result is the same as v.insert(m, 13), except that it does
not invalidate any iterators other than end.

Does that explain why the standard does not define validity?

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

kanze
Guest

Posted: Fri Sep 16, 2005 3:24 am Post subject: Re: Problems interpreting requirement for std::copy (§25.2.1

Alberto Ganesh Barbati wrote:

Quote:

kanze wrote:
Alberto Ganesh Barbati wrote:

Gabriel Dos Reis wrote:

[...]

Consider this:

p = l.end();
l.push_back( Cool

;
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 ]

Display posts from previous:

	C++Talk.NET Forum Index -> C++ language, library and standards	All times are GMT
Page 1 of 1

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum