List iterator vs. vector iterator

Question

I have two questions regarding iterators.

1. I thought the once you define an iterator to an STL container such as a vector or a list, if you add elements to the containers then these iterators won't be able to access them. But the following code defines a list of five elements and then adds another element in each loop iteration and results in an infinite loop:

   #include <iostream>
   #include <list>
   
   using namespace std;
   
   int main()
   {
       list<int> ls;
   
       for(int i = 0; i < 5; i++)
       {
           ls.push_back(i);
       }
   
       int idx = 0;
   
       for(list<int>::iterator iter = ls.begin(); iter != ls.end(); iter++)
       {
           cout << "idx: " << idx << ", *iter: " << *iter << endl;
           ls.push_back(7);
           idx++;
       }
   }
   

   However, doing the same for a vector results in an error:

   #include <iostream>
   #include <vector>
   
   using namespace std;
   
   int main()
   {
       vector<int> vec;
   
       for(int i = 0; i < 5; i++)
       {
           vec.push_back(i);
       }
   
       int idx = 0;
   
       for(vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++)
       {
           cout << "idx: " << idx << ", *iter: " << *iter << endl;
           vec.push_back(7);
           idx++;
       }
   }
   

2. I thought that when the vector container must be resized, it does so at powers of 2 and is located to a new area of memory, which is why you shouldn't define an iterator to a vector if you adding elements to it (since the iterators don't get passed to the new memory location). For example, I thought a vector containing 16 elements, after calling the push_back function, will be allocated space for 32 elements and the entire vector will be relocated. However, the this didn't happen for the following code. Was I just mistaken?

   #include <iostream>
   #include <vector>
   
   using namespace std;
   
   int main()
   {
       vector<int> vec;
   
       for(int i = 0; i < 4; i++)
       {
           vec.push_back(i);
           cout << "address of vec: " << &vec << ", capacity: " << vec.capacity() << endl;
       }
   
   
   
       for(int i = 0; i < 20; i++)
       {
           vec.push_back(i);
           cout << "address of vec: " << &vec << ", capacity: " << vec.capacity() << endl;
       }
   }
   

Answer 1

Different container's iterators have different properties. Here are the iterator invalidation rules.

The list loop: When you push onto a list all previous iterators still valid. You will never hit the end if every time you iterator forward one you also add a new element, obviously.

The vector loop: For a vector, your iterators are invalid once a push_back results in the new size exceeding the old capacity. As soon as this happens, using iter is undefined behavior (you will likely crash).

I thought that when the vector container must be resized, it does so at powers of 2 and is located to a new area of memory

This is unspecified by the standard. Some implementations of the C++ standard library double the capacity of a vector when the size exceeds the old capacity, and others grow at different rates.

Answer 2

The answer on your first question is contained in the second your question.

As for the second question then it is implementation defined how the vector allocates the memory. It is not necessary that it will double the size of the memory each time when it is exhausted.

Answer 3

The different containers generally have different guarantees with respect to the validity of iterators, and pointers/references to elements:

1. For std::list<T> the iterators and pointers/references to elements stay valid until the corresponding node gets erased or the std::list<T> exists.
2. For std::vector<T> the validity is more complicated:
   1. Iterator and pointer/reference validity is identical (and I'll only use iterators below).
   2. All iterators are invalidated when the std::vector<T> needs to resize its internal buffer, i.e., when inserting exceeds the capacity. When the capacity is exceeded and how much memory is allocated depends on the implementation (the only requirement is that the capacity grows exponentially and a factor of 2 is a reasonable choice but there are many others).
   3. When inserting into a std::vector<T> all iterators before the insertion point stay valid unless reallocation is necessary.
   4. When erasing from a std::vector<T> all iterators past the erase point are invalidated.

Other containers have, yet, different validity constraints (e.g. std::deque<T> keeps invalidating iterators but can keep pointers/references valid).