关于vector的扩容机制

马谦马谦马谦

613
文章

17
评论

2020年1月20日11:16:17

评论 952字阅读3分10秒

往vector中添加元素时，如果空间不够将会导致扩容。vector有两个属性：size和capacity。size表示已经使用的数据容量，capacity表示数组的实际容量，包含已使用的和未使用的。

vector扩容规则：

当数组大小不够容纳新增元素时，开辟更大的内存空间，把旧空间上的数据复制过来，然后在新空间中继续增加。
新的更大的内存空间，一般是当前空间的1.5倍或者2倍，这个1.5或者2被称为扩容因子，不同系统实现扩容因子也不同。

注意，扩容会导致迭代器失效。

在VS2017中，vector的扩容因子是1.5。可以追踪push_back的实现：

decltype(auto) emplace_back(_Valty&&... _Val)
{	// insert by perfectly forwarding into element at end, provide strong guarantee
	if (_Has_unused_capacity())
	{
		return (_Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...));
	}

	_Ty& _Result = *_Emplace_reallocate(this->_Mylast(), _STD forward<_Valty>(_Val)...);
    // ...
}

decltype(auto) emplace_back(_Valty&&... _Val)

{ // insert by perfectly forwarding into element at end, provide strong guarantee

if (_Has_unused_capacity())

{

return (_Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...));

}

_Ty& _Result = *_Emplace_reallocate(this->_Mylast(), _STD forward<_Valty>(_Val)...);

// ...

}

函数中先通过_Has_unused_capacity函数判断是否有还有未使用的空间，如果有未使用的空间，直接在未使用的空间上新增。如果没有未使用的空间了，就需要执行_Emplace_reallocate重新扩容：

pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val)
{	
	// ..
	const size_type _Newsize = _Oldsize + 1;
	const size_type _Newcapacity = _Calculate_growth(_Newsize);
	// ..
}

pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val)

{

// ..

const size_type _Newsize = _Oldsize + 1;

const size_type _Newcapacity = _Calculate_growth(_Newsize);

// ..

}

函数中先判断新长度，然后继续调用_Calculate_growth扩容，这个函数才是真正用来扩容的函数。

忽略过其他判断逻辑，_Calculate_growth的实现为：

size_type _Calculate_growth(const size_type _Newsize) const
{	
	// ...
    const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
    // ...
}

size_type _Calculate_growth(const size_type _Newsize) const

{

// ...

const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;

// ...

}

新的扩容大小等于当前容量再加上当前容量的一半，即按照1.5倍扩容。

在GCC的实现中，vector扩容是2倍扩容的。

1.5倍扩容和2倍扩容的区别

扩容因子越大，需要分配的新内存空间越多，越耗时。空闲空间较多，内存利用率低。
扩容因子越小，需要再分配的可能性就更高，多次扩容耗时。空闲空间较少，内存利用率高。

因此，小规模数组，添加元素不频繁的，建议使用扩容因子更小的。当数据规模越大，插入更频繁，大扩容因子更适合。

示例代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int i;
    vector<int> v;

    cout << v.capacity() << " ";
    for (i = 0; i < 10; i++) {
        v.push_back(1);
        cout << v.capacity() << " ";
    }

    return 0;
}