unordered_map을 사용할 때의 메모리 할당

Question

std::unordered_map<int,...>이 대략 동일한 크기를 유지하지만 항목을 계속 추가하고 제거하는 경우 지속적으로 메모리를 할당하거나 해제하거나 메모리를 캐시하고 다시 사용합니다 (예 : 풀 또는 벡터). 현대 표준 MS 구현 라이브러리를 가정합니다.

Answer 1

표준은 이러한 측면에 대해 구체적이지 않으므로 구현 정의됩니다. 가장 중요한 점은 사용자가 설명하는 캐싱 동작은 보통 사용자 지정 할당 자 (예 : memory pool allocator)을 사용하여 수행되므로 일반적으로 컨테이너 구현과 분리해야합니다. 정렬되지 않은 용기의 약 the standard, ~p874

관련 비트 : 정렬되지 않은 결합 용기

요소는 버킷으로 구성된다. 동일한 해시 코드가있는 키는 동일한 버킷에 나타납니다. 버킷 수는 요소가 비 순차적 연관 컨테이너에 추가 될 때 자동으로 증가하므로 버킷 당 평균 개의 요소 수가 경계 아래에 유지됩니다.

삽입 :

인서트 및 부재 반복자의 유효성에 영향을 미치지 아니한다 설치하다 경우 (N + N)의 N이 의 원소의 개수 < = Z의 *의 B, 삽입 작업 전에 용기는, N 원소 삽입의 수는, B는 컨테이너의 버킷 카운트이고, Z는 컨테이너 최대 하중 인자

라인 사이를 읽을 수 있고 반복자 유효성이 영향을받지 않기 때문에 아마 메모리 할당이 일어나지 않는다고 가정합니다. 이것이 보장되는 것은 아니지만 (예 : 버킷 데이터 구조가 연결된 목록 인 경우 반복자를 무효화하지 않고 추가 할 수 있음). 표준은 요소가 제거 될 때 일어날 일을 지정하지 않는 것 같지만, 위의 제약 조건을 무효화 할 수 없으므로 메모리를 할당 해제 할 이유가 보이지 않습니다.

특정 구현을 위해 가장 쉬운 방법은 소스를 읽거나 코드를 프로파일 링하는 것입니다. rehash 및 resize 메서드를 사용하고지도의 load_factor를 조정하여이 동작을 제어 할 수 있습니다 (필요한 경우).