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

Last update: Dec 2, 2022

Overview

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 2³² - 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

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
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

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?
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

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

$ ./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 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

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
The map can only hold up to 2³² - 1 values, that is 4 294 967 295 values.

Is there any reason for restricting it to 32 bit indexes? Could 2⁶⁴ - 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

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

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

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` 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

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)
Fix issue #24, add support for efficient serialization.

Add bool contains(...) methods.

Source code(tar.gz)
Source code(zip)
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)
Fix CMakeLists.txt. Only add the CMake installation rules for version of CMake >= 3.3 to keep compatibility with CMake 3.1.

Source code(tar.gz)
Source code(zip)
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)
v0.1.0(Feb 27, 2017)

Source code(tar.gz)
Source code(zip)