Allocator usage in C++ (STL Tree)

7
votes

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.

3
c++c++11stlallocator
The operator new does not allocate memory, it creates an object (and sometimes also allocate memory, but not in your case). So, I'd say the second line (::new(__node) _Rb_tree_node<_Val>;) probably constructs the node in the __node allocated memory block – alexeykuzmin0
Ok, but why pass the pointer __node to the operator? Furthermore, if it does construct the node, what does the ::construct() do afterwards? – gmardau
"why pass the pointer"? As answers explain, this is the placement new syntax. And how else would it know where to place the new object? – underscore_d
@Mehlins: The new keyword in normal usage does two things: it allocates memory, and then it calls the operator new function and passes it a pointer to the memory, and this function uses the constructor to create the object at that location in memory. – Mooing Duck

3 Answers

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

3
votes

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.

2
votes

It's using something called "Placement New", which allows an object to be constructed in memory that has already been allocated.

void * mem = malloc(sizeof(MyStruct));
MyStruct * my_struct_ptr = new(mem) MyStruct(/*Args...*/);

/*Do stuff...*/

my_struct_ptr->~MyStruct();//Literally one of the only times a good programmer would ever do this!
free(mem);

Or you could write it like this:

char * mem = new char[sizeof(MyStruct)];
MyStruct * my_struct_ptr = new(mem) MyStruct(/*Args...*/);

/*Do stuff...*/

my_struct_ptr->~MyStruct();//Literally one of the only times a good programmer would ever do this!
delete mem;

Or this:

char mem[sizeof(MyStruct)];
MyStruct * my_struct_ptr = new(mem) MyStruct(/*Args...*/);

/*Do stuff...*/

my_struct_ptr->~MyStruct();//Literally one of the only times a good programmer would ever do this!

The basic idea is that you now become responsible for the manual cleanup normally automatically handled by the language and compiler. Which is extremely bad practice EXCEPT when working with allocators, where direct control over the memory allocations becomes essential to writing a good allocator.