Использование распределителя в C++ (дерево STL)

Недавно я пытался понять, как работают распределители 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*.

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


c++ c++11 stl allocator
person gmardau    schedule 17.08.2016    source источник
comment
operator new не выделяет память, он создает объект (а иногда еще и выделяет память, но не в вашем случае). Итак, я бы сказал, что вторая строка (::new(__node) _Rb_tree_node<_Val>;), вероятно, создает узел в __node выделенном блоке памяти.   -  person alexeykuzmin0    schedule 17.08.2016
comment
Хорошо, но зачем передавать оператору указатель __node? Кроме того, если он создает узел, что делает потом ::construct()?   -  person gmardau    schedule 17.08.2016
comment
зачем передавать указатель? Как объясняют ответы, это синтаксис placement new. А как еще он узнает, где поместить объект new?   -  person underscore_d    schedule 17.08.2016
comment
@Mehlins: ключевое слово new при обычном использовании делает две вещи: оно выделяет память, а затем вызывает функцию operator new и передает ей указатель на память, и эта функция использует конструктор для создания объекта в этом месте в памяти.   -  person Mooing Duck    schedule 17.08.2016

Ответы (3)


arrow_upward
8
arrow_downward 

::new(__node) _Rb_tree_node<_Val>;

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

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

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

person Ilya Popov    schedule 17.08.2016
comment
Спасибо. Просто последнее. Почему для _M_valptr() используется распределитель узлов другого типа? - person gmardau; 17.08.2016
comment
@Mehlins, какой тип _M_valptr? - person user2296177; 17.08.2016
comment
Val*. Код: __gnu_cxx::__aligned_membuf<_Val> _M_storage; _Val* _M_valptr() { return _M_storage._M_ptr(); } - person gmardau; 17.08.2016
comment
@Mehlins Как уже объяснила Ами Тавори, в свою очередь вызывает метод construct распределителя, который затем вызывает новое размещение. (эта строка не выделяет никакой памяти, она только создает объект, поэтому она все равно не использует распределитель для выделения чего-либо, и поэтому тип распределителя не имеет значения) - person Ilya Popov; 17.08.2016
comment
Кстати, метод construct в allocator/allocator_traits объявлен устаревшим в C++17. - person Ilya Popov; 17.08.2016
comment
О, хорошо, я вижу. Функция построения на самом деле является шаблоном и использует вывод типа для _M_valptr(). Кроме того, функция construct устарела только для allocator. Судя по тому, что я видел, они пытаются перевести все на allocator_traits, чтобы сделать вещи более общими. Спасибо - person gmardau; 17.08.2016
comment
@Mehlins Да, я остаюсь исправленным, это не устарело в allocator_traits. И идея устаревания заключается в том, что распределитель должен заниматься только выделением памяти, ему не нужно много знать о типе и о том, как его построить. - person Ilya Popov; 17.08.2016

arrow_upward
3
arrow_downward

Линия

::new(__node) _Rb_tree_node<_Val>;

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

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

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

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

person Ami Tavory    schedule 17.08.2016
comment
Итак, я предполагаю, что он использует размещение new, потому что у него нет значения для передачи (требуется в ::construct()), а затем он использует функцию ::construct(), потому что на самом деле у него есть какое-то значение для передачи (скрытое в ...). Есть одна вещь, которую я до сих пор не понимаю. Почему для _M_valptr() используется распределитель узлов другого типа? - person gmardau; 17.08.2016
comment
@Mehlins Это действительно зависит от точной стандартной библиотеки implementation, которую вы используете, но, опять же, это почти положительно просто косвенно называет глобальное размещение новым. Как он узнает, что нужно вызывать соответствующий через распределитель узлов? через упомянутый вами механизм rebind, через шаблоны функций и т. д. Он принципиально не использует распределитель узлов, несмотря на внешний вид. - person Ami Tavory; 17.08.2016

arrow_upward
2
arrow_downward

Он использует что-то под названием "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!

Основная идея заключается в том, что теперь вы несете ответственность за ручную очистку, обычно автоматически выполняемую языком и компилятором. Это очень плохая практика, ЗА ИСКЛЮЧЕНИЕМ при работе с распределителями, когда прямой контроль над выделением памяти становится необходимым для написания хорошего распределителя.

person Xirema    schedule 17.08.2016