reserve( Container:: size_ type n) 强迫 容器 把 它的 容量 变为 至少 是 n, 前提 是 n 不小于 当前 的 大小。 这通常会 导致 重新 分配, 因为 容量 需要需要 增加。
( 如果 n 比 当前 的 容量 小, 则 vector 忽略 该 调用, 什么 也 不做; 而 string 则 可 能把 自己的 容量 减为 size() 和 n 中的 最大值, 但是 string 的 大小 肯定 保持 不变。)

int main()
{
    vector<int> vt;
    int cap = vt.capacity();
    cout<<"the original capacity is "<<cap<<endl;
    for(int i=0; i<1000; i++){
        vt.push_back(i);
        if(vt.capacity() > cap){
            cap = vt.capacity();
            cout<<"new capacity is "<<cap<<endl;
        }
    }
    return 0;
}
/*
the original capacity is 0
new capacity is 1
new capacity is 2
new capacity is 4
new capacity is 8
new capacity is 16
new capacity is 32
new capacity is 64
new capacity is 128
new capacity is 256
new capacity is 512
new capacity is 1024
*/

从运行的结果来看,vector的容量以2的倍数增长。
来看push_back的源码:

template <class _Allocator>
void
vector<bool, _Allocator>::push_back(const value_type& __x)
{
    if (this->__size_ == this->capacity())
        reserve(__recommend(this->__size_ + 1));
    ++this->__size_;
    back() = __x;
}

函数__recommend原型为:

template <class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
typename vector<bool, _Allocator>::size_type
vector<bool, _Allocator>::__recommend(size_type __new_size) const
{
    const size_type __ms = max_size();
    if (__new_size > __ms)
        this->__throw_length_error();
    const size_type __cap = capacity();
    if (__cap >= __ms / 2)
        return __ms;
    return _VSTD::max(2*__cap, __align_it(__new_size));
}

其中 __align_it 是比_new_size大的最小的2的幂。

    static size_type __align_it(size_type __new_size) _NOEXCEPT
        {return __new_size + (__bits_per_word-1) & ~((size_type)__bits_per_word-1);};

而reserve函数是这样的:

template <class _Allocator>
void
vector<bool, _Allocator>::reserve(size_type __n)
{
    if (__n > capacity())
    {
        vector __v(this->__alloc());
        __v.allocate(__n);
        __v.__construct_at_end(this->begin(), this->end());
        swap(__v);
        __invalidate_all_iterators();
    }
}

即,只有新的需求容量大于原容量,vector才会重新分配内存并构造。
假设,我们在vector对象声明后立即使用reverse改变他的容量,即在第一句后加上:vt.reserve(1000);
那么,程序输出只有:the original capacity is 1000
即,之后都不会重新分配内存。

分类: C plus plus

发表评论

电子邮件地址不会被公开。 必填项已用*标注