Allocator usage in C++ (STL Tree)

Question

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 1

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

Answer 2

The line

::new(__node) _Rb_tree_node<_Val>;

uses placement new, which simply constructs an object of type _Rb_tree_node<_Val> at given memory address __node). This constructs the node object.

Now it needs to do something with one of the members at _M_valptr(). The line

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

(indirectly calls) the allocator's construct method which is very similar to the global placement new (in fact, it typically just calls it). As such, it again takes a pointer to the location where to construct the object. This constructs the value object.