C++ 线性分配器和容器边界

Question

我正在实施自定义 GUI/game 引擎，并已选择实施异构资源管理器系统。因此，在许多情况下都非常需要自定义分配器。

我确定要使用的分配器之一是简单的线性分配器。我的理解是基本的线性分配器是这样实现的（为简洁起见没有适当的错误处理）：

struct linear_allocator
{
    using value_type = std::byte;
    using pointer = value_type*;
    using size_type = std::size_t;

    explicit linear_allocator(size_type n) noexcept
    {
        data = static_cast<pointer>(::operator new(n, std::nothrow_t{}));
    }

    ~linear_allocator() noexcept
    {
        ::operator delete(data, std::nothrow_t{});
    }

    [[nodiscard]] auto allocate(size_type n) noexcept -> pointer
    {
        auto temp = position;
        position += n;
        return temp;
    }

    auto deallocate(pointer p, size_type n) noexcept -> void
    {
        position = data;
    }

private:
    pointer data = nullptr;
    pointer position = nullptr;
};

我对这个实现的问题在于它的状态。由于这是我代码中对性能极其关键的组件，我担心这不是最佳的，而且很可能容易出错。

因为分配器包含指向初始数据根的指针和位置，因此它包含有关如何遍历内存和数据大小的信息。这意味着我要么需要提供成员数据的访问器，要么在采用此分配器的容器中提供重复的簿记信息。

在我看来，更好的解决方案是让容器拥有状态信息并将分配留给容器。因此，容器将包含所有相关信息，并且没有重复簿记。此外，如果仅在容器的构造函数中进行分配，并且仅在容器的析构函数中进行释放，则可以实现与线性分配器相同的行为。但如果这是真的，分配器似乎不再需要构造函数或析构函数，我还不如利用 std::allocator。如果是这种情况......线性分配器的目的是什么？

我似乎说服自己认为线性分配器是一种反模式。我实际上正在寻找的是某种紧密包装的异构容器，而线性分配器似乎是分配器和容器概念的奇怪合并。存储分类帐的自定义向量（如果堆包含不同大小的对象，则用于索引访问）和数据堆似乎更符合要求。

有人能解释一下分配器和容器之间的界限应该在哪里吗（尤其是在标准库的上下文中）？我假设我的理由有误。

编辑：根据下面 Eugene 的建议，我重写了我的 allocation/container 方案，如下所示（注意，这缺少 copy/move 构造函数，分配等，我只是暂时删除了......但应该在某些时候正确实施）。所提供答案的主要内容是 command_vector 构造函数和析构函数负责分配，而 linear_allocator class 现在是无状态且简单的。代码大致如下所示（我意识到我可以而且应该能够调用 alloc.allocate() 一次而不是在这里分割出 3 个单独的块）：

command_vector 容器 class

template<typename key_t, typename alloc_t = linear_allocator<std::byte>>
struct command_vector
{
    using key_type = key_t;
    using value_type = std::byte;
    using pointer = value_type*;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using allocator = alloc_t;
    using iterator = command_packet*;
    using const_iterator = const iterator;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    explicit command_vector() noexcept :
        alloc{},
        keys{ alloc.allocate(packet_count) },
        packets{ alloc.allocate(packet_count) },
        packet_pos{ packets },
        heap{ alloc.allocate(heap_size) },
        heap_pos{ heap }
    {
        
    }

    explicit command_vector(size_type max_packets, size_type max_heap) noexcept :
        alloc{},
        keys{ alloc.allocate(max_packets) },
        packets{ alloc.allocate(max_packets) },
        packet_pos{ packets },
        heap{ alloc.allocate(max_heap) },
        heap_pos{ heap }
    {

    }

    constexpr command_vector(key_type* keys, pointer packets, pointer heap) noexcept requires std::is_same_v<alloc_t, null_allocator<value_type>> :
        alloc{},
        keys{ keys },
        packets{ packets },
        packet_pos{ packets },
        heap{ heap },
        heap_pos{ heap }
    {
        
    }

    constexpr command_vector(const command_vector&) noexcept = delete;
    constexpr command_vector(command_vector&&) noexcept = delete;
    constexpr auto operator=(const command_vector&) noexcept -> command_vector& = delete;
    constexpr auto operator=(command_vector&&) noexcept -> command_vector& = delete;

    ~command_vector() noexcept
    {
        if constexpr (!std::is_same_v<allocator, null_allocator<value_type>>)
        {
            alloc.deallocate(packets);
            alloc.deallocate(heap);
        }
    }

    template<typename command_t>
    constexpr auto push_back(command_t&& command) noexcept -> void
    {
        *heap_pos   = command;
        *packet_pos = make_packet(std::forward<command_t>(command));

        heap_pos   += sizeof(std::decay_t<command_t>);
        ++packet_pos;
    }

    constexpr auto pop_back() noexcept -> void
    {
        --packet_pos;
        heap_pos = static_cast<pointer>(packet_pos->command);
    }

    constexpr auto clear() noexcept -> void
    {
        packet_pos = packets;
        heap_pos = heap;
    }

    constexpr auto size() noexcept -> difference_type
    {
        return packet_pos - packets;
    }

    constexpr auto begin()   -> iterator               { return packets;    }
    constexpr auto end()     -> iterator               { return packet_pos; }
    constexpr auto cbegin()  -> const_iterator         { return begin();    }
    constexpr auto cend()    -> const_iterator         { return end();      }
    constexpr auto rbegin()  -> reverse_iterator       { return end();      }
    constexpr auto rend()    -> reverse_iterator       { return begin();    }
    constexpr auto crbegin() -> const_reverse_iterator { return cend();     }
    constexpr auto crend()   -> const_reverse_iterator { return cbegin();   }

private:

    allocator alloc{};
    key_type* keys{};
    command_packet* packets{};
    command_packet* packet_pos{};
    pointer heap{};
    pointer heap_pos{};
};

null_allocatorclass

template<typename val_t>
struct null_allocator
{
    using value_type = val_t;
    using pointer = value_type*;
    using size_type = std::size_t;

    [[nodiscard]] constexpr auto allocate(size_type n) noexcept -> pointer
    {
        return nullptr;
    }

    constexpr auto deallocate(pointer p, size_type n) noexcept -> void
    {
        
    }
};

linear_allocator class

template<typename val_t>
struct linear_allocator
{
    using value_type = val_t;
    using pointer = value_type*;
    using size_type = std::size_t;

    [[nodiscard]] auto allocate(size_type n) noexcept -> pointer
    {
        return static_cast<pointer>(::operator new(n, std::nothrow_t{}));
    }

    auto deallocate(pointer p, size_type n) noexcept -> void
    {
        ::operator delete(p, std::nothrow_t{});
    }
};

Answer 1

please explain where the boundaries should be between allocators and containers are supposed to be

您不应该从分配器开始设计 - 它们是实现细节。从容器开始。选择具有您需要的接口的容器、最频繁操作的低算法复杂性、迭代器失效保证、异常安全保证...

完成后，测量速度。如果程序太慢并且您的容器是基于节点的，您可能可以通过自定义分配器来加速它。当然，要击败通用的 C++ 动态内存机制，您必须了解一些关于您的使用模式的特殊之处。例如，您可能希望一次释放大块内存。

编辑： 容器包含与您的问题相关的所有状态。分配器通常是无状态的——有状态分配器甚至在 C++11 之前都不是标准的。有状态分配器旨在从不同的内存池分配内存，所有状态都与池相关。

您的 linear_allocator 有问题。首先，deallocate() 应该是空的——所有内存都应该在它的 dtor 中释放。其次，它不处理复制——这是真正困难的部分——我不确定正确的语义是什么。尽管我是一位经验丰富的 C++ 程序员，但我不敢自己设计这个分配器。

A custom vector that stores a ledger (for index access if the heap contains objects of varying sizes) and a heap for data seems to be more along the lines of what is required.

如果您需要异构数据的容器，那么这听起来不错。例如，您可能需要 std::vector<std::unique_ptr<BaseClass>>。或者，您可以考虑 std::vector<std::variant<..>>。当然，您可能需要 std::vector<>.

以外的容器

C++ 线性分配器和容器边界

C++ Linear Allocator and Container Boundaries

c++

containers

memory-management

stl

allocator