如何在使用带有自定义池分配器的std：：向量时消除无用的分配和构造？

Question

我有一个自定义的池分配程序，我希望它与std::vector一起使用。

#include <iostream>
#include <memory>
#include <vector>
#include <type_traits>

    template<typename T, uint Size>
    struct ObjectPool
    {
        using value_type = T;
        using pointer = value_type *;

        ObjectPool()
        {
            for (auto i = 1; i < Size; ++i)
                buffer[i - 1].next = &buffer[i];

            nextFreeItem = &buffer[0];
        }

        ObjectPool(const ObjectPool&) = delete;

        ObjectPool(ObjectPool&& other) noexcept
            : buffer{ std::move(other.buffer) }
            , nextFreeItem{ other.nextFreeItem }
        {
            other.nextFreeItem = nullptr;
        }

        ~ObjectPool() = default;

        template<typename U>
        struct rebind
        {
            typedef ObjectPool<U, Size> other;
        };

        template<typename U, uint other_capacity>
        ObjectPool(const ObjectPool<U, other_capacity>& other) {}

        [[nodiscard]] pointer allocate(uint size = 0)
        {
            std::cout << "ObjectPool: allocate " << size << "\n";
            if (nextFreeItem == nullptr)
                throw std::bad_alloc{};

            const auto item = nextFreeItem;
            nextFreeItem = item->next;

            return reinterpret_cast<pointer>(&item->storage);
        }

        void deallocate(pointer p, uint = 0) noexcept
        {
            std::cout << "ObjectPool: deallocate\n";
            const auto item = reinterpret_cast<Item*>(p);

            item->next = nextFreeItem;
            nextFreeItem = item;
        }

        template<typename U, typename ...Args>
        void construct(U* mem, Args&& ...args)
        {
            std::cout << "ObjectPool: construct\n";
           new (mem) value_type(std::forward<Args>(args)...);
        }

        template<typename U>
        void destroy(U* mem) noexcept
        {
            std::cout << "ObjectPool: destroy\n";
            if (mem == nullptr)
                return;

            mem->~value_type();
        }

        ObjectPool& operator =(const ObjectPool&) = delete;

        ObjectPool& operator =(ObjectPool&& other) noexcept
        {
            if (this == &other)
                return *this;

            buffer = std::move(other.buffer);
            nextFreeItem = other.nextFreeItem;

            other.nextFreeItem = nullptr;

            return *this;
        }

    private:
        union Item
        {
            std::aligned_storage_t<sizeof(value_type), alignof(value_type)> storage;
            Item* next;
        };

        std::unique_ptr<Item[]> buffer = std::make_unique<Item[]>(Size);
        Item* nextFreeItem = nullptr;
    };

    int main()
    {
        std::vector<int, ObjectPool<int, 5>> pool;

        pool.push_back(5);
        pool.push_back(3);
        pool.push_back(523);

        for(const auto& p : pool) {
            std::cout << p << std::endl;
        }

        pool.pop_back();

        for(const auto& p : pool) {
            std::cout << p << std::endl;
        }
    }

这个程序的输出是

construct

• ObjectPool : construct

• ObjectPool : construct

• ObjectPool :construct

• ObjectPool: destroy

• ObjectPool : deallocate

• ObjectPool :分配3

• ：construct

• ObjectPool : construct

• ObjectPool：：：destroy

• ObjectPool : destroy

• ObjectPool：

我希望它是

ObjectPool: allocate whatever // this is space for 5
ObjectPool: construct         // constructs 5
ObjectPool: allocate whatever // this is space for 3
ObjectPool: construct         // constructs 3
ObjectPool: allocate whatever // this is space for 523
ObjectPool: construct         // constructs 523, but actual output gives garbage value
ObjectPool: destroy           // destroys 523
ObjectPool: deallocate        // deallocates 523
ObjectPool: destroy           // destroys 3
ObjectPool: destroy           // destroys 5
ObjectPool: deallocate        // deallocates 3 and 5

如您所见，当构造方法只需要调用一次时，它甚至会被调用3次。

为什么523是垃圾？如果不执行pool.reserve(5)，如何才能实现预期的输出？有可能吗？

Answer 1

传递给ObjectPool::allocate的值是将连续存储在内存中的对象的数量。这意味着当调用allocator(2)时，需要返回指向至少具有2 * sizeof(T)块的块的指针。分配器只返回指向单个块的指针。当向量构造函数将第二个(或第三个)元素添加到新生成的向量时，它将覆盖未被指定的内存。下一次对allocator的调用将分配该内存，从而导致向量的损坏。

向量的分配内存是连续的。当您第一次调用push_back时，将为向量分配一个元素(向量容量为1)。这将生成输出的第1-2行。

在第二次调用push_back时，由于向量的容量已满，因此将请求一个新的块。这将生成输出的第2-7行。第4行是将现有元素复制到新内存块，第5行是构造刚刚添加的新元素，第6行是从原始内存块中销毁该元素。第7行是释放原始内存块时(返回分配器)。向量的容量为2。

下一次对push_back的调用将再次导致向量的大小调整，生成输出的第8-14行。第9-10行将现有元素复制到新内存块，11个构造新添加的元素，12-13在旧内存块中销毁它们，14将旧内存块返回给分配器。

以下几行的输出已损坏，因为稍后对分配器的调用会将指针返回到向量对象正在使用的内存。结果数据复制会移动不正确或损坏的数据。

解决方案是让您的allocate函数保留适当数量的块。(因此allocate(2)应该向前推进两个块，假设它前进的两个块是连续的。)