9

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.

jick
  • 409
  • 5
  • 12
  • Elements in list should be safe as it should move. I say should as I just discovered a bug yesterday in VC++ where move fails in a place it shouldn't. I'd say test to make sure. It's quite easy. Store a pointer. Then keep adding to the vector to force a relocation. Compare the `.data()` pointers. When vector moves, compare pointers addresses to same element. – CodeAngry Aug 31 '14 at 21:16
  • There are some annoying standard defects, not exactly related to your case, e.g. [see here](http://stackoverflow.com/q/25104021/596781). – Kerrek SB Aug 31 '14 at 21:31
  • Thanks, @KerrekSB, according to dyp's answer in your link, it seems the C++ standards has a proposal named [LWG 2321](http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2321), which would explicitly answer my question as "Yes". So I guess the _current_ (C++11) standard doesn't quite ensure it yet. – jick Aug 31 '14 at 22:25
  • 1
    @jick It doesn't answer your question just yet: it also requires `vector` not to copy any of its elements. If it does copy elements on reallocations, any guarantees on `list`'s move constructor don't apply, since `list`'s copy constructor would be called. `vector` *shouldn't* copy its elements, but I don't know if the standard actually says it doesn't. (I wasn't able to find it, at any rate.) –  Aug 31 '14 at 22:41

2 Answers2

4

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.

Eric Niebler
  • 5,927
  • 2
  • 29
  • 43
  • Thanks for the answer! Hmm, I experimented with g++ (4.7.2) and clang++ (3.5.0) and neither moves/copies the elements (of type T). So I guess the standard does not **require** `vector>` to copy the lists. In any case, is there a technical reason that `std::list`'s move constructor is not `noexcept`, or is it more likely an oversight of the standard committee? – jick Sep 01 '14 at 21:47
  • MS's implementation of `std::list` uses dynamic sentinel nodes (at least in debug?) which means their move constructors are actually really throwing exceptions. – Kerrek SB Sep 01 '14 at 23:20
  • There was some debate on the committee about whether or not adding `noexcept` where the standard doesn't require it was a conforming extension. It was a huge bikeshed debate, and I confess I don't remember which way it went. If adding `noexcept` is not a conforming extension, then libstdc++ is actually not conforming. It just might be required to copy the lists. – Eric Niebler Sep 03 '14 at 04:31
1

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.

Michael Aaron Safyan
  • 93,612
  • 16
  • 138
  • 200
  • Any particular reason why you opted for raw pointers instead of smart pointers? –  Aug 31 '14 at 21:06
  • @hvd that's a good point. Smart pointers would generally be a better approach (depending on the type of ownership in question). I simply meant to illustrate pointer vs value, which is why I didn't pick a particular smart pointer class in my answer. – Michael Aaron Safyan Aug 31 '14 at 21:11
  • Well, in terms of practicality you may be correct, but I feel it's against the "spirit" of C++ if I need to add one level of indirection just to play it safe, unless there's a technical reason. Also, `vector*>` or even `vector>>` is not without pitfall: it means when you extend the vector the new entries will start with a NULL pointer so you always have to remember to instantiate a list object, unlike `vector>` where the compiler guarantees a fresh new list object for me. – jick Aug 31 '14 at 21:18
  • @jick getting null instead of a new list is a benefit, not a downside... it means you only have an allocation for the entries you actually need/add. – Michael Aaron Safyan Aug 31 '14 at 21:19
  • 1
    C++ 11 requires `vector` to move its elements, not copy them, and also requires that moving a `list` does not move its elements. This means that the `list` elements will not end up moved by adding more items to the `vector`. Using pointers here is unnecessary. – Cory Nelson Aug 31 '14 at 21:37
  • 1
    You're mistaken. `vector` is required to use `move_if_noexcept` when doing resizes. `list`'s move constructor is not `noexcept`. The `list`s will be copied, not moved. – Eric Niebler Sep 01 '14 at 05:31
  • I said "should" not "must". Regardless of the behavior in C++11 it is much clearer to write it with pointers explicitly. – Michael Aaron Safyan Sep 01 '14 at 06:12