具有用于STL容器的预分配内存的自定义分配器 [英] Custom allocator with preallocated memory for STL containers

问题描述

我想使用 std :: vector ，它从预分配的缓冲区中为其元素分配内存.因此，我想提供大小为 n 到 std :: vector 的大小为 n 的缓冲区指针 T *缓冲区.

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.

我以为我可以简单地编写一个类似于 std :: span 的类，该类还提供一个 push_back 方法.那正是我所需要的.但是，我偶然发现了这篇文章(参见下文)中的代码，这似乎可以通过自定义分配器解决此问题

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.

没有人对此发表评论，但没有提供带有 std :: vector< int，PreAllocator< int>>的示例.my_vec(PreAllocator< int>(& my_arr [0]，100)); 以未定义的行为提供在后端?我已使用Visual Studio 2019实现运行代码，至少此实现重新绑定了提供的分配器，以分配类型为 struct std :: _ Container_proxy 的元素.现在这应该是一个很大的问题，因为您只提供了存储100个 int 的内存.我想念什么吗?

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));
}

推荐答案

该标准对使用提供的分配器由 vector 分配的对象的类型没有要求.需求放在元素的存储上(存储必须是连续的)，但是实现可以自由分配其他类型的对象，包括使用分配器分配原始存储以放置两个内部数据的情况容器和元素.这一点与基于节点的分配器(例如 list 或 map )特别相关，但对于 vector 也有效.

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.

此外，由于用户请求，该实现可以自由执行多个分配请求.例如，两次调用 push_back 可能会导致两个分配请求.这意味着分配器必须跟踪先前分配的存储，并从未分配的存储中执行新的分配.否则，容器的内部结构或先前插入的元素可能会损坏.

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.

从这个意义上讲，问题中指定的 PreAllocator 模板确实存在多个问题.最重要的是，它不会跟踪分配的内存，并且总是从 allocate 返回指向存储开头的指针.这几乎肯定会引起问题，除非用户幸运地使用 vector 的特定实现，该实现除了为其元素分配存储空间外不分配任何其他东西，并且用户对其操作非常谨慎在 vector 上调用.

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.

最后，分配器无法确保分配的存储正确对齐.基础缓冲区仅与 alignof(int)对齐，如果容器分配其具有更高对齐要求的内部结构(例如，如果结构包含指针，并且指针大于 int ).

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.

这篇关于具有用于STL容器的预分配内存的自定义分配器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！