std :: unordered_map에 예약 방법이있는 이유는 무엇입니까?

Question

this에 따르면 당신은 std::map을위한 공간을 예약 할 수 없습니다

아니,지도의 회원은 내부적으로 트리 구조로 저장됩니다. 저장할 키와 값 을 알기 전까지는 트리를 작성할 방법이 없습니다. std::map 그것이 cppreference.com에 않는 reserve() 방법을, 부족 왜이에서

은 분명하다. 그러나 std::unordered_map않습니다는 reserve() 방법을 가지고,하지만 난 operator[], insert() 또는 emplace()와 함께 사용하려고 할 때 그들은 모두 reserve() 먼저 호출 한 날에도 불구하고 메모리를 할당로 이동합니다.

이 기능은 무엇입니까? reserve()이 필요한 공간을 적절하게 예약하지 않는 이유는 무엇입니까? 지도와 같이 미리 메모리를 할당 할 수 없다면, std::unordered_map은 왜 처음에는 reserve() 메소드를 가지고 있습니까?

Answer 1

unordered_map 컨테이너는 버킷을 사용하여 구현 되었기 때문에 reserve 메서드가 있으며 map과 같은 트리가 아닙니다.

버킷은 : 상기 용기의 내부 해시 테이블

슬롯이있는 요소가 그 키의 해시 값에 기초하여 할당되는. 버킷은 0부터 (bucket_count-1)까지 번호가 매겨집니다. (source)

단일 버킷에는 가변 개수의 항목이 있습니다. 이 수치는 load_factor을 기준으로합니다. load_factor이 특정 임계 값에 도달하면 컨테이너는 버킷 수를 늘리고지도를 다시 채 웁니다.

reserve(n)으로 전화 할 때 컨테이너는 최소한 n 개의 항목을 담을 수있는 양동이를 만듭니다.

이것은 버킷 수를 n으로 직접 설정하고 전체 해시 테이블을 다시 트리거하는 rehash(n)과는 대조적입니다.

은 참조 : Pre-allocating buckets in a C++ unordered_map

편집을 댓글에 대한 응답으로

나는 코멘트에 제기 된 질문에 대한 정확한 답을 알고하지 않기 때문에 나의 예비 연구가 결실을 증명하지 않았다, 나는 실험적으로 테스트하기로 결정했다.

당신이 n 개의 요소 양동이를 예약하는 n 개의 요소에 대한 메모리를 할당과 같은 경우 설명해 주시겠습니까 : 참고로

는 질문에 귀결? 정확하게 unordered_map에 할당 된 공간의 크기에 따라 검색 this answer

는 까다 롭고 신뢰할.그래서 Visual Studio 2015의 진단 도구를 사용하기로 결정했습니다. 다음과 같이

첫째, 내 테스트 케이스는 다음과 같습니다

#include <unordered_map> 
#include <cstdint> 

struct Foo 
{ 
    Foo() : x(0.0f), y(0.0f), z(0.0f) { } 

    float x; 
    float y; 
    float z; 
}; 

int32_t main(int32_t argc, char** argv) 
{ 
    std::unordered_map<uint32_t, Foo> mapNoReserve; 
    std::unordered_map<uint32_t, Foo> mapReserve; 

    // --> Snapshot A 

    mapReserve.reserve(1000); 

    // --> Snapshot B 

    for(uint32_t i = 0; i < 1000; ++i) 
    { 
     mapNoReserve.insert(std::make_pair(i, Foo())); 
     mapReserve.insert(std::make_pair(i, Foo())); 
    } 

    // -> Snapshot C 

    return 0; 
} 

코멘트가 표시

, 나는 메모리 스냅 샷을했다.

스냅 A : :

┌──────────────┬──────────────┬──────────────┐ 
|  Map  | Size (Bytes) | Bucket Count | 
|--------------|--------------|--------------| 
| mapNoReserve | 64   | 8   | 
| mapReserve | 64   | 8   | 
└──────────────┴──────────────┴──────────────┚ 

스냅 B :

┌──────────────┬──────────────┬──────────────┐ 
|  Map  | Size (Bytes) | Bucket Count | 
|--------------|--------------|--------------| 
| mapNoReserve | 64   | 8   | 
| mapReserve | 8231   | 1024   | 
└──────────────┴──────────────┴──────────────┚ 

스냅 C :

을 다음

결과였다은

┌──────────────┬──────────────┬──────────────┐ 
|  Map  | Size (Bytes) | Bucket Count | 
|--------------|--------------|--------------| 
| mapNoReserve | 24024  | 1024   | 
| mapReserve | 24024  | 1024   | 
└──────────────┴──────────────┴──────────────┚ 

해석 : 스냅 샷에서 볼 수 있듯이

, 우리가 그들에게 요소, reserve라고했다 심지어 하나를 추가하기 시작하면 모두 맵의 크기가 성장하는 것으로 보인다.

그래도 메모리가 할당되어 있어도 reserve에 도움이됩니까? 나는 두 가지 이유로 예라고 말할 것입니다. (1) 버킷을위한 메모리를 미리 할당하고, (2) rehash의 필요성을 방지 할 수 있습니다. 앞에서 설명한대로 맵을 완전히 다시 작성합니다.