c++ - 大条目的慢 std::map

Question

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

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

由于条目的数量很大，我担心 std::map 在插入期间会花费很多时间，因为它需要为每次插入做平衡。

仅将这些条目插入 map 会花费大量时间。我在做

map[first] = second;

两个问题: 1. 我在这种情况下使用 std::map 是否正确？ 2.我按上面的方式插入是否正确。或者我应该使用 map.insert()

很抱歉没有做实验并写下绝对数字，但我们希望就我们做的事情是否正确达成普遍共识。

此外，它们的键并不总是连续的..

附言当然，稍后我们还需要访问该映射以获取与键对应的值。

Answer 1

如果你之后不需要插入到 map 中，你可以构造一个未排序的数据 vector ，根据键对其进行排序，然后使用 std::equal_range 等函数进行搜索.
它的复杂度与 std::map 相同，但分配量要少得多。