views:

152

answers:

4

all the STL containers that implement resize use copies to populate the new elements even if the source of the copy is a default constructed object?

Why is it done this way?

I see no advantage and some cost.


As context, I ran across this while looking for a random access container for elements that can't be copied:

+1  A: 

In your case, perhaps you'd be better off storing the pointers to those objects in the container -- a pointer can be copied.

Regarding copying in a container; what's the alternative? If you've had to reallocate a new block of memory to store whatever's being stored, you have to get the existing data in there somehow!

Edmund
@Edmund - the latter is only necessary if you need to keep things contiguous. There are other alternatives.
D.Shawley
untyped allocation, placement new and a default constructor would do it for even oversizes block allocations.
BCS
A: 

The only reason that I can think of for this behavior is that the containers support insertion and insertion requires a copy. You should be able to create a container that supports resize in a manner similar to a deque (paged and non-contiguous) that default constructs the new elements. However, you would have to disallow assignment of the entire container along with insertion of elements - you could modify objects constructed in the collection instead.

My guess is that no one saw the need for a collection that does not support insertion and does not implement value-type copying. As another note, you should probably tag this as a wiki before it gets closed ;)

D.Shawley
The way they did it seams to make the interface arbitrarily and unnecessarily wider. OTOH some types of collection might not be able to get around it and making it uniform has it's advantages.
BCS
+3  A: 

It saves on complexity. We certainly need the copy-construction case, and default-construction can be modeled as replicating a default-constructed object.

The performance penalty is negligible. Writing zeroes is about the same speed as copying zeroes. The compatibility penalty is nil since all containers require copyability anyway. Default-construction on the other hand isn't required.

If you really want to use standard containers with non-copyable objects, look into C++0x and in-place construction with emplace. However, there is no method to emplace multiple elements at once. (If you're using deque, there shouldn't be much performance penalty to an emplace loop vs. resize though.)

Potatoswatter
@Potatoswatter: even with `vector`, you can always use `reserve` ahead of time to negate the performance impact.
Matthieu M.
@Matthieu: Yep. `vector::reserve` can incur a `move`/copy, though.
Potatoswatter
@Potatoswatter: indeed, in case of an insufficient capacity.
Matthieu M.
A: 

The standard containers define the requirements CopyConstructible and Assignable on the value type, and those requirements are sufficient to support all of the operations on containers and sequences (you might also want them to be comparable for associative containers, but even that's not required since you can instead supply a comparator).

What you're asking for, is to have one set of requirements for a set of operations consisting of part of the Container plus something from Sequence (namely 1-parameter resize() on those containers which never relocate their contents, operator[], clear() and the iterator interface excluding *it = t), and another set of requirements for the rest. The standard libraries prefer to do this the other way around: choose a common set of requirements which cover almost everything, and then have additional requirements for small bits of functionality (like the requirement to be default-constructible in order to call resize() without specifying the second parameter).

Containers just weren't conceived with your specific set of operations in mind - copying and assigning are intrinsic to what they're designed to do, which is to contain values that are put into them, so I speculate that in Stepanov's mind that is not a "small bit of functionality". So the wider requirements are there because the abstraction Container is bigger than your proposed ResizeableCollectionOfDefaultConstructedObjects. In fact, take away resize() and CollectionOfDefaultConstructedObjects is pretty much just an array. I guess that the designers of the STL and the C++ standard didn't encounter your use-case often enough to think it worth abstracting.

Steve Jessop