ordered map
v1.1.0
순서 맵 라이브러리는 Python의 OrderedDict와 유사한 방식으로 삽입 순서를 유지하는 해시 맵과 해시 세트를 제공합니다. 지도를 반복할 때 값은 삽입된 순서와 동일한 순서로 반환됩니다.
값은 기본 구조에 연속적으로 저장되며, 지우기 작업 후에도 값 사이에 구멍이 없습니다. 기본적으로 std::deque 이 구조에 사용되지만 std::vector 사용할 수도 있습니다. 이 구조는 values_container() 메서드를 통해 직접 액세스할 수 있으며 구조가 std::vector 인 경우 C API와 쉽게 상호 작용할 수 있도록 data() 메서드도 제공됩니다. 이는 빠른 반복을 제공하지만 O(bucket_count) 지우기 작업이라는 단점이 있습니다. O(1) pop_back() 및 O(1) unordered_erase() 함수를 사용할 수 있습니다. 순차적 삭제를 자주 사용하는 경우 다른 데이터 구조를 사용하는 것이 좋습니다.
해시 충돌을 해결하기 위해 라이브러리는 역방향 이동 삭제 기능이 있는 선형 로빈후드 탐색을 사용합니다.
라이브러리는 고유한 값을 갖는 std::deque/std::vector 와 유사한 동작을 제공하지만 조회의 경우 평균 시간 복잡도는 O(1)이고 삽입의 경우 분할 시간 복잡도는 O(1)입니다. 이로 인해 약간 더 높은 메모리 공간(기본적으로 버킷당 8바이트)이 발생합니다.
tsl::ordered_map 및 tsl::ordered_set 의 두 가지 클래스가 제공됩니다.
참고 : 라이브러리는 빠른 모듈로를 활용하기 위해 버킷 배열 크기에 대해 2의 거듭제곱을 사용합니다. 좋은 성능을 위해서는 해시 테이블에 해시 함수가 잘 분산되어 있어야 합니다. 성능 문제가 발생하면 해시 함수를 확인하세요.
tsl::ordered_map 대상을 사용할 수도 있습니다.std::unordered_map 과 비슷하지만 삽입 속도가 더 빠르고 메모리 사용량이 감소한 조회의 평균 시간 복잡도입니다(자세한 내용은 벤치마크 참조).Key 와 다른 유형의 find 사용을 허용하는 이종 조회 지원(예: std::unique_ptr<foo> 키로 사용하는 맵이 있는 경우 foo* 또는 std::uintptr_t 키 매개변수로 사용할 수 있음) std::unique_ptr<foo> 구성하지 않고 find (예제 참조).precalculated_hash 매개변수 참조).serialize/deserialize 메서드 참조)-fno-exceptions 옵션을 통해, MSVC의 /EH 옵션 없이 또는 단순히 TSL_NO_EXCEPTIONS 정의를 통해). std::terminate 예외가 비활성화된 경우 throw 명령어를 대체하는 데 사용됩니다.std::unordered_map 및 std::unordered_set 와 매우 유사한 API입니다.std::unordered_map 과의 차이점 tsl::ordered_map std::unordered_map 과 유사한 인터페이스를 가지려고 시도하지만 몇 가지 차이점이 있습니다.
RandomAccessIterator 입니다.std::vector 및 std::deque 에 더 가까운 방식으로 작동합니다(자세한 내용은 API 참조). std::vector ValueTypeContainer 로 사용하는 경우 reserve() 사용하여 일부 공간을 미리 할당하고 삽입 시 반복자가 무효화되는 것을 방지할 수 있습니다.erase() 작업은 O(bucket_count)의 복잡성을 갖습니다. 더 빠른 O(1) 버전 unordered_erase() 존재하지만 삽입 순서가 깨집니다(자세한 내용은 API 참조). O(1) pop_back() 도 사용할 수 있습니다.operator== 및 operator!= 는 순서에 따라 다릅니다. 동일한 값을 가지고 있지만 다른 순서로 삽입된 두 개의 tsl::ordered_map 동일하다고 비교되지 않습니다.operator*() 및 operator->() std::pair< std::pair<const Key, T> const std::pair<Key, T> pair<Key, T>에 대한 참조와 포인터를 반환하므로 T 값을 수정할 수 없습니다. 값을 수정하려면 반복자의 value() 메서드를 호출하여 변경 가능한 참조를 가져와야 합니다. 예: tsl::ordered_map< int , int > map = {{ 1 , 1 }, { 2 , 1 }, { 3 , 1 }};
for ( auto it = map.begin(); it != map.end(); ++it) {
// it->second = 2; // Illegal
it. value () = 2 ; // Ok
}IndexType 클래스 템플릿 매개변수를 통해 발생할 수 있습니다. 자세한 내용은 API를 확인하세요.bucket_size , bucket , ...)는 지원되지 않습니다. 스레드 안전성 보장은 std::unordered_map 과 동일합니다(즉, 작성기 없이 여러 동시 판독기를 가질 수 있음).
이러한 차이점은 std::unordered_set 과 tsl::ordered_set 사이에도 적용됩니다.
달리 언급되지 않은 경우 함수에는 강력한 예외 보장이 있습니다. 자세한 내용을 참조하세요. 아래에는 이 보증이 제공되지 않는 경우가 나열되어 있습니다.
ValueContainer::emplace_back 에 강력한 예외 보장이 있는 경우에만 보장이 제공됩니다 std::deque std::vector T 유형이 예외 사항은 세부 정보를 참조하세요).
tsl::ordered_map::erase_if 및 tsl::ordered_set::erase_if 함수는 해당 문서에 나열된 전제 조건 하에서만 보장됩니다.
순서 맵을 사용하려면 포함 경로에 포함 디렉터리를 추가하기만 하면 됩니다. 헤더 전용 라이브러리입니다.
CMake를 사용하는 경우 target_link_libraries 와 함께 CMakeLists.txt에서 내보낸 tsl::ordered_map 대상을 사용할 수도 있습니다.
# Example where the ordered-map project is stored in a third-party directory
add_subdirectory (third-party/ordered-map)
target_link_libraries (your_target PRIVATE tsl::ordered_map) make install 통해 프로젝트를 설치한 경우 add_subdirectory 대신 find_package(tsl-ordered-map REQUIRED) 사용할 수도 있습니다.
코드는 모든 C++11 표준 호환 컴파일러에서 작동해야 하며 GCC 4.8.4, Clang 3.5.0 및 Visual Studio 2015에서 테스트되었습니다.
테스트를 실행하려면 Boost Test 라이브러리와 CMake가 필요합니다.
git clone https://github.com/Tessil/ordered-map.git
cd ordered-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_ordered_map_tests API는 여기에서 찾을 수 있습니다.
# include < iostream >
# include < string >
# include < cstdlib >
# include < tsl/ordered_map.h >
# include < tsl/ordered_set.h >
int main () {
tsl::ordered_map< char , int > map = {{ ' d ' , 1 }, { ' a ' , 2 }, { ' g ' , 3 }};
map. insert ({ ' b ' , 4 });
map[ ' h ' ] = 5 ;
map[ ' e ' ] = 6 ;
map. erase ( ' a ' );
// {d, 1} {g, 3} {b, 4} {h, 5} {e, 6}
for ( const auto & key_value : map) {
std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
}
map. unordered_erase ( ' b ' );
// Break order: {d, 1} {g, 3} {e, 6} {h, 5}
for ( const auto & key_value : map) {
std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
}
for ( auto it = map. begin (); it != map. end (); ++it) {
// it->second += 2; // Not valid.
it. value () += 2 ;
}
if (map. find ( ' d ' ) != map. end ()) {
std::cout << " Found 'd'. " << std::endl;
}
const std:: size_t precalculated_hash = std::hash< char >()( ' d ' );
// If we already know the hash beforehand, we can pass it as argument to speed-up the lookup.
if (map. find ( ' d ' , precalculated_hash) != map. end ()) {
std::cout << " Found 'd' with hash " << precalculated_hash << " . " << std::endl;
}
tsl::ordered_set< char , std::hash< char >, std::equal_to< char >,
std::allocator< char >, std::vector< char >> set;
set. reserve ( 6 );
set = { ' 3 ' , ' 4 ' , ' 9 ' , ' 2 ' };
set. erase ( ' 2 ' );
set. insert ( ' 1 ' );
set. insert ( ' ' );
set. pop_back ();
set. insert ({ ' 0 ' , ' ' });
// Get raw buffer for C API: 34910
std::cout << atoi (set. data ()) << std::endl;
} 이기종 오버로드를 사용하면 사용된 유형이 해시 가능하고 Key 와 비교할 수 있는 한 조회 및 삭제 작업에 Key 이외의 다른 유형을 사용할 수 있습니다.
tsl::ordered_map/set 에서 이기종 오버로드를 활성화하려면 정규 ID KeyEqual::is_transparent 유효해야 합니다. std::map::find 와 동일한 방식으로 작동합니다. std::equal_to<> 사용하거나 자신만의 함수 객체를 정의할 수 있습니다.
KeyEqual 과 Hash 모두 서로 다른 유형을 처리할 수 있어야 합니다.
# include < functional >
# include < iostream >
# include < string >
# include < tsl/ordered_map.h >
struct employee {
employee ( int id, std::string name) : m_id(id), m_name(std::move(name)) {
}
// Either we include the comparators in the class and we use `std::equal_to<>`...
friend bool operator ==( const employee& empl, int empl_id) {
return empl. m_id == empl_id;
}
friend bool operator ==( int empl_id, const employee& empl) {
return empl_id == empl. m_id ;
}
friend bool operator ==( const employee& empl1, const employee& empl2) {
return empl1. m_id == empl2. m_id ;
}
int m_id;
std::string m_name;
};
// ... or we implement a separate class to compare employees.
struct equal_employee {
using is_transparent = void ;
bool operator ()( const employee& empl, int empl_id) const {
return empl. m_id == empl_id;
}
bool operator ()( int empl_id, const employee& empl) const {
return empl_id == empl. m_id ;
}
bool operator ()( const employee& empl1, const employee& empl2) const {
return empl1. m_id == empl2. m_id ;
}
};
struct hash_employee {
std:: size_t operator ()( const employee& empl) const {
return std::hash< int >()(empl. m_id );
}
std:: size_t operator ()( int id) const {
return std::hash< int >()(id);
}
};
int main () {
// Use std::equal_to<> which will automatically deduce and forward the parameters
tsl::ordered_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 2003
auto it = map. find ( 3 );
if (it != map. end ()) {
std::cout << it-> first . m_name << " " << it-> second << std::endl;
}
map. erase ( 1 );
// Use a custom KeyEqual which has an is_transparent member type
tsl::ordered_map<employee, int , hash_employee, equal_employee> map2;
map2. insert ({ employee ( 4 , " Johnny Doe " ), 2004 });
// 2004
std::cout << map2. at ( 4 ) << std::endl;
} 라이브러리는 지도나 세트를 직렬화 및 역직렬화하여 파일에 저장하거나 네트워크를 통해 전송할 수 있는 효율적인 방법을 제공합니다. 이렇게 하려면 사용자가 직렬화 및 역직렬화를 위한 함수 개체를 제공해야 합니다.
struct serializer {
// Must support the following types for U: std::uint64_t, float
// and std::pair<Key, T> if a map is used or Key for a set.
template < typename U>
void operator ()( const U& value);
}; struct deserializer {
// Must support the following types for U: std::uint64_t, float
// and std::pair<Key, T> if a map is used or Key for a set.
template < typename U>
U operator ()();
};구현 시 호환성이 필요한 경우 제공된 함수 객체에 직렬화/역직렬화하는 유형의 이진 호환성(엔디안, 부동 소수점 이진 표현, int 크기 등)이 남아 있습니다.
serialize 및 deserialize 메서드에 대한 자세한 내용은 API에서 확인할 수 있습니다.
# include < cassert >
# include < cstdint >
# include < fstream >
# include < type_traits >
# include < tsl/ordered_map.h >
class serializer {
public:
explicit 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 operator ()( const T& value) {
m_ostream. write ( reinterpret_cast < const char *>(&value), sizeof (T));
}
void operator ()( const std::pair<std:: int64_t , std:: int64_t >& value) {
(* this )(value. first );
(* this )(value. second );
}
private:
std::ofstream m_ostream;
};
class deserializer {
public:
explicit 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);
}
template < class T >
T operator ()() {
T value;
deserialize (value);
return value;
}
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::ordered_map<std:: int64_t , std:: int64_t > map = {{ 1 , - 1 }, { 2 , - 2 }, { 3 , - 3 }, { 4 , - 4 }};
const char * file_name = " ordered_map.data " ;
{
serializer serial (file_name);
map. serialize (serial);
}
{
deserializer dserial (file_name);
auto map_deserialized = tsl::ordered_map<std:: int64_t , std:: int64_t >:: deserialize (dserial);
assert (map == map_deserialized);
}
{
deserializer dserial (file_name);
/* *
* If the serialized and deserialized map are hash compatibles (see conditions in API),
* setting the argument to true speed-up the deserialization process as we don't have
* to recalculate the hash of each key. We also know how much space each bucket needs.
*/
const bool hash_compatible = true ;
auto map_deserialized =
tsl::ordered_map<std:: int64_t , std:: int64_t >:: deserialize (dserial, hash_compatible);
assert (map == 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/ordered_map.h >
namespace boost { namespace serialization {
template < class Archive , class Key , class T >
void serialize (Archive & ar, tsl::ordered_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::ordered_map<Key, T>& map, const unsigned int /* version */ ) {
auto serializer = [&ar]( const auto & v) { ar & v; };
map. serialize (serializer);
}
template < class Archive , class Key , class T >
void load (Archive & ar, tsl::ordered_map<Key, T>& map, const unsigned int /* version */ ) {
auto deserializer = [&ar]< typename U>() { U u; ar & u; return u; };
map = tsl::ordered_map<Key, T>:: deserialize (deserializer);
}
}}
int main () {
tsl::ordered_map<std:: int64_t , std:: int64_t > map = {{ 1 , - 1 }, { 2 , - 2 }, { 3 , - 3 }, { 4 , - 4 }};
const char * file_name = " ordered_map.data " ;
{
std::ofstream ofs;
ofs. exceptions (ofs. badbit | ofs. failbit );
ofs. open (file_name, std::ios::binary);
boost::iostreams::filtering_ostream fo;
fo. push ( boost::iostreams::zlib_compressor ());
fo. push (ofs);
boost::archive::binary_oarchive oa (fo);
oa << map;
}
{
std::ifstream ifs;
ifs. exceptions (ifs. badbit | ifs. failbit | ifs. eofbit );
ifs. open (file_name, std::ios::binary);
boost::iostreams::filtering_istream fi;
fi. push ( boost::iostreams::zlib_decompressor ());
fi. push (ifs);
boost::archive::binary_iarchive ia (fi);
tsl::ordered_map<std:: int64_t , std:: int64_t > map_deserialized;
ia >> map_deserialized;
assert (map == map_deserialized);
}
}코드는 MIT 라이선스에 따라 라이선스가 부여됩니다. 자세한 내용은 LICENSE 파일을 참조하세요.
