动态数组（Dynamic Array）

STL 中的 vector 容器就是一个基于模板泛型的动态数组，它和原生数组不同的之处在于：原生数组在定义时需要指定长度，无法随着需要自动增长，而动态数组则可以根据元素个数自动扩展内存。动态数组可以使用 C 来实现，但是为了能够支持更多的数据类型，使用 C++ 模板技术来实现会更灵活。

动态数组最核心的是其动态增长策略，原理也较为简单：

在数组实现时，引入容量概念。即：为了避免频繁的 new/delete 耗时的操作，我们可以在扩展内存时，一次申请较大的空间。
插入元素时，先判断是否容量足够。如果不足，则扩展内存。如果充足，则直接插入元素。这里需要注意的是：扩展内存就是申请一块更大的内存，需要将原空间的数据拷贝到新空间，为了避免内存泄漏，原数据空间需要及时释放。
添加到容器中的元素必须支持拷贝语义，即：元素必须能够被拷贝。

下面是具体实现代码：

template<class T>
class DynamicArray
{
public:
	// 默认构造
	DynamicArray(size_t capacity = 2);
	// 有参构造
	DynamicArray(std::initializer_list<T> list);
	// 拷贝构造
	DynamicArray(const DynamicArray<T> &arr);
	// 移动构造
	DynamicArray(DynamicArray<T> &&arr);
	// 普通赋值
	DynamicArray<T>& operator=(const DynamicArray<T> &arr);
	// 移动赋值
	DynamicArray<T>& operator=(DynamicArray<T> &&arr);
	// 添加元素
	void push_back(const T &ele);
	// 删除元素
	void remove(const T &ele);
	// 重载下标
	T& operator[](int index) const;
	// 数组大小
	size_t size() const;
	// 析构函数
	~DynamicArray();


public:
	T *p_data;       // 数据空间
	size_t m_capacity;  // 当前数组容量
	size_t m_size;      // 当前数组元素个数
};

函数实现代码：

// 默认构造
template<class T>
DynamicArray<T>::DynamicArray(size_t capacity)
{
	std::cout << "默认构造" << std::endl;
	this->m_capacity = capacity;
	this->m_size = 0;
	this->p_data = new T[m_capacity];
}

// 有参构造
template<class T>
DynamicArray<T>::DynamicArray(std::initializer_list<T> ele_list)
{
	std::cout << "有参构造" << std::endl;
	this->m_capacity = ele_list.size();
	this->m_size = ele_list.size();
	this->p_data = new T[this->m_capacity];

	size_t i = 0;
	for (auto it = ele_list.begin(); it < ele_list.end(); ++it)
	{
		this->p_data[i++] = *it;
	}
}

// 拷贝构造
template<class T>
DynamicArray<T>::DynamicArray(const DynamicArray<T> &arr)
{	
	std::cout << "拷贝构造" << std::endl;
	// 拷贝属性
	this->m_capacity = arr.m_capacity;
	this->m_size = arr.m_size;

	// 拷贝数据
	this->p_data = new T[this->m_capacity];
	for (int i = 0; i < this->m_size; ++i)
	{
		this->p_data[i] = arr.p_data[i];
	}
}


// 移动构造
template<class T>
DynamicArray<T>::DynamicArray(DynamicArray<T> &&arr)
{
	std::cout << "移动构造" << std::endl;
	this->m_capacity = arr.m_capacity;
	this->m_size = arr.m_size;
	this->p_data = arr.p_data;
	arr.p_data = nullptr;
	arr.m_capacity = 0;
	arr.m_size = 0;
}

// 普通赋值
template<class T>
DynamicArray<T>& DynamicArray<T>::operator=(const DynamicArray<T>& arr)
{
	std::cout << "普通赋值" << std::endl;
	// 拷贝属性
	this->m_capacity = arr.m_capacity;
	this->m_size = arr.m_size;

	// 如果对象拥有原数据，则释放
	if (this->p_data != nullptr)
	{
		delete[] this->p_data;
		this->p_data = nullptr;
	}

	// 拷贝数据
	this->p_data = new T[this->m_capacity];
	for (int i = 0; i < arr.m_size; ++i)
	{
		this->p_data[i] = arr.p_data[i];
	}

	return *this;
}

// 移动赋值
template<class T>
DynamicArray<T>& DynamicArray<T>::operator=(DynamicArray<T> &&arr)
{
	std::cout << "移动赋值" << std::endl;
	this->m_capacity = arr.m_capacity;
	this->m_size = arr.m_size;

	if (this->p_data != nullptr)
	{
		delete[] this->p_data;
		p_data = nullptr;
	}

	this->p_data = arr.p_data;
	arr.p_data = nullptr;
	arr.m_capacity = 0;
	arr.m_size = 0;

	return *this;
}

// 添加元素
template<class T>
void DynamicArray<T>::push_back(const T &ele)
{
	if (m_capacity == m_size)
	{
		// 扩展空间，默认2倍扩展（可自定义策略）
		size_t new_capacity = m_capacity * 2;
		T* new_data = new T[new_capacity];

		// 原空间数据拷贝到新空间
		for (int i = 0; i < m_size; ++i)
		{
			new_data[i] = this->p_data[i];
		}

		// 释放原空间
		if (this->p_data != nullptr)
		{
			delete[] this->p_data;
			this->p_data = nullptr;
		}
		
		this->m_capacity = new_capacity;
		this->p_data = new_data;
	}

	// 新元素拷贝到容器中
	this->p_data[this->m_size++] = ele;
}

// 删除元素
template<class T>
void DynamicArray<T>::remove(const T& ele)
{
	// 查找元素
	int i = 0;
	bool flag = false;
	for (;i < m_size; ++i)
	{
		if (p_data[i] == ele)
		{
			flag = true;
			break;
		}
	}

	// 删除元素
	if (flag)
	{
		for (int j = i; j < m_size - 1; ++j)
		{
			p_data[j] = p_data[j + 1];
		}

		--m_size;
	}
}

template<class T>
T& DynamicArray<T>::operator[](int index) const
{
	return p_data[index];
}

// 数组大小
template<class T>
size_t DynamicArray<T>::size() const
{
	return m_size;
}

// 析构函数
template<class T>
DynamicArray<T>::~DynamicArray()
{
	std::cout << "析构函数" << std::endl;
	if (this->p_data != nullptr)
	{
		delete[] this->p_data;
		this->p_data = nullptr;
		this->m_size = 0;
		this->m_capacity = 0;
	}
}