扩容与改变——从Pushback看数据结构
Pushback是什么？
Pushback是一种常见的数据结构，它是一种可变数组，它的主要功能是在数组的末尾添加新的元素，并返回该元素的引用。在C++中，我们可以使用STL库中的vector实现Pushback，它是一种动态数组，能够自动扩容，支持数据的动态添加和删除。
Pushback的扩容机制
Pushback在实现时，不可能无限制的扩容下去，因为这样不仅会占用过多的内存空间，而且也会影响程序的性能。所以，当vector中的元素数量接近容量时，就会触发重新分配内存的操作。vector采用的是按照当前容量的两倍进行扩容的策略，这样可以保证扩容的次数最多为logN次，从而节省了内存和程序的运行时间。
扩容操作的大致步骤如下：
1. 分配新的内存
当vector中的元素数量超过了容量值，就需要重新分配内存。新分配的内存大小是原来容量的两倍，也就是将原来的元素拷贝到新的内存中，在新分配的内存中分配空间。
2. 复制元素到新的内存中
由于新的内存中没有元素，所以我们需要将原来的元素拷贝到新的内存空间中。拷贝元素前需要判断元素类型是POD类型还是非POD类型。如果是POD类型，可以直接使用memcpy进行拷贝，如果是非POD类型，就需要调用类型的构造函数拷贝元素。
3. 销毁旧的内存
当新的内存分配好并且元素也拷贝到新的内存中之后，就需要销毁旧的内存了。方式是调用析构函数，释放旧内存空间。
Pushback的使用
在C++中使用vector类来实现Pushback是十分简单的，只需要将元素一个一个添加到向量的尾部即可。示例如下：
vector<int> v;int a=1,b=2,c=3;v.push_back(a);v.push_back(b);v.push_back(c);在实际的开发中，我们还需要注意以下几个问题：
1. 引用失效问题
由于Pushback在扩容的时候会重新分配内存，所以如果某个元素的引用被直接使用，就会出现问题。因为引用本身是一个指针，如果这个指针指向的元素被移动到了新的内存空间，那么旧的指针就会变成无效的指针，使用这样的指针将会引发一系列的问题。
为了避免这个问题，我们需要使用迭代器替代引用。如果想获取vector中某个元素的引用，可以使用vector.begin()方法返回指向第一个元素的迭代器，然后使用迭代器加上下标的偏移量进行访问。示例如下：
vector<int> v;int a=1,b=2,c=3;v.push_back(a);v.push_back(b);v.push_back(c);vector<int>::iterator iter=v.begin();cout<<*(iter+1)<<endl;2. 预分配内存
在向量中添加大量的元素时，首先需要预测元素的数量，然后分配最大的容量值，这样可以避免反复扩容的操作。例如，我们可以使用reserve()函数来预分配内存，示例如下：
vector<int> v;v.reserve(10);for(int i=0;i<10;i++){ v.push_back(i);}3. 适当的删除元素
在实际的开发中，我们还经常需要从向量中删除元素，这个时候需要注意避免过多的内存占用。一个常见的错误是使用erase()函数来删除单个元素，它会从数组中删除元素，但在删除后，向量并不会自动收缩，导致内存的浪费。所以，我们可以采用swap函数+pop_back函数的方式来删除元素，这是删除操作的一种高效的方式。
Pushback是一种常见的动态数组数据结构，它的平均性能是十分优秀的。在实际的开发中，我们可以使用STL库中的vector来实现Pushback，它的实现是基于内存的动态管理，可以自动扩容。在使用Pushback时，需要注意引用失效、预分配内存和适当的删除元素等问题。
