Is there a standard C++ class for arrays with fixed run-time-determined size?

Question

I need a container with run-time known size with no need to resizing. std::unique_ptr<T[]> would be a useful, but there is no encapsulated size member. In the same time std::array is for compile type size only. Hence I need some combination of these classes with no/minimal overhead.

Is there a standard class for my needs, maybe something in upcoming C++20?

Answer 1

Use std::vector. This is the class for runtime sized array in the STL.

It let you resize it or pushing elements into it:

auto vec = std::vector<int>{};

vec.resize(10); // now vector has 10 ints 0 initialized
vec.push_back(1); // now 11 ints

---

Some problems stated in the comments:

vector has an excessive interface

So is std::array. You have more than 20 function in std::array including operators.

Just don't use what you don't need. You don't pay for the function you won't use. It won't even increase your binary size.

vector will force initialize items on resize. As far as I know, it is not allowed to use operator[] for indexes >= size (despite calling reserve).

This is not how it is meant to be used. When reserving you should then resize the vector with resize or by pushing elements into it. You say vector will force initialize elements into it, but the problem is that you cannot call operator= on unconstructed objects, including ints.

Here's an example using reserve:

auto vec = std::vector<int>{};

vec.reserve(10); // capacity of at least 10
vec.resize(3); // Contains 3 zero initialized ints.

// If you don't want to `force` initialize elements
// you should push or emplace element into it:

vec.emplace_back(1); // no reallocation for the three operations.
vec.emplace_back(2); // no default initialize either.
vec.emplace_back(3); // ints constructed with arguments in emplace_back

---

Keep in mind that there is a high chance for such allocation and use case, the compiler may completely elide construction of elements in the vector. There may be no overhead in your code.

I would suggest to measure and profile if your code is subject to very precise performance specification. If you do not have such specification, most likely this is premature optimization. The cost of memory allocation completely out measure the time it takes to initialize elements one by one.

Other parts of your program may be refactored to gain much more performance than trivial initialization can offer you. In fact, getting in the way of it may hinder optimization and make your program slower.

Answer 2

Allocate the memory using an std::unique_ptr<T[]> like you suggested, but to use it - construct an std::span (in C++20; gsl::span before C++20) from the raw pointer and the number of elements, and pass the span around (by value; spans are reference-types, sort of). The span will give you all the bells and whistles of a container: size, iterators, ranged-for, the works.

#include <span>
// or:
// #include <gsl/span>

int main() {

    // ... etc. ...

    {
        size_t size = 10e5;
        auto uptr { std::make_unique<double[]>(size) };
        std::span<int> my_span { uptr.get(), size };
        do_stuff_with_the_doubles(my_span);
    }

    // ... etc. ...
}

For more information about spans, see:

What is a "span" and when should I use one?

Answer 3

Use std::vector. If you want to remove the possibility of changing it's size, wrap it.

template <typename T>
single_allocation_vector : private std::vector<T>, public gsl::span<T>
{
    single_allocation_vector(size_t n, T t = {}) : vector(n, t), span(vector::data(), n) {}
    // other constructors to taste
};

Answer 4

Something called std::dynarray was proposed for C++14:

std::dynarray is a sequence container that encapsulates arrays with a size that is fixed at construction and does not change throughout the lifetime of the object.

But there were too many issues and it didn't become part of the standard.

So there exists no such container currently in the STL. You can keep using vectors with an initial size.

Answer 5

Unfortunately, no new containers were added in C++ 20 (at least none that I'd be aware of). I would agree, however, that such a container would be very useful. While just using std::vector<T> with reserve() and emplace_back() will usually do OK, it does often generate inferior code compared to using a plain new T[] as the use of emplace_back() seems to inhibit vectorization. If we use an std::vector<T> with an initial size instead, compilers seem to have trouble optimizing away the value initialization of elements, even if the entire vector is going to be overwritten right afterwards. Play with an example here.

You could use, for example, a wrapper like

template <typename T>
struct default_init_wrapper
{
    T t;

public:
    default_init_wrapper() {}
    template <typename... Args>
    default_init_wrapper(Args&&... args) : t(std::forward<Args>(args)...) {}

    operator const T&() const { return t; }
    operator T&() { return t; }
};

and

std::vector<no_init_wrapper<T>> buffer(N);

to avoid the useless initialization for trivial types. Doing so seems to lead to code similarly good as the plain std::unique_ptr version. I wouldn't recommend this though, as it's quite ugly and cubmersome to use, since you then have to work with a vector of wrapped elements.

I guess the best option for now is to just roll your own container. This may serve as a starting point (beware of bugs):

template <typename T>
class dynamic_array
{
public:
    using value_type = T;
    using reference = T&;
    using const_reference = T&;
    using pointer = T*;
    using const_pointer = const T*;
    using iterator = T*;
    using const_iterator = const T*;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;

private:
    std::unique_ptr<T[]> elements;
    size_type num_elements = 0U;

    friend void swap(dynamic_array& a, dynamic_array& b)
    {
        using std::swap;
        swap(a.elements, b.elements);
        swap(a.num_elements, b.num_elements);
    }

    static auto alloc(size_type size)
    {
        return std::unique_ptr<T[]> { new T[size] };
    }

    void checkRange(size_type i) const
    {
        if (!(i < num_elements))
            throw std::out_of_range("dynamic_array index out of range");
    }

public:
    const_pointer data() const { return &elements[0]; }
    pointer data() { return &elements[0]; }

    const_iterator begin() const { return data(); }
    iterator begin() { return data(); }

    const_iterator end() const { return data() + num_elements; }
    iterator end() { return data() + num_elements; }

    const_reverse_iterator rbegin() const { return std::make_reverse_iterator(end()); }
    reverse_iterator rbegin() { return std::make_reverse_iterator(end()); }

    const_reverse_iterator rend() const { return std::make_reverse_iterator(begin()); }
    reverse_iterator rend() { return std::make_reverse_iterator(begin()); }

    const_reference operator [](size_type i) const { return elements[i]; }
    reference operator [](size_type i) { return elements[i]; }

    const_reference at(size_type i) const { return checkRange(i), elements[i]; }
    reference at(size_type i) { return checkRange(i), elements[i]; }

    size_type size() const { return num_elements; }

    constexpr size_type max_size() const { return std::numeric_limits<size_type>::max(); }

    bool empty() const { return std::size(*this) == 0U; }

    dynamic_array() = default;

    dynamic_array(size_type size)
        : elements(alloc(size)), num_elements(size)
    {
    }

    dynamic_array(std::initializer_list<T> elements)
        : elements(alloc(std::size(elements))), num_elements(std::size(elements))
    {
        std::copy(std::begin(elements), std::end(elements), std::begin(*this));
    }

    dynamic_array(const dynamic_array& arr)
    {
        auto new_elements = alloc(std::size(arr));
        std::copy(std::begin(arr), std::end(arr), &new_elements[0]);
        elements = std::move(new_elements);
        num_elements = std::size(arr);
    }

    dynamic_array(dynamic_array&&) = default;

    dynamic_array& operator =(const dynamic_array& arr)
    {
        return *this = dynamic_array(arr);
    }

    dynamic_array& operator =(dynamic_array&&) = default;

    void swap(dynamic_array& arr)
    {
        void swap(dynamic_array& a, dynamic_array& b);
        swap(*this, arr);
    }

    friend bool operator ==(const dynamic_array& a, const dynamic_array& b)
    {
        return std::equal(std::begin(a), std::end(a), std::begin(b));
    }

    friend bool operator !=(const dynamic_array& a, const dynamic_array& b)
    {
        return !(a == b);
    }
};