unordered_dense
v4.5.0
C ++ 17 이상에 대한 Robin-Hood Backward Shift 삭제를 기반으로 빠른 및 밀도로 저장된 해시 맵 및 해시 세트.
클래스 ankerl::unordered_dense::map and ankerl::unordered_dense::set std::unordered_map 및 std::unordered_set 의 (거의) 드롭 인 교체입니다. 그들은 강력한 반복 / 참조 안정성 보증을 가지고 있지 않지만 일반적으로 훨씬 빠릅니다.
또한 ankerl::unordered_dense::segmented_map 및 ankerl::unordered_dense::segmented_set 이 있습니다. 삽입물의 안정적인 반복자/참조.
ankerl::unordered_dense::hash 전문화하십시오is_transparent 사용하여 이질적인 과부하std::hash 로의 자동 폴백auto extract() && -> value_container_typeextract() 단일 요소[[nodiscard]] auto values() const noexcept -> value_container_type const&auto replace(value_container_type&& container)ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map 및 segmented_set 선택한 디자인은 std::unordered_map 에 비해 몇 가지 장점이 있습니다.
std::vector 에 저장되며 모든 데이터는 인접합니다!absl::flat_hash_map 과 같은 야구장에서 매우 빠른 삽입 및 조회 속도std::allocators 및 다형성 할당자를위한 모든 지원. ankerl::unordered_dense::pmr typedefs가 있습니다std::vector 에서 boost::interprocess::vector 또는 기타 호환 랜덤 액세스 컨테이너로 전환 할 수 있습니다.std::vector 표시 할 수있는 디버거에서 기본 데이터를 쉽게 볼 수 있습니다.무료 점심은 없으므로 몇 가지 단점이 있습니다.
std::pair<Key, Value> 의 const Key 없음 기본 설치 위치는 /usr/local 입니다.
저장소를 복제하고 복제 된 폴더 에서이 명령을 실행하십시오.
mkdir build && cd build
cmake ..
cmake --build . --target install unordered_dense 시스템을 넓게 설치하지 않으려면 설치 접두사 설정을 고려하십시오.
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX:PATH= ${HOME} /unordered_dense_install ..
cmake --build . --target install설치된 라이브러리를 사용하려면 프로젝트에 추가하십시오.
find_package (unordered_dense CONFIG REQUIRED)
target_link_libraries (your_project_name unordered_dense::unordered_dense) ankerl::unordered_dense C ++ 20 모듈을 지원합니다. src/ankerl.unordered_dense.cpp 를 컴파일하고 결과 모듈을 사용하기 만하면됩니다.
clang++ -std=c++20 -I include --precompile -x c++-module src/ankerl.unordered_dense.cpp
clang++ -std=c++20 -c ankerl.unordered_dense.pcm module_test.cpp 에서 EG와 함께 모듈을 사용하려면 사용하십시오.
import ankerl.unordered_dense;그리고 EG와 함께 컴파일합니다
clang++ -std=c++20 -fprebuilt-module-path=. ankerl.unordered_dense.o module_test.cpp -o main 간단한 데모 스크립트는 test/modules 에서 찾을 수 있습니다.
ankerl::unordered_dense::hash Wyhash를 기반으로 빠르고 고품질 해시입니다. ankerl::unordered_dense 맵/세트는 고품질의 해시 (좋은 눈사태 효과)와 품질이 좋지 않습니다. 품질이 좋은 해시에는 특수 마커가 포함됩니다.
using is_avalanching = void ; 이것은 전문화 bool , char , signed char , unsigned char , char8_t , char16_t , char32_t , wchar_t , short , unsigned short , int , unsigned int , long long long , unsigned long , unsigned long long , T* , std::unique_ptr<T> , std::shared_ptr<T> std::basic_string<C> enum 및 std::basic_string_view<C> .
그러한 마커를 포함하지 않는 해시는 품질이 좋지 않은 것으로 가정하고 맵/세트 구현 내부에서 추가 혼합 단계를 수신합니다.
간단한 사용자 정의 키 유형을 고려하십시오.
struct id {
uint64_t value{};
auto operator ==(id const & other) const -> bool {
return value == other. value ;
}
};해시의 가장 간단한 구현은 다음과 같습니다.
struct custom_hash_simple {
auto operator ()(id const & x) const noexcept -> uint64_t {
return x. value ;
}
};이것은 예를 들어 사용할 수 있습니다
auto ids = ankerl::unordered_dense::set<id, custom_hash_simple>(); custom_hash_simple using is_avalanching = void; 마커 품질이 좋지 않은 것으로 간주되며 x.value 의 추가 혼합은 세트 내부에 자동으로 제공됩니다.
id 예로 돌아가서, 우리는 고품질 해시를 쉽게 구현할 수 있습니다.
struct custom_hash_avalanching {
using is_avalanching = void ;
auto operator ()(id const & x) const noexcept -> uint64_t {
return ankerl::unordered_dense::detail::wyhash::hash (x. value );
}
}; 우리는 wyhash::hash 고품질이라는 것을 알고 있으므로 using is_avalanching = void; 맵/세트가 반환 된 값을 직접 사용하게합니다.
ankerl::unordered_dense::hash 전문화하십시오 새 클래스를 만드는 대신 ankerl::unordered_dense::hash 전문화 할 수 있습니다.
template <>
struct ankerl ::unordered_dense::hash<id> {
using is_avalanching = void ;
[[nodiscard]] auto operator ()(id const & x) const noexcept -> uint64_t {
return detail::wyhash::hash (x. value );
}
};is_transparent 사용하여 이질적인 과부하 이 맵/세트는 p2363에 설명 된 이질적인 과부하를 지원합니다. 여기에는 find , count , contains , equal_range (P0919R3 참조), erase (P2077R2 참조) 및 try_emplace , insert_or_assign , operator[] , at & emplace insert 대한 과부하가 있습니다 (P2363R3 참조).
이질적인 과부하가 영향을 받기 위해서는 hasher 와 key_equal 모두 is_transparent 세트를 가져야합니다.
Here is an example implementation that's usable with any string types that is convertible to std::string_view (eg char const* and std::string ):
struct string_hash {
using is_transparent = void ; // enable heterogeneous overloads
using is_avalanching = void ; // mark class as high quality avalanching hash
[[nodiscard]] auto operator ()(std::string_view str) const noexcept -> uint64_t {
return ankerl::unordered_dense::hash<std::string_view>{}(str);
}
}; 이 해시를 사용하려면 유형으로 지정해야하며 std :: equal_to <> : is_transparent 와 함께 key_equal 지정해야합니다.
auto map = ankerl::unordered_dense::map<std::string, size_t , string_hash, std::equal_to<>>(); 자세한 내용은 test/unit/transparent.cpp 의 예제를 참조하십시오.
std::hash 로의 자동 폴백 사용자 정의 유형의 std::hash 에 대한 구현을 사용할 수있게되면이를 자동으로 사용하고 품질이 좋지 않은 것으로 가정합니다 (따라서 std::hash 사용되지만 추가 혼합 단계가 수행됩니다).
유형에 고유 한 객체 표현 (패딩 없음, 사소한 복사 가능)이 있으면 객체의 메모리를 해시 할 수 있습니다. 간단한 수업을 고려하십시오
struct point {
int x{};
int y{};
auto operator ==(point const & other) const -> bool {
return x == other. x && y == other. y ;
}
};빠르고 고품질의 해시는 다음과 같이 쉽게 제공 할 수 있습니다.
struct custom_hash_unique_object_representation {
using is_avalanching = void ;
[[nodiscard]] auto operator ()(point const & f) const noexcept -> uint64_t {
static_assert (std::has_unique_object_representations_v<point>);
return ankerl::unordered_dense::detail::wyhash::hash (&f, sizeof (f));
}
}; 표준 std::unordered_map API (https://en.cppreference.com/w/cpp/container/unordered_map 참조) Node API와 다소 유사한 추가 API를 가지고 있지만 내부적으로 임의의 액세스 컨테이너를 사용하고 있다는 사실을 활용합니다.
auto extract() && -> value_container_type 내부적으로 사용되는 컨테이너를 추출합니다. *this 비워졌습니다.
extract() 단일 요소 erase() 와 유사하게 API Call extract() 가 있습니다. 리턴 값이 컨테이너에서 제거되는 이동 요소라는 점을 제외하고는 erase 와 정확히 동일하게 작동합니다.
auto extract(const_iterator it) -> value_typeauto extract(Key const& key) -> std::optional<value_type>template <class K> auto extract(K&& key) -> std::optional<value_type> extract(key) API는 키를 찾을 수 없을 때 비어있는 std::optional<value_type> 반환합니다.
[[nodiscard]] auto values() const noexcept -> value_container_type const&기본 값 컨테이너를 노출시킵니다.
auto replace(value_container_type&& container)내부적으로 고정 된 컨테이너를 버리고 통과 된 컨테이너로 대체합니다. 비 유니 퀴 요소가 제거되고, 비 유니 키 요소가 발견되면 컨테이너가 부분적으로 재정렬됩니다.
unordered_dense 사용자 정의 할당자를 허용하지만 해당 템플릿 인수에 대한 사용자 정의 컨테이너를 지정할 수도 있습니다. 이렇게하면 내부적으로 사용 된 std::vector eG std::deque 또는 boost::interprocess::vector 와 같은 다른 컨테이너로 교체 할 수 있습니다. 이것은 멋진 포인터 (예 : offset_ptr)를 지원하므로 컨테이너는 boost::interprocess 가 제공하는 공유 메모리와 함께 사용할 수 있습니다.
맵/세트는 두 가지 다른 버킷 유형을 지원합니다. 기본값은 거의 모든 사람에게 좋을 것입니다.
ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map 및 segmented_set ankerl::unordered_dense 기본 std::vector 보다 메모리 요구 사항이 낮은 사용자 정의 컨테이너 구현을 제공합니다. 메모리는 인접하지는 않지만 모든 요소를 재 할당하고 이동하지 않고도 세그먼트를 할당 할 수 있습니다. 요약하면, 이것은 이어집니다
std::vector 에 비해 약간 느린 인덱싱. 다음은 absl::flat_hash_map 및 ankerl::unordered_dense::map 에 대한 비교입니다. 
Abseil 은이 간단한 삽입 테스트에서 가장 빠르며 0.8 초 이상 걸립니다. 피크 메모리 사용량은 약 430MB입니다. 마지막 피크 이후 메모리 사용이 어떻게 줄어든 방법에 유의하십시오. ~ 290MB로 내려 가면 재료를 마치고 이전에 사용한 메모리 블록을 제거 할 수 있습니다.
ankerl::unordered_dense::segmented_map 이러한 피크가 없으며 메모리 사용이 원활하게 증가합니다. 인덱싱 데이터 구조 요구 사항은 여전히 고정 요소로 증가해야하기 때문에 여전히 갑작스런 하락 및 메모리 증가가 있습니다. 그러나 데이터를 별도의 컨테이너로 유지하기 때문에 먼저 이전 데이터 구조를 제거한 다음 새롭고 더 큰 인덱싱 구조를 할당 할 수 있습니다. 따라서 우리는 피크가 없습니다.
맵/세트에는 두 가지 데이터 구조가 있습니다.
std::vector<value_type> 모든 데이터를 보유합니다. 지도/세트 반복자는 단지 std::vector<value_type>::iterator ! 요소가 추가 될 때마다 벡터에 대한 emplace_back 입니다. 키는 해시이며, 버킷 어레이의 해당 위치에 항목 (버킷)이 추가됩니다. 버킷에는이 구조가 있습니다.
struct Bucket {
uint32_t dist_and_fingerprint;
uint32_t value_idx;
};각 버킷은 3 가지를 저장합니다.
dist_and_fingerprint 에서 가장 중요한 바이트 3)dist_and_fingerprint 에서 가장 낮은 바이트)이 구조는 특히 충돌 해상도 전략 Robin-Hood Hashing을 위해 후진 시프트 삭제를 위해 설계되었습니다.
키는 해시이고 버킷 어레이는 해당 지문으로 해당 위치에 항목이 있으면 검색됩니다. 발견되면 데이터 벡터의 키를 비교하고 동일하면 값이 반환됩니다.
모든 데이터는 벡터에 저장되므로 제거는 조금 더 복잡합니다.
value_idx 업데이트하십시오. 이것은 또 다른 조회가 필요합니다. 2023-09-10에 Github에서 빠른 검색을 수행 하여이지도가 인기있는 오픈 소스 프로젝트에서 사용되는지 확인했습니다. 다음은 내가 찾은 프로젝트 중 일부입니다. 그 목록에 원한다면 메모를 보내주세요!
