Mehlins Mehlins - 2 months ago 8x
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

, 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 -
- to the type of the node that the tree uses -
- 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
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
which is of type

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

::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().