大量条目时std::map运行缓慢

Question

我们有48,16,703个此格式的条目。

1 abc
2 def
...
...
4816702 blah
4816703 blah_blah

由于输入的条目数量很大，我担心std::map在插入时需要进行平衡操作，因此会花费很长时间。

仅将这些条目插入到映射中就需要很长时间。我正在进行...

map[first] = second;

两个问题： 1. 我是否正确地使用std::map来处理这些情况？ 2. 我是否正确地像上面那样插入？还是应该使用map.insert()？

很抱歉我没有做实验并写出绝对数字，但我们想要一个普遍的共识，我们是否在做正确的事情。

另外，键不总是连续的。

P.S. 当然，后来我们也需要访问该映射以获取与键对应的值。

- Rahul Bhargava

---

如果这些键只是一系列连续的整数，您可以使用数组或向量。 - Tharwen

@Tharwen，感谢您的快速回答，但它们不是连续的。这是不好的部分。已编辑问题。 - Rahul Bhargava

而且，如果不是这样的话，std::unordered_map 应该更合适，因为它的插入平均时间复杂度是常数。 - Daniel Langr

即便数字不是连续的，但如果有很多条目，例如超过最大索引的一半，并且您更关心速度而不是尺寸，则使用具有O(1)插入和检索的数组或向量仍然可能更有意义。 - Rotem

如果您的键序列已经排序，请尝试使用 map.insert(map.end(), {first, second})。演示。即使它们大多数是连续的，这也是一个胜利。 - n. m.

Answer 1

如果之后不需要插入到地图中，您可以构建一个未排序的向量来存储数据，按键排序，然后使用像 std::equal_range 这样的函数进行搜索。
这与 std::map 的复杂度相同，但分配的内存要少得多。

- Daniel

Answer 2

使用一个 std::unordered_map，它的插入时间复杂度比std::map更好，正如参考中所提到的：

Complexity

Single element insertions:
    Average case: constant.
    Worst case: linear in container size.

Multiple elements insertion:
    Average case: linear in the number of elements inserted.
    Worst case: N*(size+1): number of elements inserted times the container size plus one.

May trigger a rehash (not included in the complexity above).

这比 std::map 的插入的对数时间复杂度要好。

注意：std::map 的插入如果给出提示并且给出的位置是最佳的，可以享受“摊销常量”。 如果您的情况是这样的话，则使用 map（如果不适用于 vector）。

@n.m. 提供了一个代表性的演示

- gsamaras

---

除非他们一直重复不停。 - Matthieu Brucher

另一个值得考虑的优点可能是更低的内存开销。例如，在libstdc++中，std::map被实现为红黑树。每个存储的元素有32字节的内存开销（64位架构-左/右/父节点指针和颜色标志）。对于哈希表，可能只使用一个或两个指针。 - Daniel Langr

是的，Matthieu，这就是为什么OP应该进行基准测试的原因，因为对于他的应用程序来说，这可能是一个问题，但我认为不会。@DanielLangr确实如此，尽管我找不到任何支持（https://dev59.com/MF0Z5IYBdhLWcg3wvSd2）的证据，这就是为什么我没有在我的答案中包含它的原因。 - gsamaras

@gsamaras 当然，这是实现定义的。任何人都可以探索libstdc++、libc++或Microsoft的实现源代码以了解更多细节。 - Daniel Langr

@n.m. 我也在想这个问题...更新了我的答案，谢谢！我借用了你的演示，希望你不介意。 :) - gsamaras