What exactly is iterator returned by .end()?

This is a discussion on What exactly is iterator returned by .end()? within the C++ Programming forums, part of the General Programming Boards category; Hi, does the standard define what the iterator returned by container.end() points to? Or the question represented in code: Code: ...

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    519

    What exactly is iterator returned by .end()?

    Hi,

    does the standard define what the iterator returned by container.end() points to?

    Or the question represented in code:

    Code:
    vector<int> v;
    vector<int>::iterator iter = v.end();
    v.push_back(1);
    
    assert( iter == v.end() ); //?
    I see two possibilities:
    1. iterator returned by container.end() is implemented as a special marker element which is always the same. in this case the assert should not fail
    2. iterator returned by container.end() is dynamically derived from the last element of the container. in this case the assert should maybe fail

    What does the standard say? Does the answer depend on the container typ?

    Thank you in advance!

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,025
    If vector is empty, then an invalid iterator is returned.
    If vector is not empty, then it points to end + 1.
    (This was observed in Microsoft's implementation.)
    But regardless of how end() is implemented, adding something to the vector invalidates the iterators.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Elysia View Post
    If vector is empty, then an invalid iterator is returned.
    If vector is not empty, then it points to end + 1.
    (This was observed in Microsoft's implementation.)
    But regardless of how end() is implemented, adding something to the vector invalidates the iterators.
    Actually, I'm pretty sure a valid end iterator is always returned. begin() returns an iterator to the first element, while end() an iterator to the item past the last element. If a vector is empty, then begin() == end().
    It is true that adding something to a vector invalidates iterators. Not for all types though. For a set, if I am not mistaken, the iterators won't be invalidated. (I know this wasn't part of the question, but an in my opinion significant addition anyway).

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,025
    Well, invalid or not can be speculated, but I know that it returned NULL when it was empty, and so likely would begin, from what I observed. So I suppose it can be said that it is a valid iterator, but begin == end.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    It returns an iterator situated one element beyond the last.
    If there is no last element that is an undefined position, therefore it cannot return an iterator and returns 0.

    If the vector is empty, begin() should return 0 as well, simply because there is no first element to refer to.
    Begin would be end only in result, still not in principle as the first element can never be one element past the last element even if both elements are undefined.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,304
    Quote Originally Posted by pheres
    What does the standard say? Does the answer depend on the container typ?
    EVOEx is correct. Concerning all standard containers:
    Quote Originally Posted by C++ Standard, 2003 Edition, Section 23.1, Paragraph 7
    begin() returns an iterator referring to the first element in the container. end() returns an iterator which is the past-the-end value for the container. If the container is empty, then begin() == end();
    As such, returning a null pointer when the container is empty would satisfy the requirements for begin() and end(), but the standard does not mandate that a null pointer be returned when the container is empty. (Oh yes, and I forgot that in the first place, iterators are a generalisation of pointers, so the standard could not mandate that null pointers be returned anyway.)

    EDIT:
    To address the point on whether the assert would fail: it is obvious that the assert should fail since the previous end of the vector cannot be equal to the current end of the vector when the vector's size changes.

    Concerning invalidation of iterators: EVOEx is again correct to say that whether adding an element to a container invalidates iterators depends on the container. In the case of a vector, it also depends on whether reallocation occurs, so it is not absolutely true to say that "adding something to the vector invalidates the iterators".
    Last edited by laserlight; 12-09-2008 at 07:43 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    So looking at my peace of code that means that the push_back() will not invalidate iter, iter is still required to point to end() and the assert will pass?

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by pheres View Post
    So looking at my peace of code that means that the push_back() will not invalidate iter, iter is still required to point to end() and the assert will pass?
    may pass - it depends on how the storage is implemented. in a vector, for example, it may return the address of element(size+1).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Obviously the end of the vector is not the same after the push_back, so that assertion should never pass.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by anon View Post
    Obviously the end of the vector is not the same after the push_back, so that assertion should never pass.
    However, in a linked list, the end() may be NULL (or some other sentinel value), which is always the same value - so there's no guarantee that it actually changes the value of end.

    For a vector, I agree, it's unlikely to fail - but replace it with the "right" container class, and it may do.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,304
    Quote Originally Posted by matsp
    may pass - it depends on how the storage is implemented. in a vector, for example, it may return the address of element(size+1).
    No, as I pointed out, and which anon has confirmed, it is clear that the assertion must fail, otherwise there is a bug in the standard library implementation.

    Quote Originally Posted by matsp
    However, in a linked list, the end() may be NULL (or some other sentinel value), which is always the same value - so there's no guarantee that it actually changes the value of end.
    That is true, but pheres' example is for vector.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Code:
    vector<int> v;
    v.push_back(1);
    vector<int>::iterator end = v.end();
    v.push_back(2);
    vector<int>::iterator it;
    for (it = v.begin; it != end ; it++)
        cout << *it;
    Well try the above. If you get 1 then the iterator doesn't change (which should be the case). If you get 12 then that means that the iterator always points the end of the vector (which shouldn't be true)

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,025
    Code:
    #include <vector>
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
    	vector<int> v;
    	v.push_back(1);
    	vector<int>::iterator end = v.end();
    	v.push_back(2);
    	vector<int>::iterator it;
    	for (it = v.begin(); it != end ; it++)
    		cout << *it;
    }
    Output:
    Well, nothing.
    Visual Studio pops up a nasty dialog says "vector iterators incompatible."
    So don't count on doing something like this. When you add or delete from a vector, assume that the iterators are invalidated.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    I see. So the iterator returned by .end() is no special case regarding invalidation rules.
    Thank you all!

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,304
    Quote Originally Posted by Elysia
    When you add or delete from a vector, assume that the iterators are invalidated.
    Unless you specifically reserve to prevent reallocation, e.g.,
    Code:
    #include <vector>
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        vector<int> v;
        v.reserve(2);
        v.push_back(1);
        vector<int>::iterator end = v.end();
        v.push_back(2);
        vector<int>::iterator it;
    
        for (it = v.begin(); it != end ; it++)
            cout << *it;
    }
    Actually, thinking about matsp's claim that the assertion may pass for vector... If the capacity is enough, the iterator returned by end() for the empty container could point to the same position as the iterator returned by end() for the container with one element. It would still satisfy the requirements as long as begin() pointed to the same place... however, the flaw could be that begin() might not be allowed to point to the same place since it would be invalidated despite the fact that reallocation does not occur.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21