0

I'm learning c++ iterators.

While poking around with various excercises and algorithms, I was astonished by finding out that .begin() and .end() change address after adding elements. This breaks things like boundary checking of an iterator stored before a push_back().

I'm even more baffled that the different addresses still apparently resolve to the correct payload.

I replicated a basic example that just does basic allocation and show how the addresses change:

#include <cstdio>
#include <vector>

int main()
{
    printf("std vector push back changes begin and end\n");

    auto show_vector_stats = []( std::vector<int> &iras32_source )
    {
        printf("Begin: %p | End: %p | Diff: %d | Size: %d\n", iras32_source.begin(), iras32_source.end(), iras32_source.end() -iras32_source.begin(), iras32_source.size() );
    };

    //Create a vector
    std::vector<int> as32_my_array;
    show_vector_stats( as32_my_array );
    //add first element
    as32_my_array.push_back( 999 );
    show_vector_stats( as32_my_array );
    //Store iterator and index of first element
    int index_first_element = 0;
    std::vector<int>::iterator iterator_first_element = as32_my_array.begin();
    printf("Index from Iterator: %d\n", iterator_first_element -as32_my_array.begin());
    //Store more elements
    as32_my_array.push_back( 2 );
    show_vector_stats( as32_my_array );

    for (int s32_cnt = 0; s32_cnt < 10; s32_cnt++)
    {
        as32_my_array.push_back( 101 +s32_cnt);
    }
    show_vector_stats( as32_my_array );
    //Access by previously stored index and iterators
    printf("Access by index: %d | Address of element: %p\n", as32_my_array[index_first_element], &as32_my_array[index_first_element] );
    printf("Access by iterator: %d | Address of element: %p\n", *iterator_first_element, iterator_first_element );
    printf("Index from Iterator: %d\n", iterator_first_element -as32_my_array.begin());

    return 0;
}

OUTPUT:

std vector push back changes begin and end
Begin: 00000000 | End: 00000000 | Diff: 0 | Size: 0
Begin: 00fc1a80 | End: 00fc1a84 | Diff: 1 | Size: 1
Index from Iterator: 0
Begin: 00fc1b70 | End: 00fc1b78 | Diff: 2 | Size: 2
Begin: 00fcac28 | End: 00fcac58 | Diff: 12 | Size: 12
Access by index: 999 | Address of element: 00fcac28
Access by iterator: 999 | Address of element: 00fc1a80
Index from Iterator: -9322

Process returned 0 (0x0)   execution time : 0.050 s
Press any key to continue.

I was under the impression that modern iterators were a drop-in superior and more modern version of indexes. But some things like checking a previous iterator against a more recent .begin() will return a wrong index, like in the example above, begin()-iterator returns 0 the first time, and returns -9322 after some more elements are added...

The difference between .end() and .begin() shows the correct vector size. Likewise, in a loop without changes, the difference iterator-begin() will show the correct index.

The documentations doesn't mention that begin() will return a different address potentially with every push_back(). Only that it's empty at the beginning, like the example above shows. https://cplusplus.com/reference/vector/vector/begin/

Are iterators ONLY supposed to be used for read only loops? Am I missing something, like I'm I resolving addresses wrong?

05032 Mendicant Bias
  • 571
  • 1
  • 5
  • 15
  • 1
    Iterators become invalidated when adding elements to a vector. – PaulMcKenzie Nov 04 '22 at 08:27
  • https://stackoverflow.com/questions/6438086/iterator-invalidation-rules-for-c-containers – 463035818_is_not_an_ai Nov 04 '22 at 08:28
  • 3
    *The documentations doesn't mention that begin() will return a different address potentially with every push_back()* -- [Yes it does](https://en.cppreference.com/w/cpp/container/vector/push_back) -- "*If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated.*" – PaulMcKenzie Nov 04 '22 at 08:29
  • 1
    "drop-in superior and more modern version of indexes." no. They are drop-in superior replacements for pointers. But they arent magic. If the adress of an element changes then an iterator to it is invalidated just as a pointer is – 463035818_is_not_an_ai Nov 04 '22 at 08:31
  • 1
    btw `std::vector`s iterators often are just pointers. They refer to an element. An index alone is not sufficient to refer to an element in a container, you'd need some reference to the container as well, but typically iterators carray little to no information about the container – 463035818_is_not_an_ai Nov 04 '22 at 08:33
  • 1
    Also, the documentation you pointed to is for `vector:begin`, not `vector::push_back`. If you [go to the documentation at that site](https://cplusplus.com/reference/vector/vector/push_back/), you will see it mention that iterators are invalidated. Also in passing, note that the site that I linked to is considered superior to the one you linked to. – PaulMcKenzie Nov 04 '22 at 08:34
  • 1
    Conceptually iterators are not pointers. In some cases they can be implemented as pointers but mostly they are objects with a dereference operator. The end iterator doesn't represent an adress but an element not contained in the collection. – Pepijn Kramer Nov 04 '22 at 08:35
  • 1
    The only official documentation of C++ is the C++ standard, which does mention the invalidation of iterators, see http://eel.is/c++draft/vector#modifiers-2. If you use any other source of information, you need to be aware that it might be incomplete, imprecise, incorrect, misleading, etc. (I would suggest you at least to prefer cppreference.com to cplusplus.com.) – Daniel Langr Nov 04 '22 at 08:47
  • Thanks for the clarification, now I understand better how vector is meant to be used. Thanks for listing more authoritative references for c++. I think the documentation of .begin() and .end() should also clarify when its output becomes invalidated. Just to be clear, if I want to store the position of an element safely, I should store an index and fed that to either [] or .at()? – 05032 Mendicant Bias Nov 04 '22 at 08:52
  • well, an index might also become invalid, depending on what operations you perform on the vector – Neil Butterworth Nov 04 '22 at 08:56

0 Answers0