C++ : 표준 대 표준 : : 벡터 :: 목록

Question

의 성능 I 같은 여러 실행을 위해 다양한 N.

void vectorPerf(size_t n) 
{ 
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now(); 
    std::vector<size_t> cache; 
    for (size_t i = 0; i < n; i++) { 
     cache.push_back(i); 
    } 
    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now(); 

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count(); 

    std::cout << duration << " us." << "\n"; 

    return; 
} 

void listPerf(size_t n) 
{ 
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now(); 
    std::list<size_t> cache; 
    for (size_t i = 0; i < n; i++) { 
     cache.push_back(i); 
    } 
    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now(); 

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count(); 

    std::cout << duration << " us." << "\n"; 

    return; 
} 

int main(int argc, char** argv) 
{ 

    if (argc != 2) { 
     return -1; 
    } 
    std::stringstream ss(argv[1]); 
    size_t n; 
    ss >> n; 
    vectorPerf(n); 
    std::cout << "\n"; 
    listPerf(n); 
    std::cout << "\n"; 
} 

에 대한 표준 : : 목록 대 표준 : : 벡터의 성능을 프로필에 다음 코드를

N  std::vector std::list 
1000 46   116 
2000 85   217 
5000 196   575 
10000 420   1215 
100000 3188   10497 
1000000 34489  114330 

내가 궁금하면 표준 : : 목록의 성능을 제공하는 방법이다는 표준 : : 벡터 후 지속적으로 악화 : N의 세트, 나는 결과가 아래의 번호와 같은 순서의 일관성있는 결과를 얻을 수 . std :: vector의 경우, 내부 객체가 std :: vector를 기반으로하고 있기 때문에 성능이 상각 될 것으로 기대했을 것입니다. 내가하는 일은리스트의 끝 부분에 요소를 삽입하는 것이기 때문에 std :: list가 O (1)이 될 것이라고 기대했을 것이다. 그래서 그것은 std :: list가 std :: vector보다 좋을 것이라고 제안하지만 그 반대가 사실로 보입니다.

왜 이런 일이 일어나고 있는지 누군가가 알 수 있다면 고맙겠습니다. 2015 MBP에서 g ++를 사용하여 MacOS 10.12.6에서 컴파일 중입니다.

감사합니다.

편집 : 이제 std :: vector :: push_back()이 O (1)로 상각된다는 것을 이해했습니다. 그러나, 나에게 명확하지 않은 것은 왜 std :: list :: push_back()이 std :: vector :: push_back()보다 일관되게 성능이 떨어지는 것일까 요?

Answer 1

벡터 삽입 끝이 상각 된 O (n)보다는 상각 된 상수 (상각 된 O (1))이며,이 상황에서 벡터 용량은 실제 크기보다 빠르게 커집니다 , 여분의 공간을 할당 한 다음 채워 지므로 모든 push_back에 할당이 필요하지 않습니다.