问题标签 [intrusive-containers]

我的目标是进行字符串实习。为此，我正在寻找一个可以执行以下操作的散列容器类：

• 每个节点只分配一块内存
• 每个节点不同的用户数据大小

值类型如下所示：

每个 String 对象都有不同的大小。这将通过 operator new + Placement new 来完成。所以基本上我想自己分配Node，稍后再推入容器中。

以下容器不适合：

• std::unordored_set

• boost::multi_index::*

  无法分配不同大小的节点

• boost::intrusive::unordered_set

  一开始似乎有效。但有一些缺点。首先，您必须自己分配存储桶数组并维护负载因子。这只是不必要且容易出错。

  但另一个问题更难解决：您只能搜索具有 String 类型的对象。但是每次查找条目时分配一个字符串效率低下，并且您只有一个 std::string 作为输入。

是否有任何其他散列容器可用于此任务？

boost::intrusive 文档描述了如何将智能指针与侵入式容器一起使用，但随后说您不能使用最有可能使用的智能指针，“它必须具有与原始指针相同的所有权语义。这意味着不能使用资源管理智能指针（如 boost::shared_ptr）。”

为什么是这样？我想不出任何明显的理由应该禁止它们。究竟会破坏什么？侵入式容器无论如何都不管理它们内部项目的分配。就我而言，我想使用 intrusive_ptr，但我看不出为什么 shared_ptr 也不应该工作。

编辑：要清楚，我的意思是钩子指针（例如，侵入式单链表中的下一个指针）是一个智能指针。

我正在尝试保留特定（基）类实例的全局列表，以便我可以随时通过遍历此全局列表来跟踪它们。

我相信解决这个问题的最合适的方法是使用侵入性列表。例如，我听说可以通过深入研究 Linux 内核来遇到这些生物。

在我所处的情况下，我真的不需要这样的性能保证，并且使用侵入式列表会使我的事情变得有些复杂。

到目前为止，这是我实现这个知道所有实例的类的概念的内容。

问题是没有forward_list::erase()，而且看起来确实不像保存globallist.before_begin()在 ctor 中对我有多大好处。我永远不应该取消引用before_begin()的迭代器。它真的会保住这个位置吗？如果我保存了before_begin的迭代器，然后保存了push_front()一个新项目，那么该迭代器可能仍然无法取消引用，但它可以用于发送到erase_after()吗？

例如，从多个映射中引用一个元素，例如映射名称到元素、映射地址到元素以及映射年龄到元素。现在，例如通过名称查找元素，现在希望从所有三个地图中删除它？

想到了几个解决方案：

1) 最直接的。在名称中查找元素到元素映射，然后搜索其他两个映射以找到其中的元素，然后删除所有三个中的元素条目。

2）在所有三个映射中存储弱指针。将共享指针存储在某处，最多甚至可以存储在元素本身中。在一张地图中找到元素后，删除该元素。当尝试从其他映射访问元素并意识到弱指针无法转换为共享指针时，请删除该条目。

3) 使用侵入式地图。这样做的好处是不需要搜索剩余的地图来找到其中的元素。但是，由于对象存储在多个映射中，因此不能使元素本身具有侵入性——相反，该元素可能需要有一个实现挂钩的成员。

4) 其他？

有没有一个非常干净的好解决方案？这个问题我碰到过好几次了...

一些想法。解决方案 1 通常会随着项目的发展而自然实施。如果元素本身有其他地图的关键信息，而其他容器都是地图，这大概是可以接受的。但是，如果缺少键，或者容器是例如列表，它可能会变得非常慢。解决方案 2 取决于弱指针的实现，并且最终也可能非常慢。解决方案 3 似乎最好，但可能有点复杂？

我只是在 Windows 7 故障转储上进行一些调试，并且遇到了一个我无法完全理解的单链表。

这是 WinDBG 的输出：

从我一直在阅读的内容来看，似乎每个单链表都以列表头开头，其中包含指向列表中第一个元素的指针，如果列表为空，则为 null。

微软状态：MSDN文章

对于用作列表条目的 SINGLE_LIST_ENTRY，Next 成员指向列表中的下一个条目，如果列表中没有下一个条目，则为 NULL。对于用作列表头的 SINGLE_LIST_ENTRY，Next 成员指向列表中的第一个条目，如果列表为空，则为 NULL。

我 99% 确定这个列表包含一些条目，但我不明白 的值0x0000000000220001应该如何指向任何东西。这个值当然不能解析为有效的页面映射，所以我只能假设它是某种偏移量。但是，我不确定。

如果有人可以帮助对此有所了解，我将不胜感激。

谢谢

更新

我刚刚找到了一份文件（从中文翻译过来），似乎对结构进行了更多解释。如果有人可以提供一些意见，我将不胜感激。

后备列表文章

我实际上正在查看的是 Windows 应该用于分配 IRP 的后备列表，这是 WinDBG 的完整输出（值从原始问题更改）：

抱歉，如果某些格式丢失。本质上，这应该是一个后备列表，其中包含所有相同大小的块列表0x118 (sizeof(_IRP) + sizeof(_IO_STACK_LOCATION))

但是我不完全确定列表实际上是如何组合在一起的，我不确定这是否应该是内存块的单链接列表，或者我是否错误地阅读了所有内容。

我目前正试图围绕一些 Windows 后备列表进行思考，并且我看到一些让我感到困惑的内存地址。

由于sergmat（原始问题），从我发布的另一个问题中生成了一些代码：

从上面的 WinDBG 输出中可以看出，在地址 0x82d5ffc0 处有一个单链表。此输出是在 32 位 Windows 7 系统上生成的。

但是，这就是我感到困惑的地方，在 Windows 7 64 位系统上执行相同的操作时，这是输出（地址明显不同）：

看起来 的Next值0x0000000001bf0003不是有效的虚拟地址，我还尝试对其执行虚拟到物理的转换，但失败了。

看起来这个值是页面的某种偏移量，但我不完全确定应该如何计算地址。

列表标题中还有其他数据，这是一个_SLIST_HEADER结构，位于_SINGLE_LIST_ENTRY. 它包含以下数据：

在初始标头之后是一系列三个联合，并且由于这是一个 64 位系统，我认为Header16应该使用联合，其中包含以下内容：

该Header16.NextEntry元素确实包含一个有效的虚拟地址，所以我不确定这是否是下一个列表元素的实际值，或者其他什么。

因此，如果有人可以帮助澄清如何_SINGLE_LIST_ENTRY.Next在 64 位系统上计算元素，我将不胜感激。

谢谢

我有一个声明为class MyClass : public list_base_hook<link_mode<normal_link>>. 我还有一个声明为list<MyClass> global_list_MyClass.

global_list_MyClass我使用 for 循环插入 10 个节点。我的目标是尝试交换Node1和Node2使用boost::intrusive::swap，但似乎失败了（很多编译错误）。

我试图在互联网上搜索，但找不到任何好的例子。

示例代码：

我需要一个侵入性的、排序的、双链表。我不想使用 boost::intrusive，所以我自己这样做并遇到问题

对于双向链表，有几个操作，这里只是其中一个有助于说明我的观点：

现在假设我有一组对象在一个这样的列表中，但我希望他们的胆量是私有的：

现在我创建了我的列表（请忽略当列表为空时会出现 nullptr 异常的事实......）。

这不会编译，因为 prev_ 和 next_ 是私有的并且 insertAfter 没有访问权限。可以通过以下方式轻松解决：

但这打开了一个访问漏洞，任何人都可以使用 insertAfter 来影响 Object 的私有成员。我真正想要的是让 List 成为 Object 的朋友。我可以通过不将模板用于我的链表操作（使用普通宏）来解决这个问题，但这显然有其缺点。去这里的正确方法是什么？

我正在编写一个侵入式数据结构，并且想知道是使用基本挂钩还是成员挂钩。由于代码将被多次调用，我的问题是关于性能以及编译器能够在多大程度上内联此类代码。

基本钩子基于继承，而成员钩子通过模板参数使用指向成员的指针。我的设计选择是使用成员钩子，但我的经验表明，指针比静态代码更难优化。另一方面，所有这些指针在编译时都是已知的，也许编译器可以做一些魔术来分析正在发生的事情。

有没有人有这方面的经验？欢迎任何数据、提示或参考。

我正在开发一个 C 项目，该项目定义了一个hash.h标头，其中包含一个侵入式哈希结构及其接口，以及一个list.h包含侵入式列表及其接口的标头。

散列是使用列表实现的，并且没有其他数据结构可用于支持散列的实现，因此在这种情况下抽象不是很有价值。

所以撇开抽象不谈，使用侵入式哈希而不是侵入式列表有什么好处吗？