iterator range

[subramanian100in]

Whenever we specify an iterator range to a container operation or an
std::algorithm, the first iterator should always be a valid iterator
ie it should point to some element in the respective container? Am I
correct?

For example, suppose

vector<string> v;

v.erase(v.begin(), v.end());
sort(v.begin(), v.end());

Here since 'v' is empty, v.begin() does not refer to an element in the
container. So
both the above statements invoke undefined behaviour. Am I correct ?

Kindly clarify.

Thanks
V.Subramanian

 

[Alf P. Steinbach]

* (e-mail address removed), India:

Whenever we specify an iterator range to a container operation or an
std::algorithm, the first iterator should always be a valid iterator
ie it should point to some element in the respective container? Am I
correct?

For example, suppose

vector<string> v;

v.erase(v.begin(), v.end());
sort(v.begin(), v.end());

Here since 'v' is empty, v.begin() does not refer to an element in the
container. So
both the above statements invoke undefined behaviour. Am I correct ?

No. §23.1/7 tells you that if a container is empty, begin() == end().
It would only be undefined behavior to dereference the iterator.


Cheers, & hth.,

- Alf

 

[Andrey Tarasevich]

Whenever we specify an iterator range to a container operation or an
std::algorithm, the first iterator should always be a valid iterator
ie it should point to some element in the respective container? Am I
correct?
...

Yes and no.

Yes, the first iterator has to be valid. Moreover, the second iterator also has
to be valid. Both of them have to be valid.

And no, a valid iterator does not necessarily point to the existing element in
the container. The iterator that points to the imaginary element that follows
the last existing element in the container is also perfectly valid. It cannot be
dereferenced, but it still can be used with non-dereferencing iterator
operations. When defining a sequence, the first iterator (begin) can be equal to
the second iterator (end), which defines an empty sequence. In this case there's
no requirement for the first iterator to point to an existing element.

 

[subramanian100in]

* On Feb 9, 2:36 am, Andrey Tarasevich <[email protected]>
wrote:

Thanks to both Alf P. Steinbach and Andrey Tarasevich for the reply:

(Please bear with me for the following post)

From your replies above, what I understand is that:

when we specify an iterator range, to a container operation or an
std::algorithm, both the first iterator and the last iterator can be
the sentinel ie both of them can be off-the-end iterators. correct?

If so, how do we know whether the implementation of container member
operations or the std:algorithms which accept an input range, will not
dereference the first iterator when both the first and last are
sentinel.

Essentially how do we know that the following operations' definitions
on all compiler implementations will not dereference the the first
iterator which is already the sentinel because the container is empty.

vector<string> v;

v.erase(v.begin(), v.end());
sort(v.begin(), v.end());

Kindly clarify.

Thanks
V.Subramanian

 

[Pete Becker]

when we specify an iterator range, to a container operation or an
std::algorithm, both the first iterator and the last iterator can be
the sentinel ie both of them can be off-the-end iterators. correct?

When you pass a pair of iterators to an algorithm, the pair of
iterators must reprsent a valid sequence. Essentially, that means that
with zero or more increments you can get from the first iterator to the
second.

Containers are a common way of managing sequences, but they are not the
only way.

If so, how do we know whether the implementation of container member
operations or the std:algorithms which accept an input range, will not
dereference the first iterator when both the first and last are
sentinel.

Because algorithms (whether standalone or container members) are
written to work with valid sequences, and will not do invalid
operations on those sequences.

Essentially how do we know that the following operations' definitions
on all compiler implementations will not dereference the the first
iterator which is already the sentinel because the container is empty.

vector<string> v;

v.erase(v.begin(), v.end());
sort(v.begin(), v.end());

We know it won't do that because we trust the implementor of sort to
understand the rules for sequences. A typical algorithm looks something
like this:

template <class InIt>
InIt do_something(InIt first, InIt last)
{
while (first != last)
{
// do something with *first
++first;
}
return first;
}

 

[James Kanze]

From your replies above, what I understand is that:

when we specify an iterator range, to a container operation or an
std::algorithm, both the first iterator and the last iterator can be
the sentinel ie both of them can be off-the-end iterators. correct?

For all of the algorithms in the standard library, at any rate.

If so, how do we know whether the implementation of container
member operations or the std:algorithms which accept an input
range, will not dereference the first iterator when both the
first and last are sentinel.

The same way that you know that it won't start by incrementing
the begin iterator three times, even if there are only two
elements in the sequence. The specifications of the function.
(Presumably, you could write a function which has a
pre-condition that distance( begin, end ) >= 3. There are
probably even some strange cases where it makes sense.)

The specifications of all of the functions in the standard
library, and most reasonably defined user functions, allows
empty sequences.

Essentially how do we know that the following operations'
definitions on all compiler implementations will not
dereference the the first iterator which is already the
sentinel because the container is empty.

vector<string> v;

v.erase(v.begin(), v.end());
sort(v.begin(), v.end());

Because the specifications of the functions in the standard say
so.

 

[James Kanze]

[...]

We know it won't do that because we trust the implementor of sort to
understand the rules for sequences.

We know it doesn't do that because the standard doesn't allow it
to do that. The standard pretty much says (not in that
language) that none of the algorithms will ever access through
an iterator equalt to end.

Of course, there is an aspect of trust involve. We trust the
implementors to respect the specifications of what they
implement.

 

[Pete Becker]

[...]

We know it won't do that because we trust the implementor of sort to
understand the rules for sequences.

We know it doesn't do that because the standard doesn't allow it
to do that. The standard pretty much says (not in that
language) that none of the algorithms will ever access through
an iterator equalt to end.

Yes, that's one of the rules for sequences.

Of course, there is an aspect of trust involve. We trust the
implementors to respect the specifications of what they
implement.

Yes, that's another way of saying what I said.