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 つのクラスが提供されています。
注: ライブラリは、高速モジュロを利用するために、バケット配列のサイズに 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によく似ています。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!=は順序に依存します。同じ値を持つ 2 つのtsl::ordered_map異なる順序で挿入された場合、等しく比較されません。operator*()とoperator->()は、 std::pair<const Key, T> const std::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::vector型Tがstd::deque例外、詳細を参照してください)。
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 Serialization を使用して、生成されるシリアル化ファイルのサイズを削減します。この例では、ラムダでテンプレート パラメーター リスト構文を使用するため、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 ファイルを参照してください。
