如何在std :: vector中管理动态内存？

Question

std :: vector如何实现对不断变化的元素数量的管理:它是使用realloc()函数还是使用链表？

谢谢.

Answer 1

它使用赋予它的分配器作为第二个模板参数.就像这样.假设它在push_back中,让我们t成为要推送的对象:

...
if(_size == _capacity) { // size is never greater than capacity
    // reallocate
    T * _begin1 = alloc.allocate(_capacity * 2, 0);
    size_type _capacity1 = _capacity * 2;

    // copy construct items (copy over from old location).
    for(size_type i=0; i<_size; i++)
        alloc.construct(_begin1 + i, *(_begin + i));
    alloc.construct(_begin1 + _size, t);

    // destruct old ones. dtors are not allowed to throw here. 
    // if they do, behavior is undefined (17.4.3.6/2)
    for(size_type i=0;i<_size; i++)
        alloc.destroy(_begin + i);
    alloc.deallocate(_begin, _capacity);

    // set new stuff, after everything worked out nicely
    _begin = _begin1;
    _capacity = _capacity1;
} else { // size less than capacity
    // tell the allocator to allocate an object at the right
    // memory place previously allocated
    alloc.construct(_begin + _size, t);
}
_size++; // now, we have one more item in us
...

这样的事情.分配器将关心分配内存.它保留了分配内存和将对象构建到该内存中的步骤,因此它可以预分配内存,但尚未调用构造函数.在重新分配期间,向量必须注意由复制构造函数抛出的异常,这会使问题复杂化.以上只是一些伪代码片段 - 不是真正的代码,可能包含许多错误.如果大小超过容量,它会要求分配器分配一个新的更大的内存块,如果没有,那么它只是在先前分配的空间构造.

这个的确切语义取决于分配器.如果它是标准分配器,那么构造就可以

new ((void*)(_start + n)) T(t); // known as "placement new"

而分配allocate只会从中获取记忆::operator new.destroy会打电话给析构函数

(_start + n)->~T();

所有这些都在分配器后面抽象而且向量只是使用它.堆栈或池分配器可以完全不同.关于vector这一点的一些关键点很重要

• 调用之后reserve(N),您可以在向量中插入最多N个项目而不会有重新分配的风险.在那之前,只要size() <= capacity()它的元素的引用和迭代器仍然有效.
• Vector的存储是连续的.您可以将&v [0]视为包含当前向量中的元素的缓冲区.

Answer 2

向量的硬性规则之一是数据将存储在一个连续的内存块中.

这样你知道你理论上可以做到这一点:

const Widget* pWidgetArrayBegin = &(vecWidget[0]);

然后,您可以将pWidgetArrayBegin传递给希望将数组作为参数的函数.

唯一的例外是std :: vector <bool>特化.它实际上根本不是bool,但这是另一个故事.

所以std :: vector将重新分配内存,而不会使用链表.

这意味着你可以通过以下方式射击自己:

Widget* pInteresting = &(vecWidget.back());
vecWidget.push_back(anotherWidget);

众所周知,push_back调用可能导致向量将其内容转移到一个全新的内存块,使pInteresting无效.