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.

Firecure

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 – Pacifistic

Ok, but why pass the pointer __node to the operator? Furthermore, if it does construct the node, what does the ::construct() do afterwards? – Firecure

"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? – Take

@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. – Ottilie

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

Cruz

Thanks. Just the final thing. Why it uses the node allocator for _M_valptr(), which is of another type? – Firecure

@Mehlins what is the type of _M_valptr? – Samaria

Val*. The code is: __gnu_cxx::__aligned_membuf<_Val> _M_storage; _Val* _M_valptr() { return _M_storage._M_ptr(); } – Firecure

@Mehlins As Ami Tavory already explained, in turn calls the construct method of the allocator, which then calls placement new. (this line does not allocate any memory, it only constructs an object, so it is not using the allocator to allocate anything anyway, and thus the type of the allocator does not matter) – Cruz

By the way, construct method in the allocator / allocator_traits is declared deprecated in C++17. – Cruz

Oh, ok, I see. The construct function is actually a template and uses type inference for the _M_valptr(). Also, the construct function is only deprecated for allocator. From what I've been seeing they're trying to shift everything to allocator_traits, to make things more generic. Thanks – Firecure

@Mehlins Yes, I stay corrected, it is not deprecated in the allocator_traits. And the idea of deprecation is that the allocator should take case of allocating memory only, it does not need to know much about the type and how to construct it. – Cruz

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.

Ultrasonics

Ok, so I assume it uses the placement new because it has no value to pass (required in the ::construct()), and then it uses the ::construct() function because it actually has some value to pass (hidden in the ...). There's one thing I still don't get. Why it uses the node allocator for _M_valptr(), which is of another type? – Firecure

@Mehlins This really depends on the exact standard library implementation you're using, but, again, it's almost positively just indirectly calling the global placement new. How does it know to call the appropriate one via the node allocator? through the rebind mechanism you mentioned, through function templates, etc. It's not fundamentally using the node allocator, despite the apperance. – Ultrasonics

Answer 3

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.

Postmeridian