ordered map
v1.1.0
Библиотека упорядоченных карт предоставляет хеш-карту и хеш-набор, которые сохраняют порядок вставки аналогично OrderedDict в Python. При переборе карты значения будут возвращены в том же порядке, в котором они были вставлены.
Значения хранятся в базовой структуре последовательно, без пробелов между значениями даже после операции стирания. По умолчанию для этой структуры используется std::deque , но также можно использовать std::vector . Эта структура доступна напрямую через values_container() , а если структура представляет собой std::vector , также предоставляется метод data() для простого взаимодействия с API C. Это обеспечивает быструю итерацию, но с недостатком операции стирания O(bucket_count). Доступны функции pop_back() O(1) и unordered_erase() O(1). Если часто используется упорядоченное стирание, рекомендуется использовать другую структуру данных.
Для разрешения коллизий хэшей библиотека использует линейное зондирование Робин Гуда с удалением обратного сдвига.
Библиотека обеспечивает поведение, аналогичное 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 в API).-fno-exceptions в Clang и GCC, без опции /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 (подробнее см. API). Если вы используете std::vector как ValueTypeContainer , вы можете использовать reserve() чтобы предварительно выделить некоторое пространство и избежать признания итераторов недействительными при вставке.erase() , ее сложность составляет O(bucket_count). Существует более быстрая версия O(1) unordered_erase() , но она нарушает порядок вставки (подробнее см. API). Также доступен pop_back() O(1).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 . Подробности можно узнать в API.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, и был протестирован с 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 , квалифицированный идентификатор 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 используется с потоком сжатия Boost zlib, чтобы уменьшить размер результирующего сериализованного файла. Для примера требуется 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.
