주간 팁 #136: Unordered Containers
2017년 6월 23일 처음 게시된 TotW #136을 업데이트한 내용입니다.
작성자: Matt Kulukundis
업데이트: 2020-04-06
빠른 링크: abseil.io/tips/136
“때로는 정말 좋은 자료를 접했을 때, 그걸 최고의 쇼로 만들고자 스스로에게 기대를 걸게 됩니다. 그냥 평범한 일만 하고 집에 가는 것과는 다르죠.”
– 피터 딩클리지
요약
공식 및 최신 권장사항은 abseil.io/docs/cpp/guides/container를 참조하세요. 이 팁은 새로운 컨테이너 유형을 소개한 것이며, 표준 참조 자료는 아닙니다.
absl::*_hash_map 소개
새로운 연관 컨테이너 계열이 등장했습니다. 이 컨테이너들은 효율성을 향상시키고, C++17의 API를 미리 사용할 수 있게 해줍니다. 또한, 구현 및 기본 해시 함수에 대한 직접적인 제어를 제공하여 코드베이스의 장기적인 진화를 지원합니다. 새로운 코드는 std::unordered_map 대신 이러한 유형을 사용하는 것이 좋습니다. 이 컨테이너들의 API는 std::unordered_map과 거의 동일하므로 전환이 간단합니다.
absl::*_hash_map이 있다면, 항상 그에 대응하는 absl::*_hash_set도 있습니다. 하지만 아래의 다이어그램은 map을 기준으로 설명하며, 주로 map만 언급합니다.
absl::flat_hash_map 및 absl::flat_hash_set
기본적으로 이 컨테이너를 사용하세요. 이 컨테이너는 value_type을 메인 배열 내부에 저장합니다. 데이터가 리해시(rehash)될 때 데이터를 이동시키기 때문에 요소의 포인터 안정성이 보장되지 않습니다. 포인터 안정성이 필요하거나 값이 크다면, 대신 absl::node_hash_map 또는 absl::flat_hash_map<Key, std::unique_ptr<Value>>를 사용하는 것이 좋습니다.
주의: 리해시(rehash()) 후 포인터가 무효화되기 때문에 map["a"] = map["b"]와 같은 코드는 무효화된 메모리에 접근하게 됩니다.
absl::node_hash_map 및 absl::node_hash_set
이 컨테이너는 value_type을 메인 배열 외부의 노드에 할당합니다(예: std::unordered_map). 별도의 할당 덕분에 저장된 데이터의 포인터 안정성을 제공합니다(객체의 주소가 변경되지 않음). 빈 슬롯은 8바이트만 차지합니다. 또한, 이동 가능하지도 복사 가능하지도 않은 데이터를 저장할 수 있습니다.
일반적으로 absl::node_hash_map<K, V> 대신 absl::flat_hash_map<K, std::unique_ptr<V>>를 사용하는 것이 권장됩니다. node_hash_set의 경우도 마찬가지입니다.