Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Object properties should not be re-sorted alphabetically #2179

Closed
gatopeich opened this issue Jun 8, 2020 · 35 comments · Fixed by #2258
Closed

Object properties should not be re-sorted alphabetically #2179

gatopeich opened this issue Jun 8, 2020 · 35 comments · Fixed by #2258
Assignees
Labels
release item: ✨ new feature solution: proposed fix a fix for the issue has been proposed and waits for confirmation
Milestone

Comments

@gatopeich
Copy link
Contributor

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
Copy link
Owner

nlohmann commented Jun 8, 2020

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

@nlohmann 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 nlohmann closed this as completed Jun 8, 2020
@gatopeich
Copy link
Contributor Author

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

@gatopeich
Copy link
Contributor Author

gatopeich commented Jun 8, 2020

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
Copy link
Owner

nlohmann commented Jun 8, 2020

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
Copy link
Contributor Author

gatopeich commented Jun 10, 2020

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
Copy link
Owner

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

@gatopeich
Copy link
Contributor Author

Of course 👍

@gatopeich
Copy link
Contributor Author

gatopeich commented Jun 10, 2020

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
Copy link
Contributor Author

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

@nlohmann nlohmann reopened this Jun 19, 2020
@nlohmann
Copy link
Owner

@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
Copy link
Contributor Author

Yup, I had that working somewhere...

@gatopeich
Copy link
Contributor Author

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
Copy link
Contributor Author

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

@nlohmann
Copy link
Owner

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

@gatopeich
Copy link
Contributor Author

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
Copy link
Owner

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
Copy link
Owner

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
Copy link
Contributor Author

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

@gatopeich
Copy link
Contributor Author

gatopeich commented Jun 20, 2020

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
Copy link
Owner

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
Copy link
Contributor Author

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
Copy link
Owner

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

@gatopeich
Copy link
Contributor Author

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

@gatopeich
Copy link
Contributor Author

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
Copy link
Owner

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

@gatopeich
Copy link
Contributor Author

gatopeich commented Jun 21, 2020

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
Copy link
Contributor Author

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
Copy link
Owner

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
Copy link
Contributor Author

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
Copy link
Contributor Author

gatopeich commented Jul 6, 2020

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

@nlohmann 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 nlohmann self-assigned this Jul 11, 2020
@nlohmann nlohmann added this to the Release 3.8.1 milestone Jul 11, 2020
@gatopeich
Copy link
Contributor Author

Thanks for taking this in!

@shdxiang
Copy link

great feature @gatopeich

@ghost
Copy link

ghost commented Dec 11, 2020

@gatopeich that is a really good feature

@pkbehera
Copy link

@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
Copy link
Owner

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
release item: ✨ new feature solution: proposed fix a fix for the issue has been proposed and waits for confirmation
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants