c++ - C++ 中的分配器用法(STL 树)

Question

我最近一直在尝试了解 C++ 分配器的工作原理，并且一直在寻找 STL 库用于类似 std::set 之类的红黑树的实现。或 std::map , 但有些事情我无法理解。

首先要做的是从容器必须存储的类型转换分配器 - _Val - 树使用的节点类型 - _Rb_tree_node<_Val> - 使用重新绑定(bind)模板:

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

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

Answer 1

::new(__node) _Rb_tree_node<_Val>;

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

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

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