Указатель на объект или сам объект, который создается в выделенной памяти узлов?
В Boost.Intrusive, тип элемента контейнера это узел. Чтобы сделать его совместимым с контейнером, необходимо изменить тип элемента так, чтобы он включал элементы данных, требуемые контейнером, - либо путем наследования от базового класса (например, list_base_hook, см. здесь ) или добавив специальный элемент данных (например, list_member_hook). Вот почему они называются навязчивыми контейнерами. Для сравнения, стандартные контейнеры не требуют, чтобы вы изменяли ваши классы и вместо этого помещали их в узлы контейнера, если это необходимо.
Когда узел в списке std :: list содержит объект и навязчивый контейнер удерживает узел в своем объекте, как это приводит к лучшей локализации?
В std::list каждый контейнерный узел (который содержит ваш элемент) выделяется отдельно, в своем собственном динамическом c выделении памяти , Узел содержит указатели на предыдущий и следующий элементы в списке. Поскольку каждый узел выделяется отдельно, их месторасположение зависит от используемого распределителя памяти, но, как правило, можно предположить, что разные узлы расположены в произвольных местах в памяти, возможно, далеко и не по порядку. Кроме того, обход списка требует разыменования указателя на следующий элемент на каждой итерации, что обычно затрудняет алгоритмы кэширования памяти в ЦП.
В boost::intrusive::list контейнер не налагает какую-либо стратегию выделения памяти для пользователь. Можно иметь одну область памяти для нескольких или всех элементов контейнера для навязывания, что делает их более плотно упакованными и, возможно, упорядоченными в памяти. Это требует больше работы от пользователя, конечно. Итерация списка все еще требует разыменования указателя и вредит предварительному извлечению в ЦП, но если элементы контейнера тесно упакованы, велика вероятность того, что каждый следующий узел будет находиться в строке кэша, которая уже была извлечена из памяти для предыдущего элемента (элементов).
Еще одна вещь, которую стоит отметить, это то, что навязчивые контейнеры гораздо полезнее, когда вам нужно хранить элемент в нескольких контейнерах одновременно. В стандартных контейнерах вы должны использовать указатели для ссылки на элемент из каждого контейнера. Например:
// Element type
class Foo {};
std::list< std::shared_ptr< Foo > > list;
std::map< int, std::shared_ptr< Foo > > map;
В этом примере у вас есть как минимум одно выделение для объекта Foo, одно выделение для узла list и одно выделение для узла map. Каждое из этих распределений произвольно расположено в памяти. Доступ к элементу через list или через map требует дополнительного уровня косвенности.
С помощью интрузивных контейнеров вы можете уменьшить это до одного выделения без дополнительной косвенности:
// List hook
typedef boost::intrusive::list_base_hook<> FooListHook;
// Map/set hook
typedef boost::intrusive::set_base_hook<
boost::intrusive::optimize_size< true >
> FooSetHook;
// Node type
class Foo :
public FooListHook,
public FooSetHook
{
...
};
boost::intrusive::list< Foo, boost::intrusive::base_hook< FooListHook > > list;
boost::intrusive::set< Foo, boost::intrusive::base_hook< FooSetHook >, ... > set;
В этом случае ни list, ни set не занимаются выделением памяти самостоятельно, все необходимые данные уже находятся в узле Foo, который вы выделяете сами. Итерация через любой из контейнеров автоматически извлекает оба хука и содержимое Foo (по крайней мере, частично) в кеш, что ускоряет доступ к памяти. У этого подхода есть и другие преимущества, такие как возможность переключения между итераторами двух контейнеров без дорогостоящего поиска элементов.