c++ - 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
...

类似的东西。分配器将关心分配内存。它将分配内存和将对象构造到该内存中的步骤分开，因此它可以预分配内存，但尚未调用构造函数。在重新分配期间，vector 必须注意复制构造函数抛出的异常，这使事情变得有些复杂。以上只是一些伪代码片段——不是真正的代码，可能包含许多错误。如果大小超过容量，它会要求分配器分配一个新的更大的内存块，否则它只会在先前分配的空间上构造。

这个的确切语义取决于分配器。如果它是标准分配器，构造就可以了

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

然后分配allocate只会从 ::operator new 获取内存. destroy会调用析构函数

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

所有在分配器后面抽象出来的东西，vector 只是使用它。堆栈或池分配器的工作方式可能完全不同。关于vector的一些要点那些很重要

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