我正在寻找一种记住双向链表中位置的方法(在哈希表或其他数据结构中(。
在 C 中，我会在我的结构中添加上一个和下一个指针。然后，我可以将结构元素的引用存储在我想要的任何位置，并在以后引用它们。我只需要维护这些上一个/下一个指针来操作我的链表，并且存储的对列表中位置的引用将保持更新。
解决这个问题C++方法是什么？
最终目标是数据结构(它是有序的，但不是有序的，即不存在比较功能，但它们根据插入的位置相对排序(。随着结构的增长，我需要廉价地插入、删除、移动对象。但我还需要通过一些与排序无关的键廉价地查找每个元素，并且我查找有意义的位置(如头部、尾部和称为切片的结构中的各种检查点(。我需要能够在按键或切片查找起点后遍历序列列表。
头部和尾部将是免费的。我正在计划一个将键映射到列表元素的哈希表，以及另一个将切片映射到列表元素的哈希表。
我在这里问了一个与此相关的更具体的问题：对相同的对象同时使用映射和列表
我得出的结论是，我需要维护一个列表和指向相同数据的各种地图，以获得我需要的性能。但是通过在C++中存储迭代器来做到这一点似乎不太理想。相反，重新实现链表(将其构建到我的类中(并使用 STL 映射指向数据似乎更容易。
我希望得到一些关于哪条更有成效的路线的意见，或者是否有第三种计划可以更好地满足我的需求。我的假设是，unordered_map的 STL 实现比我实现的任何内容都快，但我可以匹配或击败列表的性能，因为我只使用其功能的子集。
谢谢！
更精确地描述我的数据/性能要求：
数据将带有唯一键。我会将其添加到队列中。我需要根据其唯一键在 O(1( 中更新/移动/删除/删除此数据。我需要插入新数据/根据存储在其他数据结构中的元数据读取数据。
当我在上面说非常大的清单时，我说的不准确。该列表肯定会放入内存中。空间足够便宜，值得使用其他数据结构来索引此列表。
我理解您的要求是：
- 数据具有唯一键
- 使用其唯一键在恒定时间内更新/移动/删除/删除此数据
根据这一点，最合适的是unodered_map：它与键一起工作，并使用哈希表来访问元素。 在平均插入中，查找，更新是常量时间(感谢哈希表(，除非哈希函数不合适(即最坏的情况，如果所有元素都产生相同的哈希值，您将拥有线性时间，就像在列表中一样，由于串流(。
这似乎也符合你的初衷：
头部和尾部将是免费的。我正在计划一个映射的哈希表 键以列出元素，以及另一个将切片映射到列表的哈希表 元素。
编辑：如果你还需要掌握元素的排序，独立于它们的键，你需要基于一个list和一个unordered_map构建一个组合容器，该将键与迭代器关联到列表中的元素。 然后，您必须管理同步，例如：
- 插入元素
- ：通过将元素插入
list来获取迭代器，然后使用元素的键将迭代器添加到unordered_map。 - 删除元素：通过在
unordered_map中搜索键来查找元素的迭代器，使用此迭代器擦除list中的元素，最后擦除unordered_map中的键。
查找元素 - ：通过在
unordered_map中搜索键来查找元素的迭代器 - 顺序迭代：使用迭代器到
list的开头。
我会把你路由到STL容器来浏览......但是当你写"非常大"这个词时(我目前是大数据专业人士(，一切都会改变。通常没有人会给你关于可扩展性的好建议，但是......这里有几点。
- 在您的案例中，什么是"非常大"？
std::list符合您的需求吗？在第 3 段之前，如果您不是太大，一切看起来都合适。您的结构适合内存吗？ - 您的结构如何与内存管理器保持一致？简单地说
C带有"prev"和"next"的类似列表具有严重的缺点 - 每个元素通常都是从内存管理器分配的。如果你很大，这很重要，并让你的内存过度使用。 - 您期望元素外部引用是什么？如果你使用指针 - 你就失去了对结构执行优化的能力。但可能你不需要它。
实际上，如果您非常大，您绝对需要考虑一些"池"管理，如果您密集修改结构，此类池中的索引可以成为很好的参考。
请考虑大两次。如果你的意思是真的很大 - 你需要特殊的解决方案。特别是如果您的数据大于内存。如果你不是那么大 - 为什么不从std:list开始呢？当你回答这个问题时，可能你的生活会容易得多;-(。