maintaining order of keys during iteration

[nickdesaulniers]

keys in JSON are not sorted, but ordered based on definition. This becomes apparent when iterating keys of an object. For example, in JavaScript, with an object literal:

x = { a: 0, b: 1 }
y = { b: 0, a: 1 }
for (var key in x) console.log(key)
for (var key in y) console.log(key)
for (var key in JSON.parse(JSON.stringify(x))) console.log(key)
for (var key in JSON.parse(JSON.stringify(y))) console.log(key)

prints

a
b
b
a
a
b
b
a

For example, I believe most JS JITs keep separate shapes for object with the same properties but defined in different orders.

[nlohmann]

When I understand you correctly, JavaScript remembers the order in which values are defined and preserves it during iteration and serialization.

However, RFC 7159 states:

An object is an unordered collection of zero or more name/value pairs, where a name is a string and a value is a string, number, boolean, null, object, or array.

(emphasis added) and

JSON parsing libraries have been observed to differ as to whether or not they make the ordering of object members visible to calling software. Implementations whose behavior does not depend on member ordering will be interoperable in the sense that they will not be affected by these differences.

The status quo

As the basic_jsonclass by default relies on std::map, we do not preserve the order of definition, but internally order values with respect to `std::map::Compare``.

Where to go from here

As the basic_json class is templated, other types can be used instead of std::map. However, a quick research showed that it is hard not to sort. The question is whether it would make sense to invest in an associative container that keeps track of the insertion order. After all, an order of object values is not specified.

[fx-lange]

Hi there, great work!

I'm currently using jsoncpp and looking for an alternative which should keep track of the insertion order. Otherwise I would need to somehow somewhere keep track of the order myself. I'll check out your json lib anyway (like the intuitive syntax). Your link suggests to use a map and a vector but to integrate that sounds like a lot of work ... Any better ideas?

[nlohmann]

You can check out https://github.com/nlohmann/fifo_map - it should work as a replacement of std::map and maintains the key's order.

[habemus-papadum]

Hi -- Are there any known gotchas to using nlohmann's fifo map as a replacement for the default std::map? I was thinking of making the switch...

[nlohmann]

@habemus-papadum I implemented that container a while ago just for the purpose of having something to refer to, because a lot of people asked for order-preserving objects. I haven't heard of any bugs, but also not of a lot users. So just give it a try and file issues if you encounter an error.

[habemus-papadum]

@nlohmann : sounds like a plan! thanks

[habemus-papadum]

sadly using json = nlohmann::basic_json<nlohmann::fifo_map> does not work out of the box. (I'm not entirely sure if this the intended invocation)

I believe the problematic places are (in nlohmann_json.hpp):

   using object_t = ObjectType<StringType,
                                basic_json,
                                std::less<StringType>,   // <-------------- This is hardcoded
                                AllocatorType<std::pair<const StringType,
                                                        basic_json>>>;

after trying to replace the comparator with the one in fifo_map, the following portion of the code complains
because it is attempts to construct the comparator with no arguments (instead of the required 1)

    /// helper for exception-safe object creation
    template<typename T, typename... Args>
    static T* create(Args&& ... args)
    {
        AllocatorType<T> alloc;
        auto deleter = [&](T * object)
        {
            alloc.deallocate(object, 1);
        };
        std::unique_ptr<T, decltype(deleter)> object(alloc.allocate(1), deleter);
        alloc.construct(object.get(), std::forward<Args>(args)...);
        assert(object.get() != nullptr);
        return object.release();
    }

This is as far as I got. I'll keep trying, but it started to look like there may not be a simple drop in solution.
Thanks for any comments!

[habemus-papadum]

I was able to make (two) small changes to json.hpp (removing the hard coded comparator & and just replacing the default template parameter in basic_json from std::map to fifo map). While ugly, this get things compiling for now. However, things still do not work because I believe the default copy/move constructors/assignment operators in fifo_map are not correct (because of the pointer living inside the comparator). That's what I am playing around with now but I might be stuck. Worse case I will create a github repo that shows the current progress.