none
Null iterator

    Question

  • What is the right way to check an STL iterator and determine if it is valid?  Include the possibility that the iterator has been declare but never set to anything.
    ~jag77
    Wednesday, July 09, 2008 1:33 AM

Answers

  •  Typically this need never arises. When you declare the iterator you should immediately initialize it, usually with xxxx.begin() or xxxx.rbegin(). It is invalid as soon as it is set to xxxx.end() (or xxxx.rend()).

    So, if you are tempted to declare it but not initialize it, then don't declare it.

    Wednesday, July 09, 2008 3:04 AM
  •  

    After posting the initial question, becoming quite frustrated with the vector STL, and the iterators and what appeared to be inconsistent behavior,  I added in a bunch of test code and made some startling discoveries.

     

    First: An iterator cannot be tested to determine if it is valid!

    This is bad design and worse coding.  The idea that there is no method available to check the validity of an iterator is just outrageous.  How can the programming community sit by and let the designers present a product with a flaw of this magnitude as this is quite surprising.

     

    Second:  When the iterator gets to the end of the list, iterator.end() is not true.  Iterator.end() -1 is true.  What the iterator says is the end of the list is really one past the end of the list.

    Again, this is really bad design.  I will present my justification in a moment.

     

    Third:  When the iterator is moving in reverse direction, iterator.begin() is really the beginning.  Its not iterator.begin() -1 or to be consistant, iterator.begin() + 1;  The begin() function is correct.  This is inconsistent with the .end() method.

     

    Justification.  Lets assume a queue going through a door.  Let a, b, c, etc be people in the queue.  Let X represent the door.  We might have the following situation:

     

    . a  b  X  c  d  e           f g

     

    This line is moving from right to left.  a and b have passed through the door. c is now the first in line and will go through the door next.  f and g are  way down the hall (maybe around the corner and e cannot see them) and are not yet in the line.   If we were to ask who is at the end of the line, the answer is e.  It is not f.  f is not in the line.  To say f is at the end of the line is just outright wrong.  But this is what is returned when we make the check 

    If( iterator_1 == list.end() )

    When this returns true, the iterator is not at the end of the list, it is not pointing at e, it is pointing to f, who is not in the list.  The iterator is not at the end, it is one past the end.

     

    The end of the queue is the last entry in the queue.  It is not one past the last entry.  This is the way the English language works in conjunction with the definition of a line or queue.  The end of the line is not, repeat Not, repeat NOT one past the end of the line.  The end() is the last entry in the line.  PERIOD.

     

    The check for the last entry in the queue must be made as:

    If( iterator_1 == list.end() – 1 )

    And that is just flat out wrong.  It is bad design.  It is bad code.  It will lead to programming errors and program crashes. 

     

     

    A google search on “stl iterator end” returns a few hits.  The first three sites returned did not mention this problem at all.

    http://www.cprogramming.com/tutorial/stl/iterators.html

    http://www.sgi.com/tech/stl/stl_introduction.html

    http://www.sgi.com/tech/stl/Vector.html

     

    the fourth and fifth sites:

    http://devmentor.org/references/stl/stl.html

    http://cs.ioc.ee/yik/schools/sum2006/generic_programming/iterators.html

     

    do recognize that end() is one past the end of the container. Each site has a nice diagram showing the asymmetry of begin() and end().

     

    Of all the sites I visited in the last hour or so, only two mentioned this inconsistency.  None of the sites and neither of the two books on my shelf behind me mention that if you try to look at the list.end() item in a container your program will crash and burn.

     

    So,…,

    I have now entered this in the database so that others might find it.  Those who google this and find the first three sites will probably become just as frustrated as I did.  And when they discover this incredibly bad design, maybe they will also raise a fuss.

     

    But then, where can you go to complain?  Who or what is the deciding body that declared end() should operate in this manner?  I would like to know.

     


    ~jag77
    • Marked as answer by JAG77 Saturday, July 12, 2008 2:44 AM
    Saturday, July 12, 2008 2:44 AM

All replies

  •  Typically this need never arises. When you declare the iterator you should immediately initialize it, usually with xxxx.begin() or xxxx.rbegin(). It is invalid as soon as it is set to xxxx.end() (or xxxx.rend()).

    So, if you are tempted to declare it but not initialize it, then don't declare it.

    Wednesday, July 09, 2008 3:04 AM
  • So does this mean that even if the container is empty, the iterator can be initialized?

    I would not have expected that, but it does seem like a good thing to be able to do.  I'll try it.

    Thank you.
    ~jag77
    Wednesday, July 09, 2008 11:11 PM
  • For empty containers, when you initialize the iterator to xxx.begin() you will discover it already equals xxx.end().
    Thursday, July 10, 2008 5:43 AM
  •  

    After posting the initial question, becoming quite frustrated with the vector STL, and the iterators and what appeared to be inconsistent behavior,  I added in a bunch of test code and made some startling discoveries.

     

    First: An iterator cannot be tested to determine if it is valid!

    This is bad design and worse coding.  The idea that there is no method available to check the validity of an iterator is just outrageous.  How can the programming community sit by and let the designers present a product with a flaw of this magnitude as this is quite surprising.

     

    Second:  When the iterator gets to the end of the list, iterator.end() is not true.  Iterator.end() -1 is true.  What the iterator says is the end of the list is really one past the end of the list.

    Again, this is really bad design.  I will present my justification in a moment.

     

    Third:  When the iterator is moving in reverse direction, iterator.begin() is really the beginning.  Its not iterator.begin() -1 or to be consistant, iterator.begin() + 1;  The begin() function is correct.  This is inconsistent with the .end() method.

     

    Justification.  Lets assume a queue going through a door.  Let a, b, c, etc be people in the queue.  Let X represent the door.  We might have the following situation:

     

    . a  b  X  c  d  e           f g

     

    This line is moving from right to left.  a and b have passed through the door. c is now the first in line and will go through the door next.  f and g are  way down the hall (maybe around the corner and e cannot see them) and are not yet in the line.   If we were to ask who is at the end of the line, the answer is e.  It is not f.  f is not in the line.  To say f is at the end of the line is just outright wrong.  But this is what is returned when we make the check 

    If( iterator_1 == list.end() )

    When this returns true, the iterator is not at the end of the list, it is not pointing at e, it is pointing to f, who is not in the list.  The iterator is not at the end, it is one past the end.

     

    The end of the queue is the last entry in the queue.  It is not one past the last entry.  This is the way the English language works in conjunction with the definition of a line or queue.  The end of the line is not, repeat Not, repeat NOT one past the end of the line.  The end() is the last entry in the line.  PERIOD.

     

    The check for the last entry in the queue must be made as:

    If( iterator_1 == list.end() – 1 )

    And that is just flat out wrong.  It is bad design.  It is bad code.  It will lead to programming errors and program crashes. 

     

     

    A google search on “stl iterator end” returns a few hits.  The first three sites returned did not mention this problem at all.

    http://www.cprogramming.com/tutorial/stl/iterators.html

    http://www.sgi.com/tech/stl/stl_introduction.html

    http://www.sgi.com/tech/stl/Vector.html

     

    the fourth and fifth sites:

    http://devmentor.org/references/stl/stl.html

    http://cs.ioc.ee/yik/schools/sum2006/generic_programming/iterators.html

     

    do recognize that end() is one past the end of the container. Each site has a nice diagram showing the asymmetry of begin() and end().

     

    Of all the sites I visited in the last hour or so, only two mentioned this inconsistency.  None of the sites and neither of the two books on my shelf behind me mention that if you try to look at the list.end() item in a container your program will crash and burn.

     

    So,…,

    I have now entered this in the database so that others might find it.  Those who google this and find the first three sites will probably become just as frustrated as I did.  And when they discover this incredibly bad design, maybe they will also raise a fuss.

     

    But then, where can you go to complain?  Who or what is the deciding body that declared end() should operate in this manner?  I would like to know.

     


    ~jag77
    • Marked as answer by JAG77 Saturday, July 12, 2008 2:44 AM
    Saturday, July 12, 2008 2:44 AM
  • JAG77 said:

     

    After posting the initial question, becoming quite frustrated with the vector STL, and the iterators and what appeared to be inconsistent behavior,  I added in a bunch of test code and made some startling discoveries.

     

    First: An iterator cannot be tested to determine if it is valid!

    This is bad design and worse coding.  The idea that there is no method available to check the validity of an iterator is just outrageous.  How can the programming community sit by and let the designers present a product with a flaw of this magnitude as this is quite surprising.

     

    Second:  When the iterator gets to the end of the list, iterator.end() is not true.  Iterator.end() -1 is true.  What the iterator says is the end of the list is really one past the end of the list.


    That is correct, and is the brilliance behind this design. You should interpret it this way: assign an iterator to xxx.begin(). You can consider it valid as long as it does not equal xxx.end(). By "end" you should think if it as "the iterator as fallen off the end, and is no longer reference a valid member.

    Again, this is really bad design.  I will present my justification in a moment.

     

    Third:  When the iterator is moving in reverse direction, iterator.begin() is really the beginning.  Its not iterator.begin() -1 or to be consistant, iterator.begin() + 1;  The begin() function is correct.  This is inconsistent with the .end() method.


    Typically if you want to go in the reverse direction you use xxx.rbegin() and xxx.rend(). It is analogous to begin() and end() and simply starts at the opposite end of the container.

     

    Justification.  Lets assume a queue going through a door.  Let a, b, c, etc be people in the queue.  Let X represent the door.  We might have the following situation:

     

    . a  b  X  c  d  e           f g

     

    This line is moving from right to left.  a and b have passed through the door. c is now the first in line and will go through the door next.  f and g are  way down the hall (maybe around the corner and e cannot see them) and are not yet in the line.   If we were to ask who is at the end of the line, the answer is e.  It is not f.  f is not in the line.  To say f is at the end of the line is just outright wrong.  But this is what is returned when we make the check 

    If( iterator_1 == list.end() )

    When this returns true, the iterator is not at the end of the list, it is not pointing at e, it is pointing to f, who is not in the list.  The iterator is not at the end, it is one past the end.

     

    The end of the queue is the last entry in the queue.  It is not one past the last entry.  This is the way the English language works in conjunction with the definition of a line or queue.  The end of the line is not, repeat Not, repeat NOT one past the end of the line.  The end() is the last entry in the line.  PERIOD.

     

    The check for the last entry in the queue must be made as:

    If( iterator_1 == list.end() – 1 )

    And that is just flat out wrong.  It is bad design.  It is bad code.  It will lead to programming errors and program crashes. 

     

     

    A google search on “stl iterator end” returns a few hits.  The first three sites returned did not mention this problem at all.

    http://www.cprogramming.com/tutorial/stl/iterators.html

    http://www.sgi.com/tech/stl/stl_introduction.html

    http://www.sgi.com/tech/stl/Vector.html

     

    the fourth and fifth sites:

    http://devmentor.org/references/stl/stl.html

    http://cs.ioc.ee/yik/schools/sum2006/generic_programming/iterators.html

     

    do recognize that end() is one past the end of the container. Each site has a nice diagram showing the asymmetry of begin() and end().

     

    Of all the sites I visited in the last hour or so, only two mentioned this inconsistency.  None of the sites and neither of the two books on my shelf behind me mention that if you try to look at the list.end() item in a container your program will crash and burn.

     

    So,…,

    I have now entered this in the database so that others might find it.  Those who google this and find the first three sites will probably become just as frustrated as I did.  And when they discover this incredibly bad design, maybe they will also raise a fuss.

     

    But then, where can you go to complain?  Who or what is the deciding body that declared end() should operate in this manner?  I would like to know.

     
    STL was one of the biggest advances in C++ in the last decade, and was so inspirational, it has been adopted into the C++ standard as part of the standard C++ library.


    Before you complain too, too much, I urge you to get a copy of Scott Meyers "Effective STL". I think he might change your mind about this important cornerstone of the C++ library.



    ~jag77



    Saturday, July 12, 2008 4:24 AM
  • JAG77:

    You can be sure that the designers of the STL thought long and hard before settling on the meaning of end().

    The way I always think of it is that it is consistent with the C/C++ usage

    const int NMAX = 6;
    double x[NMAX];
    for (int i=0; i<NMAX; ++i)
    {
      x[i] = 0.0;
    }

    x[NMAX] is not an element of the array, just as *end() is not an element of the container.

    Another reason is that if end() was the last element, then an iterator loop would have to  test for <=, which is not defined for some iterators. Iterator loops should always test for != end().




    David Wilkinson | Visual C++ MVP
    Saturday, July 12, 2008 2:24 PM
  • Hello again Dave,
    Just because people think long an hard about things does not mean they always arrive at the best solution.  Or even the right solution.

    The problem of off by one has plagued C programmers since the beginning.  The forced use of 0 to n-1 indexing has always been a problem.  (And no, I have no desire or intent to open that argument once again.  Rightly or wrongly, it has been a problem.  If you prefer, we can call it a difficulty.) 

    When using a linked list, there is no concept of 0 to n-1 or 1 to n.  There is a first element, a last element, and some quantity in between.  The comparison of the two is not valid.

    As I mentioned in my previous post, the end is not one past the last entry.  It is the last entry.  Any attempt to talk around that concept is just plain wrong.

    The operation of list.begin() and list.end() are inconsistant.  If list.end() means the iterator is outside the list and is not valid, then list.begin() on the other end should operate in the same manner.  They do not operate in the same manner.  This is a significant problem and is bad design.

    I am not interested in past behavior.  I am not interested in mathematical derivation or proof.  Humans write the code and humans must be able to read it and understand it.  list.begin() and list.end() should behave consistantly.


    ~jag77
    Saturday, July 12, 2008 5:29 PM

  • Quote>the end is not one past the last entry. 
    Quote>It is the last entry.

    Note that "one past" is consistent with the way that C and C++ file I/O
    works as well. EOF is set for a file when an attempt is made to read *past*
    the last byte of the file, not when the last byte is read. (This is a common
    source of flawed EOF testing by many programmers.)

    - Wayne


     

    Sunday, July 13, 2008 10:29 PM
  • JAG77 said:

    Hello again Dave,
    Just because people think long an hard about things does not mean they always arrive at the best solution.  Or even the right solution.

    However, this time they did.

    The problem of off by one has plagued C programmers since the beginning.  The forced use of 0 to n-1 indexing has always been a problem.  (And no, I have no desire or intent to open that argument once again.  Rightly or wrongly, it has been a problem.  If you prefer, we can call it a difficulty.) 

    This is because computers work differently then people.  Using 0 to n-1 makes perfect sense from the computers point of view.  To make the language different would add a layer of ambiguity that is not necessary and could cause more confusion.

    When using a linked list, there is no concept of 0 to n-1 or 1 to n.  There is a first element, a last element, and some quantity in between.  The comparison of the two is not valid.

    Right.  So you need an effective, optimized way to get from the beginning and through all of the elements.  That way would be with iterators.

    As I mentioned in my previous post, the end is not one past the last entry.  It is the last entry.  Any attempt to talk around that concept is just plain wrong.

    The operation of list.begin() and list.end() are inconsistant.  If list.end() means the iterator is outside the list and is not valid, then list.begin() on the other end should operate in the same manner.  They do not operate in the same manner.  

    Nor should they.  An iterator that worked the way you want it to would be next to useless. 

    This is a significant problem and is bad design.

    No, it is not a problem and it is brilliant design.  Having it your way would cause significant problems and, thus, would be a bad design.

    I am not interested in past behavior.  I am not interested in mathematical derivation or proof.  Humans write the code and humans must be able to read it and understand it.  list.begin() and list.end() should behave consistantly.

    Computers run code and the programmer should have a good understanding of how the computer works.  Making a language so that it is readable and sensible to the laymen is not an effective way to make good programs.  A computer is a complex machine and requires that you have complex knowledge to make it do what you want. 

    If the end iterator did not point to one past the end, then using the end in a loop would be useless because you would have to have more complicated code that determines if you have reached the end.  Making the end go one past allows the check to be easy.  i.e.

    for( iterator it = list.begin(); it != list.end(); ++it ){
       // do some stuff
    }

    The equivalent, if end pointed to the last element would be

    for( iterator it = list.begin(); ; ++it ){
       // do some stuff
       if( it == list.end() )
           break;
    }

    That hardly looks like an elegant alternative.  Since this is how iterators are most commonly used, your way of doing it would obviously be a bad design.  Another common operation done on containers is inserting.  If you gave end to insert and it was actually the last element, it would either overwrite the last element or need to increment itself to get to the end of the string.  With the way it is, there is nothing that has to be done. 

    It is highly advisable that you get familiar with a technology before you denounce it as bad.  It is obvious that you haven't worked with or thought much about iterators.  Because, if you had, you would realize why the way you expect or want it to be would actually be the bad design.



    Monday, July 14, 2008 7:11 PM