Menu
I don't understand why a vector's iterator should be invalidated when a reallocation happens.
Couldn't this have been prevented simply by storing an offset -- instead of a pointer -- in the iterator?
Why was vector not designed this way?
991
Iterator Invalidation in C++ When the container to which an Iterator points changes shape internally, i.e. when elements are moved from one position to another, and the initial iterator still points to the old invalid location, then it is called Iterator invalidation. One should be careful while using iterators in C++.
Same as like insert or erase. All iterators and the references are invalidated if the inserted item is not inserted at the end of the deque. If the items are deleted from any of the position except the end position, then all iterators will be invalidated. Same as like insert or erase.
For reference, std::vector::swap does not invalidate iterators.
For std::vector , all iterators are invalidated after calling insert if it causes the vector's size() to exceed its capacity() (i.e. it must reallocate).
Just to add a citation to the performance-related justification: when designing C++, Stroustrup thought it was vital that template classes like std::vector approach the performance characteristics of native arrays:
One reason for the emphasis on run-time efficiency...was that I wanted templates to be efficient enough in time and space to be used for low-level types such as arrays and lists.
...
Higher-level alternatives -- say, a range-checked array with a size() operation, a multidimensional array, a vector type with proper numeric vector operations and copy semantics, etc. -- would be accepted by users only if their run-time, space, and notational convenience approached those of built-in arrays.
In other words, the language mechanism supplying parameterized types should be such that a concerned user should be able to afford to eliminate the use of arrays in favor of a standard library class.
Bjarne Stroustrup, Design and Evolution of C++, p.342.
94
Because for iterators to do that, they'd need to store a pointer to the vector object. For each data access, they'd need to follow the pointer to the vector, then follow the pointer therein to the current location of the data array, then add the offset * the element size. That'd be much slower, and need more memory for the size_type member.
Certainly, it's a good compromise sometimes and it would be nice to be able to choose it when wanted, but it's slower and bulkier than (C-style) direct array usage. std::vector was ruthlessly scrutinised for performance when the STL was being introduced, and the normal implementation is optimised for space and speed over this convenience/reliability factor, just as the array-equivalent operator[] is as fast as arrays but less safe than at().
25
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
