CODEWITHSUNDEEP
pointersc++11vectorstl
jick
jick

Reputation: 409

Does vector<list<T>> guarantee that element addresses stay unchanged?

We all know that addresses of elements in vector<T> may change when we append more elements (due to resizing), while elements in list<T> remains at the same address.

The question is, what about vector<list<T>>? For example,

vector<list<T>> container;
// Insert some elements to container...
T* ptr = &(container[0].back());
// Insert more elements to container...

Can we assume that ptr stays valid?

Naively, I think it should, because when the vector resizes it should call the move constructor of list<T>, which should not copy/move individual elements. However, I don't know if the standard ensures this.

Upvotes: 9

Views: 393

Answers (2)

Eric Niebler
Eric Niebler

Reputation: 6177

Sorry, no. std::list's move constructor is not noexcept. std::vector used std::move_if_noexcept when doing resizes, which will be copies for the contained std::lists. All the list nodes will be allocated and copied. Their addresses will not be stable.

Upvotes: 4

Michael Aaron Safyan
Michael Aaron Safyan

Reputation: 95569

You should probably make it a vector<list<T>*> rather than a vector<list<T>>. With a vector<list<T>*>, you can be certain that the contained pointers will not be changed (and that there won't be any heavy-weight copying of the inner lists) as they are values of the vector and the values of the vector are not changed by the expansion logic. This is much safer than relying on the copying of the internal lists to only move the head element and not reallocate any of the remaining nodes (it's also more understandable). Doing it the other way is difficult to understand and is just playing with fire.

Upvotes: 1

Related Questions