Custom allocator with preallocated memory for STL containers

Question

I'd like to use a std::vector which allocates the memory for its element from a preallocated buffer. So, I would like to provide a buffer pointer T* buffer of size n to std::vector.

I thought I could simply write a std::span-like class which also provides a push_back method; that would be exactly what I need. However, I've stumbled across the code from this post (see below) which seems to solve this problem with a custom allocator.

Nobody commented on that, but doesn't the example with std::vector<int, PreAllocator<int>> my_vec(PreAllocator<int>(&my_arr[0], 100)); provided in the post end in undefined behavior? I've run the code with the Visual Studio 2019 implementation and at least this implementation is rebinding the provided allocator to allocate an element of type struct std::_Container_proxy. Now this should be a huge problem, since you've only provided memory to store your 100 int's. Am I missing something?

template <typename T>
class PreAllocator
{
private:
    T* memory_ptr;
    std::size_t memory_size;

public:
    typedef std::size_t     size_type;
    typedef T* pointer;
    typedef T               value_type;

    PreAllocator(T* memory_ptr, std::size_t memory_size) : memory_ptr(memory_ptr), memory_size(memory_size) {}

    PreAllocator(const PreAllocator& other) throw() : memory_ptr(other.memory_ptr), memory_size(other.memory_size) {};

    template<typename U>
    PreAllocator(const PreAllocator<U>& other) throw() : memory_ptr(other.memory_ptr), memory_size(other.memory_size) {};

    template<typename U>
    PreAllocator& operator = (const PreAllocator<U>& other) { return *this; }
    PreAllocator<T>& operator = (const PreAllocator& other) { return *this; }
    ~PreAllocator() {}

    pointer allocate(size_type n, const void* hint = 0) { return memory_ptr; }
    void deallocate(T* ptr, size_type n) {}

    size_type max_size() const { return memory_size; }
};

int main()
{
    int my_arr[100] = { 0 };
    std::vector<int, PreAllocator<int>> my_vec(0, PreAllocator<int>(&my_arr[0], 100));
}

Shouldn't a custom allocator throw a bad_alloc exception if memory is exhausted? Generally (from PoV of the standard) I can understand that the behavior is simply _undefined_. — πάντα ῥεῖ, Jan 20 '21 at 15:46
@πάνταῥεῖ This could be fixed by storing a "begin" and "end" pointer, instead of `memory_ptr` and `memory_size` and increasing `begin` by `n` in `allocate`. If `begin + n >= end` we could throw a `std::bad_alloc`. But that doesn't solve the issue that a STL container might allocate internal structures using the provided allocator. — 0xbadf00d, Jan 20 '21 at 15:53
As far I understood the `Allocator` is responsible for the space reserved for the types managed in the STL container class, not for the class data structures itself. All the `Allocator` needs to do is to provide a _placement new_ for `T[]`. — πάντα ῥεῖ, Jan 20 '21 at 15:57
@πάνταῥεῖ Containers like `std::list`, `std::map` et al routinely allocate memory for things other than types managed by the container; that's what `rebind` is for. An allocator only capable of allocating memory for `T` would be pretty useless for `std::list`. I don't believe there's any additional requirement for `std::vector` specifically, that it should only allocate arrays of `T`. — Igor Tandetnik, Jan 20 '21 at 16:00

Andrey Semashev · Answer 1 · 2021-01-20T16:21:16.990

The standard makes no requirement on the types of the objects that are allocated by vector using the provided allocator. The requirements are placed on the storage of the elements (the storage must be contiguous), but the implementation is free to make additional allocations of objects of other types, including the case when the allocator is used to allocate raw storage to place both internal data of the container and the elements. This point is especially relevant to node-based allocators, such as list or map, but it is also valid for vector.

Furthermore, the implementation is free to perform multiple allocation requests as a result of user requests. For example, two calls to push_back may result in two allocation requests. This means that the allocator must keep track of the previously allocated storage and perform new allocations from the unallocated storage. Otherwise, container's internal structures or previously inserted elements may get corrupted.

In this sense, the PreAllocator template, as specified in the question, indeed has multiple issues. Most importantly, it doesn't track allocated memory and always returns the pointer to the beginning of the storage from allocate. This will almost certainly cause problems, unless the user is lucky to use a specific implementation of vector that doesn't allocate anything other than the storage for its elements, and the user is very careful about the operations he invokes on the vector.

Next, the allocator does not detect storage exhaustion. This could lead to out-of-bound error conditions.

Lastly, the allocator does not ensure proper alignment of the allocated storage. The underlying buffer is only aligned to alignof(int), which may not be enough if the container allocates its internal structures that have higher alignment requirements (e.g. if the structures contain pointers, and pointers are larger than int).

The general recommendation when designing allocators is to implement them in terms of raw storage of bytes. That storage may be used to create objects of different types, sizes and alignment requirements, which may be allocated through different copies of the allocator (after rebinding to those other types). In this sense, the allocator type you pass to the container is only a handle, which may be rebound and copied by the container as it sees fit.

Custom allocator with preallocated memory for STL containers

1 Answers1

Linked