CODEWITHSUNDEEP
c++vectorstl
Anne Quinn
Anne Quinn

Reputation: 13002

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

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

Upvotes: 20

Views: 1505

Answers (2)

Ralph Tandetzky
Ralph Tandetzky

Reputation: 23600

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.

Upvotes: 16

Drew Dormann
Drew Dormann

Reputation: 63745

In C++03, a std::vector reallocation will copy ("deep copy") each element. That means for your situation, each vector would be copied.

In C++11 or later, a std::vector reallocation will move each element only if the elements have a move constructor that is noexcept.

Visual Studio 2010 lacks noexcept support, so you would still get a deep copy.

Upvotes: 9

Related Questions