为std::multiset预先分配存储

Question

我希望对std::multiset使用预先分配的存储。我对它的大小有一个上限，预先知道，但只有在运行时才知道。因此，我编写了一个类似于这个的堆栈分配器。如果请求的元素超过一个，它将使用标准分配器作为后盾：

template<class T>
class PreallocStackAllocator
{
public:
    using Chunk        = std::aligned_storage_t<sizeof(T), alignof(T)>;
    using ChunkPointer = Chunk*;
    static_assert(sizeof(Chunk) >= sizeof(T));

    using value_type = T;

    explicit PreallocStackAllocator(size_t capacity)
        : m_freelist{std::make_unique<ChunkPointer[]>(capacity)}
        , m_freelist_end{capacity}
        , m_storage{std::make_unique<Chunk[]>(capacity)}
        , m_capacity{capacity}
    {
        std::generate_n(m_freelist.get(),
                        capacity,
                        [base_address = m_storage.get(), k = static_cast<size_t>(0)]() mutable {
                            auto ret = base_address + k;
                            ++k;
                        return ret;
                    });
    }

    [[nodiscard]] T* allocate(size_t n)
    {
        if(n != 1) [[unlikely]]
        {
            return m_default_allocator.allocate(n);
        }

        assert(m_freelist_end != 0);
        --m_freelist_end;
        return reinterpret_cast<T*>(m_freelist[m_freelist_end]);
    }

    void deallocate(T* ptr, size_t n)
    {
        if(n != 1) [[unlikely]]
        {
            return m_default_allocator.deallocate(ptr, n);
        }

        if(ptr == nullptr) { return; }

        m_freelist[m_freelist_end] = reinterpret_cast<Chunk*>(ptr);
        ++m_freelist_end;
    }

    std::span<size_t const> freelist() const
    {
        return std::span{m_freelist.get(), m_freelist_end};
    }

    size_t capacity() const { return m_capacity; }

private:
    std::unique_ptr<ChunkPointer[]> m_freelist;
    size_t m_freelist_end;
    std::unique_ptr<Chunk[]> m_storage;
    size_t m_capacity;
    [[no_unique_address]] std::allocator<T> m_default_allocator;
};

这一实施有两个问题：

分配程序

1. 必须是可复制的，而且上面的类是不可能复制的.特别是，一个块将包含指向其他块的指针。因此，如果重新分配m_storage，链接就会中断。这里必须使用std::shared_ptr吗？或者复制应该简单地创建一个具有源容量的分配器，而不关心源的当前状态？

当使用自定义分配器实例化容器时，

1. 将使用分配器创建它，该分配器将为capacity T:s分配空间，并使用capacity指针创建空闲列表。然而，在现实中，我们永远不会分配T:s，而是std::_Rb_tree_node。据我所知，这个映射是通过重新绑定元函数完成的。无论如何，我们现在也会为真正的内容分配空间，但是当我们创建原始的分配器时，我们已经浪费了空间。如何解决这个问题？

Answer 1

结果，我可以使用代理分配器，它的目的是转发要分配的元素数：

    namespace prealloc_multiset_detail
    {
        template<class T>
        class Allocator: public PreallocStackAllocator<T>
        {
        public:
            template<class CapacityHolder>
            requires requires
            {
                typename CapacityHolder::IsCapacityHolder;
            }
            explicit Allocator(CapacityHolder capacity)
                : PreallocStackAllocator<T>{capacity.capacity()}
            {
            }
        };

        template<class Type>
        class AllocatorProxy
        {
        public:
            using value_type = Type;

            template<class U>
            requires(!std::same_as<U, Type>) struct rebind
            {
                using other = Allocator<U>;
            };

            explicit AllocatorProxy(size_t capacity): m_capacity{capacity} {}

            size_t capacity() const { return m_capacity; }

            struct IsCapacityHolder
            {
            };

        private:
            size_t m_capacity;
        };
    }

该集合将不可能复制，并将在移动后死亡。但是我不需要复制它，在我的例子中，移动对象上的insert也是不必要的。