Object properties should not be re-sorted alphabetically #2179

gatopeich · 2020-06-08T12:43:14Z

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

The text was updated successfully, but these errors were encountered:

nlohmann · 2020-06-08T13:00:34Z

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

gatopeich · 2020-06-08T14:53:04Z

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

gatopeich · 2020-06-08T17:10:24Z

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 · 2020-06-08T18:00:55Z

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 · 2020-06-10T09:26:03Z

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 · 2020-06-10T09:39:05Z

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

gatopeich · 2020-06-10T10:21:32Z

Of course 👍

gatopeich · 2020-06-10T10:31:42Z

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 · 2020-06-10T10:37:32Z

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

nlohmann · 2020-06-19T13:28:06Z

@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 · 2020-06-19T20:09:56Z

Yup, I had that working somewhere...

gatopeich · 2020-06-19T20:44:19Z

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 · 2020-06-19T20:55:46Z

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

nlohmann · 2020-06-20T07:29:17Z

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

gatopeich · 2020-06-20T08:03:28Z

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 · 2020-06-20T08:12:25Z

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 · 2020-06-20T08:13:46Z

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 · 2020-06-20T10:29:09Z

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

gatopeich · 2020-06-20T10:51:29Z

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 · 2020-06-20T11:21:26Z

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 · 2020-06-20T16:45:26Z

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 · 2020-06-20T18:13:10Z

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

gatopeich · 2020-06-20T19:40:57Z

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

gatopeich · 2020-06-21T20:04:51Z

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 · 2020-06-21T20:36:46Z

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

gatopeich · 2020-06-21T22:11:04Z

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 · 2020-06-21T22:40:57Z

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 · 2020-06-22T05:53:41Z

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 · 2020-06-22T17:00:54Z

I see 3 ways forward:

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

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.
Use std::forward_list instead of std::vector. Me not like it, but should work.

gatopeich · 2020-07-06T16:44:04Z

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

gatopeich · 2020-07-17T09:37:35Z

Thanks for taking this in!

shdxiang · 2020-12-11T02:44:06Z

great feature @gatopeich

ghost · 2020-12-11T13:37:53Z

@gatopeich that is a really good feature

pkbehera · 2022-10-27T11:24:47Z

@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 · 2022-10-27T13:53:11Z

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.

gatopeich added the kind: bug label Jun 8, 2020

nlohmann added solution: wontfix the issue will not be fixed (either it is impossible or deemed out of scope) and removed kind: bug labels Jun 8, 2020

nlohmann closed this as completed Jun 8, 2020

nlohmann reopened this Jun 19, 2020

nlohmann mentioned this issue Jun 25, 2020

Can I disable sorting of json values #2219

Closed

nlohmann mentioned this issue Jul 11, 2020

Add ordered_json specialization with ordered object keys #2258

Merged

nlohmann added release item: ✨ new feature solution: proposed fix a fix for the issue has been proposed and waits for confirmation and removed solution: wontfix the issue will not be fixed (either it is impossible or deemed out of scope) labels Jul 11, 2020

nlohmann self-assigned this Jul 11, 2020

nlohmann added this to the Release 3.8.1 milestone Jul 11, 2020

nlohmann closed this as completed in #2258 Jul 12, 2020

benjeffery mentioned this issue Aug 11, 2020

metadata schema equality and hence table equality is not well-defined tskit-dev/tskit#763

Closed

slayoo mentioned this issue May 18, 2023

support for nlohmann::ordered_json in addition to nlohmann::json pybind/pybind11_json#63

Open

Object properties should not be re-sorted alphabetically #2179

Object properties should not be re-sorted alphabetically #2179

Comments

gatopeich commented Jun 8, 2020

Please describe the steps to reproduce the issue.

What is the expected behavior?

And what is the actual behavior instead?

Which compiler and operating system are you using?

Which version of the library did you use?

nlohmann commented Jun 8, 2020

gatopeich commented Jun 8, 2020

gatopeich commented Jun 8, 2020 • edited

nlohmann commented Jun 8, 2020

gatopeich commented Jun 10, 2020 • edited

nlohmann commented Jun 10, 2020

gatopeich commented Jun 10, 2020

gatopeich commented Jun 10, 2020 • edited

gatopeich commented Jun 10, 2020

nlohmann commented Jun 19, 2020

gatopeich commented Jun 19, 2020

gatopeich commented Jun 19, 2020

gatopeich commented Jun 19, 2020

nlohmann commented Jun 20, 2020

gatopeich commented Jun 20, 2020

nlohmann commented Jun 20, 2020

nlohmann commented Jun 20, 2020

gatopeich commented Jun 20, 2020

gatopeich commented Jun 20, 2020 • edited

nlohmann commented Jun 20, 2020

gatopeich commented Jun 20, 2020

nlohmann commented Jun 20, 2020

gatopeich commented Jun 20, 2020

gatopeich commented Jun 21, 2020

nlohmann commented Jun 21, 2020

gatopeich commented Jun 21, 2020 • edited

gatopeich commented Jun 21, 2020

nlohmann commented Jun 22, 2020

gatopeich commented Jun 22, 2020

gatopeich commented Jul 6, 2020 • edited

gatopeich commented Jul 17, 2020

shdxiang commented Dec 11, 2020

ghost commented Dec 11, 2020

pkbehera commented Oct 27, 2022

nlohmann commented Oct 27, 2022

gatopeich commented Jun 8, 2020 •

edited

gatopeich commented Jun 10, 2020 •

edited

gatopeich commented Jun 10, 2020 •

edited

gatopeich commented Jun 20, 2020 •

edited

gatopeich commented Jun 21, 2020 •

edited

gatopeich commented Jul 6, 2020 •

edited