C++ hash map and hash set which preserve the order of insertion

Overview

Build Status Build status

C++ hash map and hash set which preserves the order of insertion

The ordered-map library provides a hash map and a hash set which preserve the order of insertion in a way similar to Python's OrderedDict. When iterating over the map, the values will be returned in the same order as they were inserted.

The values are stored contiguously in an underlying structure, no holes in-between values even after an erase operation. By default a std::deque is used for this structure, but it's also possible to use a std::vector. This structure is directly accessible through the values_container() method and if the structure is a std::vector, a data() method is also provided to easily interact with C APIs. This provides fast iteration but with the drawback of an O(n) erase operation. An O(1) pop_back() and an O(1) unordered_erase() functions are available.

To resolve collisions on hashes, the library uses linear robin hood probing with backward shift deletion.

The library provides a behaviour similar to a std::deque/std::vector with unique values but with an average time complexity of O(1) for lookups and an amortised time complexity of O(1) for insertions. This comes at the price of a little higher memory footprint (8 bytes per bucket by default).

Two classes are provided: tsl::ordered_map and tsl::ordered_set.

Note: The library uses a power of two for the size of its buckets array to take advantage of the fast modulo. For good performances, it requires the hash table to have a well-distributed hash function. If you encounter performance issues check your hash function.

Key features

  • Header-only library, just add the include directory to your include path and you are ready to go. If you use CMake, you can also use the tsl::ordered_map exported target from the CMakeLists.txt.
  • Values are stored in the same order as the insertion order. The library provides a direct access to the underlying structure which stores the values.
  • O(1) average time complexity for lookups with performances similar to std::unordered_map but with faster insertions and reduced memory usage (see benchmark for details).
  • Provide random access iterators and also reverse iterators.
  • Support for heterogeneous lookups allowing the usage of find with a type different than Key (e.g. if you have a map that uses std::unique_ptr<foo> as key, you can use a foo* or a std::uintptr_t as key parameter to find without constructing a std::unique_ptr<foo>, see example).
  • If the hash is known before a lookup, it is possible to pass it as parameter to speed-up the lookup (see precalculated_hash parameter in API).
  • Support for efficient serialization and deserialization (see example and the serialize/deserialize methods in the API for details).
  • The library can be used with exceptions disabled (through -fno-exceptions option on Clang and GCC, without an /EH option on MSVC or simply by defining TSL_NO_EXCEPTIONS). std::terminate is used in replacement of the throw instruction when exceptions are disabled.
  • API closely similar to std::unordered_map and std::unordered_set.

Differences compared to std::unordered_map

tsl::ordered_map tries to have an interface similar to std::unordered_map, but some differences exist.

  • The iterators are RandomAccessIterator.
  • Iterator invalidation behaves in a way closer to std::vector and std::deque (see API for details). If you use std::vector as ValueTypeContainer, you can use reserve() to preallocate some space and avoid the invalidation of the iterators on insert.
  • Slow erase() operation, it has a complexity of O(n). A faster O(1) version unordered_erase() exists, but it breaks the insertion order (see API for details). An O(1) pop_back() is also available.
  • The equality operators operator== and operator!= are order dependent. Two tsl::ordered_map with the same values but inserted in a different order don't compare equal.
  • For iterators, operator*() and operator->() return a reference and a pointer to const std::pair<Key, T> instead of std::pair<const Key, T> making the value T not modifiable. To modify the value you have to call the value() method of the iterator to get a mutable reference. Example:
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
}
  • By default the map can only hold up to 232 - 1 values, that is 4 294 967 295 values. This can be raised through the IndexType class template parameter, check the API for details.
  • No support for some bucket related methods (like bucket_size, bucket, ...).

Thread-safety guarantee is the same as std::unordered_map (i.e. possible to have multiple concurrent readers with no writer).

Concerning the strong exception guarantee, it holds only if ValueContainer::emplace_back has the strong exception guarantee (which is true for std::vector and std::deque as long as the type T is not a move-only type with a move constructor that may throw an exception, see details).

These differences also apply between std::unordered_set and tsl::ordered_set.

Installation

To use ordered-map, just add the include directory to your include path. It is a header-only library.

If you use CMake, you can also use the tsl::ordered_map exported target from the CMakeLists.txt with 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)  

If the project has been installed through make install, you can also use find_package(tsl-ordered-map REQUIRED) instead of add_subdirectory.

The code should work with any C++11 standard-compliant compiler and has been tested with GCC 4.8.4, Clang 3.5.0 and Visual Studio 2015.

To run the tests you will need the Boost Test library and 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 

Usage

The API can be found here.

Example

#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('\0');
    
    set.pop_back();
    set.insert({'0', '\0'});
    
    // Get raw buffer for C API: 34910
    std::cout << atoi(set.data()) << std::endl;
}

Heterogeneous lookup

Heterogeneous overloads allow the usage of other types than Key for lookup and erase operations as long as the used types are hashable and comparable to Key.

To activate the heterogeneous overloads in tsl::ordered_map/set, the qualified-id KeyEqual::is_transparent must be valid. It works the same way as for std::map::find. You can either use std::equal_to<> or define your own function object.

Both KeyEqual and Hash will need to be able to deal with the different types.

#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;
} 

Serialization

The library provides an efficient way to serialize and deserialize a map or a set so that it can be saved to a file or send through the network. To do so, it requires the user to provide a function object for both serialization and deserialization.

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()();
};

Note that the implementation leaves binary compatibility (endianness, float binary representation, size of int, ...) of the types it serializes/deserializes in the hands of the provided function objects if compatibility is required.

More details regarding the serialize and deserialize methods can be found in the 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);
    }
} 
Serialization with Boost Serialization and compression with zlib

It's possible to use a serialization library to avoid the boilerplate.

The following example uses Boost Serialization with the Boost zlib compression stream to reduce the size of the resulting serialized file. The example requires C++20 due to the usage of the template parameter list syntax in lambdas, but it can be adapted to less recent versions.

#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);
    }
}

License

The code is licensed under the MIT license, see the LICENSE file for details.

Comments
  • Packaging for conda

    Packaging for conda

    Hi,

    I just discovered this project (and the related ones) and find it really cool! We are considering adopting it for the xframe project, in order to do that I need to package it for conda.

    ordered-map is a too much generic name, so I was thinking of tsl_ordered_map, are you ok with that? Or do you prefer a different name?

    opened by JohanMabille 8
  • Recursive container

    Recursive container

    Hi! It seems the following code example doesn't work due to the std::deque<std::pair<...>> type used.

    class foo {
      tsl::ordered_map<foo, foo> map;
      bool operator==(const foo&) const;
    };
    
    namespace std {
      template <> struct hash<foo> {
    .....
      };
    }
    

    However, std::unordered_map works in this situation. I use Visual Studio 2015 Update 3.

    opened by Nekotekina 8
  • installation with cmake

    installation with cmake

    This PR enables installing ordered_map with cmake. This way packages managers can rely on a single method to install it instead of developing their own processes.

    EDIT: with that change, the CMakeLists.txt must be updated for each release so the number version matches the release tag. Another solution is to add a ordered_map_version.h file and retrieve the number from that file in the CMakeLists.txt. That still requires updating a file for a release, but it might be easier to remember.

    opened by JohanMabille 7
  • How can I insert into a specific position?

    How can I insert into a specific position?

    tsl::ordered_set<int> test{1, 3, 5, 7, 9}; I want to insert number 6 into between 5 and 7. Expected result: {1, 3, 5, 6, 7, 9} The below code always inserts into last position.

    tsl::ordered_set<int> test{1, 3, 5, 7, 9};
    test.insert(test.begin() + 3, 6);
    std::cout << "ordered_set: ";
    for (auto & i : test)
    {
            std::cout << i << " ";
    }
    std::cout <<"\n\n";
    

    output: ordered_set: 1 3 5 7 9 6

    opened by Mark-Joy 5
  • Non-const dereferencing

    Non-const dereferencing

    Hi, thanks for this great library.

    I realized iterator doesn't have non-const variant of operator*(), which is also explicitly stated in the README. value() function is recommended instead, but it doesn't play well with range-loops where values need to be mutated.

    Example code:

    #include "tsl/ordered_map.h"
    
    int main() {
        tsl::ordered_map<int, int> m;
        for (auto& v: m) {
            int& value = v.second;
        }
    }
    
    $ g++ --version 
    g++ (Debian 8.3.0-6) 8.3.0
    Copyright (C) 2018 Free Software Foundation, Inc.
    This is free software; see the source for copying conditions.  There is NO
    warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
    
    $ g++ -std=c++11 test.cpp -o test
    test.cpp: In function ‘int main()’:
    test.cpp:6:24: error: binding reference of type ‘int&’ to ‘const int’ discards qualifiers
             int& value = v.second;
                          ~~^~~~~~
    

    Is there a specific reason for disallowing it or is it just that it's not implemented? Thanks.

    opened by ozars 4
  • Runtime error

    Runtime error

    $ ./test_ordered_map
    libc++abi.dylib: terminating with uncaught exception of type boost::unit_test::framework::setup_error: test unit with name 'test_insert<tsl__ordered_map<long long, long long, std____1__hash<long long>, std____1__equal_to<long long>, std____1__allocator<std____1__pair<long long, long long> >, std____1__deque<std____1__pair<long long, long long>, std____1__allocator<std____1__pair<long long, long long> > > >>' registered multiple times
    [1]    48387 abort      ./test_ordered_map
    
    opened by dendisuhubdy 4
  • tsl::ordered_map<int, const std::string> failed to compile

    tsl::ordered_map failed to compile

    The below code is compiled just fine with previous version - when ordered_map, set, and hash are in the same file (ordered_map.h).

    With latest library, the below code failed to compile if string is const

    const tsl::ordered_map<int, const std::string> testmap{
        { 0, "Test1" },
        { 1, "Test2" },
     };
    

    The below code with no const compile just fine with latest library

    const tsl::ordered_map<int, std::string> testmap{
        { 0, "Test1" },
        { 1, "Test2" },
     };
    
    opened by Mark-Joy 4
  • Compilation error using GCC 8 RC

    Compilation error using GCC 8 RC

    Using MinGW GCC 8 RC from here. There is the compilation error when using the following code:

    template<class Key, class T, class Ignore, class Allocator, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
    using ordered_map = tsl::ordered_map<Key, T, Hash, KeyEqual, Allocator>;
    
    using namespace nlohmann;
    using json_ord = basic_json<ordered_map>;
    
    inline json_ord operator "" _json_ord(const char* s, std::size_t n)
    {
        return json_ord::parse(s, s + n);
    }
    
    inline json_ord::json_pointer operator "" _json_ord_pointer(const char* s, std::size_t n)
    {
        return json_ord::json_pointer(std::string(s, n));
    }
    
    
    void main()
    {
         auto js { R"({"3":null, "1":"the middle one...", "2":null})"_json_ord };
    }
    

    This is the following error:

    In file included from C:/MinGW/include/c++/8.0.1/deque:64,
                     from ordered-map/tsl/ordered_map.h:29,
    C:/MinGW/include/c++/8.0.1/bits/stl_deque.h: In instantiation of 'class std::deque<std::pair<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> >, s
    td::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> > > >':
    external/ordered-map/tsl/ordered_hash.h:213:97:   required from 'class tsl::detail_ordered_hash::ordered_hash<std::pair<std::__cxx11::basic_string<char>, nlohmann::basic_j
    son<ordered_map> >, tsl::ordered_map<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map>, std::hash<std::__cxx11::basic_string<char> >, std::eq
    ual_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> > >, std::deque<std::pa
    ir<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_json<nstd:
    :ordered_map> > > > >::KeySelect, tsl::ordered_map<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map>, std::hash<std::__cxx11::basic_string<char> >,
     std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> > >, std::deque
    <std::pair<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_js
    on<ordered_map> > > > >::ValueSelect, std::hash<std::__cxx11::basic_string<char> >, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const
    std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> > >, std::deque<std::pair<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_ma
    p> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> > > > >'
    external/ordered-map/tsl/ordered_map.h:106:43:   required from 'class tsl::ordered_map<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map>, std::hash
    <std::__cxx11::basic_string<char> >, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_jso
    n<ordered_map> > >, std::deque<std::pair<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> >, std::allocator<std::pair<const std::__cxx11::ba
    sic_string<char>, nlohmann::basic_json<ordered_map> > > > >'
    external/json/include/nlohmann/json.hpp:2970:15:   required from 'class nlohmann::basic_json<ordered_map>'
    json.hpp.cpp:40:79:   required from here
    C:/MinGW/include/c++/8.0.1/bits/stl_deque.h:847:21: error: static assertion failed: std::deque must have the same value_type as its allocator
           static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    
    opened by Ptomaine 4
  • 64 bit bucket_entry

    64 bit bucket_entry

    • The map can only hold up to 232 - 1 values, that is 4 294 967 295 values.

    Is there any reason for restricting it to 32 bit indexes? Could 264 - 1 values be supported with just a trivial change?

    in ordered_hash.h, the indexes are defined as 32 bit:

    class bucket_entry
    {
    public:
    	using index_type = std::uint_least32_t;
    	using truncated_hash_type = std::uint_least32_t;
    

    defining them as 64 bit would be:

    	using index_type = std::uint64_t;
    	using truncated_hash_type = std::uint64_t;
    

    Besides additional memory usage, are there any implications of allowing 64 bit indexes?

    opened by Peach1 3
  • Visual Studio 2017 and ordered-map

    Visual Studio 2017 and ordered-map

    Hi! Thank you for your numerous contributions, @Tessil !!

    I know you are familiarized with nlohmann/json and Tessil/ordered-map interaction:

    https://github.com/Tessil/ordered-map/issues/9 https://github.com/nlohmann/json/issues/546

    I need a ordered json and i am using your way. I have test this code in MinGW gcc 7.30 and it works!

    This sample is the adaptacion of nlohmann/json sample to Tessil/ordered-map, I tried to follow your instruction. Sorry for my inexperience. :-|

    #include <string>
    #include <iostream>
    #include <nlohmann/json.hpp>
    #include <tsl/ordered_map.h>
    #include <tsl/ordered_set.h>
    
    template<class Key, class T, class Ignore, class Allocator,
    	class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
    
    	using ordered_map = tsl::ordered_map<Key, T, Hash, KeyEqual,
    	typename std::allocator_traits<Allocator>::template
    	rebind_alloc<std::pair<Key, T>>>;
    
    
    using json = nlohmann::basic_json<ordered_map>; //It only works in MinGW 7.3.0 (the json is ordered :-))
    
    //using json = nlohmann::json; //It works in MSVC2017 and MinGW 7.3.0
    
    namespace ns {
    
    	// a simple struct to model a person
    	struct person {
    		std::string name;
    		std::string address;
    		int age;
    	};
    //}
    
    
    //namespace ns {
    
    
    	void to_json(json& j, const person& p) {
    		j = json{ { "name", p.name },{ "address", p.address },{ "age", p.age } };
    	}
    
    	void from_json(const json& j, person& p) {
    		p.name = j.at("name").get<std::string>();
    		p.address = j.at("address").get<std::string>();
    		p.age = j.at("age").get<int>();
    	}
    } // namespace ns
    
    
    int main()
    {
    	// create a person
    	ns::person p{ "Ned Flanders", "744 Evergreen Terrace", 60 };
    
    	// conversion: person -> json
    	json j = p;
    
    	std::cout << j << std::endl;
    	// {"address":"744 Evergreen Terrace","age":60,"name":"Ned Flanders"}
    
    	// conversion: json -> person
    	ns::person p2 = j;
    
    	// that's it
    	//assert(p == p2);
    }
    

    I get the next error in Visual Studio 2017( 15.7.1 ) (Windows 10 x64)

    1>------ Build started: Project: prueba, Configuration: Debug x64 ------
    1>main.cpp
    1>c:\program files (x86)\microsoft visual studio\2017\enterprise\vc\tools\msvc\14.14.26428\include\utility(293): error C2079: 'std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>::second' uses undefined class 'nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>'
    1>        with
    1>        [
    1>            StringType=std::string
    1>        ]
    1>c:\program files (x86)\microsoft visual studio\2017\enterprise\vc\tools\msvc\14.14.26428\include\deque(967): note: see reference to class template instantiation 'std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>' being compiled
    1>        with
    1>        [
    1>            StringType=std::string
    1>        ]
    1>p:\mis-proyectos\profesional\prueba\prueba\prueba\tsl\ordered_hash.h(215): note: see reference to class template instantiation 'std::deque<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,Allocator>' being compiled
    1>        with
    1>        [
    1>            StringType=std::string,
    1>            Allocator=std::allocator<std::pair<std::string,nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>
    1>        ]
    1>p:\mis-proyectos\profesional\prueba\prueba\prueba\tsl\ordered_map.h(106): note: see reference to class template instantiation 'tsl::detail_ordered_hash::ordered_hash<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,tsl::ordered_map<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>,std::hash<std::basic_string<char,std::char_traits<char>,std::allocator<char>>>,std::equal_to<Key>,std::allocator<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>,std::deque<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,Allocator>>::KeySelect,tsl::ordered_map<Key,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>,std::hash<std::basic_string<char,std::char_traits<char>,std::allocator<char>>>,std::equal_to<Key>,Allocator,std::deque<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,Allocator>>::ValueSelect,Hash,KeyEqual,Allocator,ValueTypeContainer>' being compiled
    1>        with
    1>        [
    1>            StringType=std::string,
    1>            Key=std::string,
    1>            Allocator=std::allocator<std::pair<std::string,nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>,
    1>            Hash=std::hash<std::basic_string<char,std::char_traits<char>,std::allocator<char>>>,
    1>            KeyEqual=std::equal_to<std::string>,
    1>            ValueTypeContainer=std::deque<std::pair<std::string,nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,std::allocator<std::pair<std::string,nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>>
    1>        ]
    1>p:\mis-proyectos\profesional\prueba\prueba\prueba\nlohmann\json.hpp(12791): note: see reference to class template instantiation 'tsl::ordered_map<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>,std::hash<std::basic_string<char,std::char_traits<char>,std::allocator<char>>>,std::equal_to<Key>,std::allocator<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>,std::deque<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,Allocator>>' being compiled
    1>        with
    1>        [
    1>            StringType=std::string,
    1>            Key=std::string,
    1>            Allocator=std::allocator<std::pair<std::string,nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>
    1>        ]
    1>p:\mis-proyectos\profesional\prueba\prueba\prueba\main.cpp(36): note: see reference to class template instantiation 'nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>' being compiled
    1>Done building project "prueba.vcxproj" -- FAILED.
    ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
    

    Could you help me? Thanks!

    DJuego

    opened by DJuego 3
  • Serialize with boost and C++11/14

    Serialize with boost and C++11/14

    I'm looking to serialize an ordered-map with boost_serialization.

    I have seen the below code for splitting into save and load, and using the serialize/deserialize methods of ordered_map, however being unfamiliar with lambdas I am not sure how to adapt this to work with C++11 or C++14.

    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);
    }
    

    How would this be done without using templated parameters in the deserializer lambda?

    opened by k-vernooy 2
  • Add an erase_if function

    Add an erase_if function

    This PR adds an erase_if function to the map that removes all elements that satisfy a predicate. The function preserves the insertion order shifting elements if necessary. It runs in O(n). I think that with the current interface it is only possible to implement something running in O(n^2).

    C++20 adds a free-standing erase_if function for maps. The function here is defined in a similar way.

    opened by rkaminsk 11
  • `tsl::ordered_set<bool>` with `std::vector`

    `tsl::ordered_set` with `std::vector`

    The readme says it's possible to use the containers with std::vector instead of std::deque. However, after changing that in ordered_set.h, the following code crashes under GCC 7.2.0, probably due to the strange specialization of std::vector<bool>.

    #include <iostream>
    
    #include "include/tsl/ordered_set.h"
    
    int main() {
        tsl::ordered_set<bool> a;
        a.insert(true);
    
        tsl::ordered_set<bool> b;
        b.insert(a.begin(), a.end());
    
        std::cout << b.size() << std::endl;
    }
    

    There is also a warning:

    lib/tsl/ordered_hash.h:387:43: warning: returning reference to temporary [-Wreturn-local-addr]
         reference operator*() const { return *m_iterator; }
                                               ^~~~~~~~~~
    

    A workaround is to keep std::deque just for bool.

    class ValueTypeContainer = typename std::conditional<
        std::is_same<Key, bool>::value,
        typename std::deque<Key, Allocator>,
        typename std::vector<Key, Allocator>>::type,
    

    Is this the reason why std::deque is used by default? I've found that std::vector makes the containers somewhat faster (though they're much faster than the default unordered containers in STL anyway).

    opened by adamsol 2
  • Eliminating the difference in what an iterator yields

    Eliminating the difference in what an iterator yields

    From your documentation you have this:

    For iterators, operator*() and operator->() return a reference and a pointer to const std::pair<Key, T> instead of std::pair<const Key, T> making the value T not modifiable. To modify the value you have to call the value() method of the iterator to get a mutable reference. Example:

    Is this something that could be eliminated? I.e. the divergence between ordered_map and unordered_map? I have code that iterates over an unordered_map in parallel using std::for_each. I need to modify the T values but with ordered_map I can't do this because the callback provided to for_each receives the dereferenced iterator, i.e. I end up with a const std::pair<Key, T> and thus have no way of calling value to get a modifiable T.

    It also pops up in using the ranged-for loops:

    for(auto& foo : some_ordered_map)

    foo here is again const std::pair<Key, T> and thus I can't possibly call value even if I wanted to, meaning I have to change all ranged-for loops to be the older, non-ranged style.

    opened by ryanmolden 5
Releases(v1.0.0)
  • v1.0.0(Jun 22, 2020)

  • v0.8.1(Feb 17, 2019)

    • Fix compilation error with GCC 9, the implicit copy/move constructor/operator of the iterator were not generated.
    • Fix issue #23, rename the internal insert with hint method to insert_hint to avoid a potential ambiguous overload with the insert with a pair of iterators.
    Source code(tar.gz)
    Source code(zip)
  • v0.8.0(Jan 27, 2019)

    • Rename CMake project name from tsl_ordered_map to tsl-ordered-map for coherence with the convention used by most package managers. The find_package(tsl-ordered-map) command must now be used instead of the find_package(tsl_ordered_map).
    • Set bucket count for default constructed map/set to 0 to avoid any allocation.
    • Fix CMake >= 3.13 warning on Policy CMP0076 and add quotes to paths.
    • Remove cxx_std_11 from target_compile_features to avoid a warning with older versions of CMake that don't support it. The warning was given even if the target_compile_features was surrounded in a if(${CMAKE_VERSION} VERSION_GREATER "3.7").
    • Fix bug where using rehash(0) on an empty map with a bucket_count > 0 would result in an invalid m_buckets pointer leading to potential segfaults.
    Source code(tar.gz)
    Source code(zip)
  • v0.7.1(Nov 3, 2018)

  • v0.7.0(Oct 12, 2018)

    • Add MSVC debugger visualization .natvis file (#20).
    • Fix issue in erase and insert_at_position on platforms where the char type is unsigned.
    • Add installation rules in the CMake of the project (#22).
    Source code(tar.gz)
    Source code(zip)
  • v0.6.0(Aug 6, 2018)

    This release introduce a minor backward incompatibility by moving the headers files.

    • Move the header files from tsl to include/tsl for more coherence with other C++ libraries.
    • For CMake users, add an exported target tsl::ordered_map to be used with target_link_libraries.
    Source code(tar.gz)
    Source code(zip)
  • v0.5.0(Aug 4, 2018)

    • In max_load_factor(float ml), check that the ml parameter is in the range [0.1, 0.95].
    • Bug correction, restore support for copy constructible only objects as key or value in a map (#11) .
    • Bug correction, set a moved hash map/set in a valid state so that it can still be used even after a move. (#17)
    • Add the possibility to use the library without exceptions (#13)
    • Add support for large maps/sets (more than 2^32 - 1 elements) through an extra class template parameter (#18)
    Source code(tar.gz)
    Source code(zip)
  • v0.4.0(Aug 12, 2017)

    • Split ordered_map.h into ordered_hash.h, ordered_map.h and ordered_set.h.
    • Move header files from src directory to tsl directory
    • Reduce default max load factor to 0.75.
    • Bug correction in equal_range, the second iterator was always equal to the first.
    • Add methods taking a precalculated hash for lookups.
    • Correct amount of reserved space for range insert.
    • Use uint_least32_t instead of uint32_t for portability.
    • Bug correction in 'iterator erase(const_iterator first, const_iterator last)`.
    • Add insert_at_position, emplace_at_position and try_emplace_at_position methods.
    • Correct method signature of emplace_hint.
    Source code(tar.gz)
    Source code(zip)
  • v0.3.0(Jul 11, 2017)

    • Add try_emplace and insert_or_assign methods (#7).
    • Bug correction (#5) for the clear() method.
    • Use 'Empty Base Optimization' for Hash and KeyEqual to reduce the sizeof(tsl::ordered_map/set).
    • Add iterator nth(size_type index) method.
    • Add missing method for operator+ in iterators (#4).
    • Bug correction, check that we are not over max_size() when inserting a new element.
    Source code(tar.gz)
    Source code(zip)
  • v0.2.0(Mar 12, 2017)

    • Add support for GCC 4 8.4.
    • Bug correction, swap was recursing infinitely.
    • Reduce identifiers length to avoid VS 'decorated name length exceeded' (C4503) warning.
    Source code(tar.gz)
    Source code(zip)
Owner
Thibaut Goetghebuer-Planchon
Thibaut Goetghebuer-Planchon
C++ implementation of a fast hash map and hash set using robin hood hashing

A C++ implementation of a fast hash map and hash set using robin hood hashing The robin-map library is a C++ implementation of a fast hash map and has

Thibaut Goetghebuer-Planchon 878 Jan 2, 2023
Rajesh Kumar Sah 1 Nov 20, 2021
A fast hash map/hash table (whatever you want to call it) for the C programming language.

C HashMap A fast hash map/hash table (whatever you want to call it) for the C programming language. It can associate a key with a pointer or integer v

Mashpoe 74 Dec 27, 2022
A drop-in replacement for std::list with 293% faster insertion, 57% faster erasure, 17% faster iteration and 77% faster sorting on average. 20-24% speed increase in use-case testing.

plf::list A drop-in replacement for std::list with (on average): 293% faster insertion 57% faster erasure 17% faster iteration 77% faster sorting 70%

Matt Bentley 117 Nov 8, 2022
Bit-Map is a simple bit map.

Bit-Map Bit-Map is a simple bit map. Usage Create a map uint8** bitmap; uint64 map_size = 32; // bit number pfs_create_bitmap(bitmap,

Pink 2 Feb 18, 2022
A benchmark for hash tables and hash functions in C++, evaluate on different data as comprehensively as possible

Hash Table Benchmark This is yet another benchmark for hash tables(hash maps) with different hash functions in C++, attempting to evaluate the perform

Ren Zibei 3 Oct 18, 2022
Explore building a hash table with two different hash functions that balances chain length

hash-duo Explore building a hash table with two different hash functions that balances chain length. There is a really cool article called Don't Throw

Terence Parr 3 May 7, 2022
Unofficial .hmap map viewer for HumandKind

bhkmap Main Features Read/Write .hmap files Display elevation level, territories, biomes, tile types, strategic resources, luxury resources, natural w

null 6 Nov 6, 2022
Header-only compile time key-value map written in C++20.

C++ Static Map Header-only compile time key-value map written in C++20. Getting Started Simply add the files in your source and #include "@dir/Static_

null 1 Oct 19, 2021
Diablo II Resurrected map revealing tool.

D2RMH Diablo II Resurrected map revealing tool. What's New v0.2 add display for Unique Chest, Well, neighbour map path fix display of correct taltomb

Soar Qin 148 Dec 30, 2022
A simple single header 64 and 32 bit hash function using only add, sub, ror, and xor.

K-HASH A simple single header 64 bit hash function using only add, sub, ror, and xor. This a just general-purpose hash function for like making hash m

null 70 Dec 27, 2022
Simple hash table implemented in C

Simple hash table written in C. To go with my article How to implement a hash table (in C). This is a learning exercise, not a battle-tested data stru

Ben Hoyt 86 Dec 10, 2022
simple hash table linear probing method can expand/reduce

hash table a simple c hash table implementation based on https://benhoyt.com/writings/hash-table-in-c/ project can store different data types (data al

Fabio Murer 1 Oct 3, 2021
Very Fast Non-Cryptographic Hash Function

KOMIHASH - Very Fast Hash Function Introduction The komihash() function available in the komihash.h file implements a very fast 64-bit hash function,

Aleksey Vaneev 94 Dec 12, 2022
HashTableBenchmark - A simple cross-platform speed & memory-efficiency benchmark for the most common hash-table implementations in the C++ world

Hash-Tables Benchmarks This repository contains a bunch of extendable benchmarks mostly for following containers: std:unordered_map from STL. google::

Unum 9 Nov 20, 2022
A collection of hash tables for parallel programming, including lock-free, wait-free tables.

Hatrack Hash tables for parallel programming This project consisists of fast hash tables suitable for parallel programming, including multiple lock-fr

null 62 Dec 13, 2022
This is a beginner-friendly project aiming to build a problem-set on different data structures and algorithms in different programming languages.

DSAready Overview This is a beginner-friendly project that aims to create a problem-set for various Data Structures and Algorithms. Being a programmer

Riddhi Jain 13 Aug 17, 2022