如何在std :: vector中管理动态内存？ [英] How is dynamic memory managed in std::vector?

问题描述

std :: vector如何实现对变化数量的元素的管理：它使用realloc（）函数还是使用链表？

How does std::vector implement the management of the changing number of elements: Does it use realloc() function, or does it use a linked list?

谢谢。

推荐答案

它使用赋予它的分配器作为第二个模板参数。像这样。说它是在push_back，让 t 是要推送的对象：

It uses the allocator that was given to it as the second template parameter. Like this then. Say it is in push_back, let t be the object to be pushed:

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

。分配器将关心分配内存。它保持分配内存和将对象构建到该内存中的步骤，因此它可以预分配内存，但尚未调用构造函数。在重新分配期间，向量必须注意由拷贝构造函数抛出的异常，这在某种程度上使问题复杂化。上面只是一些伪代码片段 - 不是真正的代码，可能包含许多错误。如果大小超过容量，则它要求分配器分配一个新的更大的内存块，如果不是，则只是在先前分配的空间上构造。

Something like that. The allocator will care about allocating memory. It keeps the steps of allocating memory and constructing object into that memory apart, so it can preallocate memory, but not yet call constructors. During reallocate, the vector has to take care about exceptions being thrown by copy constructors, which complicates the matter somewhat. The above is just some pseudo code snippet - not real code and probably contains many bugs. If the size gets above the capacity, it asks the allocator to allocate a new greater block of memory, if not then it just constructs at the previously allocated space.

这个的语义取决于分配器。如果是标准分配器，构造将执行

The exact semantics of this depend on the allocator. If it is the standard allocator, construct will do

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

并且分配 c $ c>只会从 :: operator new 获取内存。 destroy 会调用析构函数

And the allocate allocate will just get memory from ::operator new. destroy would call the destructor

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

所有被抽象在分配器后面，向量只是使用它。堆栈或池分配器可以完全不同。 向量的一些要点很重要

All that is abstracted behind the allocator and the vector just uses it. A stack or pooling allocator could work completely different. Some key points about vector that are important

• 调用 reserve（N），您最多可以将N个项目插入到您的向量中，而不会冒重新分配的风险。直到那时，只要 size（）< = capacity（），它的元素的引用和迭代器仍然有效。


• Vector的存储是连续的。您可以将& v [0]视为一个包含您目前在向量中包含的元素的缓冲区。

• After a call to reserve(N), you can have up to N items inserted into your vector without risking a reallocation. Until then, that is as long as size() <= capacity(), references and iterators to elements of it remain valid.
• Vector's storage is contiguous. You can treat &v[0] as a buffer containing as many elements you have currently in your vector.

这篇关于如何在std :: vector中管理动态内存？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！