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

Question

我最近一直在尝试了解 C++ 分配器的工作原理，并且一直在寻找 STL 库用于 std::set 或 [=15 之类的东西的红黑树的实现=], 但有些事情我想不通。

首先要做的是将分配器从容器必须存储的类型 - _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);

我假设为单个节点分配 space。但它会这样做

::new(__node) _Rb_tree_node<_Val>;

我真的不知道它做了什么，因为 __node 的 space 已经分配了。但在那之后它也这样做

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

这让我更加困惑，因为据说正在构造一个节点（是节点分配器），但它传递了 _Val*.

类型的指针 __node->_M_valptr()

如果有人能解释一下，我将不胜感激。

Answer 1

::new(__node) _Rb_tree_node<_Val>;

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

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

这一行 constructs _Val 类型的对象在 __node->_M_valptr() 指向的内存中。

Answer 2

行

::new(__node) _Rb_tree_node<_Val>;

使用 placement new，它只是在给定的内存地址 __node) 处构造一个 _Rb_tree_node<_Val> 类型的对象。这构造了节点对象。

现在它需要与 _M_valptr() 的其中一位成员做一些事情。该行

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

（间接调用）分配器的 construct method 与全局放置 new 非常相似（实际上，它通常只是调用它）。因此，它再次采用指向构造对象的位置的指针。这构造了值对象。

Answer 3

它使用了一种叫做“Placement 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!

基本思想是您现在负责通常由语言和编译器自动处理的手动清理。这是非常糟糕的做法 EXCEPT 在使用分配器时，直接控制内存分配对于编写一个好的分配器至关重要。

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

Allocator usage in C++ (STL Tree)

c++

stl

allocator

c++11