Наиболее эффективный способ хранения ссылки на контейнерный объект в каждом элементе, хранящемся в списке STL

Question

Скажите, у меня есть эта базовая настройка:

#include <list>

struct Linker
{
 Linker* to;

 //some Linker specific stuff
};

struct Holder
{
 std::list<Linker> links;

 //some Holder specific stuff
 //If I access the "to" variable in a Linker, I want to be able to access the data of the Holder that contains the Linker
};

То есть простые объекты, которые хранятся в списках, которые указывают на другие объекты, в данном случае того же типа. Когда я получаю доступ к to в Линкере и беру другой Линкер, я хочу выяснить, в каком Держателе находится этот Линкер, а также получить доступ к данным этого Линкера.

Я должен указать, после прочтения ответа Уилла, что я не пытаюсь точно смоделировать другой список. В реальной реализации не каждый элемент в списке Холдера будет компоновщиком, и мне все еще нужно получить доступ ко всему через список (с определенной итерацией заказа). Но список справляется с этим, так что все в порядке. Мне нужен определенный уровень спорадических связей между элементами, обычно в разных списках / держателях, в верхней части структуры списка в классе Holder.

Какой лучший способ сделать это? Я рассмотрел вопрос о размещении ссылки или указателя Holder в каждом компоновщике, но, скажем, я хочу отделить структуры, подобные компоновщику, от данных об их контейнере (используя их в других контекстах, где иногда нет контейнера, хочу создать снаружи без контейнера) Затем информация будет иметь Holder с функцией добавления для настройки этой информации и т. д.)

Я рассмотрел использование std :: pair со ссылкой на Holder или указателем в качестве другого типа или расширение Linker на что-то вроде HeldLinker с информацией. Также задумывался об использовании чего-то подобного для более конкретных имен переменных, чем std :: pair:

template<typename R, typename O> struct refwrap
{
 R& ref;
 O obj;

 refwrap(R& ref, const O& obj) : ref(ref), obj(obj) {}
};

Во всех этих случаях Linker* to и std::list<Linker> links будут изменены для использования соответствующего класса (std :: pair, HeldLinker, refwrap и т. Д.). Однако, кажется, что все эти «решения» вызовут такую ​​функцию:

void Holder::addlink(const Linker& link)
{
 //wrap link into whatever will hold a Holder reference/pointer
 //add to links list
}

Чтобы дважды скопировать входящий объект ссылки: при создании объекта-обертки любого типа, а затем еще раз при добавлении этого обертки в объект std :: list. Отсутствие любого из этих методов-оболочек ограничило бы его одной копией. Есть ли способ получить мой торт и съесть его, а также иметь единственную необходимую копию для добавления, а также позволить Holder обернуть объекты Linker, чтобы их ссылки также содержали объект Holder, в котором они находятся? Или есть какая-то лучшая схема «адресации», которую я мог бы использовать для компоновщика, которая не соответствует этой парадигме, выполняя то же самое?

Предпочтительно, это было бы что-то легко расширяемое, поэтому, если бы я добавил это:

struct HolderHolder
{
 std::list<Holder> holders;
};

И это установило такое же отношение, как у Линкера к Холдеру, это можно было сделать, не получая по-настоящему сумасшедших имен типов. И для HolderHolderHolder и т. Д.

Answer 1

Вы хотите наиболее эффективный способ сохранить ссылку на объект в объекте?

Наиболее эффективным способом является указатель.Вероятно, это 4 или 8 байтов, и, вероятно, не влияет на выравнивание следующего элемента в структуре, поэтому это нормально.

Вы можете сохранить байты, имея числа, которые ищут объекты-владельцы, но этоскорее всего, на самом деле не сохраняются реальные байты в распределении структуры, просто вводится заполнение.

Установка указателя требует записи в память.Возможно, место назначения находится рядом с другими записями, которые вы делаете во время инициализации;вряд ли это повлияет на производительность даже в узком цикле.

Альтернативой использованию stl::list является помещение самих узлов списка в структуру данных.

Это часто встречается в высокопроизводительныхокружение, например, ядра.Вот описание ядра Linux .

Поместив следующий (и, возможно, предыдущий) указатель (или XORing их для экономии места) внутри структуры, неттребуется отдельное выделение памяти.

Это означает, что объект в списке может быть только в одном списке за раз, но ваше поле to означает, что это так или иначе, так что это не ограничивает вас.

У вас может быть соглашение, что голова на самом деле является владельцем объекта;очевидно, что для обнаружения требуется O (n), но, возможно, вам нужно открывать to только изредка?

Итак, подведем итог:

• вы можете сэкономить память, не имея stl::list вообще, а просто просто next (и prev, или, возможно, XOR их) в самом узле
• вы можете использовать это пространство, которое вы сохраните, чтобы явно добавить поле to
• или у вас может быть соглашение, где глава списка фактически является владельцем