Menu
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.
873
You want to avoid taking the address of elements in a vector if at all possible precisely because of the unpredictable nature of reallocations. If you have to, use iterators instead of raw addresses, since checked STL implementations will tell you when they have become invalid, instead of randomly crashing.
Vector may have a default size. List does not have default size. In vector, each element only requires the space for itself only. In list, each element requires extra space for the node which holds the element, including pointers to the next and previous elements in the list.
If you don't need to insert elements often then a vector will be more efficient. It has much better CPU cache locality than a list. In other words, accessing one element makes it very likely that the next element is present in the cache and can be retrieved without having to read slow RAM.
Vectors are assigned memory in blocks of contiguous locations. When the memory allocated for the vector falls short of storing new elements, a new memory block is allocated to vector and all elements are copied from the old location to the new location. This reallocation of elements helps vectors to grow when required.
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.
68
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.
30
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
