How to avoid std::vector to copy on (re-)allocation?

Question

I just stumbled into an issue with std::vector when adding new elements to it.

It seems when you try to add more elements to it, and it needs to allocate more space, it does so by copying ~~last element~~ all elements it currently holds. This seems to assume that any element in the vector is fully valid, and as such a copy will always succeed.

In our case, this is not necessarily true. Currently we might have some left over elements in the vector, because we chose not to remove them yet, which are valid objects, but their data doesn't guarantee valid behavior. The objects have guards, but I never considered adding guards to a copy constructor as I assumed we would never be copying an invalid object (which vector forces) :

CopiedClass::CopiedClass(const CopiedClass& other)
    : member(other.member)
{
    member->DoSomething();
}

It just so happened that "member" is nulled when we are done with the original object and leave it lying about in the vector, so when std::vector tries to copy it, it crashes.

Is it possible to prevent std::vector from copying that element? Or do we have to guard against possible invalid objects being copied? Ideally we'd like to keep assuming that only valid objects are created, but that seems to imply we immediately clean them from the vector, rather than waiting and doing it at some later stage.

So you have an object that during its lifetime can become uncopyable? — NathanOliver, Oct 28 '15 at 17:45
`std::vector ` always takes copies on `push_back()`, and no you can't prevent this behavior. — πάντα ῥεῖ, Oct 28 '15 at 17:45
@πάνταῥεῖ I don' think that part is the issue. I believe the problem is the copies when the vector goes through a reallocation. — NathanOliver, Oct 28 '15 at 17:47
Initialize the vector via `vector_member(filter_garbage(other.vector_member))` in affected copy constructors (and do similar in assignment operators (maybe copy/swap)) — , Oct 28 '15 at 17:50
"It seems when you try to add more elements to it, and it needs to allocate more space, it does so by copying the last element it currently holds". Such behaviour would go right against both the standard and the common sense. Can you demonstrate it? — n. m. could be an AI, Oct 28 '15 at 17:52
How do you know if an element is invalid in the vector? Do you store this information somewhere else? E.g.: an index after which all elements are invalid? If so, you probably need your own container which *has* this knowledge. — Karoly Horvath, Oct 28 '15 at 17:55
_@Zepee_ Sounds like a serious design flaw for me, however you could eventually use a `std::list` to avoid the behavior. — πάντα ῥεῖ, Oct 28 '15 at 17:56
When you try to add more elements to a vector than it has space for, what do you expect should happen? It allocates a new, larger buffer and copies all the elements to it. That's the only possible thing it can do (well, it could refuse to insert the extra element, and would do so with a specialized allocator). — Marc Glisse, Oct 28 '15 at 18:12
One workaround would be to use a wrapper class that fixes the deficiency of your class. You could use `unique_ptr` as the wrapper. As a bonus, this would generate errors if you try to do something obviously insane, such as trying to copy the vector. — David Schwartz, Oct 28 '15 at 19:11
For clarification, yes it wasn't copying the last element... It was obviously copying all elements when re-allocating... I feel silly — Zepee, Oct 29 '15 at 09:51
The C++11 tag means you can fix this by adding a guard and at the same time add move support. Once you have the guard then you're safe against crashes accessing moved elements (because after the move the original will be invalid), and if you have more than a few bytes of data in each element the move operation will be a lot faster than a copy. — Zan Lynx, Jul 17 '16 at 01:38

score 7 · Accepted Answer · edited May 23 '17 at 11:58

It's actually a design flaw in your CopiedClass that needs to be fixed.

std::vector behaves as expected and documented.

From the little code you show

member->DoSomething();

this indicates you are going to take a shallow copy of a pointer to what ever.

in our case, this is not necessarily true. Currently we might have some left over elements in the vector, because we chose not to remove them yet, which are valid objects, but their data doesn't guarantee valid behavior.

It just so happened that "member" is nulled when we are done with the original object and leave it lying about in the vector, so when std::vector tries to copy it, it crashes.

As your copy constructor doesn't handle that situation correctly regarding following the Rule of Three your design of CopiedClass is wrong.

You should either care to create a deep copy of your member, or use a smart pointer (or a plain instance member), rather than a raw pointer.

The smart pointers should take care of the management for these members correctly.

Also for the code snippet from above, you should test against nullpointer before blindly dereferencing and calling DoSomething().

Is it possible to prevent std::vector from copying that element?

As you're asking for c++11 it's possible, but requires you never change the size of the vector, and provide a move constructor and assignment operator for CopiedClass.

Otherwise, std::vector explicitly requires copyable types (at least for certain operations):

T must meet the requirements of CopyAssignable and CopyConstructible.

It's your responsibility to meet these requirements correctly.

... it does so by copying the last element it currently holds.

Also note: In a situation the vector needs to be resized, all of the existing elements will be copied, not only the last one as you premise.

Since C++11, the requirement of copyable types only applies to certain operations. Otherwise, `std::vector>` would not be possible. — Christian Hackl, Oct 28 '15 at 18:14
@ChristianHackl Anyways it's not a question of the vector's behavior, but a faulty design of the class contained here. — πάντα ῥεῖ, Oct 28 '15 at 18:24
Absolutely. It should be refactored. (By the way, I did not downvote.) — Christian Hackl, Oct 28 '15 at 18:25
@ChristianHackl I also don't get the downvote (never suspected it was you beloved neighbor). People don't seem to get what I'm writing here. — πάντα ῥεῖ, Oct 28 '15 at 18:27
Very comprehensive answer. You're absolutely right, it is a design flaw and a bad assumption to make.. I was definitely more curious and confused as to why a previous element was being copied, which of course is the vector allocating a larger memory block and moving it's current data over... Back to data structures basics much... Thanks guys — Zepee, Oct 29 '15 at 09:49

score 2 · Answer 2 · answered Oct 28 '15 at 19:04

If you know the vector's maximum size in advance, then a workaround for this issue would be calling reserve with that maximum size. When the vector's capacity is big enough, no reallocations occur and no copies of existing elements need to be made.

But that's really just a workaround. You should redesign your class such that copying cannot suddenly become an invalid operation, either by making copying safe or by disallowing it and perhaps replace it with moving, like std::unique_ptr. If you make the validity of copying dependent on some run-time status, then you don't even need a std::vector to get into trouble. A simple CopiedClass get(); will be a potential error.

edmz · Answer 3 · 2015-10-29T10:04:05.337

It seems when you try to add more elements to it, and it needs to allocate more space, it does so by copying the last element it currently holds. This seems to assume that any element in the vector is fully valid, and as such a copy will always succeed.

Both sentences are not really correct. When vector runs out of space it, yes, performs reallocation, but of all the elements and these are copied to the new location or possibly moved. When you push_back or emplace_back, and reallocation is needed, the element will generally by copied: if an exception is thrown during that, it will be treated as if you had never added the element. If vector detects a noexcept user-defined move constructor ( MoveInsertable concept), elements are moved; if this constructor though is not noexcept, and an exception is thrown, the result is unspecified.

The objects have guards, but I never considered adding guards to a copy constructor as I assumed we would never be copying an invalid object (which vector forces) :

vector copies its value_type: it does not care whether what it contains is valid or invalid. You should take care of that in your copy control methods, whose scope is exactly to define how the object is passed around.

CopiedClass::CopiedClass(const CopiedClass& other)
    : member(other.member)
{
    member->DoSomething();
}

The obvious solution would be to check if member is valid and act thereby.

if (member.internalData.isValid())
    member->DoSomething()
// acknowledge this.member's data is invalid

We don't know how member is represented, but Boost.Optional is what you may be looking for.

Is it possible to prevent std::vector from copying that element?

Reallocation is something vector is expected to commit so, no, you can't. reserv-ing space could avoid that, but maintaining code to handle that would not really be painless. Rather, prefer a container like std::forward_list/std::list.

How to avoid std::vector to copy on (re-)allocation?

3 Answers3