C++中的分配器使用（STL树）

Question

我最近一直在尝试理解C++分配器的工作原理，查看STL库用于std::set或std::map等的红黑树实现，但有些事情让我无法理解。

首先，它使用重新绑定模板将分配器从容器需要存储的类型_Val转换为树使用的节点类型_Rb_tree_node<_Val>：

typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    rebind<_Rb_tree_node<_Val> >::other _Node_allocator;

typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;

我可以解决这个问题。

现在，当插入一个元素并需要创建一个新节点时，它会执行以下操作。

_Node_type __node = _Alloc_traits::allocate(_M_get_Node_allocator(), 1);

我假设这段代码是为单个节点分配空间。但接下来它执行了以下操作。

::new(__node) _Rb_tree_node<_Val>;

我真的不知道它是做什么的，因为已经分配了__node的空间。但在那之后它也执行了这个操作。

_Alloc_traits::construct(_M_get_Node_allocator(), __node->_M_valptr(), ...);

这让我更加困惑，因为它被认为是构造一个节点(即节点分配器)，但它传递的指针__node->_M_valptr()是_Val*类型。

如果有人能解释一下这个问题，我会非常感激。

- gmardau

---

operator new 并不是分配内存，而是创建一个对象（有时也会分配内存，但在这种情况下不会）。因此，我认为第二行 (::new(__node) _Rb_tree_node<_Val>;) 可能会在 __node 分配的内存块中构造节点。 - alexeykuzmin0

好的，但是为什么要将指针__node传递给运算符？此外，如果它确实构造了节点，那么::construct()之后会发生什么？ - gmardau

为什么要传递指针？答案解释了这是 placement new 语法。否则，它怎么知道在哪里放置 new 对象呢？ - underscore_d

@Mehlins：在正常使用中，“new”关键字有两个作用：它分配内存，然后调用“operator new”函数并将指向该内存的指针传递给它，这个函数使用构造函数在内存中创建对象。 - Mooing Duck

Answer 1

::new(__node) _Rb_tree_node<_Val>;

这种形式的 new表达式被称为'放置new'。它不会分配新的内存，而只是在参数指向的内存区域中构造一个对象。这里，__node是指向节点已经分配的内存的指针，此表达式在此处构造了一个类型为_Rb_tree_node<_Val>的对象。

_Alloc_traits::construct(_M_get_Node_allocator(), __node->_M_valptr(), ...);

这行代码构造一个类型为_Val的对象，放置在指向__node->_M_valptr()的内存中。

- Ilya Popov

---

谢谢。最后一个问题。为什么在 _M_valptr() 中使用节点分配器，而它是另一种类型的？ - gmardau

正如Ami Tavory所解释的那样，in turn调用分配器的construct方法，然后调用placement new。（这一行不会分配任何内存，它只是构造一个对象，因此它并没有使用分配器来分配任何东西，因此分配器的类型并不重要） - Ilya Popov

顺便提一下，C++17 中 allocator / allocator_traits 中的 construct 方法已被宣布为废弃。 - Ilya Popov

哦，好的，我明白了。构造函数实际上是一个模板，并使用类型推断来处理 _M_valptr()。此外，construct 函数仅对 allocator 废弃。从我所看到的情况来看，他们正在尝试将所有内容转移到 allocator_traits，以使事情更加通用化。谢谢。 - gmardau

@Mehlins 是的，我改正了，它在 allocator_traits 中没有被弃用。而废弃的想法是分配器只需要负责分配内存，它不需要知道太多有关类型和如何构造的信息。 - Ilya Popov

Answer 2

这行代码

::new(__node) _Rb_tree_node<_Val>;

使用定位new，在给定的内存地址__node上简单构造了一个类型为_Rb_tree_node<_Val>的对象。这构造了节点对象。

现在需要对_M_valptr()中的一个成员执行操作。该行代码：

_Alloc_traits::construct(_M_get_Node_allocator(), __node->_M_valptr(), ...);

（间接调用）分配器的construct方法，这与全局放置new非常相似（实际上，它通常只是调用它）。因此，它再次需要一个指向构建对象位置的指针。这会构建值对象。

- Ami Tavory

---

好的，我假设它使用放置new，因为它没有值可以传递（在::construct()中需要），然后它使用::construct()函数，因为它实际上有一些值要传递（隐藏在...中）。但有一件事我还是不明白。为什么它要为另一个类型的_M_valptr()使用节点分配器？ - gmardau

@Mehlins 这实际上取决于您使用的确切标准库实现，但是几乎可以肯定它只是间接调用全局放置new。它如何通过节点分配器调用适当的函数？通过您提到的rebind机制、函数模板等方式。尽管外观如此，但它并不根本上使用节点分配器。 - Ami Tavory

Answer 3

它使用了一种叫做“定位new”的技术，该技术允许在已经被分配的内存中构造对象。

void * mem = malloc(sizeof(MyStruct));
MyStruct * my_struct_ptr = new(mem) MyStruct(/*Args...*/);

/*Do stuff...*/

my_struct_ptr->~MyStruct();//Literally one of the only times a good programmer would ever do this!
free(mem);

或者您可以这样写：

char * mem = new char[sizeof(MyStruct)];
MyStruct * my_struct_ptr = new(mem) MyStruct(/*Args...*/);

/*Do stuff...*/

my_struct_ptr->~MyStruct();//Literally one of the only times a good programmer would ever do this!
delete mem;

或者这样：

char mem[sizeof(MyStruct)];
MyStruct * my_struct_ptr = new(mem) MyStruct(/*Args...*/);

/*Do stuff...*/

my_struct_ptr->~MyStruct();//Literally one of the only times a good programmer would ever do this!

基本思想是你现在要负责语言和编译器通常自动处理的手动清理工作。这是非常不好的实践，除了在使用分配器时，直接控制内存分配对于编写良好的分配器至关重要。

- Xirema