ISO/IEC JTC1 SC22 WG21 P00210r0

Date: 2016-01-29

To: LEWG

Thomas Köppe <tkoeppe@google.com>

A light-weight, compact dynamic array

Contents

  1. Summary
  2. Impact
  3. Synopsis
  4. Limitations
  5. Appendix I: What’s wrong with dynamic arrays?
  6. Appendix II: Early feedback
  7. Acknowledgements

Summary

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 modifications:

Bike shed: what is it called? The first obvious problem is how to name this container. Names like flexible_array or flarray seem unwieldy, small_vector suggests SSO-like optimisations, 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:

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. new 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 have resize().

Example.

compact_vector<compact_vector<short>> v(1000000); for (auto & x : v) {     x.resize(make_number(), make_default_value());     process(x.begin(), x.end()); }

Using a 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.

Impact

This is a pure library extension.

Synopsis

template <typename T, typename Alloc = allocator<T>> class compact_vector { public:    // "types" as in vector    // "constructor/copy/destroy" as in vector, requiring ForwardIterator    // "iterators" as in vector    // "capacity"    size_type size() const noexcept;    bool empty() const noexcept;    void resize(size_type n);    void resize(size_type n, const T & value);    // "element access" as in vector    // "data access" as in vector    // "modifiers"    void swap(compact_vector &) noexcept(allocator_traits::<A>::propagate_on_container_swap::value || allocator_traits::<A>::is_always_equal::value);    void clear() noexcept;    // relational operators as in vector    // "specialized algorithms" as in vector    explicit operator vector<T, Alloc>&&() && noexcept; };

Notes

Limitations

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 std::unique_ptr<char[]>(new char[n]).

Appendix I: What’s wrong with dynamic arrays?

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.

Appendix II: Early feedback

A draft of this paper was circulated on the LEWG reflector for early feedback. Here are some arbitrarily selected responses.

Acknowledgements

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 compact_vector.