Использование Allocator в C++ (STL Tree)

Question

Я недавно пытался понять, как работают распределители C++, и я искал реализацию красно-черного дерева, которое использует библиотека STL для таких вещей, как std::set или std::map , но есть некоторые вещи, от которых я не могу опустить голову.

Первое, что делает преобразование аллокатора от типа контейнера должен хранить - _Val - к типу узла, который использует дерево - _Rb_tree_node<_Val> - с помощью шаблона переназначения:

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; 

Этих Я могу разобраться.

Теперь, когда элемент вставлен, и ему необходимо создать новый узел, что он делает это

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

который я предполагаю, выделяет пространство для одного узла. Но тогда он делает это

::new(__node) _Rb_tree_node<_Val>; 

, который я действительно не знаю, что он делает, так как пространство для __node уже выделены. Но после того, что он также делает этот

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

, что делает меня еще более запутанным, потому что якобы строит узел (это аллокатор узла), но он передает указатель __node->_M_valptr() который имеет типа _Val*.

Если бы кто-нибудь мог это объяснить, я был бы очень благодарен.

Answer 1

::new(__node) _Rb_tree_node<_Val>; 

Эта форма new expression называется 'размещение нового'. Он не выделяет новую память, а только конструирует объект в области памяти, на который указывает аргумент. Здесь __node является указателем на уже выделенную память для узла, это выражение строит объект типа _Rb_tree_node<_Val> в этом месте.

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

эта линия constructs объект типа _Val в памяти, на которую указывает __node->_M_valptr().

Answer 2

Линия

::new(__node) _Rb_tree_node<_Val>; 

использует placement new, который просто строит объект типа _Rb_tree_node<_Val> по заданному адресу памяти __node). Это создает объект узла.

Теперь ему нужно что-то сделать с одним из членов на _M_valptr(). Линия

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

(косвенно вызовы) аллокатор-х construct method, который очень похож на глобальное размещение new (на самом деле, это, как правило, просто называет его). Таким образом, он снова принимает указатель на место, где будет строиться объект. Это создает объект value.

Answer 3

Он использует что-то под названием «Placement New», что позволяет создавать объект в памяти, которая уже выделена.

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); 

Или вы могли бы написать это следующим образом:

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; 

Или это:

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! 

Основная идея заключается в том, что теперь вы стали ответственны за ручной очистки обычно автоматически обрабатываются язык и компилятор. Который является крайне плохой практикой EXCEPT при работе с распределителями, где прямой контроль над выделениями памяти становится важным для написания хорошего распределителя.