slow std :: map for large entries

Question

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

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

由于条目数量非常大,我担心std :: map在插入过程中会花费很多时间,因为它需要为每次插入进行平衡.

只将这些条目插入地图需要花费大量时间.我在做

map[first] = second;

两个问题:1.我是否正确使用std :: map来处理这类案件？我是否正确插入如上所述.或者我应该使用map.insert()

我很抱歉没有做实验并写出绝对数字,但如果我们做的是正确的话,我们希望得到普遍的共识.

此外,他们的钥匙不是连续的..

PS当然,稍后我们还需要访问该地图以获取与键对应的值.

Answer 1

如果之后不需要插入地图,可以构造数据的未排序向量,根据键对其进行排序,然后使用类似函数进行搜索std::equal_range.
它具有相同的复杂性std::map,但分配要少得多.

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的插入可以享受“如果给出提示并且给出的位置是最优的则摊销常数”。如果您属于这种情况，请使用地图（如果矢量不适用）。

@nm 提供代表Live demo