索引链表的C++/STL结构( Hash表中的索引)

Question

我正在寻找一种方法来记住双链接列表中的位置(在哈希表或其他数据结构中)。

在C中，我会将prev和下一个指针添加到结构中。然后，我可以将对结构元素的引用存储在任何我想要的地方，并在以后引用它们。我只需要维护这些prev/next指针来操作我的链接列表，并且存储对列表中位置的引用将保持更新。

C++解决这个问题的方法是什么？

最终目标是数据结构(数据结构是有顺序的，但没有排序，即不存在比较函数，但根据插入的位置对它们进行了相对排序)。随着结构的增长，我需要廉价地插入、删除、移动对象。但是，我还需要通过一些与排序无关的键来查找每个元素，并查找有意义的位置(如头、尾和结构中称为片的各种检查点)。我需要能够遍历顺序列表后，查找一个起点按键或切片。

头尾都是免费的。我计划创建一个哈希表，将键映射到list元素，另一个哈希表将切片映射到list元素。

我在这里问了一个更具体的问题：Using Both Map and List for Same Objects

我得出的结论是，为了获得所需的性能，我需要同时维护一个列表和指向相同数据的各种地图。但是，通过在C++中存储迭代器来实现这一点似乎不太理想。相反，重新实现链接列表(将其构建到我的类中)并使用STL映射指向数据似乎更容易。

我希望能就哪一条路线更有成效，或者是否有更好的第三个方案更好地满足我的需要提供一些意见。我的假设是，unordered_map的STL实现比我实现的任何东西都要快，但是我可以匹配或超过list的性能，因为我只使用它的一个功能子集。

谢谢!

更精确地描述我的数据/性能要求：

数据将以唯一的键输入。我会把它加到队列里。我需要根据O(1)的唯一键更新/移动/删除/删除该数据。我需要根据存储在其他数据结构中的元数据插入新的数据/读取数据。

当我在上面说了一个很大的清单时，我说话不准确。这个列表肯定会被记在记忆里。空间足够便宜，因此值得使用其他数据结构来索引此列表。

Answer 1

我理解你的要求是：

• 数据有一个唯一的键。
• 使用唯一的键，在恒定时间内更新/移动/删除/删除该数据

根据这一点，最合适的方法是unodered_map：它使用一个键，并使用哈希表来访问元素。一般来说，insert、find、update是常数时间(多亏了哈希表)，除非哈希函数不合适(即，最坏的情况是，如果所有元素都会产生相同的哈希值，则会有线性时间，就像列表中的那样，由于合并)。

这似乎也符合你最初的意图：

头尾都是免费的。我计划创建一个哈希表，将键映射到list元素，另一个哈希表将切片映射到list元素。

编辑：--如果您还需要掌握元素的排序，独立于它们的键，则需要构建一个组合容器，它基于list和unordered_map，后者将密钥与迭代器关联到列表中的元素。然后，您必须管理同步，例如：

• insert元素:通过将元素插入到list中获得迭代器，然后使用元素的键将迭代器添加到unordered_map中。
• 删除元素:通过搜索unordered_map中的键查找迭代器到元素，使用该迭代器查找list中的擦除元素，最后删除unordered_map中的键。
• 查找元素:通过搜索unordered_map中的键查找迭代器到元素
• 顺序迭代:使用迭代器开始list。

Answer 2

我会把你路由到STL容器浏览.但是当你写单词“非常大”(我现在是大数据专业人士)时，一切都变了。通常没有人给你关于扩展性的好建议，但是..。以下是要点。

1. 在你的情况下什么是“非常大的”？std::list符合你的需要吗？在第三段之前，如果你不是太大的话，一切看起来都是合适的。你的结构适合记忆吗？
2. 您的结构与内存管理器对齐如何？简单地说，带有'prev‘和'next’的C-like列表具有严重的缺点--每个元素通常都是从内存管理器分配的。如果你是大的，这很重要，并使你的内存过度使用。
3. 您期望元素外部引用是什么？如果您使用指针-您松散的能力来执行优化您的结构。但也许你不需要它。

实际上，如果您真的很大，那么您肯定需要考虑一些“池”管理，如果您密集地修改您的结构，这些池中的索引可能是相当好的参考。

请考虑两次大的问题。如果你的意思是真的很大-你需要特殊的解决方案。尤其是当你的数据比你的内存大的时候。如果你不是那么大，为什么不从std:list开始呢？当你回答这个问题时，你的生活可能会轻松得多;-)