robin map
v1.3.0
로빈 맵 라이브러리는 충돌을 해결하기 위해 역방향 이동 삭제 기능이 있는 개방형 주소 지정 및 선형 로빈 후드 해싱을 사용하는 빠른 해시 맵 및 해시 세트의 C++ 구현입니다.
tsl::robin_map , tsl::robin_set , tsl::robin_pg_map 및 tsl::robin_pg_set 의 네 가지 클래스가 제공됩니다. 처음 두 개는 더 빠르며 두 가지 성장 정책의 거듭제곱을 사용하고, 마지막 두 개는 대신 프라임 성장 정책을 사용하며 열악한 해시 함수에 더 잘 대처할 수 있습니다. 해시의 하위 비트에서 패턴이 반복될 가능성이 있는 경우 프라임 버전을 사용하십시오(예: ID 해시 함수로 포인터를 저장하는 경우). 자세한 내용은 성장정책을 참조하세요.
다른 해시 맵에 대한 tsl::robin_map 의 벤치마크는 여기에서 찾을 수 있습니다. 이 페이지는 또한 사용 사례에 맞게 시도해야 하는 해시 테이블 구조에 대한 몇 가지 조언을 제공합니다( tsl 네임스페이스의 여러 해시 테이블 구현으로 인해 약간의 어려움을 겪는 경우 유용함).
헤더 전용 라이브러리, 포함 경로에 포함 디렉터리를 추가하기만 하면 바로 사용할 수 있습니다. CMake를 사용하는 경우 CMakeLists.txt에서 내보낸 tsl::robin_map 대상을 사용할 수도 있습니다.
빠른 해시 테이블, 벤치마크에서 일부 숫자를 확인하세요.
이동 전용 및 기본이 아닌 생성 가능한 키/값을 지원합니다.
Key 와 다른 유형의 find 사용을 허용하는 이종 조회 지원(예: std::unique_ptr<foo> 키로 사용하는 맵이 있는 경우 foo* 또는 std::uintptr_t 키 매개변수로 사용할 수 있음) std::unique_ptr<foo> 구성하지 않고 find (예제 참조).
키에서 센티널 값을 예약할 필요가 없습니다.
해시 또는 키 동일 함수의 계산 비용이 많이 드는 경우 더 빠른 재해시 및 조회를 위해 저장된 키-값과 함께 해시 값을 저장할 수 있습니다. 해시는 정렬로 인해 메모리의 구조 크기에 영향을 미치지 않는다는 것을 라이브러리가 감지할 수 있는 경우 명시적으로 묻지 않더라도 저장될 수 있습니다. 자세한 내용은 StoreHash 템플릿 매개변수를 참조하세요.
조회 전에 해시가 알려진 경우 이를 매개변수로 전달하여 조회 속도를 높일 수 있습니다(API의 precalculated_hash 매개변수 참조).
효율적인 직렬화 및 역직렬화 지원(자세한 내용은 API의 예제 및 serialize/deserialize 메서드 참조)
예외를 비활성화한 상태에서 라이브러리를 사용할 수 있습니다(Clang 및 GCC의 -fno-exceptions 옵션을 통해, MSVC의 /EH 옵션 없이 또는 단순히 TSL_NO_EXCEPTIONS 정의를 통해). std::terminate 예외가 비활성화된 경우 throw 명령어를 대체하는 데 사용됩니다.
std::unordered_map 및 std::unordered_set 와 매우 유사한 API입니다.
std::unordered_map 과의 차이점 tsl::robin_map std::unordered_map 과 유사한 인터페이스를 가지려고 시도하지만 몇 가지 차이점이 있습니다.
강력한 예외 보장은 다음 문이 true인 경우에만 유지됩니다. std::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value (여기서 value_type tsl::robin_set 및 std::pair<Key, T> 의 Key 입니다.) , tsl::robin_map 의 경우 std::pair<Key, T> ). 그렇지 않고 교체 또는 이동 중에 예외가 발생하면 구조가 정의되지 않은 상태가 될 수 있습니다. 표준에 따라 복사 생성자가 없고 이동 생성자가 없는 value_type 도 이 조건을 충족하므로 구조에 대한 강력한 예외 보장이 보장됩니다(자세한 내용은 API 참조).
Key 유형과 map의 경우 T 교체 가능해야 합니다. 또한 복사 및/또는 이동이 가능해야 합니다.
반복자 무효화는 동일한 방식으로 작동하지 않습니다. 해시 테이블을 수정하는 모든 작업은 반복자를 무효화합니다(자세한 내용은 API 참조).
맵의 키 또는 값에 대한 참조 및 포인터는 이러한 키-값에 대한 반복자와 동일한 방식으로 무효화됩니다.
tsl::robin_map 의 반복자의 경우, operator*() 및 operator->() std::pair< std::pair<const Key, T> const std::pair<Key, T> ::pair<Key, T>에 대한 참조 및 포인터를 반환하여 값을 만듭니다. T 수정할 수 없습니다. 값을 수정하려면 반복자의 value() 메서드를 호출하여 변경 가능한 참조를 가져와야 합니다. 예:
tsl::robin_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}};for(auto it = map.begin(); it != map.end() ; ++it) {//it->초 = 2; // 불법.값() = 2; // 좋아요} 일부 버킷 관련 메소드(예: bucket_size , bucket , ...)는 지원되지 않습니다.
이러한 차이점은 std::unordered_set 과 tsl::robin_set 사이에도 적용됩니다.
스레드 안전성 보장은 std::unordered_map/set 와 동일합니다(즉, 작성기 없이 여러 판독기를 가질 수 있음).
라이브러리는 GrowthPolicy 템플릿 매개변수를 통해 여러 성장 정책을 지원합니다. 라이브러리에서는 세 가지 정책을 제공하지만 필요한 경우 자체 정책을 쉽게 구현할 수 있습니다.
tsl::rh::power_of_two_growth_policy. tsl::robin_map/set 에서 사용하는 기본 정책입니다. 이 정책은 해시 테이블의 버킷 배열 크기를 2의 거듭제곱으로 유지합니다. 이 제약 조건을 통해 정책은 해시를 버킷에 매핑하기 위해 느린 모듈로 작업을 사용하지 않고 hash % 2 n 대신 hash & (2 n - 1) 사용합니다(빠른 모듈로 참조). 빠르지만 2의 거듭제곱을 갖는 모듈로는 결국 가장 중요한 비트만 마스크하므로 잘못된 해시 함수로 인해 많은 충돌이 발생할 수 있습니다.
tsl::rh::prime_growth_policy. tsl::robin_pg_map/set 에서 사용하는 기본 정책입니다. 정책은 해시 테이블의 버킷 배열 크기를 소수로 유지합니다. 해시를 버킷에 매핑할 때 소수를 모듈로로 사용하면 해시 함수가 좋지 않더라도 버킷 전체에 해시가 더 잘 분산됩니다. 컴파일러가 모듈로 연산을 최적화할 수 있도록 정책은 상수 소수 모듈로가 있는 조회 테이블을 사용합니다(자세한 내용은 API 참조). tsl::rh::power_of_two_growth_policy 보다 느리지만 더 안전합니다.
tsl::rh::mod_growth_policy. 정책은 매개변수에 전달된 사용자 정의 가능한 성장 인자에 따라 지도를 확장합니다. 그런 다음 모듈로 연산자를 사용하여 해시를 버킷에 매핑합니다. 느리지만 더 유연합니다.
자체 정책을 구현하려면 다음 인터페이스를 구현해야 합니다.
struct custom_policy {// 해시 테이블 생성 및 재해시 시 호출되는 min_bucket_count_in_out은 해시 테이블에 필요한 최소 버킷입니다. 정책은 필요한 경우 이를 더 많은 수의 버킷으로 변경할 수 있으며 // 해시 테이블은 이 값을 버킷 수로 사용합니다. 0 버킷이 요청되면 값//은 0.explicit custom_policy(std::size_t& min_bucket_count_in_out);에 있어야 합니다. // 해시가 속한 버킷[0, bucket_count())을 반환합니다. // bucket_count()가 0이면 항상 0을 반환해야 합니다.std::size_t bucket_for_hash(std::size_t hash) const noException; // 다음 성장에 사용해야 할 버킷 수를 반환합니다.std::size_t next_bucket_count() const; // 정책이 지원하는 최대 버킷 수std::size_t max_bucket_count() const; // 버킷 수 0으로 정책이 생성된 것처럼 성장 정책을 재설정합니다.// 삭제 후 bucket_for_hash()가 호출되면 정책은 항상 0을 반환해야 합니다.voidclear() noException;
}Robin-map을 사용하려면 포함 경로에 포함 디렉터리를 추가하기만 하면 됩니다. 헤더 전용 라이브러리입니다.
CMake를 사용하는 경우 target_link_libraries 와 함께 CMakeLists.txt에서 내보낸 tsl::robin_map 대상을 사용할 수도 있습니다.
# robin-map 프로젝트가 타사 디렉터리에 저장되는 예add_subdirectory(third-party/robin-map)target_link_libraries(your_target PRIVATE tsl::robin_map)
make install 통해 프로젝트를 설치한 경우 add_subdirectory 대신 find_package(tsl-robin-map REQUIRED) 사용할 수도 있습니다.
라이브러리는 vcpkg 및 conan에서 사용할 수 있습니다. Debian, Ubuntu 및 Fedora 패키지 리포지토리에도 있습니다.
코드는 모든 C++17 표준 호환 컴파일러에서 작동해야 합니다.
테스트를 실행하려면 Boost Test 라이브러리와 CMake가 필요합니다.
자식 클론 https://github.com/Tessil/robin-map.gitcd robin-map/tests mkdir 빌드cd 빌드 씨메이크 .. cmake --build ../tsl_robin_map_tests
API는 여기에서 찾을 수 있습니다.
모든 메소드는 아직 문서화되어 있지 않지만 달리 지정하는 경우를 제외하고 std::unordered_map 및 std::unordered_set 의 동작을 복제합니다.
#include <cstdint>#include <iostream>#include <string>#include <tsl/robin_map.h>#include <tsl/robin_set.h>int main() {
tsl::robin_map<std::string, int> map = {{"a", 1}, {"b", 2}};
지도["c"] = 3;
지도["d"] = 4;
map.insert({"e", 5});
map.erase("b"); for(auto it = map.begin(); it != map.end(); ++it) {//it->second += 2; // 유효하지 않음.it.value() += 2;
} // {d, 6} {a, 3} {e, 7} {c, 5}for(const auto& key_value : map) {
std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
if(map.find("a") != map.end()) {
std::cout << ""a"를 찾았습니다." << 표준::endl;
} const std::size_t precalculated_hash = std::hash<std::string>()("a");// 해시를 미리 알고 있다면 매개변수로 전달하여 조회 속도를 높일 수 있습니다.if( map.find("a", precalculated_hash) != map.end()) {
std::cout << "해시가 있는 "a"를 찾았습니다. " << precalculated_hash << "." << 표준::endl;
}
/* * 해시를 계산하고 두 std::string을 비교하는 작업은 느릴 수 있습니다. * StoreHash를 true로 설정하면 * 각 std::string의 해시를 해시 맵에 저장하여 삽입 및 조회를 더 빠르게 수행할 수 있습니다. */
tsl::robin_map<std::string, int, std::hash<std::string>,
std::equal_to<std::string>,
std::allocator<std::pair<std::string, int>>, true> map2;
map2["a"] = 1;
map2["b"] = 2; // {a, 1} {b, 2}for(const auto& key_value : map2) {
std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
tsl::robin_set<int> 세트;
set.insert({1, 9, 0});
set.insert({2, -1, 9}); // {0} {1} {2} {9} {-1}for(const auto& key : set) {
std::cout << "{" << 키 << "}" << std::endl;
}
} 이기종 오버로드를 사용하면 사용된 유형이 해시 가능하고 Key 와 비교할 수 있는 한 조회 및 삭제 작업에 Key 이외의 다른 유형을 사용할 수 있습니다.
tsl::robin_map/set 에서 이기종 오버로드를 활성화하려면 정규 ID KeyEqual::is_transparent 유효해야 합니다. std::map::find 와 동일한 방식으로 작동합니다. std::equal_to<> 사용하거나 자신만의 함수 객체를 정의할 수 있습니다.
KeyEqual 과 Hash 모두 서로 다른 유형을 처리할 수 있어야 합니다.
#include <기능>#include <iostream>#include <string>#include <tsl/robin_map.h>struct Employee(int id, std::string name) : m_id(id), m_name(std::move (이름)) {
} // 클래스에 비교기를 포함하고 `std::equal_to<>`를 사용합니다...friend bool Operator==(const Employees& empl, int empl_id) {return empl.m_id == empl_id;
} 친구 부울 연산자==(int empl_id, const 직원& empl) {return empl_id == empl.m_id;
} 친구 부울 연산자==(const 직원& empl1, const 직원& empl2) {return empl1.m_id == empl2.m_id;
}
int m_id;
표준::문자열 m_name;
};// ... 또는 Employees.struct equal_employee {is_transparent = void;를 사용하여 비교하기 위해 별도의 클래스를 구현합니다. bool 연산자()(const 직원& empl, int empl_id) const {return empl.m_id == empl_id;
} bool 연산자()(int empl_id, const 직원& empl) const {return empl_id == empl.m_id;
} bool 연산자()(const 직원& empl1, const 직원& empl2) const {return empl1.m_id == empl2.m_id;
}
};구조 hash_employee {
std::size_t 연산자()(const 직원& empl) const {return std::hash<int>()(empl.m_id);
}
std::size_t 연산자()(int id) const {return std::hash<int>()(id);
}
};int main() {// 매개변수를 자동으로 추론하고 전달하는 std::equal_to<>를 사용합니다.tsl::robin_map<employee, int, hash_employee, std::equal_to<>> map;
map.insert({employee(1, "John Doe"), 2001});
map.insert({employee(2, "Jane Doe"), 2002});
map.insert({employee(3, "John Smith"), 2003});// John Smith 2003auto it = map.find(3);if(it != map.end()) {
std::cout << it->first.m_name << " " << it->second << std::endl;
}
map.erase(1);// is_transparent 멤버가 있는 사용자 정의 KeyEqual을 사용합니다. typetsl::robin_map<employee, int, hash_employee, equal_employee> map2;
map2.insert({employee(4, "Johnny Doe"), 2004});// 2004std::cout << map2.at(4) << std::endl;
}라이브러리는 지도나 세트를 직렬화 및 역직렬화하여 파일에 저장하거나 네트워크를 통해 전송할 수 있는 효율적인 방법을 제공합니다. 이렇게 하려면 사용자가 직렬화 및 역직렬화를 위한 함수 개체를 제공해야 합니다.
struct serializer {// U에 대해 다음 유형을 지원해야 합니다: std::int16_t, std::uint32_t, // std::uint64_t, float 및 std::pair<Key, T>(맵이 사용되는 경우) 또는 Key for / / set.template<typename U>void Operator()(const U& value);
}; struct deserializer {// U에 대해 다음 유형을 지원해야 합니다: std::int16_t, std::uint32_t, // std::uint64_t, float 및 std::pair<Key, T>(맵이 사용되는 경우) 또는 Key for / / set.template<유형 이름 U>
U 연산자()();
};구현 시 호환성이 필요한 경우 제공된 함수 객체에 직렬화/역직렬화하는 유형의 이진 호환성(엔디안, 부동 소수점 이진 표현, int 크기 등)이 남아 있습니다.
serialize 및 deserialize 메서드에 대한 자세한 내용은 API에서 확인할 수 있습니다.
#include <cassert>#include <cstdint>#include <fstream>#include <type_traits>#include <tsl/robin_map.h>클래스 직렬 변환기 {public:serializer(const char* file_name) {
m_ostream.Exceptions(m_ostream.badbit | m_ostream.failbit);
m_ostream.open(file_name, std::ios::binary);
} template<class T, typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>void 연산자()(const T& value) {
m_ostream.write(reinterpret_cast<const char*>(&value), sizeof(T));
} 무효 연산자()(const std::pair<std::int64_t, std::int64_t>& value) {
(*this)(value.first);
(*this)(value.second);
}private:std::ofstream m_ostream;
};class deserializer {public:deserializer(const char* file_name) {
m_istream.Exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
m_istream.open(file_name, std::ios::binary);
} 템플릿<클래스 T>
T 연산자()() {
T 값;역직렬화(값); 반환값;
}
private:template<class T, typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>void deserialize(T& value) {
m_istream.read(reinterpret_cast<char*>(&value), sizeof(T));
} void deserialize(std::pair<std::int64_t, std::int64_t>& value) {deserialize(value.first);deserialize(value.second);
}private:std::ifstream m_istream;
};int main() {const tsl::robin_map<std::int64_t, std::int64_t> map = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
const char* file_name = "robin_map.data";
{
직렬 변환기 serial(file_name);
map.serialize(직렬);
}
{
deserializer dserial(file_name);auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial); 주장(맵 == map_deserialized);
}
{
디시리얼라이저 dserial(file_name); /** * 직렬화 및 역직렬화된 맵이 해시 호환 가능한 경우(API의 조건 참조), * 인수를 true로 설정하면 각 키의 해시를 다시 계산할 필요가 없기 때문에 역직렬화 프로세스의 속도가 * 향상됩니다. 우리는 또한 각 버킷에 얼마나 많은 공간이 필요한지 알고 있습니다. */const bool hash_ Compatible = true;auto map_deserialized =
tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial, hash_ Compatible); 주장(맵 == map_deserialized);
}
}상용구를 피하기 위해 직렬화 라이브러리를 사용하는 것이 가능합니다.
다음 예에서는 Boost zlib 압축 스트림과 함께 Boost 직렬화를 사용하여 직렬화된 결과 파일의 크기를 줄입니다. 이 예제에서는 람다의 템플릿 매개변수 목록 구문 사용으로 인해 C++20이 필요하지만 최신 버전에도 적용할 수 있습니다.
#include <boost/archive/binary_iarchive.hpp>#include <boost/archive/binary_oarchive.hpp>#include <boost/iostreams/filter/zlib.hpp>#include <boost/iostreams/filtering_stream.hpp>#include <boost /serialization/split_free.hpp>#include <boost/serialization/utility.hpp>#include <cassert>#include <cstdint>#include <fstream>#include <tsl/robin_map.h>namespace Boost { 네임스페이스 직렬화 {template<class Archive, class Key, class T>void serialize(Archive & ar, tsl::robin_map <Key, T>& map, const unsigned int version) {split_free(ar, map, version);
}template<class Archive, class Key, class T>void save(Archive & ar, const tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {auto serializer = [&ar](const 자동& v) { ar & v; };
map.serialize(직렬 변환기);
}template<class Archive, class Key, class T>void load(Archive & ar, tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {auto deserializer = [&ar]<typename U >() { 유 유; ar&u; 당신을 돌려 보내십시오; };
map = tsl::robin_map<Key, T>::deserialize(deserializer);
}
}}int 메인() {
tsl::robin_map<std::int64_t, std::int64_t> map = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
const char* file_name = "robin_map.data";
{
표준::ofstream ofs;
ofs.Exceptions(ofs.badbit | ofs.failbit);
ofs.open(파일_이름, std::ios::binary);
Boost::iostreams::filtering_ostream fo;
fo.push(boost::iostreams::zlib_compressor());
fo.push(ofs);
Boost::archive::binary_oarchive oa(fo);
oa << 지도;
}
{
표준::ifstream ifs;
ifs.Exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);
ifs.open(파일_이름, std::ios::binary);
Boost::iostreams::filtering_istream fi;
fi.push(boost::iostreams::zlib_decompressor());
fi.push(ifs);
Boost::archive::binary_iarchive ia(fi);
tsl::robin_map<std::int64_t, std::int64_t> map_deserialized;
ia >> map_deserialized; 주장(맵 == map_deserialized);
}
} tsl::robin_map 및 tsl::robin_set 과 관련된 두 가지 잠재적인 성능 문제는 주목할 만합니다.
잘못된 해시입니다 . 많은 충돌을 일으키는 해시 함수는 다음과 같은 놀라운 동작을 초래할 수 있습니다. 충돌 횟수가 특정 임계값을 초과하면 해시 테이블이 자동으로 확장되어 문제를 해결합니다. 그러나 퇴화된 경우 이러한 확장은 충돌 횟수에 영향을 미치지 않아 선형 삽입 순서로 인해 기하급수적인 저장 용량 증가로 이어지는 오류 모드가 발생할 수 있습니다.
이 사례는 산술 유형 T 에 대해 기본 STL std::hash<T> 와 함께 기본 2의 거듭제곱 증가 전략을 사용할 때 주로 관찰되었으며, 이는 종종 항등식입니다! 예제는 이슈 #39를 참조하세요. 해결책은 간단합니다. 더 나은 해시 함수 및/또는 tsl::robin_pg_set / tsl::robin_pg_map 사용하세요.
요소 삭제 및 낮은 부하율 . tsl::robin_map 및 tsl::robin_set STL 맵/세트 API를 미러링합니다. 이 API는 특정 위치에서 요소를 제거하고 다음 요소를 가리키는 유효한 반복기를 반환하는 iterator erase(iterator) 메서드를 노출합니다.
이 새로운 반복자 객체를 생성하려면 테이블에서 비어 있지 않은 다음 버킷으로 이동해야 합니다. 이는 해시 테이블의 로드 비율 이 낮을 때(즉, capacity() size() 보다 훨씬 큰 경우) 비용이 많이 드는 작업이 될 수 있습니다.
게다가 erase() 메소드는 테이블을 축소하고 다시 해시하지 않습니다. 이는 이 함수의 사양에서 허용되지 않기 때문입니다. 중간 삽입 없이 선형 순서로 무작위 제거를 수행하면 2차 런타임 비용이 발생하는 퇴화 사례가 발생할 수 있습니다.
이러한 경우 반복자 반환 값이 필요하지 않은 경우가 많으므로 비용이 전혀 필요하지 않습니다. 따라서 tsl::robin_set 및 tsl::robin_map 모두 다음 요소를 찾을 필요가 없도록 반복자를 반환하지 않는 대체 삭제 방법인 void erase_fast(iterator) 를 제공합니다.
코드는 MIT 라이선스에 따라 라이선스가 부여됩니다. 자세한 내용은 LICENSE 파일을 참조하세요.
