从零实现 std::vector：从基础到完整的 Allocator 支持

std::vector 是 C++ 中最常用的容器之一。它提供了动态数组的功能，支持随机访问、自动扩容，并且在内存中连续存储元素。本文将详细介绍如何从零实现一个 Vector 类，分为两个版本：一个简化版（不带 Allocator），一个完整版（带 Allocator 支持）。

目录

1. Vector 的核心概念
2. 版本一：简化实现（不带 Allocator）
3. 版本二：完整实现（带 Allocator 支持）
4. 关键实现细节与注意点
5. 两个版本的对比
6. 总结

---

1. Vector 的核心概念

1.1 基本结构

Vector 的核心是三个成员变量：

T *ptr_;        // 指向动态分配的内存
size_t size_;     // 当前元素数量
size_t capacity_; // 已分配的内存可容纳的元素数量

这三个变量共同描述了 Vector 的状态：ptr_ 指向一块连续内存，其中前 size_ 个位置存放了有效元素，而整块内存可以容纳 capacity_ 个元素。

1.2 核心操作

Vector 需要支持以下核心操作：

操作	说明
构造/析构	创建和销毁 Vector
拷贝/移动	复制或转移 Vector 的所有权
push_back/emplace_back	在末尾添加元素
pop_back	移除末尾元素
insert/erase	在任意位置插入或删除元素
resize/reserve	调整大小或预分配容量
元素访问	operator[]、at、begin、end

1.3 内存管理的关键：分离分配与构造

在 C++ 中，对象的生命周期包含两个阶段：

1. 内存分配：为对象分配原始内存空间
2. 对象构造：在已分配的内存上调用构造函数

对于 Vector 来说，这种分离至关重要。我们需要预先分配一块较大的内存（capacity），但只在其中一部分位置构造对象（size）。这就是为什么我们不能简单地使用 new T[n]——它会同时分配内存并构造所有对象。

---

2. 版本一：简化实现（不带 Allocator）

这个版本使用 malloc/free 进行内存管理，使用 placement new 和显式析构函数调用来管理对象生命周期。

2.1 完整代码

#include <cstddef>
#include <cstdlib>
#include <new>
#include <stdexcept>
#include <utility>

template <typename T> 
class Vector {
public:
  // ==================== 构造函数 ====================
  
  // 默认构造函数：创建空 vector，不分配内存
  Vector() : ptr_(nullptr), size_(0), capacity_(0) {}
  
  // 指定大小的构造函数：创建包含 size 个默认构造元素的 vector
  Vector(size_t size)
      : ptr_(static_cast<T *>(malloc(size * sizeof(T)))),  // 分配原始内存
        size_(size),
        capacity_(size) {
    // malloc 失败时返回 nullptr，需要检查并抛出异常
    if (!ptr_)
      throw std::bad_alloc();
    // 使用 placement new 在已分配的内存上逐个构造对象
    // T{} 表示值初始化（对于基本类型是零初始化，对于类类型调用默认构造函数）
    for (size_t i = 0; i < size_; i++)
      new (ptr_ + i) T{};
  }

  // ==================== 拷贝控制 ====================

  // 拷贝构造函数：深拷贝另一个 vector 的所有元素
  Vector(const Vector &other) 
      : size_(other.size_), capacity_(other.capacity_) {
    // 空 vector 不需要分配内存
    ptr_ = capacity_ == 0 ? nullptr
                          : static_cast<T *>(malloc(capacity_ * sizeof(T)));
    // 使用拷贝构造函数逐个构造元素
    for (size_t i = 0; i < size_; i++)
      new (ptr_ + i) T(other.ptr_[i]);
  }
  
  // 移动构造函数：窃取另一个 vector 的资源
  // 这是一个 O(1) 操作，只是指针的转移
  Vector(Vector &&other)
      : ptr_(other.ptr_),           // 窃取指针
        size_(other.size_),         // 窃取大小
        capacity_(other.capacity_) { // 窃取容量
    // 将源对象置于有效但空的状态
    // 这很重要，因为源对象的析构函数仍会被调用
    other.ptr_ = nullptr;
    other.size_ = 0;
    other.capacity_ = 0;
  }

  // 赋值运算符：使用 copy-and-swap 惯用法
  // 参数按值传递，这会自动调用拷贝构造函数或移动构造函数
  Vector &operator=(Vector other) {
    swap(other);  // 交换资源
    return *this;
    // other 在函数结束时析构，自动释放原有资源
  }

  // 析构函数：销毁所有元素并释放内存
  ~Vector() {
    // 按逆序销毁元素（与构造顺序相反，这是 C++ 的惯例）
    // 注意：使用 i > 0 而非 i >= 0，因为 size_t 是无符号类型
    for (size_t i = size_; i; i--)
      ptr_[i - 1].~T();  // 显式调用析构函数，但不释放内存
    free(ptr_);          // 释放整块内存
  }

  // ==================== 元素添加与删除 ====================

  // push_back（左值版本）：在末尾添加元素的拷贝
  void push_back(const T &v) {
    ensure_capacity(size_ + 1);      // 确保有足够空间
    new (ptr_ + size_) T(v);         // 在末尾位置拷贝构造新元素
    size_++;                         // 更新大小
  }

  // push_back（右值版本）：在末尾添加元素（移动语义）
  void push_back(T &&v) {
    ensure_capacity(size_ + 1);
    new (ptr_ + size_) T(std::move(v));  // 移动构造新元素
    size_++;
  }

  // emplace_back：在末尾原位构造元素
  // 使用完美转发，避免不必要的拷贝或移动
  template <typename... Args> 
  void emplace_back(Args &&...args) {
    ensure_capacity(size_ + 1);
    // std::forward 保持参数的值类别（左值/右值）
    new (ptr_ + size_) T(std::forward<Args>(args)...);
    size_++;
  }

  // pop_back：移除末尾元素
  void pop_back() {
    ptr_[size_ - 1].~T();  // 销毁最后一个元素
    size_--;               // 减小大小（内存不释放，留作后用）
  }

  // clear：移除所有元素
  void clear() { resize(0); }

  // ==================== erase 操作 ====================

  // erase（单元素版本）：删除指定位置的元素
  T *erase(T *pos) { return erase(pos, pos + 1); }

  // erase（范围版本）：删除 [first, last) 范围内的元素
  T *erase(T *first, T *last) {
    if (first >= last)
      return first;  // 空范围，无需操作
    
    // 将 [last, end) 的元素向前移动到 first 位置
    move_range(last, end(), first);
    
    // 计算新大小
    size_t new_size = size_ - (last - first);
    
    // 销毁尾部多余的元素（它们已经被移动走了，但仍需析构）
    for (size_t pos = new_size; pos < size_; pos++)
      (ptr_ + pos)->~T();
    
    size_ = new_size;
    return first;  // 返回指向被删除元素后继的迭代器
  }

  // ==================== insert 操作 ====================

  // insert（单元素左值版本）：在指定位置插入元素的拷贝
  T *insert(T *pos, const T &value) {
    // 保存旧指针，因为 ensure_capacity 可能会重新分配内存
    T *old_ptr = ptr_;
    ensure_capacity(size_ + 1);
    // 如果发生了重新分配，需要根据偏移量重新计算 pos
    pos = pos - old_ptr + ptr_;
    
    // 将 [pos, end) 的元素向后移动一位，为新元素腾出空间
    move_range_backward(pos, end(), pos + 1);
    
    // 在 pos 位置放置新元素
    if (pos < end())
      *pos = value;           // 已构造的位置，使用赋值
    else
      new (pos) T(value);     // 未构造的位置，使用 placement new
    
    size_++;
    return pos;
  }

  // insert（单元素右值版本）：在指定位置插入元素（移动语义）
  T *insert(T *pos, T &&value) {
    T *old_ptr = ptr_;
    ensure_capacity(size_ + 1);
    pos = pos - old_ptr + ptr_;
    move_range_backward(pos, end(), pos + 1);
    
    if (pos < end())
      *pos = std::move(value);
    else
      new (pos) T(std::move(value));
    
    size_++;
    return pos;
  }

  // insert（填充版本）：在指定位置插入 count 个相同元素
  T *insert(T *pos, size_t count, const T &value) {
    T *old_ptr = ptr_;
    ensure_capacity(size_ + count);
    pos = pos - old_ptr + ptr_;
    
    // 将 [pos, end) 的元素向后移动 count 位
    move_range_backward(pos, end(), pos + count);
    
    // 在 [pos, pos + count) 范围内填充新元素
    for (size_t i = 0; i < count; i++)
      if (pos + i < end())
        *(pos + i) = value;
      else
        new (pos + i) T(value);
    
    size_ += count;
    return pos;
  }

  // ==================== 容量与大小 ====================

  size_t size() const { return size_; }
  size_t capacity() const { return capacity_; }
  bool empty() const { return size_ == 0; }

  // ==================== 元素访问 ====================

  // operator[]：不进行边界检查，未定义行为如果越界
  T &operator[](size_t i) { return ptr_[i]; }
  const T &operator[](size_t i) const { return ptr_[i]; }

  // at：进行边界检查，越界时抛出异常
  T &at(size_t i) {
    if (i >= size_)
      throw std::out_of_range("index out of range");
    return ptr_[i];
  }
  const T &at(size_t i) const {
    if (i >= size_)
      throw std::out_of_range("index out of range");
    return ptr_[i];
  }

  // ==================== 其他操作 ====================

  // swap：交换两个 vector 的内容，O(1) 操作
  void swap(Vector &other) noexcept {
    using std::swap;
    swap(ptr_, other.ptr_);
    swap(size_, other.size_);
    swap(capacity_, other.capacity_);
  }

  // 迭代器支持（使用原始指针作为迭代器）
  T *begin() { return ptr_; }
  const T *begin() const { return ptr_; }
  T *end() { return ptr_ + size_; }
  const T *end() const { return ptr_ + size_; }

  // reserve：预分配至少 new_capacity 的空间
  void reserve(size_t new_capacity) { ensure_capacity(new_capacity); }

  // resize：调整 vector 的大小
  void resize(size_t new_size) {
    ensure_capacity(new_size);
    if (new_size > size_) {
      // 扩大：在新位置默认构造元素
      for (size_t i = size_; i < new_size; i++)
        new (ptr_ + i) T{};
    } else {
      // 缩小：销毁多余的元素
      for (size_t i = size_; i > new_size; i--)
        ptr_[i - 1].~T();
    }
    size_ = new_size;
  }

private:
  // ==================== 私有辅助函数 ====================

  // ensure_capacity：确保容量至少为 new_capacity
  // 如果需要扩容，采用倍增策略以保证 push_back 的均摊 O(1) 复杂度
  void ensure_capacity(size_t new_capacity) {
    if (new_capacity <= capacity_)
      return;  // 容量足够，无需操作

    // 倍增策略：新容量 = max(需求容量, 当前容量 * 2)
    capacity_ = std::max(new_capacity, capacity_ * 2);
    
    // 分配新内存
    T *new_ptr_ = static_cast<T *>(malloc(sizeof(T) * capacity_));
    if (!new_ptr_)
      throw std::bad_alloc();
    
    // 将旧元素移动到新内存
    for (size_t i = 0; i < size_; i++) {
      new (new_ptr_ + i) T(std::move(ptr_[i]));  // 移动构造
      ptr_[i].~T();                              // 销毁旧对象
    }
    
    // 释放旧内存并更新指针
    free(ptr_);
    ptr_ = new_ptr_;
  }

  // move_range：将 [first, last) 范围的元素移动到 pos 开始的位置
  // 用于 erase 操作，向前移动元素
  // 前提条件：[first, last) 范围内的元素都已构造
  void move_range(T *first, T *last, T *pos) {
    for (; first != last; first++, pos++) {
      if (pos < end())
        *pos = std::move(*first);       // 目标位置已构造，使用移动赋值
      else
        new (pos) T(std::move(*first)); // 目标位置未构造，使用移动构造
    }
  }

  // move_range_backward：将 [first, last) 范围的元素向后移动到以 pos 开始的位置
  // 用于 insert 操作，向后移动元素以腾出空间
  // 从后向前移动，避免覆盖还未移动的元素
  void move_range_backward(T *first, T *last, T *pos) {
    // 计算目标范围的末尾位置
    pos = last - first + pos;
    // 从后向前逐个移动
    for (; last != first; last--, pos--) {
      if (pos - 1 < end())
        *(pos - 1) = std::move(*(last - 1));       // 目标已构造
      else
        new (pos - 1) T(std::move(*(last - 1)));   // 目标未构造
    }
  }

  // ==================== 成员变量 ====================
  T *ptr_;          // 指向动态分配的内存块
  size_t size_;     // 当前存储的元素数量
  size_t capacity_; // 当前内存块可容纳的元素数量
};

2.2 关键技术点

Placement New

Placement new 允许我们在已分配的内存上构造对象：

new (ptr_ + i) T(value);  // 在 ptr_ + i 位置构造 T 对象

这与普通的 new 不同——普通 new 会先分配内存再构造对象，而 placement new 只负责构造。

显式析构函数调用

与 placement new 配对，我们需要显式调用析构函数来销毁对象（但不释放内存）：

ptr_[i].~T();  // 销毁对象，但不释放内存

Copy-and-Swap 惯用法

赋值运算符使用 copy-and-swap 惯用法：

Vector &operator=(Vector other) {  // 注意：按值传递
    swap(other);
    return *this;
}

这个技巧的妙处在于：

1. 参数按值传递，自动处理拷贝或移动
2. 交换后，原有资源由 other 的析构函数释放
3. 天然异常安全——如果拷贝失败，*this 不受影响

---

3. 版本二：完整实现（带 Allocator 支持）

这个版本使用标准的 Allocator 接口，这是 C++ 标准库容器的标准做法。

3.1 完整代码

#include <algorithm>
#include <cstddef>
#include <cstdlib>
#include <memory>
#include <new>
#include <stdexcept>
#include <utility>

template <typename T, typename Allocator = std::allocator<T>> 
class Vector {
  // 使用 allocator_traits 提供统一的分配器接口
  // 好处：即使自定义分配器缺少某些方法，traits 也能提供默认实现
  using Traits = std::allocator_traits<Allocator>;

public:
  // ==================== 构造函数 ====================
  
  // 默认构造函数：创建空 vector
  // 可以接受一个可选的分配器参数
  Vector(const Allocator &allocator = Allocator{})
      : ptr_(nullptr), size_(0), capacity_(0), allocator_(allocator) {}
  
  // 指定大小的构造函数：创建包含 size 个默认构造元素的 vector
  Vector(size_t size, const Allocator &allocator = Allocator{})
      : size_(size), capacity_(size), allocator_(allocator) {
    // 只有 capacity > 0 时才分配内存
    // 这避免了分配 0 字节内存的未定义行为
    if (capacity_ > 0)
      ptr_ = Traits::allocate(allocator_, capacity_);
    // 使用分配器的 construct 方法构造每个元素
    for (size_t i = 0; i < size_; i++)
      Traits::construct(allocator_, ptr_ + i);
  }

  // ==================== 拷贝控制 ====================

  // 拷贝构造函数：深拷贝另一个 vector
  // 同时拷贝分配器（这是默认行为，但完整实现应该检查 
  // allocator_traits::select_on_container_copy_construction）
  Vector(const Vector &other)
      : size_(other.size_), 
        capacity_(other.capacity_),
        allocator_(other.allocator_) {
    ptr_ = capacity_ == 0 ? nullptr : Traits::allocate(allocator_, capacity_);
    for (size_t i = 0; i < size_; i++)
      Traits::construct(allocator_, ptr_ + i, other.ptr_[i]);
  }
  
  // 移动构造函数：窃取另一个 vector 的资源
  // 分配器也被移动（而非拷贝）
  Vector(Vector &&other)
      : ptr_(other.ptr_), 
        size_(other.size_), 
        capacity_(other.capacity_),
        allocator_(std::move(other.allocator_)) {
    // 将源对象置于有效但空的状态
    other.ptr_ = nullptr;
    other.size_ = 0;
    other.capacity_ = 0;
  }

  // 赋值运算符：使用 copy-and-swap 惯用法
  Vector &operator=(Vector other) {
    swap(other);
    return *this;
  }

  // 析构函数：销毁所有元素并释放内存
  ~Vector() {
    // 使用分配器的 destroy 方法销毁每个元素
    for (size_t i = size_; i; i--)
      Traits::destroy(allocator_, ptr_ + (i - 1));
    // 使用分配器释放内存
    Traits::deallocate(allocator_, ptr_, capacity_);
  }

  // ==================== 元素添加与删除 ====================

  // push_back（左值版本）
  void push_back(const T &v) {
    ensure_capacity(size_ + 1);
    Traits::construct(allocator_, ptr_ + size_, v);
    size_++;
  }

  // push_back（右值版本）
  void push_back(T &&v) {
    ensure_capacity(size_ + 1);
    Traits::construct(allocator_, ptr_ + size_, std::move(v));
    size_++;
  }

  // emplace_back：原位构造元素，完美转发参数
  template <typename... Args> 
  void emplace_back(Args &&...args) {
    ensure_capacity(size_ + 1);
    Traits::construct(allocator_, ptr_ + size_, std::forward<Args>(args)...);
    size_++;
  }

  // pop_back：移除末尾元素
  void pop_back() {
    Traits::destroy(allocator_, ptr_ + size_ - 1);
    size_--;
  }

  // clear：移除所有元素
  void clear() { resize(0); }

  // ==================== erase 操作 ====================

  // erase（单元素版本）
  T *erase(T *pos) { return erase(pos, pos + 1); }

  // erase（范围版本）：删除 [first, last) 范围内的元素
  T *erase(T *first, T *last) {
    if (first >= last)
      return first;
    
    // 将后面的元素向前移动
    move_range(last, end(), first);
    
    size_t new_size = size_ - (last - first);
    
    // 销毁尾部多余的元素
    for (size_t pos = new_size; pos < size_; pos++)
      Traits::destroy(allocator_, ptr_ + pos);
    
    size_ = new_size;
    return first;
  }

  // ==================== insert 操作 ====================

  // insert（单元素左值版本）
  T *insert(T *pos, const T &value) {
    // 保存旧指针，用于在可能的重新分配后重新计算 pos
    T *old_ptr = ptr_;
    ensure_capacity(size_ + 1);
    // 重新计算 pos（如果发生了重新分配，ptr_ 会改变）
    pos = pos - old_ptr + ptr_;
    
    // 向后移动元素，腾出空间
    move_range_backward(pos, end(), pos + 1);
    
    // 放置新元素
    if (pos < end())
      *pos = value;
    else
      Traits::construct(allocator_, pos, value);
    
    size_++;
    return pos;
  }

  // insert（单元素右值版本）
  T *insert(T *pos, T &&value) {
    T *old_ptr = ptr_;
    ensure_capacity(size_ + 1);
    pos = pos - old_ptr + ptr_;
    move_range_backward(pos, end(), pos + 1);
    
    if (pos < end())
      *pos = std::move(value);
    else
      Traits::construct(allocator_, pos, std::move(value));
    
    size_++;
    return pos;
  }

  // insert（填充版本）
  T *insert(T *pos, size_t count, const T &value) {
    T *old_ptr = ptr_;
    ensure_capacity(size_ + count);
    pos = pos - old_ptr + ptr_;
    move_range_backward(pos, end(), pos + count);
    
    for (size_t i = 0; i < count; i++)
      if (pos + i < end())
        *(pos + i) = value;
      else
        Traits::construct(allocator_, pos + i, value);
    
    size_ += count;
    return pos;
  }

  // ==================== 容量与大小 ====================

  size_t size() const { return size_; }
  size_t capacity() const { return capacity_; }
  bool empty() const { return size_ == 0; }

  // ==================== 元素访问 ====================

  T &operator[](size_t i) { return ptr_[i]; }
  const T &operator[](size_t i) const { return ptr_[i]; }

  T &at(size_t i) {
    if (i >= size_)
      throw std::out_of_range("index out of range");
    return ptr_[i];
  }
  const T &at(size_t i) const {
    if (i >= size_)
      throw std::out_of_range("index out of range");
    return ptr_[i];
  }

  // ==================== 其他操作 ====================

  // swap：交换两个 vector 的内容
  // 注意：也交换分配器，这对于 copy-and-swap 惯用法是必要的
  // 完整实现应该检查 propagate_on_container_swap
  void swap(Vector &other) noexcept {
    using std::swap;
    swap(ptr_, other.ptr_);
    swap(size_, other.size_);
    swap(capacity_, other.capacity_);
    swap(allocator_, other.allocator_);
  }

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

  // reserve：预分配空间
  void reserve(size_t new_capacity) { ensure_capacity(new_capacity); }

  // resize：调整大小
  void resize(size_t new_size) {
    ensure_capacity(new_size);
    if (new_size > size_) {
      for (size_t i = size_; i < new_size; i++)
        Traits::construct(allocator_, ptr_ + i);
    } else {
      for (size_t i = size_; i > new_size; i--)
        Traits::destroy(allocator_, ptr_ + i - 1);
    }
    size_ = new_size;
  }

  // get_allocator：返回分配器的拷贝（标准做法是返回值而非引用）
  Allocator get_allocator() const { return allocator_; }

private:
  // ==================== 私有辅助函数 ====================

  // ensure_capacity：确保容量足够，带有强异常安全保证
  void ensure_capacity(size_t new_capacity) {
    if (new_capacity <= capacity_)
      return;

    // 使用局部变量存储新容量，避免在异常发生时修改成员变量
    size_t new_cap = std::max(new_capacity, capacity_ * 2);
    T *new_ptr = Traits::allocate(allocator_, new_cap);
    
    // 记录已构造的元素数量，用于异常处理时的清理
    size_t constructed = 0;
    try {
      for (; constructed < size_; constructed++)
        // std::move_if_noexcept：如果移动构造函数是 noexcept 的则移动，
        // 否则拷贝。这确保了强异常安全：
        // - 如果移动不会抛异常，使用移动（更高效）
        // - 如果移动可能抛异常但可以拷贝，使用拷贝（保证源对象不变）
        // - 如果只能移动（不可拷贝），仍然移动（无法保证强异常安全）
        Traits::construct(allocator_, new_ptr + constructed,
                          std::move_if_noexcept(ptr_[constructed]));
    } catch (...) {
      // 构造过程中发生异常：清理已构造的对象
      for (size_t i = constructed; i > 0; i--)
        Traits::destroy(allocator_, new_ptr + (i - 1));
      // 释放新分配的内存
      Traits::deallocate(allocator_, new_ptr, new_cap);
      // 重新抛出异常，原 vector 保持不变（强异常安全）
      throw;
    }

    // 所有元素都成功转移后，销毁旧元素并释放旧内存
    for (size_t i = size_; i > 0; i--)
      Traits::destroy(allocator_, ptr_ + (i - 1));
    Traits::deallocate(allocator_, ptr_, capacity_);
    
    // 更新成员变量
    ptr_ = new_ptr;
    capacity_ = new_cap;
  }

  // move_range：将 [first, last) 移动到 pos 开始的位置
  void move_range(T *first, T *last, T *pos) {
    for (; first != last; first++, pos++) {
      if (pos < end())
        *pos = std::move(*first);
      else
        Traits::construct(allocator_, pos, std::move(*first));
    }
  }

  // move_range_backward：将 [first, last) 向后移动
  void move_range_backward(T *first, T *last, T *pos) {
    pos = last - first + pos;
    for (; last != first; last--, pos--) {
      if (pos - 1 < end())
        *(pos - 1) = std::move(*(last - 1));
      else
        Traits::construct(allocator_, pos - 1, std::move(*(last - 1)));
    }
  }

  // ==================== 成员变量 ====================
  T *ptr_;              // 数据指针
  size_t size_;         // 当前元素数量
  size_t capacity_;     // 当前容量
  Allocator allocator_; // 分配器实例
};

3.2 Allocator 相关的关键技术点

std::allocator_traits

C++11 引入了 std::allocator_traits，它提供了一个统一的接口来操作 allocator：

using Traits = std::allocator_traits<Allocator>;

// 分配内存
T* ptr = Traits::allocate(allocator_, n);

// 构造对象
Traits::construct(allocator_, ptr, args...);

// 销毁对象
Traits::destroy(allocator_, ptr);

// 释放内存
Traits::deallocate(allocator_, ptr, n);

使用 allocator_traits 而不是直接调用 allocator 的成员函数有一个重要好处：它能为缺少某些成员函数的 allocator 提供默认实现。

std::move_if_noexcept

这是实现强异常安全的关键：

Traits::construct(allocator_, new_ptr + i,
                  std::move_if_noexcept(ptr_[i]));

std::move_if_noexcept 的行为：

• 如果 T 的移动构造函数是 noexcept 的，返回 T&&（移动）
• 如果 T 的移动构造函数可能抛异常但 T 可拷贝，返回 const T&（拷贝）
• 如果 T 只能移动（不可拷贝），返回 T&&（移动，即使可能抛异常）

这样做的原因是：如果移动可能抛异常，我们宁愿拷贝——因为拷贝失败时源对象不受影响，可以保证强异常安全。

Allocator 的交换

在 swap 函数中，我们也交换了 allocator：

void swap(Vector &other) noexcept {
    using std::swap;
    swap(ptr_, other.ptr_);
    swap(size_, other.size_);
    swap(capacity_, other.capacity_);
    swap(allocator_, other.allocator_);  // 重要！
}

这是因为赋值运算符使用 copy-and-swap。如果不交换 allocator，在 other 析构时，可能用错误的 allocator 释放内存。

---

4. 关键实现细节与注意点

4.1 容量增长策略

capacity_ = std::max(new_capacity, capacity_ * 2);

我们采用倍增策略：每次扩容时，容量翻倍。这保证了 push_back 的均摊时间复杂度是 O(1)。

如果每次只增加固定数量（如 +10），那么 n 次 push_back 需要 O(n²) 的时间。

4.2 insert 时的指针失效处理

T *insert(T *pos, const T &value) {
    T *old_ptr = ptr_;
    ensure_capacity(size_ + 1);
    pos = pos - old_ptr + ptr_;  // 关键：重新计算 pos
    // ...
}

ensure_capacity 可能会重新分配内存，导致 ptr_ 改变。因此我们需要：

1. 保存旧的 ptr_
2. 扩容后，根据偏移量重新计算 pos

4.3 逆序销毁元素

for (size_t i = size_; i > 0; i--)
    Traits::destroy(allocator_, ptr_ + (i - 1));

我们按逆序销毁元素，这与构造顺序相反。虽然对于简单类型没有区别，但这是 C++ 的惯例，与栈上对象的析构顺序一致。

注意这里使用 i > 0 而不是 i >= 0，因为 size_t 是无符号类型，i >= 0 永远为真，会导致无限循环。

4.4 异常安全

在带 Allocator 的版本中，ensure_capacity 实现了强异常安全：

size_t constructed = 0;
try {
    for (; constructed < size_; constructed++)
        Traits::construct(allocator_, new_ptr + constructed,
                          std::move_if_noexcept(ptr_[constructed]));
} catch (...) {
    // 清理已构造的对象
    for (size_t i = constructed; i > 0; i--)
        Traits::destroy(allocator_, new_ptr + (i - 1));
    Traits::deallocate(allocator_, new_ptr, new_cap);
    throw;  // 重新抛出异常
}

如果构造过程中抛出异常，我们会清理所有已构造的对象，释放新分配的内存，然后重新抛出异常。原有的 Vector 保持不变。

4.5 move_range 与 move_range_backward

这两个辅助函数用于 insert 和 erase 操作：

// 向前移动：用于 erase
void move_range(T *first, T *last, T *pos);

// 向后移动：用于 insert
void move_range_backward(T *first, T *last, T *pos);

关键点是区分已构造位置和未构造位置：

• 已构造位置：使用移动赋值 *pos = std::move(*first)
• 未构造位置：使用 placement new 或 Traits::construct

---

5. 两个版本的对比

特性	简化版	Allocator 版
内存分配	malloc/free	Traits::allocate/deallocate
对象构造	new (ptr) T(...)	Traits::construct(alloc, ptr, ...)
对象销毁	ptr->~T()	Traits::destroy(alloc, ptr)
异常安全	基本保证	强异常安全（使用 move_if_noexcept）
自定义内存管理	不支持	支持
代码复杂度	较简单	较复杂
与标准库兼容性	低	高

何时使用哪个版本？

简化版适用于：

• 学习和理解 Vector 的基本原理
• 不需要自定义内存分配的场景
• 追求代码简洁性

Allocator 版适用于：

• 需要与标准库行为一致
• 需要自定义内存分配（如内存池、追踪分配等）
• 对异常安全有严格要求

---

6. 总结

实现一个完整的 Vector 涉及多个 C++ 核心概念：

1. 内存管理：分离分配与构造，正确处理 capacity 和 size
2. 对象生命周期：placement new、显式析构、构造/析构顺序
3. 移动语义：移动构造、移动赋值、完美转发
4. 异常安全：强异常保证、move_if_noexcept、RAII
5. Allocator 模型：allocator_traits、allocator 传播
6. 设计模式：copy-and-swap 惯用法

这些概念不仅适用于 Vector，也是实现其他标准库容器的基础。理解这些细节，将帮助你更好地理解和使用 C++ 标准库，也为实现更复杂的数据结构打下基础。

进一步改进的方向

• 使用 move_if_noexcept 改进简化版的异常安全性
• 实现完整的 allocator 传播语义（propagate_on_container_copy_assignment 等）
• 添加 shrink_to_fit() 方法
• 实现 cbegin() / cend() 返回 const 迭代器
• 添加初始化列表构造函数 Vector(std::initializer_list<T>)
• 实现迭代器范围构造函数 template<typename InputIt> Vector(InputIt first, InputIt last)