Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Will std::vectors inside another vector reallocate when the first vector reallocates?

Tags:

I have a vector std::vector<std::vector<ContactPairs>> m_contactPairs;

If I call m_contactPairs.push_back() or any other function that will resize the outermost vector, will the elements inside that vector have to reallocate (the inner elements in this case being std::vector<ContactPairs>), or will the inner vectors just do a shallow copy and keep pointing at the same memory they already own?

I'm using Visual Studio 2010, which is prior C++11, but has some of the functionality as extensions

like image 395
Anne Quinn Avatar asked Jan 27 '15 15:01

Anne Quinn


People also ask

What happens when you std :: move a vector?

std::move. std::move is used to indicate that an object t may be "moved from", i.e. allowing the efficient transfer of resources from t to another object. In particular, std::move produces an xvalue expression that identifies its argument t . It is exactly equivalent to a static_cast to an rvalue reference type.

How do I move one vector to another in C++?

You can't move elements from one vector to another the way you are thinking about; you will always have to erase the element positions from the first vector. If you want to change all the elements from the first vector into the second and vice versa you can use swap. @R.

Does vector erase reallocate?

Use vector::erase . It will not reallocate memory. If your erased range does not extend to the end of the container, it WILL re-locate the end elements. That means the ending elements will be move d to their proper spot in memory which likely incurs a data copy.

What happens when vector is full in C++?

It will sit there on its stack position and wait to get destroyed, regardless of how much memory it handles itself on the heap.


1 Answers

Short answer: It depends on the standard you are using and the library implementation:

  • In C++98 and C++03 there is no move, hence everything will be deeply copied including a reallocation.
  • In C++11 and C++14 there will be a deep copy including a reallocation, or, if the implementation provides a noexcept on the move constructor of std::vector<ContactPairs>.
  • In the upcoming C++17 the inner vector will be moved and no deep copy is performed.

And here's the reasoning:

  1. The inner vectors type std::vector<ContactPairs> has a move constructor which is noexcept according to the upcoming C++17 standard (as of N4296) and not noexcept according to the C++11 and C++14 standards, section [vector.modifiers]. You can also find this here. However, even C++11 and C++14 compliant implementations may specify noexcept, since implementations may provide stronger guarantees than prescribed by the standard (see C++ Standard 17.6.5.12). Many implemetations do not do that yet though.

  2. The implementation of the std::vector<T>::push_back() is required to guarantee strong exception safety, i. e. if it throws there are no side-effects. (See the C++ standard, section [container.requirements.general] §10 or §11 or here.)

  3. If the new size of the vector on which you call push_back() exceeds its capacity, then memory needs to be allocated for the new spot and the elements need to be copied or moved to the new spot. If moving the elements of the outer vector can fail (no noexcept), then the elements need to be copied in order to implement the strong exception guarantee. In this case, each copy of an inner vector does require an additional allocation. However, if moving is noexcept, then the whole moving-in-a-loop cannot throw and is safe to use to implement the strong exception guarantee.

Implementing std::vector<T> move construction with the noexcept guarantee seems to be a trivial thing for std::vector. I suspect, the standards committee might have been hesitant to put this guarantee into the standard for consistency's sake: For other node-based containers it can be beneficial to have sentinel nodes, which require an allocation even for default construction. Since the moved-from container needs to be valid after the move, there might be an allocation necessary for an std::list move which might throw, for example. Hence, there's no noexcept guarantee for the move constructor of std::list and other node-based standard container types.

like image 58
Ralph Tandetzky Avatar answered Oct 04 '22 17:10

Ralph Tandetzky