ISO/IEC JTC1 SC22 WG21 P00210r0
To: LEWGThomas Köppe <email@example.com>
Short form. We propose a light-weight, dynamic array which is in every
aspect identical to
std::vector<T, A> except that it does not allow
efficient size-changing operations. For many use cases, the two containers can be used
interchangeably, but the light-weight container will typically only consume 2/3 of the space
of a vector, since it does not need to keep track of a capacity separately from the size. In
other words, it is just like
std::vector<T, A> with the following
resize(n)always reallocates unless
n == size().
Bike shed: what is it called? The first obvious problem is how to name
this container. Names like
flarray seem unwieldy,
small_vector suggests SSO-like
vlarray is too much like VLA
or valarray, and
dyn_array is too close to
dynarray. As a
placeholder we use “
compact_vector” for now, with the understanding
that this will need to be revised. We are open to suggestions.
What this proposal is not: A preliminary discussion on the reflector showed that a lot of people have specific expectations, desires and goals in this design space. We would like to establish clear boundaries for this proposal:
std::dynarray. This proposal does not share the goals of
dynarray, and it comes with its own motivation and rationale.
First and foremost we would like this proposal to be considered in isolation and on its own merits. We will gladly work on unification and harmonising with the authors of any other paper in this design space that LEWG finds desirable, once that time comes.
Long rationale. The author considers dynamic arrays (i.e.
T[n]()) a misfeature of the language (see the appendix for a
summary of its failings). In almost every way, one may replace such a dynamic array with
std::vector<T>(n), except for the undeniable fact that a vector is
larger. While we already need to store and communicate the size of a dynamic array in order
to use it safely, there is generally no reason for the cost of keeping a separate capacity
counter around. Until now, the library has been missing a simpler dynamic container that
meets precisely, and without the cost of unwanted generality, those needs which currently
call for dynamic arrays.
The solution. We propose a new container class template, for now and for
exposition only referred to as
compact_vector, which is in every aspect like
std::vector, except that it does not have growing insertion operations,
shrinking erasure operations, or a notion of capacity. Note in particular that we still
vector<short> instead of
compact_vector<short> would require a million unused additional
capacity pointers. If the size of each
v[i] is small, this may well be
a non-trivial cost which the proposed container avoids.
This is a pure library extension.
assignrequire forward iterators (so as to be able to precompute the size).
compact_vectorto be implemented in such a fashion that the allocated storage can be transplanted into a
vectorwith the same template arguments. Note that we do not have the opposite operation, stealing from a vector. To do so we would require a vector whose size is equal to its capacity, which cannot be achieved portably. This would be nice to have in the future, since it would allow using a
vectoras a “builder” for a “frozen”
resizefunction is called with
n != size().
We can replace uses of
new T[n]() and most uses of
new T[n] with
compact_vector<T>(n). The only feature that we deliberately choose not
to provide is uninitialised storage, like
new char[n]. User code benefits
from uninitialised allocations (and this is a real use case!), but it requires cooperation
from the user for correctness. Users requiring uninitialised storage can resort to
Dynamic arrays, i.e. arrays created via either
new T[n] or some placement variant
thereof, are an odd-man-out in many regards. We will enumerate a few.
Base * p = new Deriveddoes at least contain an expression with which one might statically derive a description of the created object, even though that code snippet does not capture it.)
new Tmeans something surprising when
Tis an array type, and
p->~T()is ill-formed. This means, for example, that there is no straightforward notion of an
allocate_sharedfor a shared pointer to an array; rather, we have a sequence of elements under shared ownership which are destroyed by a hand-crafted deleter that destroys array elements.
+ y”) remains unresolved (cf. CWG 476, EWG 68).
T * ptr = new T[n];have shown the general confusion between something that is empty and something which consists of
A draft of this paper was circulated on the LEWG reflector for early feedback. Here are some arbitrarily selected responses.
The author wishes to thank everyone who provided valuable feedback on the LEWG reflector.
Particular thanks go to David Krauss, Edward Smith-Rowland and Howard Hinnant for
improving the stealing interface, and to Ville Voutilainen for suggesting the name