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

예. Big O의 관점에서 N 요소를 하나씩 삽입하는 것은 O (N * logN)이며, 맵 (일반적으로 일종의 균형 이진 트리)은 O (N) 만 필요합니다.

GCC의 libstdC++ 구현을 참조로 사용할 수도 있습니다.
gcc/libstdc++-v3/include/bits/stl_map.h