Как избавиться от бесполезных распределений и конструкций при использовании std :: vector с пользовательским распределителем пулов?

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

Выход этой программы:

1. ObjectPool: allocate 1
2. ObjectPool: конструкция
3. ObjectPool: выделить 2
4. ObjectPool: конструкция
5. ObjectPool: конструкция
6. ObjectPool: уничтожить
7. ObjectPool: deallocate
8. ObjectPool: выделить 3
9. ObjectPool: конструкция
10. ObjectPool: конструкция
11. ObjectPool: конструкция
12. ObjectPool: уничтожить
13. ObjectPool: уничтожить
14. ObjectPool: deallocate
15. 523
16. 3
17. -539300144
18. ObjectPool: уничтожить
19. 523
20. 3
21. ObjectPool: уничтожить
22. ObjectPool: уничтожить
23. ObjectPool: освободить

I ожидайте, что он будет

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) блоков. Ваш распределитель возвращает только указатель на один блок. Когда векторный конструктор добавляет 2-й (или 3-й) элемент к вновь созданному вектору, он перезапишет память, которая не была специально назначена. Следующий вызов 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) должен продвинуться nextFreeItem на два блока, предполагая, что два, которые он продвигает, являются смежными.)