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

如果有人能够解释这一点,我将非常感激.

Answer 1

::new(__node) _Rb_tree_node<_Val>;

这种新表达形式称为"放置新".它不分配新内存,而只构造参数指向的内存区域中的对象.这__node是一个指向已经为节点分配的内存的指针,这个表达式_Rb_tree_node<_Val>在这个地方构造一个类型的对象.

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

这一行在指向的内存中构造一个类型的对象._Val__node->_M_valptr()