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>

include/nlohmann/detail/conversions/from_json.hpp

@@ -266,22 +266,6 @@ template<typename ConstructibleArrayType>
 void from_json_array_reserve(ConstructibleArrayType& /*arr*/, std::size_t /*size*/, priority_tag<0> /*unused*/)
 {}
 
-// append through push_back() where available; containers without it (such as
-// std::set) fall back to insert(end(), ...), which is what std::inserter did
-template<typename ConstructibleArrayType, typename ValueType>
-auto from_json_array_append(ConstructibleArrayType& arr, ValueType&& value, priority_tag<1> /*unused*/)
--> decltype(arr.push_back(std::forward<ValueType>(value)), void())
-{
-    arr.push_back(std::forward<ValueType>(value));
-}
-
-template<typename ConstructibleArrayType, typename ValueType>
-void from_json_array_append(ConstructibleArrayType& arr, ValueType&& value, priority_tag<0> /*unused*/)
-{
-    using std::end;
-    arr.insert(end(arr), std::forward<ValueType>(value));
-}
-
 template<typename BasicJsonType, typename ConstructibleArrayType,
          enable_if_t<
              std::is_assignable<ConstructibleArrayType&, ConstructibleArrayType>::value,
@@ -291,15 +275,17 @@ auto from_json_array_impl(const BasicJsonType& j, ConstructibleArrayType& arr, p
     j.template get<typename ConstructibleArrayType::value_type>(),
     void())
 {
+    using std::end;
+
     ConstructibleArrayType ret;
-    const auto* inner_array = j.template get_ptr<const typename BasicJsonType::array_t*>();
-    from_json_array_reserve(ret, inner_array->size(), priority_tag<1> {});
-    for (const auto& elem : *inner_array)
+    from_json_array_reserve(ret, j.size(), priority_tag<1> {});
+    std::transform(j.begin(), j.end(),
+                   std::inserter(ret, end(ret)), [](const BasicJsonType & i)
     {
         // get<BasicJsonType>() returns *this, this won't call a from_json
         // method when value_type is BasicJsonType
-        from_json_array_append(ret, elem.template get<typename ConstructibleArrayType::value_type>(), priority_tag<1> {});
-    }
+        return i.template get<typename ConstructibleArrayType::value_type>();
+    });
     arr = std::move(ret);
 }
 

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/json.hpp

@@ -3333,22 +3333,6 @@ public:
         return j.m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
     }
 
-    /// @brief out-of-line throw helpers: building the message inline blocks inlining of the hot accessors
-    /// @throw out_of_range.401
-    JSON_HEDLEY_NO_RETURN JSON_HEDLEY_NEVER_INLINE
-    static void throw_array_index_out_of_range(size_type idx, const basic_json& j)
-    {
-        JSON_THROW(out_of_range::create(detail::exception_id::array_index_out_of_range, detail::concat("array index ", std::to_string(idx), " is out of range"), &j));
-    }
-
-    /// @throw out_of_range.403
-    template<typename KeyType>
-    JSON_HEDLEY_NO_RETURN JSON_HEDLEY_NEVER_INLINE
-    static void throw_key_not_found(const KeyType& key, const basic_json& j)
-    {
-        JSON_THROW(out_of_range::create(detail::exception_id::key_not_found, detail::concat("key '", key, "' not found"), &j));
-    }
-
     /// @brief checked object element access used by the at() overloads taking a key
     /// @throw type_error.304 if @a j is not an object
     /// @throw out_of_range.403 if @a key is not found
@@ -3369,7 +3353,7 @@ public:
             // std::map or ordered_map) never moves from its argument, so key is still
             // valid here regardless of whether KeyType was deduced as an rvalue reference
             // NOLINTNEXTLINE(bugprone-use-after-move,hicpp-invalid-access-moved)
-            throw_key_not_found(key_for_message(key), j);
+            JSON_THROW(out_of_range::create(detail::exception_id::key_not_found, detail::concat("key '", key_for_message(key), "' not found"), &j));
         }
         return it->second;
     }
@@ -3406,7 +3390,7 @@ public:
 
         if (JSON_HEDLEY_UNLIKELY(idx >= j.m_data.m_value.array->size()))
         {
-            throw_array_index_out_of_range(idx, j);
+            JSON_THROW(out_of_range::create(detail::exception_id::array_index_out_of_range, detail::concat("array index ", std::to_string(idx), " is out of range"), &j));
         }
 
         return (*j.m_data.m_value.array)[idx];

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

@@ -5962,22 +5962,6 @@ template<typename ConstructibleArrayType>
 void from_json_array_reserve(ConstructibleArrayType& /*arr*/, std::size_t /*size*/, priority_tag<0> /*unused*/)
 {}
 
-// append through push_back() where available; containers without it (such as
-// std::set) fall back to insert(end(), ...), which is what std::inserter did
-template<typename ConstructibleArrayType, typename ValueType>
-auto from_json_array_append(ConstructibleArrayType& arr, ValueType&& value, priority_tag<1> /*unused*/)
--> decltype(arr.push_back(std::forward<ValueType>(value)), void())
-{
-    arr.push_back(std::forward<ValueType>(value));
-}
-
-template<typename ConstructibleArrayType, typename ValueType>
-void from_json_array_append(ConstructibleArrayType& arr, ValueType&& value, priority_tag<0> /*unused*/)
-{
-    using std::end;
-    arr.insert(end(arr), std::forward<ValueType>(value));
-}
-
 template<typename BasicJsonType, typename ConstructibleArrayType,
          enable_if_t<
              std::is_assignable<ConstructibleArrayType&, ConstructibleArrayType>::value,
@@ -5987,15 +5971,17 @@ auto from_json_array_impl(const BasicJsonType& j, ConstructibleArrayType& arr, p
     j.template get<typename ConstructibleArrayType::value_type>(),
     void())
 {
+    using std::end;
+
     ConstructibleArrayType ret;
-    const auto* inner_array = j.template get_ptr<const typename BasicJsonType::array_t*>();
-    from_json_array_reserve(ret, inner_array->size(), priority_tag<1> {});
-    for (const auto& elem : *inner_array)
+    from_json_array_reserve(ret, j.size(), priority_tag<1> {});
+    std::transform(j.begin(), j.end(),
+                   std::inserter(ret, end(ret)), [](const BasicJsonType & i)
     {
         // get<BasicJsonType>() returns *this, this won't call a from_json
         // method when value_type is BasicJsonType
-        from_json_array_append(ret, elem.template get<typename ConstructibleArrayType::value_type>(), priority_tag<1> {});
-    }
+        return i.template get<typename ConstructibleArrayType::value_type>();
+    });
     arr = std::move(ret);
 }
 
@@ -21573,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
@@ -21617,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())
             {
@@ -21626,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
                     {
@@ -21640,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
                     {
@@ -21660,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;
                 }
             }
@@ -21706,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();
     }
 
     /*!
@@ -29172,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;
@@ -32695,22 +32714,6 @@ public:
         return j.m_data.m_value.object->find(lookup_key(std::forward<KeyType>(key)));
     }
 
-    /// @brief out-of-line throw helpers: building the message inline blocks inlining of the hot accessors
-    /// @throw out_of_range.401
-    JSON_HEDLEY_NO_RETURN JSON_HEDLEY_NEVER_INLINE
-    static void throw_array_index_out_of_range(size_type idx, const basic_json& j)
-    {
-        JSON_THROW(out_of_range::create(detail::exception_id::array_index_out_of_range, detail::concat("array index ", std::to_string(idx), " is out of range"), &j));
-    }
-
-    /// @throw out_of_range.403
-    template<typename KeyType>
-    JSON_HEDLEY_NO_RETURN JSON_HEDLEY_NEVER_INLINE
-    static void throw_key_not_found(const KeyType& key, const basic_json& j)
-    {
-        JSON_THROW(out_of_range::create(detail::exception_id::key_not_found, detail::concat("key '", key, "' not found"), &j));
-    }
-
     /// @brief checked object element access used by the at() overloads taking a key
     /// @throw type_error.304 if @a j is not an object
     /// @throw out_of_range.403 if @a key is not found
@@ -32731,7 +32734,7 @@ public:
             // std::map or ordered_map) never moves from its argument, so key is still
             // valid here regardless of whether KeyType was deduced as an rvalue reference
             // NOLINTNEXTLINE(bugprone-use-after-move,hicpp-invalid-access-moved)
-            throw_key_not_found(key_for_message(key), j);
+            JSON_THROW(out_of_range::create(detail::exception_id::key_not_found, detail::concat("key '", key_for_message(key), "' not found"), &j));
         }
         return it->second;
     }
@@ -32768,7 +32771,7 @@ public:
 
         if (JSON_HEDLEY_UNLIKELY(idx >= j.m_data.m_value.array->size()))
         {
-            throw_array_index_out_of_range(idx, j);
+            JSON_THROW(out_of_range::create(detail::exception_id::array_index_out_of_range, detail::concat("array index ", std::to_string(idx), " is out of range"), &j));
         }
 
         return (*j.m_data.m_value.array)[idx];

tests/benchmarks/src/benchmarks.cpp

@@ -9,10 +9,7 @@
 #include <benchmark/benchmark.h>
 #include <nlohmann/json.hpp>
 #include <fstream>
-#include <array>
-#include <deque>
 #include <numeric>
-#include <set>
 #include <vector>
 #include <test_data.hpp>
 
@@ -624,51 +621,4 @@ static void FromCborChunkedString(benchmark::State& state, const std::size_t chu
 
 BENCHMARK_CAPTURE(FromCborChunkedString, 10000 chunks, 10000);
 
-// checked element access (at(i) must inline like operator[])
-static void ArrayAt(benchmark::State& state)
-{
-    json j = json::array();
-    for (int i = 0; i < 1000; ++i)
-    {
-        j.push_back(i);
-    }
-    const json& cj = j;
-
-    for (auto _ : state)
-    {
-        std::int64_t sum = 0;
-        for (std::size_t i = 0; i < 1000; ++i)
-        {
-            sum += cj.at(i).get<int>();
-        }
-        benchmark::DoNotOptimize(sum);
-    }
-    state.SetItemsProcessed(state.iterations() * 1000);
-}
-
-BENCHMARK(ArrayAt);
-
-// conversion of a JSON array into standard containers
-template<typename Container>
-static void GetArray(benchmark::State& state)
-{
-    json j = json::array();
-    for (int i = 0; i < 1000; ++i)
-    {
-        j.push_back(i);
-    }
-
-    for (auto _ : state)
-    {
-        auto c = j.get<Container>();
-        benchmark::DoNotOptimize(c);
-    }
-    state.SetItemsProcessed(state.iterations() * 1000);
-}
-
-BENCHMARK_TEMPLATE(GetArray, std::vector<int>);
-BENCHMARK_TEMPLATE(GetArray, std::deque<int>);
-BENCHMARK_TEMPLATE(GetArray, std::set<int>);
-BENCHMARK_TEMPLATE(GetArray, std::array<int, 1000>);
-
 BENCHMARK_MAIN();

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}}));
+    }
+}