vector 的数据安排以及操作方式，与array常常相似，两者的唯一差别在于空间运用的灵活性：array是静态空间，一旦配置了不能改变。vector动态空间，可以根据需要，自行扩充空间以容纳新元素。
vector的实现技术关键在于其对大小控制以及重新配置时的数据移动效率。因为重新申请内存，拷贝原数据，释放原vector是要花很长时间。所以在满载时，申请新空间的大小要在空间和时间上取出平衡。
vector结构很简单：
vector.png
template <typename T>
class Vector
{
......
typedef allocator<T> dataAlloc;
private:
T* _start;
T* _finish;
T* _end_of_storage;
}
迭代器
typedef T* iterator;
typedef const T *const_iterator
原生指针就可以充当迭代器。
添加元素
push_back(const T &value)
- 有空间则直接用 construct 构造元素。
- 没有空间则先重新分配新的内存，然后再把以前的元素拷贝之后，构造元素。也是因此，迭代器会失效
if (size() == capacity())
reallocateAndCopy();
dataAlloc::construct(_finish++, value);
insert(iterator position, const size_type n, const T &value)
- 备用空间足够
2 种情况：- a: 插入点后现有元素个数 >= 新增元素个数
- b: 插入点后现有元素个数 <= 新增元素个数
- 备用空间不足
- 第一步：将原vector [ _start, position )拷贝至新的 vector
- 第二步：构造n个value
- 第三步：将 [ position, _finish )元素也拷贝至新的 vector
- 第四步：析构并释放原vector
/* 备用空间足够 */
if (_end_of_storage - _finish >= n) {
size_type elems_after = _finish - position;
iterator old_finish = _finish;
if (elems_after > n) {
/* 插入点后现有元素个数 >= x新增元素个数 */
uninitialized_copy(position, old_finish - n, old_finish);
_finish += n;
} else {
/* 插入点后现有元素个数 <= x新增元素个数 */
uninitialied_fill_n(_finish, n - elems_after, value);
_finish += n - elems_after;
uninitialized_copy(position, old_finish, _finish);
_finish += elems_after;
fill(position, old_finish, value);
}
}
/* 备用空间不够 */
else {
size_type old_size = size();
size_type len = old_size + max(old_size, n); // 新长度为旧长度的2倍，或者旧长度+新元素个数
iterator new_start = dataAlloc::allocate(len);
iterator new_finish = new_start;
try{
/* 将原 vector[_start, position) 拷贝至新的vec */
new_finish = uninitialized_copy(_start, position, new_start);
/* 构造 n 个value */
new_finish = uninitialied_fill_n(new_finish, n, value);
/* 将 [position, _finish) 元素也拷贝过来 */
new_finish = uninitialized_copy(position, _finish, new_finish);
} catch(...) {
destory(new_start, new_finish);
dataAlloc::deallocate(new_start, len);
throw;
}
/* 析构并释放原vector */
destroyAndFree();
_start = new_start;
_finish = new_finish;
_end_of_storage = _start + len;
}
备用空间足够，插入点后现有元素个数 <= 新增元素个数.png
修改容量
resize
- n > capacity()需要重新分配内存空间，复制原size()元素,释放原资源,增加(n - size())个元素
- size() < n <= capacity 不需要重新分配内存空间，增加(n - capacaity())个元素
- n == size() 什么都不做
- n < size() 需要析构(size() - n)个元素
void resize(size_type n, const T &value) {
if (n > capacity()) {
size_type addElementLength = n - size();
/* 重新分配内存 */
T *newStart = dataAlloc::allocate(n);
T *newFinish = uninitialized_copy(begin(), end(), newStart);
/* 拷贝元素 */
newFinish = uninitialied_fill_n(newFinish, addElementLength, value);
/* 销毁原内存 */
destroyAndFree();
/* 更新相关指针 */
_start = newStart;
_finish = newFinish;
_end_of_storage = _start + n;
} else if (n <= capacity() && n > size()) {
size_type addElementLength = n - size();
_finish = uninitialied_fill_n(end(), addElementLength, value);
} else if (n < size()) {
dataAlloc::destroy(begin() + n, end());
_finish = _start + n;
}
}
reserve
- n > capacity() 重新分配内存空间,复制原size()元素,释放原资源。
void reserve(size_type n) {
if (n > capacity()) {
T *new_start = dataAlloc::allocate(n);
T *new_finish = uninitialized_copy(begin(), end(), new_start);
destroyAndFree();
_start = new_start;
_finish = new_finish;
_end_of_storage = _start + n;
}
}
删除元素
void pop_back()
void Vector<T>::pop_back() {
dataAlloc::destroy(--_finish);
}
iterator erase(iterator first, iterator last)
size_type remove_element_counts = last - first; // 要删除的个数
if (remove_element_counts > 0) {
auto it = first;
for (; last != _finish; last++, it++)
*it = *last;
dataAlloc::destroy(it, _finish);
_finish = _finish - remove_element_counts;
}
return first;
iterator erase(iterator first, iterator last).png
iterator erase(iterator position)
return erase(position, position + 1);
