【C++特殊工具与技术】优化内存分配(二)：allocator类

T* p = new T(10);  // 分配内存 + 构造对象（调用T的构造函数）
delete p;          // 析构对象 + 释放内存（调用T的析构函数）

std::allocator<T> alloc;
T* p = alloc.allocate(1);  // 仅分配内存（不构造对象）
alloc.construct(p, 10);    // 在p指向的内存中构造对象（调用T的构造函数）
alloc.destroy(p);          // 析构对象（调用T的析构函数）
alloc.deallocate(p, 1);    // 释放内存

#include <memory>
#include <stdexcept>

template <typename T>
class MyVector {
private:
    T* elements;          // 指向元素的起始位置
    T* first_free;        // 指向最后一个已构造元素的下一个位置
    T* cap;               // 指向内存的末尾（容量上限）
    std::allocator<T> alloc;  // 内存分配器

    // 辅助函数：重新分配内存并复制元素
    void reallocate();

public:
    // 构造函数
    MyVector() : elements(nullptr), first_free(nullptr), cap(nullptr) {}

    // 析构函数
    ~MyVector() {
        if (elements) {
            // 先销毁所有已构造的元素
            for (T* p = first_free; p != elements; ) {
                alloc.destroy(--p);
            }
            // 释放内存
            alloc.deallocate(elements, cap - elements);
        }
    }

    // 添加元素
    void push_back(const T& value);

    // 当前元素数量
    size_t size() const { return first_free - elements; }

    // 容量
    size_t capacity() const { return cap - elements; }
};

template <typename T>
void MyVector<T>::push_back(const T& value) {
    // 如果没有空间或容量已满，需要重新分配
    if (first_free == cap) {
        reallocate();  // 重点：重新分配内存的逻辑
    }
    // 在first_free位置构造新元素（调用拷贝构造函数）
    alloc.construct(first_free, value);
    ++first_free;  // 移动到下一个空闲位置
}

// 销毁最后一个元素（类似vector::pop_back）
void pop_back() {
    if (size() > 0) {
        --first_free;
        alloc.destroy(first_free);  // 调用析构函数
    }
}

// 析构函数中的内存释放
~MyVector() {
    if (elements) {
        // 销毁所有元素
        for (T* p = first_free; p != elements; ) {
            alloc.destroy(--p);  // 逆序销毁（与构造顺序相反）
        }
        // 释放内存（分配时的容量是cap - elements）
        alloc.deallocate(elements, cap - elements);
    }
}

template <typename T>
void MyVector<T>::reallocate() {
    // 计算新容量：初始为1，之后每次翻倍
    size_t new_capacity = (capacity() == 0) ? 1 : capacity() * 2;

    // 分配新内存
    T* new_elements = alloc.allocate(new_capacity);

    // 将旧元素复制到新内存（使用uninitialized_copy）
    T* dest = new_elements;
    T* src = elements;
    for (size_t i = 0; i < size(); ++i) {
        alloc.construct(dest++, std::move(*src++));  // 使用移动构造减少拷贝
    }

    // 销毁旧元素并释放旧内存
    for (T* p = first_free; p != elements; ) {
        alloc.destroy(--p);
    }
    alloc.deallocate(elements, cap - elements);

    // 更新指针
    elements = new_elements;
    first_free = dest;
    cap = elements + new_capacity;
}

// 替换循环部分
T* new_first_free = std::uninitialized_copy(
    std::make_move_iterator(elements),  // 转换为移动迭代器
    std::make_move_iterator(first_free),
    new_elements
);

#include <iostream>
#include <string>

int main() {
    MyVector<std::string> vec;
    vec.push_back("hello");
    vec.push_back("world");
    vec.push_back("allocator");

    std::cout << "Size: " << vec.size() << std::endl;       // 输出：3
    std::cout << "Capacity: " << vec.capacity() << std::endl; // 输出：4（初始扩容为2，第二次扩容为4）

    // 遍历元素（需要添加迭代器或访问函数）
    // 假设添加了operator[]：
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";  // 输出：hello world allocator
    }
    std::cout << std::endl;

    vec.pop_back();
    std::cout << "Size after pop: " << vec.size() << std::endl; // 输出：2
    return 0;
}

#include <memory>
#include <vector>
#include <stdexcept>

// 内存池节点（每个节点存储一个T对象）
template <typename T>
struct PoolNode {
    union {
        T data;         // 对象数据
        PoolNode* next; // 空闲链表指针（未使用时）
    };
    PoolNode() : next(nullptr) {}
};

// 自定义内存池allocator
template <typename T>
class PoolAllocator {
public:
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using size_type = size_t;

    // 构造函数：初始化内存池
    PoolAllocator(size_t block_size = 1024) : block_size_(block_size), free_list_(nullptr) {
        allocate_block(); // 预分配一个内存块
    }

    // 分配一个T对象的内存
    T* allocate(size_t n) {
        if (n != 1) {  // 仅支持分配单个对象
            throw std::invalid_argument("PoolAllocator only supports allocating one object at a time");
        }
        if (!free_list_) {
            allocate_block(); // 内存池空，分配新块
        }
        PoolNode<T>* node = free_list_;
        free_list_ = node->next;
        return &node->data;
    }

    // 释放一个T对象的内存
    void deallocate(T* p, size_t n) {
        if (n != 1) {
            throw std::invalid_argument("PoolAllocator only supports deallocating one object at a time");
        }
        PoolNode<T>* node = reinterpret_cast<PoolNode<T>*>(p);
        node->next = free_list_;
        free_list_ = node;
    }

    // 构造对象（使用标准allocator的默认实现）
    template <typename U, typename... Args>
    void construct(U* p, Args&&... args) {
        std::allocator<U>().construct(p, std::forward<Args>(args)...);
    }

    // 销毁对象（使用标准allocator的默认实现）
    template <typename U>
    void destroy(U* p) {
        std::allocator<U>().destroy(p);
    }

private:
    size_t block_size_;      // 每个内存块的节点数
    PoolNode<T>* free_list_; // 空闲节点链表

    // 分配一个内存块（包含block_size_个节点）
    void allocate_block() {
        PoolNode<T>* block = new PoolNode<T>[block_size_];
        // 将新块的节点加入空闲链表
        for (size_t i = 0; i < block_size_; ++i) {
            block[i].next = free_list_;
            free_list_ = &block[i];
        }
    }
};

int main() {
    // 使用PoolAllocator的vector，存储int类型
    std::vector<int, PoolAllocator<int>> vec;

    // 批量插入元素（内存池预分配，减少new调用）
    for (int i = 0; i < 1000; ++i) {
        vec.push_back(i);
    }

    std::cout << "vec size: " << vec.size() << std::endl;  // 输出：1000
    return 0;
}

std::allocator<int> alloc;
int* p = alloc.allocate(5);  // 分配5个int的内存（未初始化）
*p = 42;  // 直接赋值（int是POD类型，允许；但如果是类类型则未定义行为）

std::allocator<std::string> str_alloc;
std::string* str_p = str_alloc.allocate(1);
str_p->size();  // 错误！std::string未构造，调用成员函数未定义行为

std::allocator<int> alloc;
int* p = alloc.allocate(3);
alloc.deallocate(p, 5);  // 错误！释放的数量必须与allocate的参数一致（3）

void reallocate() {
    T* new_elements = alloc.allocate(new_cap);
    // 复制元素时可能抛出异常（如T的拷贝构造函数异常）
    for (size_t i = 0; i < size(); ++i) {
        alloc.construct(new_elements + i, elements[i]);  // 假设这里抛出异常
    }
    // 如果异常发生，new_elements未释放，导致内存泄漏
}