有序地插入到stl :: map更快？

由于stl::map是一个有序映射，插入一个有序数据集会更快吗？特别是如果我们考虑一个大型数据集？有序地插入到stl :: map更快？

2016-09-28 Sampath

为什么不试试看？ – NathanOliver

我认为这取决于具体的实施。 'map'通常使用某种树形结构 - 红黑树或AVL树或其他类型。插入已排序的序列仍然会每隔一段时间都会触发重新平衡，这是影响插入性能的唯一因素。也就是说，可能会有一些魔法序列不会触发重新平衡或不经常触发它们。未必排序的序列。 –

@WhiZTiM：表现的第二条法则，“永远不要依赖在一台机器上测量的结果”。 –

当然，排序的数据。

#include <map> 
#include <vector> 

int main() { 
    std::vector<int> data { 0, 1, 2, 3, 4, 5 }; 
    std::map<int, int> result; 
    // From: http://en.cppreference.com/w/cpp/container/map/insert 
    // Amortized constant if the insertion happens in the position just before 
    // the hint, logarithmic in the size of the container otherwise. 
    for(auto i : data) 
     result.insert(result.end(), { i, i}); 
}

来源

2016-09-28 15:54:35

是的，的确如此。从大O的角度看，逐个插入N个元素为O（N * logN），相比之下，构建映射（通常是某种平衡二叉树）只需要O（N）。

您也可以将GCC的libstdC++实现作为参考。
gcc/libstdc++-v3/include/bits/stl_map.h

来源

2016-09-29 13:03:14

有序地插入到stl :: map更快？

回答

相关问题