slow std :: map for large entries

提问于 2024-04-26T19:50:14+08:00

浏览次

3

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

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

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

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

map[first] = second;

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

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

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

附：当然，稍后我们还需要访问该 Map 以获取与键对应的值 .

2 回答

2

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

回复于 2024-04-26T19:50:14+08:00
7
使用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 （如果矢量不适用） .

@牛米 . 提供代表性的现场演示
回复于 2024-04-26T19:50:14+08:00

相关问题