手撕vector

手撕不了一点

#pragma once
#include <cstddef>
#include <stdexcept>
#include <algorithm>
#include <initializer_list>
#include <memory>
#include <new>

// 简单的内存池分配器，用于高效内存管理
template <typename T>
class PoolAllocator {
private:
    struct Block {
        Block* next; // 指向下一个空闲块的指针
    };
    static constexpr size_t POOL_SIZE = 1024 * sizeof(T); // 内存池总大小
    static constexpr size_t BLOCK_SIZE = sizeof(T) > sizeof(Block) ? sizeof(T) : sizeof(Block); // 每个块的大小
    unsigned char* pool_;  // 原始内存池
    Block* free_list_;     // 空闲块链表头
    size_t pool_size_;     // 内存池总大小

// 初始化空闲块链表，将内存池分割为链接的块
void init_pool() {
    free_list_ = reinterpret_cast<Block*>(pool_);
    Block* current = free_list_;
    size_t block_count = pool_size_ / BLOCK_SIZE;
    for (size_t i = 0; i < block_count - 1; ++i) {
        current->next = reinterpret_cast<Block*>(reinterpret_cast<unsigned char*>(current) + BLOCK_SIZE);
        current = current->next;
    }
    current->next = nullptr;
}

public:
    using value_type = T;

// 构造函数：分配内存池并初始化空闲链表
PoolAllocator() : pool_(new unsigned char[POOL_SIZE]), free_list_(nullptr), pool_size_(POOL_SIZE) {
    init_pool();
}

// 析构函数：释放内存池
~PoolAllocator() { delete[] pool_; }

// 从内存池分配单个块
T* allocate(size_t n) {
    if (n != 1) throw std::bad_alloc(); // 仅支持单对象分配
    if (!free_list_) throw std::bad_alloc(); // 内存池已耗尽
    Block* block = free_list_;
    free_list_ = free_list_->next;
    return reinterpret_cast<T*>(block);
}

// 将块归还到内存池
void deallocate(T* p, size_t n) noexcept {
    if (n != 1) return;
    Block* block = reinterpret_cast<Block*>(p);
    block->next = free_list_;
    free_list_ = block;
}

// 支持不同类型的重绑定
template <typename U>
struct rebind {
    using other = PoolAllocator<U>;
};

};

// 向量实现，支持自定义分配器
template <typename T, typename Alloc = std::allocator<T>>
class MyVector {
private:
    using AllocTraits = std::allocator_traits<Alloc>;
    T* data_;         // 动态数组指针
    size_t size_;     // 元素数量
    size_t capacity_; // 当前容量
    Alloc alloc_;     // 分配器实例

// 重新分配到新容量，移动现有元素
void reallocate(size_t new_capacity) {
    T* new_data = AllocTraits::allocate(alloc_, new_capacity);
    for (size_t i = 0; i < size_; ++i) {
        AllocTraits::construct(alloc_, new_data + i, std::move(data_[i]));
        AllocTraits::destroy(alloc_, data_ + i);
    }
    if (data_) AllocTraits::deallocate(alloc_, data_, capacity_);
    data_ = new_data;
    capacity_ = new_capacity;
}

// 销毁指定范围内的元素
void destroy_range(T* first, T* last) {
    while (first != last) {
        AllocTraits::destroy(alloc_, first);
        ++first;
    }
}

public:
    // 默认构造函数：空向量
    MyVector() : data_(nullptr), size_(0), capacity_(0), alloc_() {}

// 初始化列表构造函数
MyVector(std::initializer_list<T> init, const Alloc& alloc = Alloc())
    : data_(nullptr), size_(0), capacity_(0), alloc_(alloc) {
    reserve(init.size());
    for (const T& value : init) {
        push_back(value);
    }
}

// 拷贝构造函数
MyVector(const MyVector& other)
    : data_(nullptr), size_(0), capacity_(0), alloc_(AllocTraits::select_on_container_copy_construction(other.alloc_)) {
    reserve(other.size_);
    for (size_t i = 0; i < other.size_; ++i) {
        push_back(other.data_[i]);
    }
}

// 移动构造函数
MyVector(MyVector&& other) noexcept
    : data_(other.data_), size_(other.size_), capacity_(other.capacity_), alloc_(std::move(other.alloc_)) {
    other.data_ = nullptr;
    other.size_ = 0;
    other.capacity_ = 0;
}

// 析构函数：清理元素和内存
~MyVector() {
    destroy_range(data_, data_ + size_);
    if (data_) AllocTraits::deallocate(alloc_, data_, capacity_);
}

// 拷贝赋值运算符
MyVector& operator=(const MyVector& other) {
    if (this != &other) {
        MyVector temp(other);
        std::swap(data_, temp.data_);
        std::swap(size_, temp.size_);
        std::swap(capacity_, temp.capacity_);
        std::swap(alloc_, temp.alloc_);
    }
    return *this;
}

// 移动赋值运算符
MyVector& operator=(MyVector&& other) noexcept {
    if (this != &other) {
        destroy_range(data_, data_ + size_);
        if (data_) AllocTraits::deallocate(alloc_, data_, capacity_);
        data_ = other.data_;
        size_ = other.size_;
        capacity_ = other.capacity_;
        alloc_ = std::move(other.alloc_);
        other.data_ = nullptr;
        other.size_ = 0;
        other.capacity_ = 0;
    }
    return *this;
}

// 元素访问
T& operator[](size_t index) { return data_[index]; }
const T& operator[](size_t index) const { return data_[index]; }

// 安全元素访问，带边界检查
T& at(size_t index) {
    if (index >= size_) throw std::out_of_range("索引越界");
    return data_[index];
}
const T& at(size_t index) const {
    if (index >= size_) throw std::out_of_range("索引越界");
    return data_[index];
}

// 容量操作
size_t size() const { return size_; }
size_t capacity() const { return capacity_; }
bool empty() const { return size_ == 0; }

// 预留容量，必要时重新分配
void reserve(size_t new_capacity) {
    if (new_capacity > capacity_) {
        reallocate(new_capacity);
    }
}

// 调整大小，添加默认元素或裁剪
void resize(size_t new_size) {
    if (new_size > size_) {
        reserve(new_size);
        while (size_ < new_size) {
            AllocTraits::construct(alloc_, data_ + size_, T());
            ++size_;
        }
    } else {
        destroy_range(data_ + new_size, data_ + size_);
        size_ = new_size;
    }
}

// 元素操作
// 在末尾追加元素
void push_back(const T& value) {
    if (size_ == capacity_) {
        reserve(capacity_ == 0 ? 1 : capacity_ * 2);
    }
    AllocTraits::construct(alloc_, data_ + size_, value);
    ++size_;
}

// 在末尾原地构造元素
template <typename... Args>
void emplace_back(Args&&... args) {
    if (size_ == capacity_) {
        reserve(capacity_ == 0 ? 1 : capacity_ * 2);
    }
    AllocTraits::construct(alloc_, data_ + size_, std::forward<Args>(args)...);
    ++size_;
}

// 删除最后一个元素
void pop_back() {
    if (size_ > 0) {
        AllocTraits::destroy(alloc_, data_ + size_ - 1);
        --size_;
    }
}

// 在指定位置插入元素
void insert(T* pos, const T& value) {
    size_t index = pos - data_;
    if (index > size_) throw std::out_of_range("无效插入位置");
    if (size_ == capacity_) {
        reserve(capacity_ == 0 ? 1 : capacity_ * 2);
    }
    for (size_t i = size_; i > index; --i) {
        AllocTraits::construct(alloc_, data_ + i, std::move(data_[i - 1]));
        AllocTraits::destroy(alloc_, data_ + i - 1);
    }
    AllocTraits::construct(alloc_, data_ + index, value);
    ++size_;
}

// 删除指定位置的元素
void erase(T* pos) {
    size_t index = pos - data_;
    if (index >= size_) throw std::out_of_range("无效删除位置");
    for (size_t i = index; i < size_ - 1; ++i) {
        AllocTraits::construct(alloc_, data_ + i, std::move(data_[i + 1]));
        AllocTraits::destroy(alloc_, data_ + i + 1);
    }
    AllocTraits::destroy(alloc_, data_ + size_ - 1);
    --size_;
}

// 迭代器
T* begin() { return data_; }
T* end() { return data_ + size_; }
const T* begin() const { return data_; }
const T* end() const { return data_ + size_; }

};  

代码讲解

以下是对上述 my_vector.h 实现的详细讲解，涵盖主要功能、设计思路和关键特性：

1. 内存池分配器（PoolAllocator）：

   • 目的：提供高效的内存分配，减少动态分配（如 malloc）的开销，适合资源受限环境。
   • 实现：
     • 使用固定大小的内存池（POOL_SIZE），通过空闲链表（free_list_）管理块。
     • 每个块的大小为 BLOCK_SIZE，确保足够存储 T 或 Block（取较大者）。
     • allocate 从空闲链表获取块，时间复杂度 ( O(1) )。
     • deallocate 将块归还空闲链表，同样 ( O(1) )。
   • 特性：
     • 仅支持单对象分配（n == 1），适合 MyVector 的连续内存需求。
     • 通过 rebind 支持不同类型的分配，符合 C++ 分配器标准。
     • 抛出 std::bad_alloc 处理内存耗尽，增强健壮性。

2. vector实现（MyVector）：

   • 目的：模拟 std::vector，支持动态数组功能，同时兼容自定义分配器。
   • 核心功能：
     • 构造与销毁：支持默认、初始化列表、拷贝、移动构造函数，以及析构函数，确保资源正确管理。
     • 元素访问：通过 operator[]（无边界检查）和 at（带边界检查）访问元素，at 抛出 std::out_of_range。
     • 容量管理：
       • reserve 预分配容量，resize 调整大小，必要时构造或销毁元素。
       • 容量翻倍策略（capacity_ * 2）均摊 ( O(1) ) 插入复杂度。
     • 元素操作：
       • push_back：追加元素，必要时扩展容量。
       • emplace_back：原地构造元素，减少拷贝/移动开销。
       • pop_back：删除末尾元素。
       • insert：在指定位置插入元素，移动后续元素，时间复杂度 ( O(n) )。
       • erase：删除指定位置元素，移动后续元素，时间复杂度 ( O(n) )。
     • 迭代器：提供简单的指针迭代器（begin、end），支持范围遍历。

3. 异常安全：

   • 强异常保证：insert、erase、emplace_back 在异常时保持对象一致性，通过移动操作和临时对象实现。
   • 基本异常保证：内存分配失败不破坏对象，析构函数正确清理。
   • at 和 insert/erase 的边界检查抛出 std::out_of_range，便于调试。

4. 设计亮点：

   • 分配器抽象：通过 AllocTraits 支持 std::allocator 或 PoolAllocator，增强灵活性。
   • 移动语义：拷贝/移动构造函数和赋值运算符优化性能，移动操作标记为 noexcept。
   • 内存效率：PoolAllocator 减少碎片，连续内存布局（data_）保持缓存友好性。
   • 简洁性：代码结构清晰，注释详细，易于维护和扩展。

5. 局限性：

   • PoolAllocator 仅支持单对象分配，内存池大小固定（耗尽时抛异常）。
   • insert 和 erase 时间复杂度为 ( O(n) )，不适合频繁中间操作。
   • 迭代器仅为简单指针，未实现完整随机访问迭代器类。

6. 扩展方向：

   • 动态内存池：支持池扩展，适应更大内存需求。
   • 完整迭代器：实现 STL 兼容的随机访问迭代器，支持复杂算法。
   • 多对象分配：扩展 PoolAllocator 支持 n 个对象分配。
   • 性能优化：调整容量增长策略（如 1.5 倍）以减少内存浪费，或添加 shrink_to_fit。

使用示例

#include "my_vector.h"
#include <iostream>
#include <string>

int main() {
    MyVector<std::string, PoolAllocator<std::string>> vec;
    vec.emplace_back("Hello"); // 原地构造
    vec.emplace_back(5, 'a'); // 构造 "aaaaa"
    vec.insert(vec.begin() + 1, "World"); // 插入
    for (const auto& s : vec) {
        std::cout << s << " "; // 输出: Hello World aaaaa
    }
    std::cout << std::endl;
    vec.erase(vec.begin() + 1); // 删除 World
    for (const auto& s : vec) {
        std::cout << s << " "; // 输出: Hello aaaaa
    }
    std::cout << std::endl;
    try {
        vec.at(10); // 抛出异常
    } catch (const std::out_of_range& e) {
        std::cout << "错误: " << e.what() << std::endl;
    }
    return 0;
}