470,870 Members | 1,387 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,870 developers. It's quick & easy.

What is the defined behavior of past bound iterator

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

Apr 6 '06 #1
7 1787

Pe*******@gmail.com wrote:
I'm wondering is the standard defined behavior of past bound iterator.


The defined behavior is that the behavior is undefined.

Apr 6 '06 #2
Pe*******@gmail.com wrote:
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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Apr 6 '06 #3
Victor Bazarov wrote:
std::vector<int>::iterator it = v.begin();
-- it;
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.
-- it;


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


Apr 6 '06 #4
Pete C wrote:
Victor Bazarov wrote:
std::vector<int>::iterator it = v.begin();
-- it;


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.


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


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


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
--
Please remove capital As from my address when replying by mail
Apr 6 '06 #5
Victor Bazarov wrote:
Pete C wrote:
Victor Bazarov wrote:
std::vector<int>::iterator it = v.begin();
-- it;

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.


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

Apr 7 '06 #6
Pete C wrote:
[..]
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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Apr 7 '06 #7

Victor Bazarov wrote:
Pete C wrote:
Victor Bazarov wrote:
std::vector<int>::iterator it = v.begin();
-- it;

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.


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

-- it;

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


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::prev==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.

Apr 10 '06 #8

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

220 posts views Thread by Brandon J. Van Every | last post: by
3 posts views Thread by Marco Aschwanden | last post: by
8 posts views Thread by Steven T. Hatton | last post: by
140 posts views Thread by Oliver Brausch | last post: by
1 post views Thread by Mitan | last post: by
669 posts views Thread by Xah Lee | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.