Compile-time array with runtime variable size

The code in this post is bad. Its purpose is only to show what I want to say.

An array has fixed size and compile-time allocation and it’s preferred in some real-time situations. If you want a variable number of elements, you could choose a vector. A vector has runtime allocation on the heap, which cannot always offer the predictability and performance required by some applications.

But what if you need both? Compile-time allocation and a different number of elements each time a function is called with some data from a source. You can use an array and a variable for the number of elements:

// Declare the maximum number of elements and the array
constexpr std::size_t max_size = 10;
std::array<int, max_size> elements{4, 5};

// Each call, you will get the elements array and
// the number of elements sent
std::size_t number_of_elements = 2;

// You should make sure the number of elements is not greater
// than the maximum
if (number_of_elements > max_size) {
    throw std::out_of_range{"too many elements"};
}

auto work = [](const std::array<int, max_size>& elements, const std::size_t number_of_elements) {
    // Then iterate through all the elements passed this time
    for (auto it = elements.begin(); it != elements.begin() + number_of_elements; ++it) {
        // ...
    }
};

work(elements, number_of_elements);

Some problems with this approach:

    • all functions that need this array must include the number of elements in their signature
    • the number of elements could be altered by mistake
    • each time you iterate the array you must specify which is its end

It would great to have a container similar to an array/vector that would prevent the issues above. Maybe there is already an implementation for this but I didn’t find it. So I wrote a few lines which partially implement this container. The idea is to have perfect integration with all STD algorithms, to be able to use it like it was an array.

My container is far from the idea of perfect, it just shows some features. I’m actually wrapping an STD array and using two iterators: one for writing data into the array and one for reading. The usage is pretty simple.

You can declare an empty array:

VariableSizeArray<int, 3> empty_vsarray;

assert(empty_vsarray.size() == 0);
static_assert(empty_vsarray.max_size() == 3, "max size not 3");
assert(empty_vsarray.empty());

Or one with some values:

VariableSizeArray<int, 3> vsarray_with_values = {1, 2};

assert(vsarray_with_values.size() == 2);
static_assert(vsarray_with_values.max_size() == 3, "max size not 3");
assert(!vsarray_with_values.empty());

assert(vsarray_with_values.front() == 1);
assert(vsarray_with_values[1] == 2);
try {
    vsarray_with_values.at(2);
}
catch (const std::out_of_range& ex) {
    std::cout << ex.what() << '\n';
}

 

And the fun part comes. If you get some input elements from a source and the number of elements, you can copy them into the VariableSizeArray, then you use it as an STD array. My implementation  requires you to use begin/end only for writing and cbegin/cend only for reading, because the write iterator will alter the variable size of the array.

// External input
std::array<int, 5> input = {1, 2, 3};
std::size_t count = 3;

// Copy data into the variable size array
VariableSizeArray<int, 3> output;
std::copy(input.cbegin(), input.cbegin() + count, output.begin());

// Then use as an STD array
assert(output[0] == 1);
assert(output[1] == 2);
assert(output[2] == 3);
assert(output.size() == 3);

assert(std::accumulate(output.cbegin(), output.cend(), 0) == 6);

for (auto it = output.cbegin(); it != output.cend(); ++it) {
    std::cout << *it << "\n";
    break;
}
assert(output.size() == 3);

for (std::size_t i = 0; i < output.size(); ++i) {
    std::cout << output.at(i) << "\n";
}
assert(output.size() == 3);

Of course, it would be great to use like this:

for (auto element : output) {
    // ...
}

But it uses the write iterator and, if you put a break in the for loop, the size will be incorrect after the loop.

The implementation is basic, the particularity being the iterators:

template <typename T, std::size_t MaxSize>
class VariableSizeArray {
   public:
    using value_type = T;
    using size_type = std::size_t;
    using reference = value_type&;
    using iterator = WriteIterator<T, MaxSize>;

    constexpr VariableSizeArray() : data_{}, size_{0} {};

    template <typename... Types>
    VariableSizeArray(Types... elements) : data_{elements...}, size_{sizeof...(elements)}
    {
        static_assert(sizeof...(elements) <= MaxSize, "too many elements");
    }

    WriteIterator<T, MaxSize> begin() noexcept
    {
        size_ = 0;
        return WriteIterator<T, MaxSize>{data_.data(), size_};
    }

    WriteIterator<T, MaxSize> end() noexcept { return WriteIterator<T, MaxSize>{data_ + size_, size_}; }

    ReadIterator<T> cbegin() const noexcept { return ReadIterator<T>{data_.data()}; }

    ReadIterator<T> cend() const noexcept { return ReadIterator<T>{data_.data() + size_}; }

    reference at(size_type index)
    {
        if (index >= size_) {
            throw std::out_of_range{"index is greater than variable size"};
        }

        return data_[index];
    }

    reference operator[](size_type index) { return data_[index]; }
    reference front() noexcept { return data_[0]; }
    reference back() noexcept { return data_[size_]; }
    reference data() noexcept { return data_; }

    bool empty() const noexcept { return size_ == 0; }
    size_type size() const noexcept { return size_; }
    constexpr size_type max_size() const noexcept { return MaxSize; }

   private:
    std::array<T, MaxSize> data_;
    size_type size_;
};

Besides a pointer to the array elements, the writer iterator is given a reference to the variable size of the array, so it can increment it each time its increment operator is called.

template <typename T, std::size_t MaxSize>
struct WriteIterator {
    using value_type = T;
    using pointer = value_type*;
    using reference = value_type&;

    pointer ptr;
    std::size_t& size_;

    WriteIterator operator++()
    {
        if (size_ + 1 > MaxSize) {
            throw std::out_of_range{"max size exceeded"};
        }

        ++size_;
        ++ptr;

        return *this;
    }

    reference operator*() { return *ptr; }

    pointer operator->() { return ptr; }

    bool operator!=(const WriteIterator& it) { return ptr != it.ptr; }
};

What’s special about this iterator is that it needs an iterator_traits specialization for the std::copy operation:

template <typename T, std::size_t MaxSize>
struct std::iterator_traits<WriteIterator<T, MaxSize>> {
    using value_type = typename WriteIterator<T, MaxSize>::value_type;
};

And the read iterator is, of course, the read-only counterpart.

template <typename T>
struct ReadIterator {
    using value_type = T;
    using const_pointer = const value_type*;
    using const_reference = const value_type&;

    const_pointer ptr;

    ReadIterator operator++()
    {
        ++ptr;
        return *this;
    }

    const_reference operator*() const { return *ptr; }

    const_pointer operator->() const { return ptr; }

    bool operator!=(const ReadIterator& it) const { return ptr != it.ptr; }
};

 

You can download the source code and try it, maybe new ideas come up.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.