c++ - C++ 中的密集索引映射

Question

我很难找到一种容器，也许我使用的命名不正确。

有谁知道像 std::map 这样的 C++ 容器，但关键是整数类型。它具有按索引插入、删除和检索的 O(1) 复杂度。它的迭代器应该遍历由索引（键）映射的元素。它还应该以有序的方式遍历索引。它应该是随机访问并且具有 O(1) 复杂度才能移动到任意位置。

我愿意考虑迭代器是双向的并且它的递增/递减是 O(1) 复杂度的情况。

Answer 1

你在问不可能的事

O(1)按顺序删除、插入、搜索和迭代将O(n)通过推送所有元素来启用排序，然后按顺序迭代。

以整数排序而闻名的最佳算法是O(n * sqrt(loglogn))，所以如果我们有像您描述的那样 - 它会击败最知名的整数排序算法。

---

编辑（根据您对问题的评论）：

如果您可以使用O(1)搜索/查找/插入，但不保证迭代顺序 - 您可以使用unordered_map，它实现了一个哈希表。