STL Container插入元素和内存透视

Question

这个问题是 问题 的扩展，我想了解如何将元素插入 STL容器。

假设我有一个对象；，我想将其插入到任何STL容器中，我知道有一个分配器的概念来处理记忆。但我无法理解实际对象是如何复制到STL内存中的。因此，当我调用Container.insert时，我的对象存储在堆栈上，STL如何创建该对象的副本并将该对象存储到其内存中。

任何模拟相同内容的等效 C++ 代码都会有所帮助。

Answer 1

该方法并不复杂。基本上，容器将从分配器获取内存，然后执行复制构造（在该内存上使用placement-new）。更容易看到的容器是vector：

void push_back( T const & value ) {
   ensure_enough_capacity();
   new (end_ptr++) T( value );
}

其中ensure_enough_capacity()确定向量是否必须增长并执行此操作，也就是说，如果，它将最终调用分配器>size()==capacity() 当 push_back 被调用时。

下一个复杂级别是列表，其中每个节点都是单独分配的，并且库必须管理一些额外的信息。在这种情况下，代码将类似于：

void push_back( T const& value ) {
    node* n = allocator::allocate( sizeof(node) );
    new (n) node( value, x, y );
}

其中 x 和 y 是初始化节点的 next 和 last< 的适当指针/code> 指针（对于 last 通常是指向最后一个节点的指针，对于 next 则是指向哨兵节点的指针——超出末尾无效），以及假设这个特定的构造函数将复制构造值，然后修复所有引用的指针。

有序关联容器在管理平衡树方面具有额外的复杂性，但方法是相同的：分配一个足够大的块来容纳值和额外信息，然后使用placement-new来构建节点。剩下的就是数据结构的细节了。

Answer 2

使用适当的复制构造函数（或者可能是 C++11 中的移动构造函数）复制对象。假设您已预先分配了一个包含 N 个 Foo 对象的数组，并且其中已有 length 对象，则 std::vector 中的代码可能会看起来像：

void std::vector<Foo>::push_back( const Foo& n ) { 
    new( my_memory+length ) Foo(n);
    ++length;
}

new后面的括号表示“placement new”，即在预分配的存储上调用new。

Answer 3

大多数插入函数的原型都是

void insert(const A& a);

采用 cost& 本质上是一种传递值而不将其复制到形式参数的方法。

容器 - 取决于它们的工作方式 - 具有包含 A 的内部结构。
例如，一个列表有一个

struct node
{
   A val;
   node* next;
   node* prev;

   node(const A& a) :val(a), next(), perv()
   { }  
};

Insert，此时不只需要注意

void insert(const A& a)
{
   node* n = new(allocator.allocate()) node(a);
   /*set next and prev accordingly to list functionality*/
}

该引用通过节点构造函数传递并传递给节点嵌入的 A 的初始值设定项，即它自己的复制构造函数。

请注意，allocator.allocate() 实际上必须为节点分配空间，而不仅仅是 A。因此，列表中的分配器实例的类型将是 typename Allocator::rebind::other ，其中 Allocator 是 list 的第二个模板参数，默认为 std::allocator。

Answer 4

内存分配方面真正发生的情况是：_it 使用作为 allocator 模板参数传入的分配器。

 map<int , long , less<int> , myAllocator<pair<int, long> > > myMap;

无论您做什么 myAllocator ，它的分配（如果有）都将被使用。从技术上讲，这意味着您可以预先分配所有对（可能来自向量）。它还意味着正在使用新的放置，就像在向量情况下一样，只是，对于小分配，您的分配将被多次调用，而不是单个连续分配。

这只会导致容器无法保证存储是连续的（就像向量情况一样），但是，由于实现的原因，它可能仍然是连续的 编写分配器

是一个高级主题，已在

• 现代 C++ 设计 (A.Alexandrescu)
• Boost 库
• 另请参阅EASTL （设计用于（嵌入式) 游戏编程；在这种环境中，堆通常“不存在”或被禁止；此外，EASTL 没有默认的性能是最重要的。分配器。）
  _{https://github.com/paulhodge/EASTL}