What is the defined behavior of past bound iterator

[PengYu.UT]

I'm wondering is the standard defined behavior of past bound iterator.

In the following example it seems that afer first "--it", it point to
-1 index. I'm wondering if it is true independent of which STL
implementation that I am using.


#include <iostream>
#include <vector>

int main(int argc, char *argv[]) {
std::vector<int> v;
for(int i = 0; i < 10; ++ i) {
v.push_back(i);
}
std::vector<int>::iterator it = v.begin();
-- it;
-- it;
std::cout << *it << std::endl;
++ it;
std::cout << *it << std::endl;
++ it;
std::cout << *it << std::endl;
++ it;
std::cout << *it << std::endl;
}

The output:
0
0
0
1

 

[Noah Roberts]

I'm wondering is the standard defined behavior of past bound iterator.

The defined behavior is that the behavior is undefined.

 

[Victor Bazarov]

I'm wondering is the standard defined behavior of past bound iterator.

Where did you find that term "past bound"?

In the following example it seems that afer first "--it", it point to
-1 index. I'm wondering if it is true independent of which STL
implementation that I am using.

Yes, it's true independent of whatever. Its behavour is _undefined_.

#include <iostream>
#include <vector>

int main(int argc, char *argv[]) {
std::vector<int> v;
for(int i = 0; i < 10; ++ i) {
v.push_back(i);
}
std::vector<int>::iterator it = v.begin();
-- it;

Bam!!! 'it' is now _invalid_.

-- it;

BANG!!! Undefined behaviour. Everything after that is irrelevant.

std::cout << *it << std::endl;
++ it;
std::cout << *it << std::endl;
++ it;
std::cout << *it << std::endl;
++ it;
std::cout << *it << std::endl;
}

The output:
0
0
0
1

V

 

[Pete C]

Bam!!! 'it' is now _invalid_.

Do you not get undefined behaviour at this point? Are you saying that
if we did "exit(0);" now, the program would be OK? I didn't realise
that.

 

[Victor Bazarov]

Do you not get undefined behaviour at this point? Are you saying that
if we did "exit(0);" now, the program would be OK? I didn't realise
that.

Invalidation of an iterator is a normal thing. Undefined behaviour
occurs when you try to _use_ an invalid iterator.

Here, decrementing means using. You need to know its value to give
it a new one. But evaluating the iterator when it's invalid is not
defined.

V

 

[Pete C]

Invalidation of an iterator is a normal thing. Undefined behaviour
occurs when you try to _use_ an invalid iterator.

OK, I just had a rummage around in the standard. In 24.1.4 (Table 75)
it say that a precondition for --r (where r is a bidirectional
iterator) is that there must exist an iterator s such that r == ++s.
But because ++s is only valid for iterators that are dereferencable
(Table 74), this condition cannot be satisfied when r lies at the
beginning of a sequence.
So seems to me that a statement like --v.begin(); is a violation of
this precondition. If not, could you please explain where I have gone
wrong? Thanks...

 

[Victor Bazarov]

[..]
OK, I just had a rummage around in the standard. In 24.1.4 (Table 75)
it say that a precondition for --r (where r is a bidirectional
iterator) is that there must exist an iterator s such that r == ++s.
But because ++s is only valid for iterators that are dereferencable
(Table 74), this condition cannot be satisfied when r lies at the
beginning of a sequence.
So seems to me that a statement like --v.begin(); is a violation of
this precondition. If not, could you please explain where I have gone
wrong? Thanks...

I think you got it right. Note that --v.end() is not a violation (to
be honest, I've never seen "--v.begin()" anywhere, but the 'end' one I
have, indeed).

V

 

[Michiel.Salters]

Invalidation of an iterator is a normal thing. Undefined behaviour
occurs when you try to _use_ an invalid iterator.


Here, decrementing means using. You need to know its value to give
it a new one. But evaluating the iterator when it's invalid is not
defined.

Nope, it isn't. This is intentional; it allows for e.g. simple linked
list
implementations. The first iterator will have list::iterator:rev==0,
and --it; translates to it = *(it.prev);.

Else, you should be able to decrement it N times, increment it N times,
and get back to begin. Logically, that means the iterator would have to
store N (which is a large overhead for single-linked lists)
Furthermore,
it would be very tricky to keep such an N-before-begin iterator valid
if
one inserts an element at the begin of such a list.

Lots of pain, little gain: a good reason to disallow the creation of
such
invalid iterators altogether. After all, it's equally invalid for
arrays, and we
could handle those as well.

HTH,
Michiel Salters

HTH,
Michiel Salters.