주간 팁 #144: 연관 컨테이너에서의 이종 조회(Heterogeneous Lookup)
2018년 3월 23일 처음 게시된 TotW #144을 업데이트한 내용입니다.
작성자: Samuel Benzaquen
업데이트: 2020-04-06
빠른 링크: abseil.io/tips/144
소개
연관 컨테이너는 요소를 키와 연결합니다. 컨테이너에 요소를 삽입하거나 조회하려면 동등한 키가 필요합니다. 일반적으로 컨테이너는 특정 타입의 키를 요구하며, 이는 거의 동등한 타입 간(예: std::string과 absl::string_view) 변환 작업을 필요로 해 비효율을 초래할 수 있습니다.
이러한 불필요한 작업을 방지하기 위해, 일부 컨테이너는 이종 조회(Heterogeneous Lookup) 기능을 제공합니다. 이 기능을 통해 호출자가 키 타입에 상관없이 키를 전달할 수 있으며, 사용자 정의 비교자(functor)가 이를 지원하면 됩니다. STL 컨테이너에서 이 기능의 예로 std::map::find를 참조하세요.
투명 비교자(Transparent Functors)
투명 비교자는 특정 타입 하나에 국한되지 않고 여러 타입을 허용하는 비교자입니다. 이 비교자는 is_transparent이라는 내부 타입을 정의하여 이를 명시적으로 알립니다. 이 내부 타입의 구체적인 정의는 중요하지 않으며, 단지 태그로 사용됩니다. 일반적으로 is_transparent를 void로 선언합니다.
컨테이너가 투명 비교자를 감지하면, 조회 함수는 사용자 지정 값을 key_type으로 변환하지 않고 그대로 전달합니다(암시적 또는 명시적 변환 없이).
그러나 이종 조회를 암묵적으로 지원하는 것은 위험할 수 있습니다. 변환 후 값 간의 관계가 유지되지 않을 수 있기 때문입니다. 예를 들어, 1.0 < 1.1이 참이지만, static_cast<int>(1.0) == static_cast<int>(1.1)이 될 수 있습니다. 따라서 std::set<int>에서 double을 사용해 값을 조회하면 잘못된 결과를 초래할 수 있습니다. 이러한 잠재적 버그 때문에 이 기능은 명시적으로 활성화(opt-in)해야 합니다.
성능을 위한 이종 조회
이종 조회를 사용하는 일반적인 이유 중 하나는 성능 개선입니다. key_type을 생성하려면 비효율적인 작업이 필요할 수 있기 때문입니다. 예를 들어:
std::map<std::string, int> m = ...;
absl::string_view some_key = ...;
// 쿼리를 위해 임시 `std::string`을 생성합니다.
// 이 경우 할당 + 복사 + 해제 비용이 find() 호출 시간의 대부분을 차지할 수 있습니다.
auto it = m.find(std::string(some_key));
대신 투명 비교자를 사용하면 다음과 같습니다:
struct StringCmp {
using is_transparent = void;
bool operator()(absl::string_view a, absl::string_view b) const {
return a < b;
}
};
std::map<std::string, int, StringCmp> m = ...;
absl::string_view some_key = ...;
// `StringCmp`는 `absl::string_view`로 암시적으로 변환 가능한 모든 타입을 허용하며,
// `is_transparent` 태그를 선언함으로써 이를 알립니다.
// 이제 `some_key`를 `std::string`으로 변환하지 않고 `find()`에 전달할 수 있습니다.
// 이 경우 `std::string` 인스턴스를 생성하기 위한 불필요한 메모리 할당을 피할 수 있습니다.
auto it = m.find(some_key);
다른 용도는 무엇인가요?
키를 조회하기 위해 유효한 key_type 객체를 생성하는 것이 불가능하거나 번거로운 경우에도 이 기능이 유용합니다. 이런 경우, 대안으로 필요한 정보를 포함한 훨씬 간단한 타입을 사용할 수 있습니다. 예를 들어:
struct ThreadCmp {
using is_transparent = void;
// 일반 오버로드
bool operator()(const std::thread& a, const std::thread& b) const {
return a.get_id() < b.get_id();
}
// 투명 오버로드
bool operator()(const std::thread& a, std::thread::id b) const {
return a.get_id() < b;
}
bool operator()(std::thread::id a, const std::thread& b) const {
return a < b.get_id();
}
bool operator()(std::thread::id a, std::thread::id b) const {
return a < b;
}
};
std::set<std::thread, ThreadCmp> threads = ...;
// 동일한 ID를 가진 `std::thread` 인스턴스를 생성할 수 없지만,
// 대신 ID로 조회할 수 있습니다.
std::thread::id id = ...;
auto it = threads.find(id);
STL 컨테이너 지원 및 대안
표준 정렬 컨테이너(std::{map, set, multimap, multiset})는 이종 조회를 지원합니다.
표준 unordered 컨테이너(std::unordered_{map, set, multimap, multiset})는 C++20부터 이종 조회를 지원합니다.
Swiss Tables의 새로운 컨테이너 계열은 문자열 타입(std::string, absl::string_view 등) 및 스마트 포인터(T*, std::shared_ptr, std::unique_ptr)에 대해 이종 조회를 지원합니다. 이 컨테이너는 해시 함수와 동등 함수 모두 투명 태그로 선언해야 합니다. 기타 키 타입은 사용자 명시적 설정이 필요합니다.
B-Tree 컨테이너(absl::btree_{set, map, multiset, multimap})도 이종 조회를 지원합니다.
Protocol Buffers’ 연관 맵 구현(google::protobuf::Map)은 std::string을 키로 사용할 때 문자열 유사 키(absl::string_view로 변환 가능한 모든 타입)를 이용한 이종 조회를 지원합니다.