In my project I am trying to create a vector and saving an iterator pointing to some element of the vector that I may want to remove later. In the meantime new elements will be added to the vector and after adding some elements I want to delete the iterator that I had saved from the vector.
This is what I tried to do:
std::vector<foo> vec;
vec.push_back(foo());
std::vector<foo>::iterator it = vec.begin();
for (int i = 0; i < 10; i ) {
vec.push_back(foo());
}
vec.erase(it);
But by doing it this way, there is a execution error that says "Vector erase iterator outside range" Why is this approach wrong? And how can I do it right?
CodePudding user response:
Vector iterators are invalidated on reallocation, when the size exceeds the reserved capacity. Since you didn't do a vec.reserve(10)
, any of the push_back's could invalidate it
.
Note that .reserve
itself can cause a reallocation, so that has to happen before the initialization of it
.
CodePudding user response:
Yes since your code invokes undefined behavior.
Adding items to vector invalidates all iterator and use of invalidated iterator leads to undefined behavior.
Reason is that there is some reserved memory for items of vector. When this memory is not enough to hold new item, new fragment of memory is allocated and content is copied to new place. Then old fragment of memory is freed. Old iterator still points to old place which was just freed.
In documentation you can find:
std::vector<T,Allocator>::push_back - cppreference.com
If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.
To fix issue (and make code faster) you can reserve required amount of space for given number of items.
CodePudding user response:
This example will show you what happens, the more elements you add to a vector the more memory it needs. A vector will "grow" and move elements around in memory. (That's also why a call to reserve can speed up your code but that's another story)
#include <vector>
#include <iostream>
struct foo {};
int main()
{
std::vector<foo> vec;
vec.push_back(foo());
std::vector<foo>::iterator it = vec.begin();
auto capacity = vec.capacity();
for (int i = 0; i < 20; i )
{
std::cout << "iteration " << i << ", size = " << vec.size() << ", capacity = " << vec.capacity() << "\n";
vec.push_back(foo());
if (capacity != vec.capacity())
{
std::cout << "vector memory has been reallocated, all iterators are no longer valid\n";
capacity = vec.capacity();
}
}
//vec.erase(it);
}