Make flatten() linear for ordered_json

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

include/nlohmann/detail/input/json_sax.hpp

@@ -674,16 +674,19 @@ class json_sax_dom_callback_parser
         if (keep && ref_stack.back())
         {
             auto& obj = *ref_stack.back()->m_data.m_value.object;
-            const auto it = obj.find(val);
-            if (it != obj.end())
+            // a single lookup: insert the placeholder, or find the existing member
+            const auto inserted = obj.emplace(val, discarded);
+            const auto it = inserted.first;
+            if (!inserted.second)
             {
                 // this is a duplicate key (legal in JSON); remember its
                 // current value so it can be restored later if the new
                 // value is rejected by the callback, instead of being
                 // erased together with the discarded placeholder
                 duplicate_key_stash.emplace_back(&(it->second), it->second);
+                it->second = discarded;
             }
-            object_element = &(obj[val] = discarded);
+            object_element = &(it->second);
         }
 
         return true;

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

@@ -13850,16 +13850,19 @@ class json_sax_dom_callback_parser
         if (keep && ref_stack.back())
         {
             auto& obj = *ref_stack.back()->m_data.m_value.object;
-            const auto it = obj.find(val);
-            if (it != obj.end())
+            // a single lookup: insert the placeholder, or find the existing member
+            const auto inserted = obj.emplace(val, discarded);
+            const auto it = inserted.first;
+            if (!inserted.second)
             {
                 // this is a duplicate key (legal in JSON); remember its
                 // current value so it can be restored later if the new
                 // value is rejected by the callback, instead of being
                 // erased together with the discarded placeholder
                 duplicate_key_stash.emplace_back(&(it->second), it->second);
+                it->second = discarded;
             }
-            object_element = &(obj[val] = discarded);
+            object_element = &(it->second);
         }
 
         return true;
@@ -21559,6 +21562,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 +21623,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 +21633,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 +21647,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 +21667,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 +21713,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 +29183,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/benchmarks/README.md

@@ -16,13 +16,6 @@ Micro-benchmarks for parsing, serialization and the binary formats, written with
 | `FromBinaryBuffer`, `FromBinaryFile` | read CBOR, MessagePack, UBJSON, BJData and BSON from a buffer or a `FILE*` |
 | `FromBinaryShape` | read deeply nested, container-heavy and scalar-heavy documents in every binary format |
 | `FromCborChunkedString` | read CBOR strings split into indefinite-length chunks |
-| `SaxParse` | parse with a SAX handler that only counts events, so no values are built |
-| `Copy`, `Destroy`, `Equal`, `Iterate` | copy, destroy, or compare a parsed document, or visit every value with range-based `for` loops |
-| `Flatten`, `FlattenOrdered`, `Unflatten` | `flatten()` for `json` and `ordered_json`, and `unflatten()` |
-| `Diff`, `Patch` | `diff()` against the document with every eighth scalar changed, and applying that patch |
-| `JsonPointerParse`, `JsonPointerToString`, `JsonPointerAt`, `JsonPointerContains` | the JSON pointers of every scalar in a document: parse them from strings, turn them back into strings, look them up with `at()` and `contains()` |
-| `GetVectorInt`, `GetVectorDouble`, `GetMap` | `get<std::vector<std::int64_t>>()`, `get<std::vector<double>>()` and `get<std::map<std::string, json>>()` on large arrays and a large flat object |
-| `ToJsonStrings` | create a `json` array from a `std::vector` of 100,000 strings, copied or moved |
 
 The input files are those of [nativejson-benchmark](https://github.com/miloyip/nativejson-benchmark) (`canada`,
 `citm_catalog`, `twitter`), a large `jeopardy` file, and number-heavy files (`floats`, `signed_ints`, ...).

tests/benchmarks/src/benchmarks.cpp

@@ -8,11 +8,8 @@
 
 #include <benchmark/benchmark.h>
 #include <nlohmann/json.hpp>
-#include <cstdint>
 #include <fstream>
-#include <map>
 #include <numeric>
-#include <string>
 #include <vector>
 #include <test_data.hpp>
 
@@ -624,524 +621,4 @@ static void FromCborChunkedString(benchmark::State& state, const std::size_t chu
 
 BENCHMARK_CAPTURE(FromCborChunkedString, 10000 chunks, 10000);
 
-//////////////////////////////////////////////////////////////////////////////
-// SAX-parse JSON from string
-//
-// sax_parse() with a handler that does next to nothing runs the lexer and
-// parser without building values, so the gap to ParseString above is the cost
-// of building the DOM.
-//////////////////////////////////////////////////////////////////////////////
-
-static std::string read_file(const char* filename)
-{
-    std::ifstream f(filename);
-    return std::string((std::istreambuf_iterator<char>(f)), std::istreambuf_iterator<char>());
-}
-
-static json load_json(const char* filename)
-{
-    return json::parse(read_file(filename));
-}
-
-/// SAX handler that only counts the events, so that the handler costs next to nothing
-class counting_sax : public nlohmann::json_sax<json>
-{
-  public:
-    std::size_t events = 0;
-
-    bool null() override
-    {
-        return count();
-    }
-    bool boolean(bool /*val*/) override
-    {
-        return count();
-    }
-    bool number_integer(number_integer_t /*val*/) override
-    {
-        return count();
-    }
-    bool number_unsigned(number_unsigned_t /*val*/) override
-    {
-        return count();
-    }
-    bool number_float(number_float_t /*val*/, const string_t& /*s*/) override
-    {
-        return count();
-    }
-    bool string(string_t& /*val*/) override
-    {
-        return count();
-    }
-    bool binary(binary_t& /*val*/) override
-    {
-        return count();
-    }
-    bool start_object(std::size_t /*elements*/) override
-    {
-        return count();
-    }
-    bool key(string_t& /*val*/) override
-    {
-        return count();
-    }
-    bool end_object() override
-    {
-        return count();
-    }
-    bool start_array(std::size_t /*elements*/) override
-    {
-        return count();
-    }
-    bool end_array() override
-    {
-        return count();
-    }
-    bool parse_error(std::size_t /*position*/, const std::string& /*last_token*/, const json::exception& /*ex*/) override
-    {
-        return false;
-    }
-
-  private:
-    bool count()
-    {
-        ++events;
-        return true;
-    }
-};
-
-static void SaxParse(benchmark::State& state, const char* filename)
-{
-    const std::string str = read_file(filename);
-
-    for (auto _ : state)
-    {
-        counting_sax sax;
-        bool result = json::sax_parse(str, &sax);
-        benchmark::DoNotOptimize(result);
-        benchmark::DoNotOptimize(sax.events);
-    }
-
-    state.SetBytesProcessed(state.iterations() * str.size());
-}
-BENCHMARK_CAPTURE(SaxParse, canada,       TEST_DATA_DIRECTORY "/nativejson-benchmark/canada.json");
-BENCHMARK_CAPTURE(SaxParse, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(SaxParse, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-//////////////////////////////////////////////////////////////////////////////
-// work with values: copy, destroy, compare, iterate
-//
-// The parsed test files stand in for a document an application keeps around.
-// Each benchmark times one whole-document operation; setup and cleanup run
-// outside the timed section.
-//////////////////////////////////////////////////////////////////////////////
-
-static void Copy(benchmark::State& state, const char* filename)
-{
-    const json j = load_json(filename);
-
-    for (auto _ : state)
-    {
-        auto* copy = new json(j);
-
-        state.PauseTiming();
-        delete copy;
-        state.ResumeTiming();
-    }
-}
-BENCHMARK_CAPTURE(Copy, canada,       TEST_DATA_DIRECTORY "/nativejson-benchmark/canada.json");
-BENCHMARK_CAPTURE(Copy, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(Copy, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-static void Destroy(benchmark::State& state, const char* filename)
-{
-    const json j = load_json(filename);
-
-    for (auto _ : state)
-    {
-        state.PauseTiming();
-        auto* copy = new json(j);
-        state.ResumeTiming();
-
-        delete copy;
-    }
-}
-BENCHMARK_CAPTURE(Destroy, canada,       TEST_DATA_DIRECTORY "/nativejson-benchmark/canada.json");
-BENCHMARK_CAPTURE(Destroy, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(Destroy, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-static void Equal(benchmark::State& state, const char* filename)
-{
-    // two separate values, so that the comparison cannot stop at identical addresses
-    const json j = load_json(filename);
-    const json copy = j;
-
-    for (auto _ : state)
-    {
-        bool result = (j == copy);
-        benchmark::DoNotOptimize(result);
-    }
-}
-BENCHMARK_CAPTURE(Equal, canada,       TEST_DATA_DIRECTORY "/nativejson-benchmark/canada.json");
-BENCHMARK_CAPTURE(Equal, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(Equal, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-/// visit every value with range-based for loops, as client code walks a document
-static std::size_t count_values(const json& j)
-{
-    std::size_t result = 1;
-    if (j.is_structured())
-    {
-        for (const auto& element : j)
-        {
-            result += count_values(element);
-        }
-    }
-    return result;
-}
-
-static void Iterate(benchmark::State& state, const char* filename)
-{
-    const json j = load_json(filename);
-
-    for (auto _ : state)
-    {
-        std::size_t result = count_values(j);
-        benchmark::DoNotOptimize(result);
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(count_values(j)));
-}
-BENCHMARK_CAPTURE(Iterate, canada,       TEST_DATA_DIRECTORY "/nativejson-benchmark/canada.json");
-BENCHMARK_CAPTURE(Iterate, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(Iterate, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-//////////////////////////////////////////////////////////////////////////////
-// flatten and unflatten
-//////////////////////////////////////////////////////////////////////////////
-
-static void Flatten(benchmark::State& state, const char* filename)
-{
-    const json j = load_json(filename);
-
-    for (auto _ : state)
-    {
-        json flat = j.flatten();
-        benchmark::DoNotOptimize(flat);
-    }
-}
-BENCHMARK_CAPTURE(Flatten, canada,       TEST_DATA_DIRECTORY "/nativejson-benchmark/canada.json");
-BENCHMARK_CAPTURE(Flatten, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(Flatten, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-// ordered_json objects look keys up linearly, which flatten() used to do for
-// every value; canada (330,000 values in one flat object) is left out, as it
-// would take minutes with such versions
-static void FlattenOrdered(benchmark::State& state, const char* filename)
-{
-    const nlohmann::ordered_json j = nlohmann::ordered_json::parse(read_file(filename));
-
-    for (auto _ : state)
-    {
-        nlohmann::ordered_json flat = j.flatten();
-        benchmark::DoNotOptimize(flat);
-    }
-}
-BENCHMARK_CAPTURE(FlattenOrdered, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(FlattenOrdered, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-static void Unflatten(benchmark::State& state, const char* filename)
-{
-    const json flat = load_json(filename).flatten();
-
-    for (auto _ : state)
-    {
-        json j = flat.unflatten();
-        benchmark::DoNotOptimize(j);
-    }
-}
-BENCHMARK_CAPTURE(Unflatten, canada,       TEST_DATA_DIRECTORY "/nativejson-benchmark/canada.json");
-BENCHMARK_CAPTURE(Unflatten, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(Unflatten, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-//////////////////////////////////////////////////////////////////////////////
-// diff and patch
-//
-// The target is the document with every eighth scalar changed, so the patch
-// has one "replace" operation per changed value and the structure stays the
-// same.
-//////////////////////////////////////////////////////////////////////////////
-
-static void change_every_eighth_scalar(json& j, std::size_t& counter)
-{
-    if (j.is_structured())
-    {
-        for (auto& element : j)
-        {
-            change_every_eighth_scalar(element, counter);
-        }
-        return;
-    }
-
-    if (++counter % 8 != 0)
-    {
-        return;
-    }
-
-    switch (j.type())
-    {
-        case json::value_t::number_integer:
-            j = j.get<json::number_integer_t>() + 1;
-            break;
-        case json::value_t::number_unsigned:
-            j = j.get<json::number_unsigned_t>() + 1;
-            break;
-        case json::value_t::number_float:
-            j = j.get<json::number_float_t>() + 0.5;
-            break;
-        case json::value_t::string:
-            j = j.get<std::string>() + "!";
-            break;
-        case json::value_t::boolean:
-            j = !j.get<bool>();
-            break;
-        case json::value_t::null:
-        case json::value_t::object:
-        case json::value_t::array:
-        case json::value_t::binary:
-        case json::value_t::discarded:
-        default:
-            j = 0;
-            break;
-    }
-}
-
-static json changed_copy(const json& j)
-{
-    json result = j;
-    std::size_t counter = 0;
-    change_every_eighth_scalar(result, counter);
-    return result;
-}
-
-static void Diff(benchmark::State& state, const char* filename)
-{
-    const json source = load_json(filename);
-    const json target = changed_copy(source);
-
-    for (auto _ : state)
-    {
-        json patch = json::diff(source, target);
-        benchmark::DoNotOptimize(patch);
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(json::diff(source, target).size()));
-}
-BENCHMARK_CAPTURE(Diff, canada,       TEST_DATA_DIRECTORY "/nativejson-benchmark/canada.json");
-BENCHMARK_CAPTURE(Diff, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(Diff, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-static void Patch(benchmark::State& state, const char* filename)
-{
-    const json source = load_json(filename);
-    const json patch = json::diff(source, changed_copy(source));
-
-    for (auto _ : state)
-    {
-        json result = source.patch(patch);
-        benchmark::DoNotOptimize(result);
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(patch.size()));
-}
-BENCHMARK_CAPTURE(Patch, canada,       TEST_DATA_DIRECTORY "/nativejson-benchmark/canada.json");
-BENCHMARK_CAPTURE(Patch, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(Patch, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-//////////////////////////////////////////////////////////////////////////////
-// JSON Pointer
-//
-// The pointers are those of every scalar in the document, i.e., the keys of
-// its flattened form.
-//////////////////////////////////////////////////////////////////////////////
-
-static std::vector<std::string> pointer_strings(const json& j)
-{
-    std::vector<std::string> result;
-    const json flat = j.flatten();
-    result.reserve(flat.size());
-    for (auto it = flat.begin(); it != flat.end(); ++it)
-    {
-        result.push_back(it.key());
-    }
-    return result;
-}
-
-static std::vector<json::json_pointer> pointers(const json& j)
-{
-    const std::vector<std::string> strings = pointer_strings(j);
-    std::vector<json::json_pointer> result;
-    result.reserve(strings.size());
-    for (const auto& s : strings)
-    {
-        result.emplace_back(s);
-    }
-    return result;
-}
-
-static void JsonPointerParse(benchmark::State& state, const char* filename)
-{
-    const std::vector<std::string> strings = pointer_strings(load_json(filename));
-
-    for (auto _ : state)
-    {
-        for (const auto& s : strings)
-        {
-            json::json_pointer ptr(s);
-            benchmark::DoNotOptimize(ptr);
-        }
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(strings.size()));
-}
-BENCHMARK_CAPTURE(JsonPointerParse, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(JsonPointerParse, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-static void JsonPointerToString(benchmark::State& state, const char* filename)
-{
-    const std::vector<json::json_pointer> ptrs = pointers(load_json(filename));
-
-    for (auto _ : state)
-    {
-        for (const auto& ptr : ptrs)
-        {
-            std::string s = ptr.to_string();
-            benchmark::DoNotOptimize(s);
-        }
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(ptrs.size()));
-}
-BENCHMARK_CAPTURE(JsonPointerToString, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(JsonPointerToString, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-static void JsonPointerAt(benchmark::State& state, const char* filename)
-{
-    const json j = load_json(filename);
-    const std::vector<json::json_pointer> ptrs = pointers(j);
-
-    for (auto _ : state)
-    {
-        for (const auto& ptr : ptrs)
-        {
-            const json& value = j.at(ptr);
-            benchmark::DoNotOptimize(&value);
-        }
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(ptrs.size()));
-}
-BENCHMARK_CAPTURE(JsonPointerAt, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(JsonPointerAt, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-static void JsonPointerContains(benchmark::State& state, const char* filename)
-{
-    const json j = load_json(filename);
-    const std::vector<json::json_pointer> ptrs = pointers(j);
-
-    for (auto _ : state)
-    {
-        for (const auto& ptr : ptrs)
-        {
-            bool result = j.contains(ptr);
-            benchmark::DoNotOptimize(result);
-        }
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(ptrs.size()));
-}
-BENCHMARK_CAPTURE(JsonPointerContains, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-BENCHMARK_CAPTURE(JsonPointerContains, twitter,      TEST_DATA_DIRECTORY "/nativejson-benchmark/twitter.json");
-
-//////////////////////////////////////////////////////////////////////////////
-// conversions from and to C++ containers
-//////////////////////////////////////////////////////////////////////////////
-
-static void GetVectorInt(benchmark::State& state, const char* filename)
-{
-    const json j = load_json(filename);
-
-    for (auto _ : state)
-    {
-        auto v = j.get<std::vector<std::int64_t>>();
-        benchmark::DoNotOptimize(v);
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(j.size()));
-}
-BENCHMARK_CAPTURE(GetVectorInt, signed_ints, TEST_DATA_DIRECTORY "/regression/signed_ints.json");
-
-static void GetVectorDouble(benchmark::State& state, const char* filename)
-{
-    const json j = load_json(filename);
-
-    for (auto _ : state)
-    {
-        auto v = j.get<std::vector<double>>();
-        benchmark::DoNotOptimize(v);
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(j.size()));
-}
-BENCHMARK_CAPTURE(GetVectorDouble, floats, TEST_DATA_DIRECTORY "/regression/floats.json");
-
-// a large flat object: the flattened document, one member per scalar
-static void GetMap(benchmark::State& state, const char* filename)
-{
-    const json j = load_json(filename).flatten();
-
-    for (auto _ : state)
-    {
-        auto m = j.get<std::map<std::string, json>>();
-        benchmark::DoNotOptimize(m);
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(j.size()));
-}
-BENCHMARK_CAPTURE(GetMap, citm_catalog, TEST_DATA_DIRECTORY "/nativejson-benchmark/citm_catalog.json");
-
-/// 100,000 strings, each too long for the small string optimization
-static std::vector<std::string> make_strings()
-{
-    std::vector<std::string> result;
-    result.reserve(100000);
-    for (std::size_t i = 0; i < 100000; ++i)
-    {
-        result.push_back("a string that does not fit in place: " + std::to_string(i));
-    }
-    return result;
-}
-
-static void ToJsonStrings(benchmark::State& state, const bool move)
-{
-    const std::vector<std::string> strings = make_strings();
-
-    for (auto _ : state)
-    {
-        state.PauseTiming();
-        std::vector<std::string> input = strings;
-        state.ResumeTiming();
-
-        auto* j = move ? new json(std::move(input)) : new json(input);
-
-        state.PauseTiming();
-        delete j;
-        state.ResumeTiming();
-    }
-
-    state.SetItemsProcessed(state.iterations() * static_cast<std::int64_t>(strings.size()));
-}
-BENCHMARK_CAPTURE(ToJsonStrings, copy, false);
-BENCHMARK_CAPTURE(ToJsonStrings, move, true);
-
 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}}));
+    }
+}