How to define a safe container or view for variable size arrays (vector) without dynamic memory allocation (heap)?

Question

Constraints: On the target platform I can neither use dynamic memory allocation nor the C++ Standard Library or any other third-party libraries. The language is restricted to C++11 without the usage of compiler specific extensions.

How to handle arrays (or non-owning views) with variable size without dynamic memory allocation and guarantee of valid memory? The size can not be part of the type (as for example with std::array). Arrays can be defined statically. The container type does not need to own the elements but can be initialized with (a pointer to) static memory. The main objective is that the provided data / elements are in valid memory. Secondary would be that the container object provides the number of (valid) elements.

For example the following shall be achieved:

struct S { X x; };

Where S has a fixed size and X is some kind of container pointing to or composed of a number of elements. The number of elements shall not be part of the type X (shall be no class template depending on the size) but is constant for each object and may be a const member.

It must be ensured that the memory pointed to is valid. For example it shall not point to a former automatic variable.

The following things did not work out:

• Usage of std::vector (or similar): Would require to implement that container without the use of dynamic memory allocation.
• In a similar question it has been suggested to use boost::container::static_vector. The caveat is that the maximum capacity has to be statically served for each object, if I understood it correctly. This is not feasible as it can not be estimated what a suitable limit would be. Also allocating superfluous static memory must be avoided as memory is expensive on the target platform.
• std::array can not be used as it contains the size in its type.
• Usage of alloca() is out of question.

I did define a non-owning view over a contiguous sequence of objects (resembling template<class T> std::span<T, std::dynamic_extent>) and initialize it with an array with static storage duration. Here is a simplified example:

This is the example type:

template<typename ElementType>
struct Container
{
    public:
    // type containing size can be used to pass size to `Container()` as template argument
    template<ElementType * POINTER, std::size_t N> struct Configuration {};

    // constructor accepts pointer to object with static storage duration only
    template<ElementType * POINTER, std::size_t N> 
    Container(const Configuration<POINTER, N>&) : data(POINTER), numberOfElements(N) {}

    //! @return number of elements
    constexpr std::size_t size() const noexcept { return numberOfElements; }

    constexpr ElementType& operator[](const std::size_t index) const noexcept { return data[index]; }

    private:
    ElementType* const data;
    const std::size_t numberOfElements;
};

The restriction to static storage duration of the pointer is achieved by the constructor. This needs an object of Container::Configuration. This in turn requires a pointer as template argument which must have static storage duration (by language definition).

Here is how to use it:

// prints the elements of the container
template<typename T>
void printElements(const Container<T>& container)
{
    for(std::size_t i=0; i<container.size(); ++i)
    {
        std::cout << container[i] << " ";
    }
    std::cout << std::endl;
}

// array with static storage duration 
int globalArray[] = { 1111, 2222, 3333, 4444 };

int main()
{    
    Container<int>::Configuration<globalArray, sizeof(globalArray)/sizeof(globalArray[0])> arrayConfig;
    Container<int> cB(arrayConfig);
    printElements(cB);

    return 0;
}

It accomplishes that the argument passed to printElements can not point to invalid memory.

This works so far in simple examples. It also contains the size which is useful compared to a plain pointer. And would be even more handy if local static values would have static storage duration in C++11 (they have apparently in C++17).

Before I require this type to be used on a large scale within the target software I wonder if there may be more suitable ways to achieve the desired safety guarantees.

Answer 1

Usage of std::vector (or similar): Would require to implement that container without the use of dynamic memory allocation.

Yes. So you write your own allocator that works on a static pool. Really, implement dynamic allocation, just on a staticcally allocated buffer. I think this is the way you should go.

Theoretically (i've been never able to do it properly) you can estimate the maximum stack usage of your program at compile time in certain environments (no recursive functions, no threads, all libraries are statically linked/bare-metal target, etc...). The rest of the memory can go for a statically allocated buffer for dynamic allocation. But if you can't calculate it, you can estimate some maximum value of free memory you have on your system. Well, if the memory on your platform is precious and you run out of memory, no magic trick is going to help you. Expect re-writting everything to use less memory or moving to a target with more memory.

boost::pool_alloc. And some standard containers like std::vector take an allocator as a template argument. Assuming you have no dynamic allocation, you could link with your own implementation of new() and such functions implementing the standard allocator on your own.

std::array can not be used as it contains the size in its type.

So use std::array and convert it to span.

Or better - write your own std::array that just takes a static buffer with size as the constructor. Or right - it's a span.

And a C++20 span implementation compatible with C++11 is available here. I recommend to use it.

template<typename T>
void printElements(T container)
{
    for (auto& i : container)
    {
        std::cout << container[i] << " ";
    }
    std::cout << std::endl;
}

// array with static storage duration 
int globalArray[] = { 1111, 2222, 3333, 4444 };

#include <tcb/span.hpp>
using tcb::span;

int main()
{    
    span<int> cB(globalArray, 
                 globalArray + sizeof(globalArray)/sizeof(globalArray[0]));
    printElements(cB);
    return 0;
}

Also, if you choose to implement your own container, please follow the naming from standard library. Define member types like value_type allocator_type size_type etc. and functions like begin(), push_back() etc. It will be easier for others to use it.

If you need full vector functionality like push_back and pop etc. just implement your own that takes a buffer as a constructor parameter. Like this:

/*
 * vector.hpp
 *
 *  Created on: 7 lut 2019
 *      Author: Kamil Cukrowski
 *     License: Under GPLv2+ license.
 */
#ifndef STACK_VECTOR_HPP_
#define STACK_VECTOR_HPP_

#include <cstddef>
#include <array>
#include <algorithm>
#include <iterator>
#include <cassert>

namespace stack {

/**
 * Vector on statically allocated buffer
 */
template<typename T>
class vector {
public:
    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference = T &;
    using const_reference = const 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>;

private:
    T *_mem{nullptr};
    size_type N{0};
    size_type _pos{0};

public:
    vector(T *_mem, std::size_t count) :
        _mem(_mem), N(count) {}

    constexpr pointer
    data() noexcept
    { return _mem; }

    constexpr const_pointer
    data() const noexcept
    { return _mem; }


    constexpr iterator
    begin() noexcept
    { return iterator(data()); }

    constexpr const_iterator
    begin() const noexcept
    { return const_iterator(data()); }

    constexpr iterator
    end() noexcept
    { return iterator(data() + _pos); }

    constexpr const_iterator
    end() const noexcept
    { return const_iterator(data() + _pos); }


    constexpr const_iterator
    cbegin() const noexcept
    { return const_iterator(data()); }

    constexpr const_iterator
    cend() const noexcept
    { return const_iterator(end()); }


    constexpr const_iterator
    max_end() const noexcept
    { return const_iterator(_mem + N); }

    constexpr size_type
    size() const noexcept
    { return _pos; }

    constexpr size_type
    capacity() const noexcept
    { return _mem.size(); }

    constexpr bool
    full() const noexcept
    { return end() == max_end(); }

    constexpr bool
    empty() const noexcept
    { return begin() == end(); }

    constexpr reference
    front() noexcept
    { return *begin(); }

    constexpr const_reference
    front() const noexcept
    { return *begin(); }

    constexpr reference
    back() noexcept
    { return *(end() - 1); }

    constexpr const_reference
    back() const noexcept
    { return *(end() - 1); }

    constexpr size_type
    free() const noexcept
    { return max_end() - end(); }

    constexpr const_reference
    operator[](size_type idx) const noexcept
    { return _mem[idx]; }

    constexpr reference
    operator[](size_type idx) noexcept
    { return _mem[idx]; }

    constexpr reference
    at(size_type idx) {
        if (idx > size()) {
            throw std::out_of_range("");
        }
        return this->operator[](idx);
    }

    constexpr reference
    at(size_type idx) const {
        if (idx > size()) {
            throw std::out_of_range("");
        }
        return this->operator[](idx);
    }

private:
    constexpr bool
    _is_valid_iterator(const_iterator position) noexcept
    {
        return begin() <= position && position <= end();
    }

    constexpr bool
    _is_valid_iterator_range(const_iterator first, const_iterator last) noexcept
    {
        return _is_valid_iterator(first) &&
                _is_valid_iterator(last) &&
                first < last;
    }

public:
    constexpr void
    clear() noexcept
    { _pos = 0; }

    constexpr iterator
    insert(iterator position, value_type&& data) noexcept
    {
        if (!_is_valid_iterator(position)) {
            return iterator{};
        }
        *position = data;
        return position;
    }

    constexpr int
    push_back(value_type data) noexcept {
        return push_back_n(&data, 1);
    }

    constexpr int
    push_back_n(const_pointer data, std::size_t n) noexcept {
        if (free() < n) return -1;
        std::copy_n(data, n, end());
        _pos += n;
        return 0;
    }

    constexpr int
    pop_back() noexcept
    { return empty() ? -1 : ((_pos--), 0); }

    constexpr void
    resize(size_type count) noexcept
    {
        if (count <= capacity()) {
            _pos = count;
        }
    }

    constexpr void
    resize(size_type count, const value_type& value) noexcept {
        if (count <= capacity()) {
            if (count > size()) {
                std::move(end(), end() + count - size(), value);
            }
            resize(count);
        }
    }

    constexpr void
    shift_left(size_type n) noexcept {
        std::move(begin() + n, end(), begin());
        _pos -= n;
    }

    constexpr void
    shift_left(iterator newbegin) noexcept {
        assert(_is_valid_iterator(newbegin));
        shift_left(newbegin - begin());
    }

    constexpr int
    shift_right(size_type count, const T& init = T{}) noexcept
    {
        assert(0);
        if (count + size() > capacity()) {
            return -1;
        }
        std::move_backward(begin(), end(), end() + count);
        std::fill(begin(), begin() + count, init);
        _pos += count;
        return 0;
    }

    constexpr void
    input_advance(difference_type n) {
        _pos += n;
        assert(0 <= _pos && _pos <= capacity());
    }
};

}

#endif

It was meant to hold only simple types, so there are no placement new used. For anything more complicated, this is just a start - you would need to call placement_new and proper constructors for element T on ex. push_back and call destructores when doing pop_back() and such operations. And I use noexcept in some places - the code base didn't use any exception, because they usually call dynamic allocation.

Usage example:

#include <iostream>

int main() {
    std::array<int, 5> _mem_for_vector;
    stack::vector<int> v{_mem_for_vector.data(), 5};
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    // will print 1 2 3 on separate lines
    for (auto& i : v) {
        std::cout << i << std::endl;
    }
}