Mehlins Mehlins - 3 months ago 22
C++ Question

Allocator usage in C++ (STL Tree)

I've recently been trying to understand how c++ allocators work, and I've been looking to the implementation of the red-black tree that the STL library uses for things like

std::set
or
std::map
, but there are some things that I can't get my head around.

The first thing that does is convert the allocator from the type the container has to store -
_Val
- to the type of the node that the tree uses -
_Rb_tree_node<_Val>
- using the rebind template:

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;


This I can sort out.

Now, when an element is inserted and it needs to create a new node what it does is this

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


which I assume allocates space for a single node. But then it does this

::new(__node) _Rb_tree_node<_Val>;


which I really don't know what it does, since the space for
__node
has already been allocated. But after that it also does this

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


which makes me even more confused, because is supposedly constructing a node (is the node allocator), but it passes the pointer
__node->_M_valptr()
which is of type
_Val*
.

If someone could explain this, I would be very grateful.

Answer
::new(__node) _Rb_tree_node<_Val>;

This form of new expression is called 'placement new'. It does not allocate new memory, but only constructs an object in the memory region pointed by the argument. Here __node is a pointer to already allocated memory for the node, this expression constructs an object of type _Rb_tree_node<_Val> in this place.

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

this line constructs an object of type _Val in the memory pointed to by __node->_M_valptr().