What is the defined behavior of past bound iterator

Discussion in 'C++' started by PengYu.UT@gmail.com, Apr 6, 2006.

  1. Guest

    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, 2006
    #1
    1. Advertising

  2. Noah Roberts Guest

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


    The defined behavior is that the behavior is undefined.
    Noah Roberts, Apr 6, 2006
    #2
    1. Advertising

  3. 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
    Victor Bazarov, Apr 6, 2006
    #3
  4. Pete C Guest

    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.
    >
    Pete C, Apr 6, 2006
    #4
  5. 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
    Victor Bazarov, Apr 7, 2006
    #5
  6. Pete C Guest

    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...
    Pete C, Apr 7, 2006
    #6
  7. 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
    Victor Bazarov, Apr 7, 2006
    #7
  8. Guest

    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, 2006
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. sunil panda

    Lower bound & Upper bound

    sunil panda, Dec 25, 2003, in forum: Java
    Replies:
    9
    Views:
    7,192
    thushara wijeratna
    Oct 7, 2008
  2. Rhiner Dan
    Replies:
    1
    Views:
    731
    Mike Wahler
    Mar 27, 2005
  3. Mario Krsnic
    Replies:
    0
    Views:
    361
    Mario Krsnic
    Jun 23, 2006
  4. Oodini
    Replies:
    1
    Views:
    1,737
    Keith Thompson
    Sep 27, 2005
  5. Mark Stijnman
    Replies:
    5
    Views:
    498
    Mark Stijnman
    Jan 28, 2006
Loading...

Share This Page