完整参考实现

#pragma once

#include <concepts>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#include <stdexcept>
#include <type_traits>
#include <utility>

namespace mini {

// 手搓 std::vector 的教学实现。
// 跟着 tutorial/ 一步步抄：每段逻辑都标了 Step 编号。
template <typename T, typename Allocator = std::allocator<T>>
class Vector {
public:
    using value_type             = T;
    using allocator_type         = Allocator;
    using size_type              = std::size_t;
    using difference_type        = std::ptrdiff_t;
    using reference              = T&;
    using const_reference        = const T&;
    using pointer                = typename std::allocator_traits<Allocator>::pointer;
    using const_pointer          = typename std::allocator_traits<Allocator>::const_pointer;
    using iterator               = T*;
    using const_iterator         = const T*;
    using reverse_iterator       = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

private:
    using AllocTraits = std::allocator_traits<Allocator>;

    // Step 01: 三个核心状态。capacity_ 是已申请的槽位数，size_ 是已构造的元素数。
    T*        data_{nullptr};
    size_type size_{0};
    size_type capacity_{0};

    // Step 02: 空分配器不占额外空间（C++20）。
    [[no_unique_address]] Allocator alloc_{};

public:
    // ---------------------------------------------------------------------
    // 构造 / 析构
    // ---------------------------------------------------------------------

    Vector() noexcept(std::is_nothrow_default_constructible_v<Allocator>) = default;

    explicit Vector(const Allocator& alloc) noexcept
        : alloc_(alloc) {}

    // 需要 T 能被 allocator 无参 construct（默认构造 / 值初始化）。
    explicit Vector(size_type count, const Allocator& alloc = Allocator())
        requires std::default_initializable<T>
        : alloc_(alloc) {
        if (count == 0) {
            return;
        }
        data_     = allocate_n(count);
        capacity_ = count;
        try {
            uninitialized_value_construct_n(data_, count);
            size_ = count;
        } catch (...) {
            deallocate_n(data_, capacity_);
            data_     = nullptr;
            capacity_ = 0;
            throw;
        }
    }

    Vector(size_type count, const T& value, const Allocator& alloc = Allocator())
        requires std::copy_constructible<T>
        : alloc_(alloc) {
        if (count == 0) {
            return;
        }
        data_     = allocate_n(count);
        capacity_ = count;
        try {
            uninitialized_fill_n(data_, count, value);
            size_ = count;
        } catch (...) {
            deallocate_n(data_, capacity_);
            data_     = nullptr;
            capacity_ = 0;
            throw;
        }
    }

    Vector(std::initializer_list<T> init, const Allocator& alloc = Allocator())
        requires std::copy_constructible<T>
        : alloc_(alloc) {
        const size_type count = init.size();
        if (count == 0) {
            return;
        }
        data_     = allocate_n(count);
        capacity_ = count;
        try {
            uninitialized_copy_n(data_, init.begin(), count);
            size_ = count;
        } catch (...) {
            deallocate_n(data_, capacity_);
            data_     = nullptr;
            capacity_ = 0;
            throw;
        }
    }

    Vector(const Vector& other)
        requires std::copy_constructible<T>
        : alloc_(AllocTraits::select_on_container_copy_construction(other.alloc_)) {
        copy_from_range(other.data_, other.size_);
    }

    Vector(const Vector& other, const Allocator& alloc)
        requires std::copy_constructible<T>
        : alloc_(alloc) {
        copy_from_range(other.data_, other.size_);
    }

    Vector(Vector&& other) noexcept
        : data_(std::exchange(other.data_, nullptr)),
          size_(std::exchange(other.size_, 0)),
          capacity_(std::exchange(other.capacity_, 0)),
          alloc_(std::move(other.alloc_)) {}

    Vector(Vector&& other, const Allocator& alloc)
        : alloc_(alloc) {
        if (alloc_ == other.alloc_) {
            data_     = std::exchange(other.data_, nullptr);
            size_     = std::exchange(other.size_, 0);
            capacity_ = std::exchange(other.capacity_, 0);
            return;
        }
        move_from_range(other.data_, other.size_);
    }

    ~Vector() {
        destroy_range(data_, data_ + size_);
        deallocate_n(data_, capacity_);
    }

    Vector& operator=(const Vector& other)
        requires std::copy_constructible<T>
    {
        if (this == &other) {
            return *this;
        }
        if constexpr (AllocTraits::propagate_on_container_copy_assignment::value) {
            Vector tmp(other, other.alloc_);
            alloc_ = other.alloc_;
            swap_storage(tmp);
        } else {
            Vector tmp(other, alloc_);
            swap_storage(tmp);
        }
        return *this;
    }

    Vector& operator=(Vector&& other) noexcept(
        AllocTraits::propagate_on_container_move_assignment::value ||
        AllocTraits::is_always_equal::value) {
        if (this == &other) {
            return *this;
        }

        if constexpr (AllocTraits::propagate_on_container_move_assignment::value) {
            reset_storage();
            steal_storage(other);
            alloc_ = std::move(other.alloc_);
        } else if (alloc_ == other.alloc_) {
            reset_storage();
            steal_storage(other);
        } else {
            Vector tmp(std::move(other), alloc_);
            swap_storage(tmp);
        }
        return *this;
    }

    Vector& operator=(std::initializer_list<T> init)
        requires std::copy_constructible<T>
    {
        Vector tmp(init, alloc_);
        swap_storage(tmp);
        return *this;
    }

    allocator_type get_allocator() const noexcept {
        return alloc_;
    }

    // ---------------------------------------------------------------------
    // 元素访问
    // ---------------------------------------------------------------------

    reference at(size_type index) {
        if (index >= size_) {
            throw std::out_of_range("mini::Vector::at");
        }
        return data_[index];
    }

    const_reference at(size_type index) const {
        if (index >= size_) {
            throw std::out_of_range("mini::Vector::at");
        }
        return data_[index];
    }

    reference operator[](size_type index) noexcept {
        return data_[index];
    }

    const_reference operator[](size_type index) const noexcept {
        return data_[index];
    }

    reference front() noexcept {
        return data_[0];
    }

    const_reference front() const noexcept {
        return data_[0];
    }

    reference back() noexcept {
        return data_[size_ - 1];
    }

    const_reference back() const noexcept {
        return data_[size_ - 1];
    }

    T* data() noexcept {
        return data_;
    }

    const T* data() const noexcept {
        return data_;
    }

    // ---------------------------------------------------------------------
    // 迭代器
    // ---------------------------------------------------------------------

    iterator begin() noexcept {
        return data_;
    }

    const_iterator begin() const noexcept {
        return data_;
    }

    const_iterator cbegin() const noexcept {
        return data_;
    }

    iterator end() noexcept {
        return data_ + size_;
    }

    const_iterator end() const noexcept {
        return data_ + size_;
    }

    const_iterator cend() const noexcept {
        return data_ + size_;
    }

    reverse_iterator rbegin() noexcept {
        return reverse_iterator(end());
    }

    const_reverse_iterator rbegin() const noexcept {
        return const_reverse_iterator(end());
    }

    reverse_iterator rend() noexcept {
        return reverse_iterator(begin());
    }

    const_reverse_iterator rend() const noexcept {
        return const_reverse_iterator(begin());
    }

    // ---------------------------------------------------------------------
    // 容量
    // ---------------------------------------------------------------------

    [[nodiscard]] bool empty() const noexcept {
        return size_ == 0;
    }

    size_type size() const noexcept {
        return size_;
    }

    size_type max_size() const noexcept {
        const auto alloc_max = AllocTraits::max_size(alloc_);
        const auto diff_max =
            static_cast<size_type>(std::numeric_limits<difference_type>::max());
        return alloc_max < diff_max ? alloc_max : diff_max;
    }

    size_type capacity() const noexcept {
        return capacity_;
    }

    // Step 04: 只申请内存，不构造新元素。n <= capacity 时是空操作。
    void reserve(size_type new_cap) {
        if (new_cap <= capacity_) {
            return;
        }
        reallocate(new_cap);
    }

    void shrink_to_fit() {
        if (size_ == capacity_) {
            return;
        }
        if (size_ == 0) {
            deallocate_n(data_, capacity_);
            data_     = nullptr;
            capacity_ = 0;
            return;
        }
        reallocate(size_);
    }

    // ---------------------------------------------------------------------
    // 修改器
    // ---------------------------------------------------------------------

    void clear() noexcept {
        destroy_range(data_, data_ + size_);
        size_ = 0;
    }

    void push_back(const T& value)
        requires std::copy_constructible<T>
    {
        emplace_back(value);
    }

    void push_back(T&& value) {
        emplace_back(std::move(value));
    }

    // Step 05: 就地构造。扩容时先在新缓冲区构造新元素，再搬迁旧元素，
    // 这样 push_back(v[0]) 这种“引用指向自己”的写法也是安全的。
    template <typename... Args>
    reference emplace_back(Args&&... args) {
        if (size_ < capacity_) {
            AllocTraits::construct(alloc_, data_ + size_, std::forward<Args>(args)...);
            ++size_;
            return data_[size_ - 1];
        }

        const size_type new_cap  = recommend_capacity(size_ + 1);
        T*              new_data = allocate_n(new_cap);
        T*              new_elem = nullptr;
        try {
            AllocTraits::construct(
                alloc_, new_data + size_, std::forward<Args>(args)...);
            new_elem = new_data + size_;
            uninitialized_relocate_n(new_data, data_, size_);
        } catch (...) {
            if (new_elem != nullptr) {
                AllocTraits::destroy(alloc_, new_elem);
            }
            deallocate_n(new_data, new_cap);
            throw;
        }

        T*        old_data = data_;
        size_type old_cap  = capacity_;
        size_type old_size = size_;
        data_              = new_data;
        capacity_          = new_cap;
        ++size_;
        destroy_range(old_data, old_data + old_size);
        deallocate_n(old_data, old_cap);
        return data_[size_ - 1];
    }

    void pop_back() {
        AllocTraits::destroy(alloc_, data_ + size_ - 1);
        --size_;
    }

    // Step 06: 无参 resize 需要 T 可默认构造；带值的 overload 不需要。
    void resize(size_type count)
        requires std::default_initializable<T>
    {
        if (count < size_) {
            destroy_range(data_ + count, data_ + size_);
            size_ = count;
            return;
        }
        if (count == size_) {
            return;
        }
        if (count <= capacity_) {
            uninitialized_value_construct_n(data_ + size_, count - size_);
            size_ = count;
            return;
        }
        grow_buffer_and_append(count, [this](T* dest, size_type n) {
            uninitialized_value_construct_n(dest, n);
        });
    }

    void resize(size_type count, const T& value)
        requires std::copy_constructible<T>
    {
        if (count < size_) {
            destroy_range(data_ + count, data_ + size_);
            size_ = count;
            return;
        }
        if (count == size_) {
            return;
        }
        // 先拷一份，避免 value 指向本 vector 内元素时重分配使引用失效。
        T extra(value);
        if (count <= capacity_) {
            uninitialized_fill_n(data_ + size_, count - size_, extra);
            size_ = count;
            return;
        }
        grow_buffer_and_append(count, [this, &extra](T* dest, size_type n) {
            uninitialized_fill_n(dest, n, extra);
        });
    }

    void swap(Vector& other) noexcept {
        using std::swap;
        if constexpr (AllocTraits::propagate_on_container_swap::value) {
            swap(alloc_, other.alloc_);
        }
        swap_storage(other);
    }

    friend bool operator==(const Vector& lhs, const Vector& rhs) {
        if (lhs.size_ != rhs.size_) {
            return false;
        }
        for (size_type i = 0; i < lhs.size_; ++i) {
            if (!(lhs.data_[i] == rhs.data_[i])) {
                return false;
            }
        }
        return true;
    }

    friend bool operator!=(const Vector& lhs, const Vector& rhs) {
        return !(lhs == rhs);
    }

private:
    // Step 02 -------------------------------------------------------------

    T* allocate_n(size_type n) {
        if (n == 0) {
            return nullptr;
        }
        return std::to_address(AllocTraits::allocate(alloc_, n));
    }

    void deallocate_n(T* ptr, size_type n) noexcept {
        if (ptr == nullptr) {
            return;
        }
        AllocTraits::deallocate(alloc_, ptr, n);
    }

    // Step 03 -------------------------------------------------------------

    void destroy_range(T* first, T* last) noexcept {
        while (last != first) {
            --last;
            AllocTraits::destroy(alloc_, last);
        }
    }

    void uninitialized_value_construct_n(T* dest, size_type n) {
        size_type i = 0;
        try {
            for (; i < n; ++i) {
                AllocTraits::construct(alloc_, dest + i);
            }
        } catch (...) {
            destroy_range(dest, dest + i);
            throw;
        }
    }

    void uninitialized_fill_n(T* dest, size_type n, const T& value) {
        size_type i = 0;
        try {
            for (; i < n; ++i) {
                AllocTraits::construct(alloc_, dest + i, value);
            }
        } catch (...) {
            destroy_range(dest, dest + i);
            throw;
        }
    }

    template <typename InputIt>
    void uninitialized_copy_n(T* dest, InputIt src, size_type n) {
        size_type i = 0;
        try {
            for (; i < n; ++i, ++src) {
                AllocTraits::construct(alloc_, dest + i, *src);
            }
        } catch (...) {
            destroy_range(dest, dest + i);
            throw;
        }
    }

    void uninitialized_move_n(T* dest, T* src, size_type n) {
        size_type i = 0;
        try {
            for (; i < n; ++i) {
                AllocTraits::construct(alloc_, dest + i, std::move(src[i]));
            }
        } catch (...) {
            destroy_range(dest, dest + i);
            throw;
        }
    }

    // 能无异常移动就移动；否则若可拷贝就拷贝，给 push_back / reserve 强异常安全。
    void uninitialized_relocate_n(T* dest, T* src, size_type n) {
        if constexpr (std::is_nothrow_move_constructible_v<T> ||
                      !std::is_copy_constructible_v<T>) {
            uninitialized_move_n(dest, src, n);
        } else {
            uninitialized_copy_n(dest, src, n);
        }
    }

    // Step 04 -------------------------------------------------------------

    size_type recommend_capacity(size_type min_cap) const {
        const size_type max_n = max_size();
        if (min_cap > max_n) {
            throw std::length_error("mini::Vector::reserve");
        }
        size_type new_cap = 1;
        if (capacity_ > 0) {
            if (capacity_ > max_n / 2) {
                new_cap = max_n;
            } else {
                new_cap = capacity_ * 2;
            }
        }
        return new_cap < min_cap ? min_cap : new_cap;
    }

    void reallocate(size_type new_cap) {
        T* new_data = allocate_n(new_cap);
        try {
            uninitialized_relocate_n(new_data, data_, size_);
        } catch (...) {
            deallocate_n(new_data, new_cap);
            throw;
        }

        T*        old_data = data_;
        size_type old_cap  = capacity_;
        size_type old_size = size_;
        data_              = new_data;
        capacity_          = new_cap;
        destroy_range(old_data, old_data + old_size);
        deallocate_n(old_data, old_cap);
    }

    // 扩容并在尾巴上构造新元素。失败时旧缓冲区原封不动（含 capacity）。
    template <typename TailCtor>
    void grow_buffer_and_append(size_type count, TailCtor&& construct_tail) {
        const size_type new_cap  = recommend_capacity(count);
        const size_type appended = count - size_;
        T*              new_data = allocate_n(new_cap);
        bool            tail_ok  = false;
        try {
            construct_tail(new_data + size_, appended);
            tail_ok = true;
            uninitialized_relocate_n(new_data, data_, size_);
        } catch (...) {
            if (tail_ok) {
                destroy_range(new_data + size_, new_data + count);
            }
            deallocate_n(new_data, new_cap);
            throw;
        }

        T*        old_data = data_;
        size_type old_cap  = capacity_;
        size_type old_size = size_;
        data_              = new_data;
        capacity_          = new_cap;
        size_              = count;
        destroy_range(old_data, old_data + old_size);
        deallocate_n(old_data, old_cap);
    }

    void copy_from_range(const T* src, size_type n) {
        if (n == 0) {
            return;
        }
        data_     = allocate_n(n);
        capacity_ = n;
        try {
            uninitialized_copy_n(data_, src, n);
            size_ = n;
        } catch (...) {
            deallocate_n(data_, capacity_);
            data_     = nullptr;
            capacity_ = 0;
            throw;
        }
    }

    void move_from_range(T* src, size_type n) {
        if (n == 0) {
            return;
        }
        data_     = allocate_n(n);
        capacity_ = n;
        try {
            uninitialized_move_n(data_, src, n);
            size_ = n;
        } catch (...) {
            deallocate_n(data_, capacity_);
            data_     = nullptr;
            capacity_ = 0;
            throw;
        }
    }

    void reset_storage() noexcept {
        destroy_range(data_, data_ + size_);
        deallocate_n(data_, capacity_);
        data_     = nullptr;
        size_     = 0;
        capacity_ = 0;
    }

    void steal_storage(Vector& other) noexcept {
        data_     = std::exchange(other.data_, nullptr);
        size_     = std::exchange(other.size_, 0);
        capacity_ = std::exchange(other.capacity_, 0);
    }

    void swap_storage(Vector& other) noexcept {
        using std::swap;
        swap(data_, other.data_);
        swap(size_, other.size_);
        swap(capacity_, other.capacity_);
    }
};

template <typename T, typename Allocator>
void swap(Vector<T, Allocator>& lhs, Vector<T, Allocator>& rhs) noexcept {
    lhs.swap(rhs);
}

}  // namespace mini