Make flatten() linear for ordered_json

json_pointer::flatten inserted every leaf with operator[], which searches
ordered_map linearly, so flatten() was quadratic (citm_catalog.json: 265 ms
vs 5 ms for json). Flattened paths are unique by construction, so
ordered_map gets emplace_new_key() to append a key known to be absent;
other object types still use operator[]. Parent pointers are set once at
the end for JSON_DIAGNOSTICS.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>

docs/mkdocs/docs/api/basic_json/array_t.md

@@ -27,7 +27,7 @@ To store objects in C++, a type is defined by the template parameters explained
 
 ### Default type
 
-With the default values for `ArrayType` (`std::vector`) and `AllocatorType` (`std::allocator`), the default value for
+With the default values for `ArrayType` (`std::vector`) and `AllocatorType` (`std::allocator`), the default type for
 `array_t` is:
 
 ```cpp

docs/mkdocs/docs/api/basic_json/boolean_t.md

@@ -23,7 +23,7 @@ To store boolean values in C++, a type is defined by the template parameter  `Bo
 
 ### Default type
 
-With the default values for `BooleanType` (`#!cpp bool`), the default value for `boolean_t` is `#!cpp bool`.
+With the default values for `BooleanType` (`#!cpp bool`), the default type for `boolean_t` is `#!cpp bool`.
 
 ### Storage
 

docs/mkdocs/docs/api/basic_json/number_float_t.md

@@ -35,7 +35,7 @@ type to use.
 
 ### Default type
 
-With the default values for `NumberFloatType` (`double`), the default value for `number_float_t` is `#!cpp double`.
+With the default values for `NumberFloatType` (`double`), the default type for `number_float_t` is `#!cpp double`.
 
 ### Default behavior
 
@@ -52,8 +52,9 @@ With the default values for `NumberFloatType` (`double`), the default value for
 > interoperability can be achieved by implementations that expect no more precision or range than these provide, in the
 > sense that implementations will approximate JSON numbers within the expected precision.
 
-This implementation does exactly follow this approach, as it uses double precision floating-point numbers. Note that
-numbers smaller than `-1.79769313486232e+308` or greater than `1.79769313486232e+308` are rejected during parsing with
+This implementation does exactly follow this approach, as it uses double precision floating-point numbers by default.
+Note that with the default `double`, numbers smaller than `-1.79769313486232e+308` or greater than
+`1.79769313486232e+308` are rejected during parsing with
 [`out_of_range.406`](../../home/exceptions.md#jsonexceptionout_of_range406). Non-finite values (NaN and infinity) can
 only be stored by assigning them directly and are serialized to `null`.
 

docs/mkdocs/docs/api/basic_json/number_integer_t.md

@@ -31,7 +31,7 @@ to use.
 
 ### Default type
 
-With the default values for `NumberIntegerType` (`std::int64_t`), the default value for `number_integer_t` is
+With the default values for `NumberIntegerType` (`std::int64_t`), the default type for `number_integer_t` is
 `#!cpp std::int64_t`.
 
 ### Default behavior

docs/mkdocs/docs/api/basic_json/number_unsigned_t.md

@@ -32,7 +32,7 @@ the type to use.
 
 ### Default type
 
-With the default values for `NumberUnsignedType` (`std::uint64_t`), the default value for `number_unsigned_t` is
+With the default values for `NumberUnsignedType` (`std::uint64_t`), the default type for `number_unsigned_t` is
 `#!cpp std::uint64_t`.
 
 ### Default behavior

docs/mkdocs/docs/api/basic_json/object_t.md

@@ -36,7 +36,7 @@ To store objects in C++, a type is defined by the template parameters described
 ### Default type
 
 With the default values for `ObjectType` (`std::map`), `StringType` (`std::string`), and `AllocatorType`
-(`std::allocator`), the default value for `object_t` is:
+(`std::allocator`), the default type for `object_t` is:
 
 ```cpp
 // until C++14

docs/mkdocs/docs/api/basic_json/string_t.md

@@ -32,7 +32,7 @@ JSON class into byte-sized characters during deserialization.
 
 ### Default type
 
-With the default values for `StringType` (`std::string`), the default value for `string_t` is `#!cpp std::string`.
+With the default values for `StringType` (`std::string`), the default type for `string_t` is `#!cpp std::string`.
 
 ### Encoding
 

docs/mkdocs/docs/features/types/index.md

@@ -120,7 +120,7 @@ requirements are collected in [Template Parameter Requirements](template_paramet
 
 ### Default type
 
-With the default values for *ObjectType* (`std::map`), *StringType* (`std::string`), and *AllocatorType* (`std::allocator`), the default value for `object_t` is:
+With the default values for *ObjectType* (`std::map`), *StringType* (`std::string`), and *AllocatorType* (`std::allocator`), the default type for `object_t` is:
 
 ```cpp
 std::map<
@@ -177,7 +177,7 @@ json j = m;
 
 ### Default type
 
-With the default values for *ArrayType* (`std::vector`) and *AllocatorType* (`std::allocator`), the default value for `array_t` is:
+With the default values for *ArrayType* (`std::vector`) and *AllocatorType* (`std::allocator`), the default type for `array_t` is:
 
 ```cpp
 std::vector<
@@ -209,7 +209,7 @@ Unicode values are split by the JSON class into byte-sized characters during des
 
 ### Default type
 
-With the default values for *StringType* (`std::string`), the default value for `string_t` is `#!cpp std::string`.
+With the default values for *StringType* (`std::string`), the default type for `string_t` is `#!cpp std::string`.
 
 ### Encoding
 
@@ -234,7 +234,7 @@ String values are stored as pointers in a `basic_json` type. That is, for any ac
 
 ### Default type
 
-With the default values for *BooleanType* (`#!cpp bool`), the default value for `boolean_t` is `#!cpp bool`.
+With the default values for *BooleanType* (`#!cpp bool`), the default type for `boolean_t` is `#!cpp bool`.
 
 ### Storage
 
@@ -252,9 +252,9 @@ This description includes both integer and floating-point numbers. However, C++
 
 ### Default types
 
-With the default values for *NumberIntegerType* (`std::int64_t`), the default value for `number_integer_t` is `std::int64_t`.
-With the default values for *NumberUnsignedType* (`std::uint64_t`), the default value for `number_unsigned_t` is `std::uint64_t`.
-With the default values for *NumberFloatType* (`#!cpp double`), the default value for `number_float_t` is `#!cpp double`.
+With the default values for *NumberIntegerType* (`std::int64_t`), the default type for `number_integer_t` is `std::int64_t`.
+With the default values for *NumberUnsignedType* (`std::uint64_t`), the default type for `number_unsigned_t` is `std::uint64_t`.
+With the default values for *NumberFloatType* (`#!cpp double`), the default type for `number_float_t` is `#!cpp double`.
 
 ### Default behavior
 
@@ -281,7 +281,7 @@ As this range is a subrange of the exactly supported range [`INT64_MIN`, `INT64_
 
 > This specification allows implementations to set limits on the range and precision of numbers accepted. Since software that implements IEEE 754-2008 binary64 (double precision) numbers is generally available and widely used, good interoperability can be achieved by implementations that expect no more precision or range than these provide, in the sense that implementations will approximate JSON numbers within the expected precision.
 
-This implementation does exactly follow this approach, as it uses double precision floating-point numbers. Note that numbers smaller than `#!c -1.79769313486232e+308` or greater than `#!c 1.79769313486232e+308` are rejected during parsing with [`out_of_range.406`](../../home/exceptions.md#jsonexceptionout_of_range406). Non-finite values (NaN and infinity) can only be stored by assigning them directly and are serialized to `#!json null`.
+This implementation does exactly follow this approach, as it uses double precision floating-point numbers by default (see *NumberFloatType* above). Note that with the default `#!cpp double`, numbers smaller than `#!c -1.79769313486232e+308` or greater than `#!c 1.79769313486232e+308` are rejected during parsing with [`out_of_range.406`](../../home/exceptions.md#jsonexceptionout_of_range406). Non-finite values (NaN and infinity) can only be stored by assigning them directly and are serialized to `#!json null`.
 
 ### Storage
 

include/nlohmann/detail/json_pointer.hpp

@@ -938,6 +938,23 @@ class json_pointer
     }
 
   private:
+    // Add the entry (key, v) to the object `obj`. Flattened paths are pairwise
+    // distinct, so objects that can append a key known to be absent
+    // (ordered_map) skip the lookup, which is linear and would make flatten
+    // quadratic; all other object types use operator[].
+    template<typename ObjectType, typename ValueType>
+    static auto add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, int /*unused*/)
+    -> decltype(obj.emplace_new_key(key, std::forward<ValueType>(v)), void())
+    {
+        obj.emplace_new_key(key, std::forward<ValueType>(v));
+    }
+
+    template<typename ObjectType, typename ValueType>
+    static void add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, ...)
+    {
+        obj[key] = std::forward<ValueType>(v);
+    }
+
     /*!
     @param[in] reference_string  the reference string to the current value
     @param[in] value             the value to consider
@@ -982,7 +999,8 @@ class json_pointer
 
         // flatten `v`, whose path is `path`: primitives and empty containers
         // are added to the result right away; other containers get a frame
-        const auto enter = [&stack, &path, &result](const BasicJsonType & v)
+        auto& object = *result.m_data.m_value.object;
+        const auto enter = [&stack, &path, &object](const BasicJsonType & v)
         {
             switch (v.type())
             {
@@ -991,7 +1009,7 @@ class json_pointer
                     if (v.m_data.m_value.array->empty())
                     {
                         // flatten empty array as null
-                        result[path] = nullptr;
+                        add_flattened(object, path, nullptr, 0);
                     }
                     else
                     {
@@ -1005,7 +1023,7 @@ class json_pointer
                     if (v.m_data.m_value.object->empty())
                     {
                         // flatten empty object as null
-                        result[path] = nullptr;
+                        add_flattened(object, path, nullptr, 0);
                     }
                     else
                     {
@@ -1025,7 +1043,7 @@ class json_pointer
                 default:
                 {
                     // add a primitive value with its reference string
-                    result[path] = v;
+                    add_flattened(object, path, v, 0);
                     return;
                 }
             }
@@ -1071,6 +1089,10 @@ class json_pointer
                 enter(it->second);
             }
         }
+
+        // the entries were added without going through basic_json, so the
+        // parent pointers (JSON_DIAGNOSTICS) have to be set now
+        result.set_parents();
     }
 
     /*!

include/nlohmann/ordered_map.hpp

@@ -143,6 +143,17 @@ public:
         return {std::prev(this->end()), true};
     }
 
+    /// @brief add an element at the end without checking whether the key exists
+    /// @note The caller must guarantee that @a key is not yet contained, otherwise
+    ///       the container holds duplicate keys. This avoids the linear search of
+    ///       emplace() and operator[] when many keys known to be new are added.
+    template<class V, detail::enable_if_t<
+                 detail::is_constructible<T, V>::value, int> = 0>
+    void emplace_new_key(const key_type& key, V && t)
+    {
+        append(key, std::forward<V>(t));
+    }
+
     T& operator[](const key_type& key)
     {
         return emplace(key, T{}).first->second;

single_include/nlohmann/json.hpp

@@ -21559,6 +21559,23 @@ class json_pointer
     }
 
   private:
+    // Add the entry (key, v) to the object `obj`. Flattened paths are pairwise
+    // distinct, so objects that can append a key known to be absent
+    // (ordered_map) skip the lookup, which is linear and would make flatten
+    // quadratic; all other object types use operator[].
+    template<typename ObjectType, typename ValueType>
+    static auto add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, int /*unused*/)
+    -> decltype(obj.emplace_new_key(key, std::forward<ValueType>(v)), void())
+    {
+        obj.emplace_new_key(key, std::forward<ValueType>(v));
+    }
+
+    template<typename ObjectType, typename ValueType>
+    static void add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, ...)
+    {
+        obj[key] = std::forward<ValueType>(v);
+    }
+
     /*!
     @param[in] reference_string  the reference string to the current value
     @param[in] value             the value to consider
@@ -21603,7 +21620,8 @@ class json_pointer
 
         // flatten `v`, whose path is `path`: primitives and empty containers
         // are added to the result right away; other containers get a frame
-        const auto enter = [&stack, &path, &result](const BasicJsonType & v)
+        auto& object = *result.m_data.m_value.object;
+        const auto enter = [&stack, &path, &object](const BasicJsonType & v)
         {
             switch (v.type())
             {
@@ -21612,7 +21630,7 @@ class json_pointer
                     if (v.m_data.m_value.array->empty())
                     {
                         // flatten empty array as null
-                        result[path] = nullptr;
+                        add_flattened(object, path, nullptr, 0);
                     }
                     else
                     {
@@ -21626,7 +21644,7 @@ class json_pointer
                     if (v.m_data.m_value.object->empty())
                     {
                         // flatten empty object as null
-                        result[path] = nullptr;
+                        add_flattened(object, path, nullptr, 0);
                     }
                     else
                     {
@@ -21646,7 +21664,7 @@ class json_pointer
                 default:
                 {
                     // add a primitive value with its reference string
-                    result[path] = v;
+                    add_flattened(object, path, v, 0);
                     return;
                 }
             }
@@ -21692,6 +21710,10 @@ class json_pointer
                 enter(it->second);
             }
         }
+
+        // the entries were added without going through basic_json, so the
+        // parent pointers (JSON_DIAGNOSTICS) have to be set now
+        result.set_parents();
     }
 
     /*!
@@ -29158,6 +29180,17 @@ public:
         return {std::prev(this->end()), true};
     }
 
+    /// @brief add an element at the end without checking whether the key exists
+    /// @note The caller must guarantee that @a key is not yet contained, otherwise
+    ///       the container holds duplicate keys. This avoids the linear search of
+    ///       emplace() and operator[] when many keys known to be new are added.
+    template<class V, detail::enable_if_t<
+                 detail::is_constructible<T, V>::value, int> = 0>
+    void emplace_new_key(const key_type& key, V && t)
+    {
+        append(key, std::forward<V>(t));
+    }
+
     T& operator[](const key_type& key)
     {
         return emplace(key, T{}).first->second;

tests/src/unit-json_pointer.cpp

@@ -24,6 +24,8 @@ using nlohmann::json;
 #endif
 
 #include <map>
+#include <string>
+#include <vector>
 #include <sstream>
 
 TEST_CASE("JSON pointers")
@@ -1071,3 +1073,53 @@ TEST_CASE("flatten of structured values")
               R"({"/z":"s","/a~1b/~0":1,"/a~1b/k":null,"/a/0":1,"/a/1/c":null,"/a/1/b":null,"/a/2/0/x~0~1/0":true,"/a/2/0/x~0~1/1":null,"/a/2/0/w":2})");
     }
 }
+
+TEST_CASE("flatten of ordered_json")
+{
+    using nlohmann::ordered_json;
+
+    SECTION("keeps the document order of the leaves")
+    {
+        const ordered_json j = ordered_json::parse(R"({
+            "z": 1, "a": {"y": [true, null, {}], "b": "x", "": []},
+            "m~n": 2.5, "o/p": {"k": {}}, "0": [[1], [2, 3]]
+        })");
+
+        const ordered_json flat = j.flatten();
+        std::vector<std::string> keys;
+        for (const auto& el : flat.items())
+        {
+            keys.push_back(el.key());
+        }
+        const std::vector<std::string> expected =
+        {
+            "/z", "/a/y/0", "/a/y/1", "/a/y/2", "/a/b", "/a/", "/m~0n", "/o~1p/k", "/0/0/0", "/0/1/0", "/0/1/1"
+        };
+        CHECK(keys == expected);
+        CHECK(flat.size() == expected.size());
+        CHECK(flat["/m~0n"] == 2.5);
+        CHECK(flat["/a/y/2"].is_null());
+    }
+
+    SECTION("round-trips and agrees with json")
+    {
+        ordered_json j;
+        for (int i = 0; i < 200; ++i)
+        {
+            j["k" + std::to_string(i)] = {{"v", i}, {"l", {i, i + 1, "s"}}};
+        }
+        const ordered_json flat = j.flatten();
+        CHECK(flat.size() == 800);
+        CHECK(flat.unflatten() == j);
+
+        // same entries as for a sorted object
+        const nlohmann::json plain = nlohmann::json::parse(j.dump());
+        CHECK(nlohmann::json::parse(flat.dump()) == plain.flatten());
+    }
+
+    SECTION("primitive and empty root")
+    {
+        CHECK(ordered_json(1).flatten() == ordered_json({{"", 1}}));
+        CHECK(ordered_json::array().flatten() == ordered_json({{"", nullptr}}));
+    }
+}