Validity of iterator after insert for std::list and std::vector

Question

Suppose, there are two iterator pointing at different places at different places.

For a list, are they still valid if an item is inserted between them?

If I understood correctly, a std::list object is usually implemented as a doubly-linked list, hence upon an insertion (or a deletion) the the iterators are still valid.

However, for an array, I believe this is not the case. If an item is now deleted between two iterators - does that mean the iterator pointing to the item toward the end of the vector now points at the subsequent item (or the end iterator if the second iterator is pointing at the last time)

Is my understand correct?

See __Iterator invalidation__ here - https://en.cppreference.com/w/cpp/container/vector — Richard Critten, Aug 02 '20 at 16:45
Better is this summary of [iterator invalidation across all containers](https://en.cppreference.com/w/cpp/container). — Raymond Chen, Aug 02 '20 at 16:46

score 2 · Accepted Answer · answered Aug 02 '20 at 16:47

2

iterators shows location on memory. Iterator behavior depends on representation of container in memory. As you said, std::list is implemented using linked list. nodes can be anywhere in memory. They are connected with next pointer of previous node. so if you insert an item in between two items, their location on memory is kept.

But in the case of array or vector, where container is stored as contiguous memory if you want to insert or delete an item between two elements you have to shift one of the elements or construct the array/vector somewhere else. This is why iterators may not be valid in insert or delete operation. It is better to use remove and erase idiom instead of deleting while iterating so that your algorithms are abstracted from underlying data structure.

answered Aug 02 '20 at 16:47

Muhammet Ali Asan

1,486
22
39

let me make this clear - in the case of a vector, if something is removed, then the iterators became invalid (because there is a chance the vector has been moved?) – Lost1 Aug 02 '20 at 16:50
1

@Lost1, erasing an element from a vector never causes a reallocation, so iterators before that element remain valid, and those after it are invalidated. – Evg Aug 02 '20 at 16:51
yes elements are definitely moved. but it depends on implementation of erase. instead of moving remaining elements, one compiler may allocate a new vector in different memory with remaining elements. But in any case iterators are not staying valid. – Muhammet Ali Asan Aug 02 '20 at 16:55

Validity of iterator after insert for std::list and std::vector

1 Answers1