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

Question

由於stl::map是一個有序映射，插入一個有序數據集會更快嗎？特別是如果我們考慮一個大型數據集？

Answer 1

當然，排序的數據。

#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}); 
} 

Answer 2

是的，的確如此。從大O的角度看，逐個插入N個元素爲O（N * logN），相比之下，構建映射（通常是某種平衡二叉樹）只需要O（N）。

您也可以將GCC的libstdC++實現作爲參考。
gcc/libstdc++-v3/include/bits/stl_map.h