c++ - 在 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 以及访问该链接器的数据。

在阅读 Will 的回答后，我应该明确指出，我并不是要准确地模拟另一个列表。在实际实现中，并非 Holder 列表中的每个项目都是链接器，我仍然需要通过列表访问所有内容(使用特定于顺序的迭代)。但是列表处理了这个，所以没关系。我需要在 Holder 类的列表结构之上，在通常位于不同列表/Holder 中的项目之间进行一定程度的零星链接。

执行此操作的最佳方法是什么？我考虑过在每个链接器中放置一个 Holder 引用或指针，但假设我想将链接器之类的结构与其容器的数据分开(在有时没有容器的其他上下文中使用它们，想要在没有容器的情况下构建外部info 然后让 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;
};

并且它设置了与 Linker 到 Holder 类似的关系，它可以在没有真正疯狂的类型名称的情况下完成。以及对于 HolderHolderHolder 等

Answer 1

您想要以最有效的方式在对象中存储对对象的引用？

最有效的方法是指针。它可能是 4 或 8 个字节，并且可能不会影响结构中下一项的对齐，因此没问题。

您可以通过查找所有者对象的数字来节省字节，但这实际上可能不会在结构分配中节省实际字节，它只是引入了填充。

设置一个指针需要一个内存字写入。目的地可能与您在初始化期间正在进行的其他写入相邻；即使在紧密循环中，它也不太可能影响性能。

使用 STL::list 的替代方法是将列表节点本身放入数据结构中。

这在高性能环境中很常见，例如内核。这是对 the Linux kernel one 的描述.

通过将下一个(也可能是上一个)指针(或 XORing them 以节省空间)放在结构中，不需要单独的内存分配。

这意味着列表中的一个对象一次只能在一个列表中，但是您的 to 字段无论如何都意味着这个，所以这不会限制您。

您可以约定头部实际上是拥有对象；这显然需要 O(n) 才能发现，但也许您只需要偶尔发现 to？

总结一下:

• 您可以通过根本不使用 STL::list 来节省内存，而只使用 next(和 prev，或者也许XOR 它们)在节点本身
• 你可以使用你节省的这个空间来显式地添加一个to字段
• 或者你可以有一个约定，其中列表的头部实际上是所有者