ordered map
v1.1.0
توفر مكتبة الخرائط المرتبة خريطة تجزئة ومجموعة تجزئة تحافظ على ترتيب الإدراج بطريقة مشابهة لـ OrderedDict في Python. عند التكرار على الخريطة، سيتم إرجاع القيم بنفس الترتيب الذي تم إدراجها به.
يتم تخزين القيم بشكل متجاور في البنية الأساسية، ولا توجد فجوات بين القيم حتى بعد عملية المسح. بشكل افتراضي، يتم استخدام std::deque لهذه البنية، ولكن من الممكن أيضًا استخدام std::vector . يمكن الوصول إلى هذه البنية مباشرة من خلال طريقة values_container() وإذا كانت البنية std::vector ، فسيتم أيضًا توفير طريقة data() للتفاعل بسهولة مع واجهات برمجة التطبيقات C. يوفر هذا تكرارًا سريعًا ولكن مع عيب عملية المسح 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 .
ملاحظة : تستخدم المكتبة قوة اثنين لحجم مصفوفة الدلاء الخاصة بها للاستفادة من المعامل السريع. للحصول على أداء جيد، يتطلب الأمر أن يكون لجدول التجزئة وظيفة تجزئة موزعة بشكل جيد. إذا واجهت مشكلات في الأداء، فتحقق من وظيفة التجزئة لديك.
tsl::ordered_map من CMakeLists.txt.std::unordered_map ولكن مع عمليات إدراج أسرع واستخدام أقل للذاكرة (راجع المعيار لمزيد من التفاصيل).find بنوع مختلف عن Key (على سبيل المثال، إذا كان لديك خريطة تستخدم std::unique_ptr<foo> كمفتاح، فيمكنك استخدام foo* أو std::uintptr_t كمعلمة رئيسية لـ find دون إنشاء std::unique_ptr<foo> ، انظر المثال).precalculated_hash في API).serialize/deserialize في واجهة برمجة التطبيقات للحصول على التفاصيل).-fno-exceptions في Clang وGC، بدون خيار /EH على MSVC أو ببساطة عن طريق تحديد 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 (راجع واجهة برمجة التطبيقات لمزيد من التفاصيل). إذا كنت تستخدم std::vector كـ ValueTypeContainer ، فيمكنك استخدام reserve() لتخصيص بعض المساحة مسبقًا وتجنب إبطال المكررات عند الإدراج.erase() لها تعقيد O (bucket_count). يوجد إصدار أسرع من O(1) unordered_erase() ، ولكنه يكسر ترتيب الإدراج (راجع واجهة برمجة التطبيقات لمزيد من التفاصيل). يتوفر أيضًا O(1) pop_back() .operator== operator!= يعتمدان على الترتيب. لا يمكن مقارنة اثنين من tsl::ordered_map بنفس القيم ولكن تم إدراجهما بترتيب مختلف.operator*() operator->() بإرجاع مرجع ومؤشر إلى const std::pair<Key, T> بدلاً من std::pair<const 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 ، تحقق من واجهة برمجة التطبيقات للحصول على التفاصيل.bucket_size ، bucket ، ...). ضمان سلامة سلسلة الرسائل هو نفسه std::unordered_map (أي من الممكن أن يكون لديك عدة قراء متزامنين بدون كاتب).
تنطبق هذه الاختلافات أيضًا بين std::unordered_set و tsl::ordered_set .
إذا لم يتم ذكر خلاف ذلك، تتمتع الوظائف بضمان الاستثناء القوي، راجع التفاصيل. ندرج أدناه الحالات التي لا يتم فيها توفير هذا الضمان.
يتم توفير الضمان فقط إذا كانت ValueContainer::emplace_back تتمتع بضمان الاستثناء القوي (وهو ما ينطبق على std::vector و std::deque طالما أن النوع T ليس من النوع القابل للتحريك فقط مع مُنشئ النقل الذي قد يرمي استثناء، انظر التفاصيل).
تتمتع وظائف tsl::ordered_map::erase_if و tsl::ordered_set::erase_if بالضمان فقط بموجب الشروط المسبقة المدرجة في وثائقها.
لاستخدام الخريطة المرتبة، ما عليك سوى إضافة دليل التضمين إلى مسار التضمين الخاص بك. إنها مكتبة رأسية فقط .
إذا كنت تستخدم CMake، فيمكنك أيضًا استخدام الهدف المُصدَّر tsl::ordered_map من CMakeLists.txt مع target_link_libraries .
# 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 ، فيمكنك أيضًا استخدام find_package(tsl-ordered-map REQUIRED) بدلاً من add_subdirectory .
يجب أن تعمل التعليمات البرمجية مع أي مترجم متوافق مع معيار C++ 11 وقد تم اختبارها مع دول مجلس التعاون الخليجي 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 يمكن العثور على واجهة برمجة التطبيقات هنا.
# 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 ، يجب أن يكون المعرف المؤهل 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 ()();
};لاحظ أن التنفيذ يترك التوافق الثنائي (endianness، التمثيل الثنائي العائم، حجم int، ...) للأنواع التي يقوم بتسلسلها/إلغاء تسلسلها في أيدي كائنات الوظيفة المتوفرة إذا كان التوافق مطلوبًا.
يمكن العثور على مزيد من التفاصيل بشأن طرق serialize deserialize في واجهة برمجة التطبيقات.
# 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 Serialization مع تدفق ضغط Boost zlib لتقليل حجم الملف المتسلسل الناتج. يتطلب المثال لغة C++20 نظرًا لاستخدام بنية قائمة معلمات القالب في lambdas، ولكن يمكن تكييفها مع الإصدارات الأقل حداثة.
# 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، راجع ملف الترخيص للحصول على التفاصيل.
