索引链表的 C++/STL 结构（Indices in Hash Table）
C++/STL Structure for Indexed Linked List (Indices in Hash Table)
我正在寻找一种方法来记住双向链表中的位置（在哈希 tables 或其他数据结构中）。
在 C 中，我会添加指向我的结构的 prev 和 next 指针。然后，我可以在任何我想要的地方存储对我的结构元素的引用，并在以后引用它们。我只需要维护这些 prev/next 指针来操作我的链表，并且存储的对列表中位置的引用将保持更新。
解决此问题的 C++ 方法是什么？
最终目标是一个数据结构（它是有序的，但不是有序的，即不存在比较函数，但它们是根据插入的位置相对排序的）。随着结构的增长，我需要廉价地插入、删除、移动对象。但我还需要通过一些与排序无关的键廉价地查找每个元素，并且我查找有意义的位置（如头、尾和称为切片的结构中的各种检查点）。我需要能够在按键或切片查找起始位置后遍历序列表。
头部和尾部将自由。我正在计划一个哈希 table 将键映射到列表元素，另一个哈希 table 将切片映射到列表元素。
我在这里问了一个与此相关的更具体的问题：
我得出的结论是，我需要同时维护一个 List 和指向相同数据的各种 Map 以获得我需要的性能。但是通过在 C++ 中存储迭代器来做到这一点似乎不太合适。相反，重新实现链表（将其构建到我的 class 中）并使用 STL 映射指向数据似乎更容易。
我希望就哪条路线更有成效，或者是否有第三种计划更能满足我的需求提供一些意见。我的假设是 unordered_map 的 STL 实现比我要实现的任何东西都快，但我可以匹配或击败列表的性能，因为我只使用了它的功能的一个子集。
谢谢！
更准确地描述我的 data/performance 要求：
数据将带有唯一键。我会将其添加到队列中。
我需要根据其唯一键 update/move/remove/delete 在 O(1) 中对这些数据进行处理。
我需要根据存储在其他数据结构中的元数据插入新的 data/read 数据。
当我在上面说非常大的列表时，我说的不准确。该列表肯定会适合内存。 Space 足够便宜，值得使用其他数据结构来索引此列表。
我会将您转到 STL 容器进行浏览...但是当您写字 'very large'（我目前是大数据专业人士）时，一切都会改变。
通常没有人会为您提供有关可伸缩性的好建议，但是...这里有几点。
- 在你的情况下 'very large' 是什么？
std::list 是否符合您的需求？如果你不是太大，在第 3 段之前一切看起来都很合适。你的结构适合记忆吗？
- 你的结构如何与内存管理器对齐？简单的
C-like 列表 'prev' 和 'next' 有严重的缺点——每个元素通常都是从内存管理器分配的。如果你很大，这很重要，会让你的内存过度使用。
- 您希望元素外部参考是什么？如果你使用指针 - 你失去了对你的结构进行优化的能力。但你可能不需要它。
实际上，如果您的规模很大，您肯定需要考虑一些 'pools' 管理，如果您大量修改结构，此类池中的索引可以作为很好的参考。
请考虑大两次。如果你的意思真的很大 - 你需要特殊的解决方案。特别是如果您的数据大于您的内存。如果您不是那么大 - 为什么不从 std:list 开始呢？当您回答这个问题时，您的生活可能会轻松得多 ;-).
我理解您的要求是：
- 数据有唯一键
- update/move/remove/delete 这个数据在常数时间内，使用它的唯一键
根据这个，最合适的是 unodered_map：它使用一个键，并使用散列 table 来访问元素。在平均插入、查找、更新中，时间是恒定的（感谢散列table），除非散列函数不合适（即最坏情况下，如果所有元素都产生相同的散列值，你将有线性时间，如在列表中，由于冲突）。
这似乎也符合你的初衷：
Head and tail will be free. I was planning a hash table that maps the
keys to list elements, and another hash table that maps slices to list
elements.
编辑： 如果您还需要掌握元素的排序，独立于它们的键，您需要构建一个组合容器，基于 list和一个 unordered_map ，它将迭代器的键与列表中的元素相关联。然后您必须管理同步，例如：
- 插入元素：通过将元素插入
list 来获取迭代器，然后使用元素的键将迭代器添加到 unordered_map。
- 删除元素：通过搜索
unordered_map 中的键找到元素的迭代器，使用此迭代器擦除 list 中的元素，最后擦除 unordered_map 中的键.
- 查找元素：通过搜索
unordered_map 中的键找到元素的迭代器
- 顺序迭代：使用迭代器到
list 的开头。
我正在寻找一种方法来记住双向链表中的位置（在哈希 tables 或其他数据结构中）。
在 C 中，我会添加指向我的结构的 prev 和 next 指针。然后，我可以在任何我想要的地方存储对我的结构元素的引用，并在以后引用它们。我只需要维护这些 prev/next 指针来操作我的链表，并且存储的对列表中位置的引用将保持更新。
解决此问题的 C++ 方法是什么？
最终目标是一个数据结构（它是有序的，但不是有序的，即不存在比较函数，但它们是根据插入的位置相对排序的）。随着结构的增长，我需要廉价地插入、删除、移动对象。但我还需要通过一些与排序无关的键廉价地查找每个元素，并且我查找有意义的位置（如头、尾和称为切片的结构中的各种检查点）。我需要能够在按键或切片查找起始位置后遍历序列表。
头部和尾部将自由。我正在计划一个哈希 table 将键映射到列表元素，另一个哈希 table 将切片映射到列表元素。
我在这里问了一个与此相关的更具体的问题：
我得出的结论是，我需要同时维护一个 List 和指向相同数据的各种 Map 以获得我需要的性能。但是通过在 C++ 中存储迭代器来做到这一点似乎不太合适。相反，重新实现链表（将其构建到我的 class 中）并使用 STL 映射指向数据似乎更容易。
我希望就哪条路线更有成效，或者是否有第三种计划更能满足我的需求提供一些意见。我的假设是 unordered_map 的 STL 实现比我要实现的任何东西都快，但我可以匹配或击败列表的性能，因为我只使用了它的功能的一个子集。
谢谢！
更准确地描述我的 data/performance 要求：
数据将带有唯一键。我会将其添加到队列中。 我需要根据其唯一键 update/move/remove/delete 在 O(1) 中对这些数据进行处理。 我需要根据存储在其他数据结构中的元数据插入新的 data/read 数据。
当我在上面说非常大的列表时，我说的不准确。该列表肯定会适合内存。 Space 足够便宜，值得使用其他数据结构来索引此列表。
我会将您转到 STL 容器进行浏览...但是当您写字 'very large'（我目前是大数据专业人士）时，一切都会改变。
通常没有人会为您提供有关可伸缩性的好建议，但是...这里有几点。
- 在你的情况下 'very large' 是什么？
std::list是否符合您的需求？如果你不是太大，在第 3 段之前一切看起来都很合适。你的结构适合记忆吗？ - 你的结构如何与内存管理器对齐？简单的
C-like 列表 'prev' 和 'next' 有严重的缺点——每个元素通常都是从内存管理器分配的。如果你很大，这很重要，会让你的内存过度使用。 - 您希望元素外部参考是什么？如果你使用指针 - 你失去了对你的结构进行优化的能力。但你可能不需要它。
实际上，如果您的规模很大，您肯定需要考虑一些 'pools' 管理，如果您大量修改结构，此类池中的索引可以作为很好的参考。
请考虑大两次。如果你的意思真的很大 - 你需要特殊的解决方案。特别是如果您的数据大于您的内存。如果您不是那么大 - 为什么不从 std:list 开始呢？当您回答这个问题时，您的生活可能会轻松得多 ;-).
我理解您的要求是：
- 数据有唯一键
- update/move/remove/delete 这个数据在常数时间内，使用它的唯一键
根据这个，最合适的是 unodered_map：它使用一个键，并使用散列 table 来访问元素。在平均插入、查找、更新中，时间是恒定的（感谢散列table），除非散列函数不合适（即最坏情况下，如果所有元素都产生相同的散列值，你将有线性时间，如在列表中，由于冲突）。
这似乎也符合你的初衷：
Head and tail will be free. I was planning a hash table that maps the keys to list elements, and another hash table that maps slices to list elements.
编辑： 如果您还需要掌握元素的排序，独立于它们的键，您需要构建一个组合容器，基于 list和一个 unordered_map ，它将迭代器的键与列表中的元素相关联。然后您必须管理同步，例如：
- 插入元素：通过将元素插入
list来获取迭代器，然后使用元素的键将迭代器添加到unordered_map。 - 删除元素：通过搜索
unordered_map中的键找到元素的迭代器，使用此迭代器擦除list中的元素，最后擦除 unordered_map 中的键. - 查找元素：通过搜索
unordered_map 中的键找到元素的迭代器
- 顺序迭代：使用迭代器到
list的开头。