I have two questions regarding iterators.
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++; } }
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; } }
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, usingiter
is undefined behavior (you will likely crash).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.