gcc版本: gcc 2.95.3
篇幅原因,这里先看一部分源码
vector
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc>
{
private:
typedef _Vector_base<_Tp, _Alloc> _Base;
public:
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type* iterator; //迭代器
typedef const value_type* const_iterator;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef typename _Base::allocator_type allocator_type;
allocator_type get_allocator() const {
return _Base::get_allocator(); }
...
vecotr 本身其实是没有任何数据的
从这可以看出 vector 实际上是继承了 另一个类.
_Vector_base 类 的数据部分
protected:
_Tp* _M_start;
_Tp* _M_finish;
_Tp* _M_end_of_storage;
也就是说一个未初始化的vecotr 只有三根指针.
_M_start: 表示目前使用空间头
_M_finish: 表示目前使用空间尾
_M_end_of_storage: 表示目前可用空间的尾
解释一下空间的终止指针:
vecotr 的大小一共两个,一个元素的个数 —size()
另一个是 vecotr锁分配的空间的大小 --capacity()
如图:
int main( )
{
vector<double> v;
cout << sizeof(v) << "\n";
}
输出的结果是 24 ,正好是三根指针的大小(64 位)
继续往下看源码
源码节选
一些常用的成员函数
public:
iterator begin() {
return _M_start; } //头迭代器
iterator end() {
return _M_finish; } //尾迭代器
size_type size() const //元素的个数
{
return size_type(end() - begin()); }
size_type max_size() const //vector 可以容纳最大元素数
{
return size_type(-1) / sizeof(_Tp); }
size_type capacity() const //整个空间的容量
{
return size_type(_M_end_of_storage - begin()); }
bool empty() const //是否为空
{
return begin() == end(); }
当然 vector 也重载了 [] 运算符
reference operator[](size_type __n) {
return *(begin() + __n); }
const_reference operator[](size_type __n) const {
return *(begin() + __n); }
然后看看 push_back()
void push_back(const _Tp& __x) {
if (_M_finish != _M_end_of_storage) {
//尚且还有备用空间
construct(_M_finish, __x); //全局函数
++_M_finish; //调整水位
}
else //无备用空间
_M_insert_aux(end(), __x);
}
void push_back() {
if (_M_finish != _M_end_of_storage) {
construct(_M_finish);
++_M_finish;
}
else
_M_insert_aux(end());
}
说明: 进行push_back() 前,首先判断是否还有剩余的空间如果有就将这个元素放到finish位置上,
如果没有备用空间,调用 _M_insert_aux()
_M_insert_aux()的一个重载版本(加了注释)
// 当push_back 内存不够时
template <class _Tp, class _Alloc>
void
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
if (_M_finish != _M_end_of_storage) {
//尚且有备用空间 为什么这里还有在判断一次呢? 因为这个函数处了被push_back调用>，还会被别的函数调用
construct(_M_finish, *(_M_finish - 1));
++_M_finish;
_Tp __x_copy = __x;
copy_backward(__position, _M_finish - 2, _M_finish - 1);
*__position = __x_copy;
}
else {
//已经没有备用空间
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1; //先判断是否为0,因为第一次如果没有初始化,直接push_back的时候,大小为0 ,如果是0,就
iterator __new_start = _M_allocate(__len); // 否则就为原来的2被 //放1个元素
iterator __new_finish = __new_start;
__STL_TRY {
//将原vector的内容拷贝到新 vector
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
//拷贝安插点后的原内容(因为它也可能被insert(p,x) 呼叫)
construct(__new_finish, __x); //为新元素设置初值
++__new_finish;
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
destroy(begin(), end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
从源代码也可以看出 vector 的空间是以 2 倍增长的.
为什么要以 2 倍增长呢?
从源码可以看出,当空间不足时,是开启一个更大的空间去存放数据,而每次开辟空间后,都要将之前的数据拷贝复制 到新的空间.
所以为了降低空间配置时的速度问题,vector 实际配置的大小可能比客户需求量更大一些,以备将来可能的扩充. 这便是容量(capacity) 的观念.
vector的迭代器
节选
public:
typedef _Tp value_type;
typedef value_type* pointer;
typedef value_type* iterator; //迭代器
从源码中可以看出 vector 的迭代器其实就是简单的 指针.