c++ - 我想我需要一个带键的链表结构。有什么建议么？

Question

我想将数据存储在 map 结构中，因为我需要使用键访问元素。我还将迭代连续的元素，因此 list 结构将是我在这里的最佳选择。我认为我需要一种混合数据结构，以提供两全其美的优势。

所以基本上我希望随机访问具有 O(log(n)) 复杂度，迭代具有 O(c) 复杂度。 cstdlib 或 Qt 是否有任何值得考虑的内置结构？在这种情况下是否有更合适的替代方法？

Answer 1

如果您关心迭代的顺序:

将迭代器从一个元素移动到下一个元素在 list 和 (multi)map 中都是 O(c) 操作，除了 c 稍微小一点list，因此将两者结合起来不太可能获得太多。

您可能最好只使用 map 单独使用。 map 自然地按照键的顺序(在您的情况下是约会开始时间)对其元素进行排序，因此您可以轻松地以相同的顺序进行迭代。查找单个元素的时间复杂度为 O(log(n))。当集合需要可变时，这是合适的。

或者，您可以将元素存储在一个vector 中，然后在需要迭代之前对其进行排序。排序后，您可以通过 binary_search (O(log(n))) 找到单个元素并自然迭代，性能出色(但仍然是 O(c))。排序是昂贵的，所以这仅适用于集合(大部分)不可变的情况。

如果您不关心迭代的顺序:

只需使用 unordered_(multi)map - 通过适当的散列，它往往比 map 更快。​​