Блог

Я пытаюсь реализовать std::list (MSVC). И одна вещь, которую я не могу понять:

 template <class _Value_type, class _Voidptr> // voidptr? For what?
struct _List_node { // list node
    using value_type = _Value_type;
    using _Nodeptr   = _Rebind_pointer_t<_Voidptr, _List_node>; // what is the purpose of such rebind?
    ...
}
 

Я понимаю причину повторного привязки распределителя, но указатель? Почему я должен его использовать и где?

UPD: Я понимаю, что такое повторная привязка. Я имею в виду, почему не просто _Nodeptr* ? Зачем мне нужно повторное связывание? (Благодаря Evg)

Ответ на этот вопрос также исходит от распределителей. Давайте посмотрим, как _Rebind_pointer_t определяется:

 template <class _Ptr, class _Ty>
using _Rebind_pointer_t = typename pointer_traits<_Ptr>::template rebind<_Ty>;
 

То есть мы имеем

 template <class _Value_type, class _Voidptr>
struct _List_node {
    using _Nodeptr = typename pointer_traits<_Voidptr>::template rebind<_List_node>;
    // ...
}
 

Теперь давайте посмотрим, как _List_node используется:

 using _Node = _List_node<_Ty, typename _Alty_traits::void_pointer>;
 

По сути, мы повторно привязываем распределитель void_pointer к _List_node указателю. Этот трюк необходим для поддержки распределителей, которые используют необычные указатели внутри.

Один из таких примеров можно найти в Boost .Межпроцессная библиотека. Он имеет boost::interprocess::allocator:

Совместимый с STL распределитель, который использует диспетчер сегментов в качестве источника памяти. Тип внутреннего указателя будет того же типа (raw, smart), typename SegmentManager::void_pointer что и type . Это позволяет размещать распределитель в общей памяти, файлах с отображением памяти и т. Д…

Например, мы можем написать

 namespace bi = boost::interprocess;
using Allocator = bi::allocator<int, bi::managed_shared_memory::segment_manager>;
std::list<int, Allocator> list(/* allocator object */);
 

Теперь std::allocator_traits<decltype(list)::allocator_type>::void_pointer это будет не void* так, как с распределителем по умолчанию, но boost::interprocess::offset_ptr<void, ...> . В результате _Nodeptr не _Nodeptr* будет , но boost::interprocess::offset_ptr<_Nodeptr, ...> .

Пользователь создает экземпляр списка с value_type. помощью, например, для list<int> value_type would be int . Также распределитель списков (который также может быть предоставлен) выделяет память для объектов value_type ‘s.

Но value_type это не то, что содержит список внутри. Список содержит внутренне **Nodes** значение, для которого value_type является членом.

Таким образом, чтобы иметь возможность преобразовывать выделение и указатель из value_type в Node (который содержит value_type и указатель, по крайней мере, на следующий узел), используется повторная привязка.

Напротив, это не было vector<int> бы необходимо для примера. Это потому, что внутреннее представление vector обычно будет содержать внутри указатель на массив объектов value_type, и в данном случае это int . Поэтому здесь не требуется повторная привязка.