nlohmann/json

Object properties should not be re-sorted alphabetically

gatopeich opened this issue · 35 comments

gatopeich commented

Usually JSON documents have a meaningful ordering of properties, and rarely it is alphabetical.

With this library all JSON data gets sorted alphabetically, which is undesirable.

I guess it must be due to use of std::map.

Please describe the steps to reproduce the issue.

#include <iostream>
#include "json.hpp"

using Json = nlohmann::json;

int main() {
  std::cout << ">>> " << Json{{"C",1},{"B",2},{"A",3}}.dump() << std::endl;
}

What is the expected behavior?

>>> {"C":1, "B":2, "A":3}

And what is the actual behavior instead?

{"A":3,"B":2,"C":1}

Which compiler and operating system are you using?

  • Compiler: clang-7 and gcc-7
  • Operating system: Ubuntu 18

Which version of the library did you use?

  • [ x ] latest release version 3.7.3
nlohmann commented

This behavior is described in the readme including ways to circumvent it.

  • 👀1
gatopeich commented

Thanks, I had missed the Order of object keys section in README.
Great library BTW.

gatopeich commented

I just want to highlight that some unordered_map example in the README does not seem to work:

std::unordered_map<const char*, double> c_umap { {"one", 1.2}, {"two", 2.3}, {"three", 3.4} };
json j_umap(c_umap);
// {"one": 1.2, "two": 2.3, "three": 3.4}

This produces exactly the same as the default:

cout << j_umap.dump() << endl;
=> {"one":1.2,"three":3.4,"two":2.3}`.
nlohmann commented

The README does not mention using std::unordered_map as workaround, but tsl::unordered_map or nlohmann::fifo_map, see https://github.com/nlohmann/json/blob/develop/README.md#order-of-object-keys.

gatopeich commented

Sure though the commented output under std::unordered_map above is misguiding. I suggest correcting it to highlight the actual order.

To preserve insertion order in my use case, I made a minimal solution based on std::vector.
Leaving it here for those who for any reason don't want to import further non-standard dependencies, or want a starting point to build their own:

/// VecMap: a minimal map-like container that preserves insertion order
/// for use within nlohmann::basic_json<VecMap>
template<class Key, class T, class IgnoredLess=std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>,
    class Container = std::vector<std::pair<const Key, T>, Allocator>>
struct VecMap : Container
{
    using key_type = Key;
    using mapped_type = T;    
    using value_type = std::pair<const Key, T>;
    using Container::Container;
    auto emplace( Key && key, T && t ) {
        for (auto it=this->begin(); it !=this->end(); ++it)
            if (it->first == key)
                return std::pair {it, false};
        this->emplace_back(key, t);
        return std::pair {--this->end(), true};
    }
    T& operator[]( Key && key ) {
        return emplace(std::move(key), T{}).first->second;
    }
};

Again, thanks for this great JSON library!

nlohmann commented

Your VecMap container is very nice and compact. Can I use this as example in the documentation?

gatopeich commented

Of course 👍

gatopeich commented

It works well in my tests.
It is an effective choice for small objects due to the low overhead of std::vector. And its algorithmic simplicity makes it a good target for compiler optimization.

    using Json = nlohmann::json;
    using FifoJson = nlohmann::basic_json<VecMap>;

    vector<pair<string,string>> vec {{"Z","1"},{"Y","2"},{"X","3"}};
    cout << Json(vec) << endl;
   // => [["Z","1"],["Y","2"],["X","3"]] - array, not object

    VecMap<string,string> vm {{"Z","1"}};
    vm["Z"] = "2";
    vm["Y"] = "3";
    vm["X"] = "4";
    cout << Json(vm) << endl;  // VecMap::mapped_type makes it look like a map ~ object
    // => {"X":"4","Y":"3","Z":"2"}

    cout << FifoJson(vm) << endl;
    // => {"Z":"2","Y":"3","X":"4"}  - Object, in insertion order

    FifoJson fj {{"Z","1"},{"Y","2"},{"X",3}};
    fj["Z"] = 4;
    fj["A"] = 5;
    cout << fj << endl;
    // => {"Z":4,"Y":"2","X":3,"A":5}
gatopeich commented

It was missing using mapped_type = T to be fully recognized. Just added it and updated the above comments...

nlohmann commented

@gatopeich

I am currently trying to put this all together to add this as ordered_json to the library. While writing tests, I saw that removing elements is not yet working. This is my current approach:

std::size_t erase(const key_type& key)
{
    std::size_t result = 0;
    for (auto it = this->begin(); it != this->end();)
    {
        if (it->first == key)
        {
            ++result;
            it = Container::erase(it);
        }
        else
        {
            ++it;
        }
    }

    return result;
}

which fails due to an error in it = Container::erase(it);:

cannot be assigned because its copy assignment operator is implicitly deleted

Any ideas? Here is the current state: 4fd0d02

gatopeich commented

Yup, I had that working somewhere...

gatopeich commented

The problem is about moving the pair<const Key, T> because Key is const... Making it non-const gets us going but I am looking for a neater solution...

gatopeich commented

Actually there seems to be no cleaner way than to make those pairs have a non-const Key.

nlohmann commented

I could not make it to work. Can you make a concrete example how to remove the const?

gatopeich commented

This is my latest working version, with erase:

#include <vector>

/// VecMap: a minimal map-like container that preserves insertion order
/// for use within nlohmann::basic_json<VecMap>
template <class Key, class T, class IgnoredLess = std::less<Key>,
	class Allocator = std::allocator<std::pair<Key, T>>,
	class Container = std::vector<std::pair<Key, T>, Allocator>>
struct VecMap : Container
{
	using key_type = Key;
	using mapped_type = T;
	using value_type = typename Container::value_type; // On GCC just "using Container::value_type"
	using Container::Container;
	auto emplace(Key &&key, T &&t) {
        for (auto it=this->begin(); it !=this->end(); ++it)
            if (it->first == key)
                return std::pair {it, false};
        Container::emplace_back(key, t);
        return std::pair {--this->end(), true};
    }
	T &operator[](Key &&key) {
		return emplace(std::move(key), T{}).first->second;
	}
	std::size_t erase(const Key &key) {
        for (auto it=this->begin(); it!=this->end(); ++it)
            if (it->first == key) {
                Container::erase(it);
                return 1;
            }
        return 0;
	}
};

https://repl.it/repls/EducatedImpeccableCalculators#main.cpp

nlohmann commented

This does not work for me:

In file included from ../test/src/unit-ordered_json.cpp:32:
In file included from ../include/nlohmann/json.hpp:37:
/Users/niels/Documents/projects/clang10/bin/../include/c++/v1/algorithm:1868:19: error: object of type 'std::__1::pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > >' cannot be assigned because its copy assignment operator is implicitly deleted
        *__result = _VSTD::move(*__first);
                  ^
/Users/niels/Documents/projects/clang10/bin/../include/c++/v1/algorithm:1893:19: note: in instantiation of function template specialization 'std::__1::__move<std::__1::pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > > *, std::__1::pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > > *>' requested here
    return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
                  ^
/Users/niels/Documents/projects/clang10/bin/../include/c++/v1/vector:1717:36: note: in instantiation of function template specialization 'std::__1::move<std::__1::pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > > *, std::__1::pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > > *>' requested here
    this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
                                   ^
../include/nlohmann/ordered_map.hpp:35:20: note: in instantiation of member function 'std::__1::vector<std::__1::pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > >, std::__1::allocator<std::__1::pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > > > >::erase' requested here
        Container::erase(it);
                   ^
../include/nlohmann/json.hpp:4224:36: note: in instantiation of member function 'nlohmann::ordered_map<std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > >, std::__1::less<void>, std::__1::allocator<std::__1::pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > > >, std::__1::vector<std::__1::pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > >, std::__1::allocator<std::__1::pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > > > > >::erase' requested here
            return m_value.object->erase(key);
                                   ^
../test/src/unit-ordered_json.cpp:57:8: note: in instantiation of member function 'nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > >::erase' requested here
    oj.erase("element1");
       ^
/Users/niels/Documents/projects/clang10/bin/../include/c++/v1/utility:310:5: note: copy assignment operator is implicitly deleted because 'pair<const std::__1::basic_string<char>, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char>, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > >' has a user-declared move constructor
    pair(pair&&) = default;
    ^
1 error generated.
nlohmann commented

I see your code running - maybe it's a C++17 vs. C++11 issue? I already had to change the return type of emplace to std::pair<typename Container::iterator, bool> to make the code compile.

gatopeich commented

I see. Definitely C++17 vs C++11 may have something to do...

gatopeich commented

Adapted to C++11 here:
https://repl.it/@gatopeich/C11-VecMap

template <class Key, class T, class IgnoredLess = std::less<Key>,
	class Allocator = std::allocator<std::pair<Key, T>>,
	class Container = std::vector<std::pair<Key, T>, Allocator>>
struct VecMap : Container
{
	using key_type = Key;
	using mapped_type = T;
	using typename Container::value_type;
	using typename Container::iterator;
	using Container::Container;

	std::pair<iterator, bool>
	emplace(Key &&key, T &&t) {
        for (auto it=this->begin(); it !=this->end(); ++it)
            if (it->first == key)
                return {it, false};
        Container::emplace_back(key, t);
        return {--this->end(), true};
  }

	T &operator[](Key &&key) {
		return emplace(std::move(key), T{}).first->second;
	}
	unsigned erase(const Key &key) {
    for (auto it=this->begin(); it!=this->end(); ++it)
      if (it->first == key) {
        Container::erase(it);
        return 1;
      }
      return 0;
	}
};
nlohmann commented

This code does not work with my setup (Clang 10):

/Users/niels/Documents/projects/clang10/bin/../include/c++/v1/vector:491:5: error: static_assert failed due to requirement 'is_same<std::__1::pair<const std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > >, std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, nlohmann::basic_json<nlohmann::ordered_map, std::vector, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, bool, long long, unsigned long long, double, std::allocator, adl_serializer, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > > >::value' "Allocator::value_type must be same type as value_type"
    static_assert((is_same<typename allocator_type::value_type, value_type>::value),
    ^              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This error goes away if I switch the type back to std::pair<const Key, T>, but then erase does not work.

gatopeich commented

That may be cause the allocator passed by basic_json is not compatible.
Can you try removing "Allocator" from VecMap's Container declaration so the default one is used?

nlohmann commented

I did not get it to work, I'm sorry. It would be great to see a PR.

gatopeich commented

Will do that. I am away from computer today just trying to help from my phone 🙂

  • 👍1
gatopeich commented

I forked, but how should I build and test?
I am using VS code on Linux. Installed clang-10 and run "make json_test" which spits a lot of compiler warnings, then running test/json_test I get this:

src/unit-testsuites.cpp:351: FATAL ERROR: test case CRASHED: SIGSEGV - Segmentation violation signal

===============================================================================
src/unit-testsuites.cpp:351:
TEST CASE:  json.org examples

===============================================================================
[doctest] test cases:     77 |     67 passed |     10 failed |     18 skipped
[doctest] assertions: 2870902 | 2870881 passed |     21 failed |
[doctest] Status: FAILURE!
Segmentation fault
nlohmann commented

Just open a merge request, then the CI is run with a lot of different compilers.

gatopeich commented

I see it fails only on MacOS build, with "Apple clang version 11.0.3 (clang-1103.0.32.62)", with the assertion you mentioned above.
Looking into that Allocator::value_type...

gatopeich commented

The problem is in the definition of object_t there is an assumption that the allocator is for a const string:

    using object_t = ObjectType<StringType,
          basic_json,
          object_comparator_t,
          AllocatorType<std::pair<const StringType,
          basic_json>>>;

And a const string may have a specialized implementation, e.g. with smaller allocation requirements, thus with incompatible allocator...

nlohmann commented

I took the default template arguments from std::map:

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

I'm afraid changing this would break the API. Any idea how to fix the "vector of pairs" approach? Maybe using two vectors?

gatopeich commented

I see 3 ways forward:

  1. Optimal: find if C++11 has some way to put AllocatorType<Container::value_type> inside the declaration of object_t. Note that Container::value_type == object_t::value_type == basic_json::value_type so it is a self-referencing template... Seems beyond my template abilities, but it would clear the way to any Container class, not just std::vector.

Probably the cleanest way is by wrapping std::map:

template<class Key, class T, template<class> AllocatorType>
class MapWrapper : std:map<Key, T, std::less<Key>, AllocatorType<const Key, T>> {}

then ObjectType = MapWrapper, and object_t declaration would be much simpler:

object_t = ObjectType<StringType, basic_json, AllocatorType>;

Only I would not want to go into mayor refactoring 🙂 so...

  1. Re-implement vector::erase() without relying on pair move operations missing due to const member. e.g. by using in-place destructor + constructor. I am working at this now.

  2. Use std::forward_list instead of std::vector. Me not like it, but should work.

gatopeich commented

Hey @nlohmann my pull request #2206 is ready and waiting...

  • 👍1
  • 🚀1
gatopeich commented

Thanks for taking this in!

  • 👍1
shdxiang commented

great feature @gatopeich

Deleted user commented

@gatopeich that is a really good feature

  • 👍2
  • ❤️2
pkbehera commented

@nlohmann I think this should have been named unordered_json, in-line with what std::map, std::unordered_map, std::set, std::unordered_set do.

std::map orders its elements in a particular fashion, while std::unordered_map preserves the order in which its elements are inserted. So std::map is actually an alias for ordered_map

Similarly nhlomann::json should have been alias for ordered_json as implicitly sorts the elements and nhlomann::unordered_json should preserve the order of insertion (i.e. it does not sort). 😄

nlohmann commented

std::map orders its elements in a particular fashion, while std::unordered_map preserves the order in which its elements are inserted.

This is not true. In std::unordered_map, elements are hashed and stored in buckets.

Similarly nhlomann::json should have been alias for ordered_json as implicitly sorts the elements and nhlomann::unordered_json should preserve the order of insertion (i.e. it does not sort). 😄

See https://json.nlohmann.me/features/object_order/ on the rationale.