vector的数据结构
template <class T, class Alloc = alloc>
class vector {
...
public:
iterator begin() { return start; }
iterator end() { return finish; }
size_type size() const { return size_type(end() - begin()); }
size_type capacity() const { return size_type(end_of_storage - begin()); }
bool empty() const { return begin() == end(); }
reference operator[](size_type n) { return *(begin() + n); }
reference front() { return *begin(); }
reference back() { return *(end() - 1); }
...
protected:
iterator start; //表示目前使用空间的头
iterator finish; //表示目前使用空间的尾
iterator end_of_storage; //表示目前可用空间的尾
...
}
vector 有 size(), capacity(), resize(), reserve() 这几个和大小, 容量相关的接口
size() 表示 vector 的大小(已用空间大小);
resize() 表示改变 vector 的大小(已用空间大小);
capacity() 表示 vector 的容量(总大小);
reserve() 表示改变 vector 的容量(总大小);
capacity() - size() 表示 vector 剩余可用空间的大小. vector 的容量永远大于或等于其大小. 当 capacity() = size() 时, 表示已经没有剩余空间, 下次增加数据会引起vector空间的动态增长。
vector容量增长.png
vector内存管理
void push_back(const T& x)
{
if (finish != end_of_storage) //还有备用空间
{
construct(finish, x); //全局函数
++finish; //调整finish
}
else //无备用空间
{
insert_aux(end(), x); //vector member function
}
}
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x)
{
if (finish = != end_of_storage) // 还有备用空间
{
construct(finish, *(finish - 1)); // 在备用空间起始处构造一个元素，并以vector最后一个元素值为其初值
++finish; // 调整finish
T x_copy = x;
copy_backward(position, finish - 2, finish - 1);
*position = x_copy;
}
else // 已无备用空间
{
const size_type old_size = size();
const size_type len = old_size != 0 ? 2 * ols_size : 1;
// 以上配置原则，如果原大小为0，则配置1（个元素）
// 如果原大小不为0，则配置原大小的两倍
// 前半段用来放置源数据，后半段准备用来放置新数据
iterator new_start = data_allocator::allocate(len); // 实际配置
iterator new_finish = new_start;
try {
// 将原 vector 的内容拷贝到新的 vector
// uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);
// 迭代器 first 指向输入端的起始位置, 迭代器 last 指向输入端的结束位置(前闭后开区间)
// 迭代器 result 指向输出端(欲初始化空间)的起始位置
new_finish = uninitialized_copy(start, position, new_start);
// 为新元素设定初值x
construct(new_finish, x);
// 调整finish
++new_finish;
// 将安插点的原内容也拷贝过来
new_finish = uninitialized_copy(position, finish, new_finish);
}
catch (...) {
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
// 析构并释放原 vector
destory(begin(), end());
deallocate();
// 调整迭代器, 指向新 vector
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
动态扩容是只分配一个原来大小两倍的新空间, 然后将源数据拷贝到新空间, 再在新空间构造新元素, 最后是否原空间
由于动态扩容涉及到新内存的分配, 源数据的拷贝以及原内存的释放, 这一系列操作对性能影响较大, 为了预防动态扩容, 如果预先知道要添加元素的数量, 可以先对vector做 reserve() 操作, 将 vector 的容量设置成需要的大小
