数据结构（动态数组）

 一、基本特性

 二、优、缺点

 优点：

1. 访问效率高：支持通过下标快速访问元素，时间复杂度为 O(1)
2. 尾部添加/删除效率高（动态数组）：push_back() 和 pop_back() 操作时间复杂度为 O(1)（均摊）

 缺点：

1. 插入/删除（非尾部）代价大：需要移动大量元素，时间复杂度为 O(n)
2. 扩容代价高：如果数组满了需要扩容，通常按1.5 或 2倍扩容策略，会发生一次 O(n) 拷贝操作

三、典型操作复杂度分析

四、动态数组类实现详解

功能列表：

• 支持动态扩容

• 支持拷贝构造函数、拷贝赋值运算符、移动构造函数、移动赋值运算符

• 支持 push_back、pop_back、insert、erase

• 支持查找、访问、容量大小获取

• 支持 [] 运算符重载访问元素

template<typename T>
class Array {
public:// 构造函数Array(int capacity = 10): m_size(0), m_capacity(capacity){m_pArr = new T[m_capacity];}// 拷贝构造函数Array(const Array& other): m_size(other.m_size), m_capacity(other.m_capacity){m_pArr = new T[m_capacity];for (int i = 0; i < m_size; ++i) {m_pArr[i] = other.m_pArr[i];}}// 拷贝赋值运算符Array& operator=(const Array& other) {if (this == &other) return *this;delete[] m_pArr;m_capacity = other.m_capacity;m_size = other.m_size;m_pArr = new T[m_capacity];for (int i = 0; i < m_size; ++i) {m_pArr[i] = other.m_pArr[i];}return *this;}// 移动构造函数Array(Array&& other) noexcept: m_size(other.m_size),m_capacity(other.m_capacity),m_pArr(other.m_pArr){other.m_pArr = nullptr;other.m_size = 0;other.m_capacity = 0;}// 移动赋值运算符Array& operator=(Array&& other) noexcept {if (this == &other) return *this;delete[] m_pArr;m_size = other.m_size;m_capacity = other.m_capacity;m_pArr = other.m_pArr;other.m_pArr = nullptr;other.m_size = 0;other.m_capacity = 0;return *this;}// 析构函数~Array() {delete[] m_pArr;m_pArr = nullptr;}// 尾部添加元素void push_back(const T& val) {if (m_size == m_capacity) {expand(2 * m_capacity);}m_pArr[m_size++] = val;}// 原地构造对象（避免额外拷贝）template<typename... Args>void emplace_back(Args&&... args) {if (m_size == m_capacity) {expand(2 * m_capacity);}new (m_pArr + m_size) T(std::forward<Args>(args)...);++m_size;}// 删除尾部元素void pop_back() {if (m_size > 0) {m_size--;}}// 插入元素到指定位置void insert(int pos, const T& val) {if (pos < 0 || pos > m_size) {throw std::out_of_range("insert: out of range");}if (m_size == m_capacity) {expand(m_capacity == 0 ? 1 : 2 * m_capacity);}for (int i = m_size - 1; i >= pos; --i) {m_pArr[i + 1] = m_pArr[i];}m_pArr[pos] = val;m_size++;}// 删除指定位置的元素void erase(int pos) {if (pos < 0 || pos >= m_size) {throw std::out_of_range("erase: out of range");}for (int i = pos; i < m_size - 1; ++i) {m_pArr[i] = m_pArr[i + 1];}m_size--;}// 查找某个元素，返回下标，不存在返回 -1int find(const T& val) const {for (int i = 0; i < m_size; ++i) {if (m_pArr[i] == val) {return i;}}return -1;}// 预留容量void reserve(int newCapacity) {if (newCapacity > m_capacity) {expand(newCapacity);}}// 清空元素void clear() {m_size = 0;}// 判空bool empty() const {return m_size == 0;}// 获取数组大小int size() const {return m_size;}// 获取数组容量int capacity() const {return m_capacity;}// 访问首尾元素T& front() {if (empty()) throw std::out_of_range("front(): array is empty");return m_pArr[0];}T& back() {if (empty()) throw std::out_of_range("back(): array is empty");return m_pArr[m_size - 1];}// 下标访问元素（非 const）T& operator[](int pos) {if (pos < 0 || pos >= m_size) {throw std::out_of_range("operator[]: out of range");}return m_pArr[pos];}// 下标访问元素（const 版本）const T& operator[](int pos) const {if (pos < 0 || pos >= m_size) {throw std::out_of_range("operator[]: out of range");}return m_pArr[pos];}// 支持范围 for 循环（const）const T* begin() const { return m_pArr; }const T* end() const { return m_pArr + m_size; }// 非 const 版本迭代器T* begin() { return m_pArr; }T* end() { return m_pArr + m_size; }private:// 扩容方法void expand(int newCapacity) {T* newArr = new T[newCapacity];for (int i = 0; i < m_size; ++i) {newArr[i] = m_pArr[i];}delete[] m_pArr;m_pArr = newArr;m_capacity = newCapacity;}private:int m_size;       // 当前元素个数int m_capacity;   // 当前容量T* m_pArr;        // 数组首地址
};