slow std :: map for large entries

loading...


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 以获取与键对应的值 .

loading...

2回答

  • 2

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


  • 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 (如果矢量不适用) .

    @牛米 . 提供代表性的现场演示

评论

暂时没有评论!