Test unordered object equality without std::unordered_map

basic_json<std::unordered_map> instantiates std::pair<const string,
basic_json> while basic_json is still incomplete. The standard does not
require std::unordered_map to support that, and libstdc++ 6 to 9 as well
as the EDG front ends of icpc and nvc++ reject it, which broke the build
of unit-comparison on those CI jobs.

The test now uses an object type derived from std::map (which, as the
default object type, works everywhere) whose comparator orders keys
ascending or descending as chosen at construction, and whose operator==
does not depend on the order of the entries - the property of
std::unordered_map the test is about.

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

include/nlohmann/detail/conversions/to_json.hpp

@@ -42,10 +42,6 @@ namespace detail
  * j.m_data.m_value.destroy(j.m_data.m_type) to avoid a memory leak in case j contains an
  * allocated value (e.g., a string). See bug issue
  * https://github.com/nlohmann/json/issues/2865 for more information.
- *
- * A value that has to be allocated is created before the old one is destroyed:
- * were it the other way around, an exception while creating the new value would
- * leave j with the type of the new value, but the pointer to the destroyed old one.
  */
 
 template<value_t> struct external_constructor;
@@ -69,20 +65,18 @@ struct external_constructor<value_t::string>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, const typename BasicJsonType::string_t& s)
     {
-        const typename BasicJsonType::json_value value(s);
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::string;
-        j.m_data.m_value = value;
+        j.m_data.m_value = s;
         j.assert_invariant();
     }
 
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, typename BasicJsonType::string_t&& s)
     {
-        const typename BasicJsonType::json_value value(std::move(s));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::string;
-        j.m_data.m_value = value;
+        j.m_data.m_value = std::move(s);
         j.assert_invariant();
     }
 
@@ -91,10 +85,9 @@ struct external_constructor<value_t::string>
                              int > = 0 >
     static void construct(BasicJsonType& j, const CompatibleStringType& str)
     {
-        auto* created = j.template create<typename BasicJsonType::string_t>(str);
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::string;
-        j.m_data.m_value.string = created;
+        j.m_data.m_value.string = j.template create<typename BasicJsonType::string_t>(str);
         j.assert_invariant();
     }
 };
@@ -105,20 +98,18 @@ struct external_constructor<value_t::binary>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, const typename BasicJsonType::binary_t& b)
     {
-        const typename BasicJsonType::json_value value(b);
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::binary;
-        j.m_data.m_value = value;
+        j.m_data.m_value = typename BasicJsonType::binary_t(b);
         j.assert_invariant();
     }
 
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, typename BasicJsonType::binary_t&& b)
     {
-        const typename BasicJsonType::json_value value(std::move(b));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::binary;
-        j.m_data.m_value = value;
+        j.m_data.m_value = typename BasicJsonType::binary_t(std::move(b));
         j.assert_invariant();
     }
 };
@@ -168,10 +159,9 @@ struct external_constructor<value_t::array>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, const typename BasicJsonType::array_t& arr)
     {
-        const typename BasicJsonType::json_value value(arr);
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value = value;
+        j.m_data.m_value = arr;
         j.set_parents();
         j.assert_invariant();
     }
@@ -179,10 +169,9 @@ struct external_constructor<value_t::array>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, typename BasicJsonType::array_t&& arr)
     {
-        const typename BasicJsonType::json_value value(std::move(arr));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value = value;
+        j.m_data.m_value = std::move(arr);
         j.set_parents();
         j.assert_invariant();
     }
@@ -198,10 +187,9 @@ struct external_constructor<value_t::array>
         using std::begin;
         using std::end;
 
-        auto* created = j.template create<typename BasicJsonType::array_t>(begin(arr), end(arr));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value.array = created;
+        j.m_data.m_value.array = j.template create<typename BasicJsonType::array_t>(begin(arr), end(arr));
         j.set_parents();
         j.assert_invariant();
     }
@@ -209,17 +197,15 @@ struct external_constructor<value_t::array>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, const std::vector<bool>& arr)
     {
-        typename BasicJsonType::array_t elements;
-        elements.reserve(arr.size());
-        for (const bool x : arr)
-        {
-            elements.push_back(x);
-        }
-        const typename BasicJsonType::json_value value(std::move(elements));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value = value;
-        j.set_parents();
+        j.m_data.m_value = value_t::array;
+        j.m_data.m_value.array->reserve(arr.size());
+        for (const bool x : arr)
+        {
+            j.m_data.m_value.array->push_back(x);
+            j.set_parent(j.m_data.m_value.array->back());
+        }
         j.assert_invariant();
     }
 
@@ -227,12 +213,11 @@ struct external_constructor<value_t::array>
              enable_if_t<std::is_convertible<T, BasicJsonType>::value, int> = 0>
     static void construct(BasicJsonType& j, const std::valarray<T>& arr)
     {
-        typename BasicJsonType::array_t elements(arr.size());
-        std::copy(std::begin(arr), std::end(arr), elements.begin());
-        const typename BasicJsonType::json_value value(std::move(elements));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value = value;
+        j.m_data.m_value = value_t::array;
+        j.m_data.m_value.array->resize(arr.size());
+        std::copy(std::begin(arr), std::end(arr), j.m_data.m_value.array->begin());
         j.set_parents();
         j.assert_invariant();
     }
@@ -244,16 +229,14 @@ struct external_constructor<value_t::array>
              enable_if_t<is_compatible_range_view<std::remove_cvref_t<CompatibleArrayType>>::value, int> = 0>
     static void construct(BasicJsonType& j, CompatibleArrayType && arr)
     {
-        typename BasicJsonType::array_t elements;
-        for (auto&& x : std::forward<CompatibleArrayType>(arr))
-        {
-            elements.push_back(x);
-        }
-        const typename BasicJsonType::json_value value(std::move(elements));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value = value;
-        j.set_parents();
+        j.m_data.m_value = value_t::array;
+        for (auto&& x : std::forward<CompatibleArrayType>(arr))
+        {
+            j.m_data.m_value.array->push_back(x);
+            j.set_parent(j.m_data.m_value.array->back());
+        }
         j.assert_invariant();
     }
 #endif
@@ -265,10 +248,9 @@ struct external_constructor<value_t::object>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, const typename BasicJsonType::object_t& obj)
     {
-        const typename BasicJsonType::json_value value(obj);
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::object;
-        j.m_data.m_value = value;
+        j.m_data.m_value = obj;
         j.set_parents();
         j.assert_invariant();
     }
@@ -276,10 +258,9 @@ struct external_constructor<value_t::object>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, typename BasicJsonType::object_t&& obj)
     {
-        const typename BasicJsonType::json_value value(std::move(obj));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::object;
-        j.m_data.m_value = value;
+        j.m_data.m_value = std::move(obj);
         j.set_parents();
         j.assert_invariant();
     }
@@ -291,10 +272,9 @@ struct external_constructor<value_t::object>
         using std::begin;
         using std::end;
 
-        auto* created = j.template create<typename BasicJsonType::object_t>(begin(obj), end(obj));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::object;
-        j.m_data.m_value.object = created;
+        j.m_data.m_value.object = j.template create<typename BasicJsonType::object_t>(begin(obj), end(obj));
         j.set_parents();
         j.assert_invariant();
     }

include/nlohmann/json.hpp

@@ -1492,13 +1492,28 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                         compare_keys(current.lhs_object_it->first, current.rhs_object_it->first,
                                      std::integral_constant<bool, Ordered> {});
 
-                    if (key_result != compare_result::equal)
-                    {
-                        return key_result;
-                    }
-
                     left = &(current.lhs_object_it->second);
                     right = &(current.rhs_object_it->second);
+
+                    if (key_result != compare_result::equal)
+                    {
+                        // An object type without a fixed order of its entries -
+                        // std::unordered_map, say - may enumerate two equal
+                        // objects differently, and its operator== does not care.
+                        // Equality then finds the entry by its key; an ordering,
+                        // or an object type that compares its entries in
+                        // sequence (ordered_map), is decided by the key itself.
+                        const auto* rhs_object = current.rhs_value->m_data.m_value.object;
+                        const auto found = (!Ordered && !detail::is_ordered_map<object_t>::value)
+                                           ? rhs_object->find(current.lhs_object_it->first)
+                                           : rhs_object->cend();
+                        if (found == rhs_object->cend())
+                        {
+                            return key_result;
+                        }
+                        right = &(found->second);
+                    }
+
                     ++current.lhs_object_it;
                     ++current.rhs_object_it;
                 }
@@ -1687,8 +1702,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         if (is_an_object)
         {
             // the initializer list is a list of pairs -> create an object
-            m_data.m_value = value_t::object;
             m_data.m_type = value_t::object;
+            m_data.m_value = value_t::object;
 
             for (auto& element_ref : init)
             {
@@ -1710,8 +1725,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             }
 #endif
             // the initializer list describes an array -> create an array
-            m_data.m_value.array = create<array_t>(init.begin(), init.end());
             m_data.m_type = value_t::array;
+            m_data.m_value.array = create<array_t>(init.begin(), init.end());
         }
 
         set_parents();
@@ -1724,8 +1739,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     static basic_json binary(const typename binary_t::container_type& init)
     {
         auto res = basic_json();
-        res.m_data.m_value = init;
         res.m_data.m_type = value_t::binary;
+        res.m_data.m_value = init;
         return res;
     }
 
@@ -1735,8 +1750,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     static basic_json binary(const typename binary_t::container_type& init, typename binary_t::subtype_type subtype)
     {
         auto res = basic_json();
-        res.m_data.m_value = binary_t(init, subtype);
         res.m_data.m_type = value_t::binary;
+        res.m_data.m_value = binary_t(init, subtype);
         return res;
     }
 
@@ -1746,8 +1761,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     static basic_json binary(typename binary_t::container_type&& init)
     {
         auto res = basic_json();
-        res.m_data.m_value = std::move(init);
         res.m_data.m_type = value_t::binary;
+        res.m_data.m_value = std::move(init);
         return res;
     }
 
@@ -1757,8 +1772,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     static basic_json binary(typename binary_t::container_type&& init, typename binary_t::subtype_type subtype)
     {
         auto res = basic_json();
-        res.m_data.m_value = binary_t(std::move(init), subtype);
         res.m_data.m_type = value_t::binary;
+        res.m_data.m_value = binary_t(std::move(init), subtype);
         return res;
     }
 
@@ -2815,8 +2830,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // implicitly convert a null value to an empty array
         if (is_null())
         {
-            m_data.m_value.array = create<array_t>();
             m_data.m_type = value_t::array;
+            m_data.m_value.array = create<array_t>();
             assert_invariant();
         }
 
@@ -2875,8 +2890,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // implicitly convert a null value to an empty object
         if (is_null())
         {
-            m_data.m_value.object = create<object_t>();
             m_data.m_type = value_t::object;
+            m_data.m_value.object = create<object_t>();
             assert_invariant();
         }
 
@@ -2928,8 +2943,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // implicitly convert a null value to an empty object
         if (is_null())
         {
-            m_data.m_value.object = create<object_t>();
             m_data.m_type = value_t::object;
+            m_data.m_value.object = create<object_t>();
             assert_invariant();
         }
 
@@ -3864,8 +3879,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // transform a null object into an array
         if (is_null())
         {
-            m_data.m_value = value_t::array;
             m_data.m_type = value_t::array;
+            m_data.m_value = value_t::array;
             assert_invariant();
         }
 
@@ -3897,8 +3912,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // transform a null object into an array
         if (is_null())
         {
-            m_data.m_value = value_t::array;
             m_data.m_type = value_t::array;
+            m_data.m_value = value_t::array;
             assert_invariant();
         }
 
@@ -3929,8 +3944,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // transform a null object into an object
         if (is_null())
         {
-            m_data.m_value = value_t::object;
             m_data.m_type = value_t::object;
+            m_data.m_value = value_t::object;
             assert_invariant();
         }
 
@@ -3985,8 +4000,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // transform a null object into an array
         if (is_null())
         {
-            m_data.m_value = value_t::array;
             m_data.m_type = value_t::array;
+            m_data.m_value = value_t::array;
             assert_invariant();
         }
 
@@ -4010,8 +4025,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // transform a null object into an object
         if (is_null())
         {
-            m_data.m_value = value_t::object;
             m_data.m_type = value_t::object;
+            m_data.m_value = value_t::object;
             assert_invariant();
         }
 
@@ -4192,8 +4207,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // implicitly convert a null value to an empty object
         if (is_null())
         {
-            m_data.m_value.object = create<object_t>();
             m_data.m_type = value_t::object;
+            m_data.m_value.object = create<object_t>();
             assert_invariant();
         }
 

single_include/nlohmann/json.hpp

@@ -6571,10 +6571,6 @@ namespace detail
  * j.m_data.m_value.destroy(j.m_data.m_type) to avoid a memory leak in case j contains an
  * allocated value (e.g., a string). See bug issue
  * https://github.com/nlohmann/json/issues/2865 for more information.
- *
- * A value that has to be allocated is created before the old one is destroyed:
- * were it the other way around, an exception while creating the new value would
- * leave j with the type of the new value, but the pointer to the destroyed old one.
  */
 
 template<value_t> struct external_constructor;
@@ -6598,20 +6594,18 @@ struct external_constructor<value_t::string>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, const typename BasicJsonType::string_t& s)
     {
-        const typename BasicJsonType::json_value value(s);
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::string;
-        j.m_data.m_value = value;
+        j.m_data.m_value = s;
         j.assert_invariant();
     }
 
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, typename BasicJsonType::string_t&& s)
     {
-        const typename BasicJsonType::json_value value(std::move(s));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::string;
-        j.m_data.m_value = value;
+        j.m_data.m_value = std::move(s);
         j.assert_invariant();
     }
 
@@ -6620,10 +6614,9 @@ struct external_constructor<value_t::string>
                              int > = 0 >
     static void construct(BasicJsonType& j, const CompatibleStringType& str)
     {
-        auto* created = j.template create<typename BasicJsonType::string_t>(str);
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::string;
-        j.m_data.m_value.string = created;
+        j.m_data.m_value.string = j.template create<typename BasicJsonType::string_t>(str);
         j.assert_invariant();
     }
 };
@@ -6634,20 +6627,18 @@ struct external_constructor<value_t::binary>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, const typename BasicJsonType::binary_t& b)
     {
-        const typename BasicJsonType::json_value value(b);
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::binary;
-        j.m_data.m_value = value;
+        j.m_data.m_value = typename BasicJsonType::binary_t(b);
         j.assert_invariant();
     }
 
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, typename BasicJsonType::binary_t&& b)
     {
-        const typename BasicJsonType::json_value value(std::move(b));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::binary;
-        j.m_data.m_value = value;
+        j.m_data.m_value = typename BasicJsonType::binary_t(std::move(b));
         j.assert_invariant();
     }
 };
@@ -6697,10 +6688,9 @@ struct external_constructor<value_t::array>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, const typename BasicJsonType::array_t& arr)
     {
-        const typename BasicJsonType::json_value value(arr);
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value = value;
+        j.m_data.m_value = arr;
         j.set_parents();
         j.assert_invariant();
     }
@@ -6708,10 +6698,9 @@ struct external_constructor<value_t::array>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, typename BasicJsonType::array_t&& arr)
     {
-        const typename BasicJsonType::json_value value(std::move(arr));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value = value;
+        j.m_data.m_value = std::move(arr);
         j.set_parents();
         j.assert_invariant();
     }
@@ -6727,10 +6716,9 @@ struct external_constructor<value_t::array>
         using std::begin;
         using std::end;
 
-        auto* created = j.template create<typename BasicJsonType::array_t>(begin(arr), end(arr));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value.array = created;
+        j.m_data.m_value.array = j.template create<typename BasicJsonType::array_t>(begin(arr), end(arr));
         j.set_parents();
         j.assert_invariant();
     }
@@ -6738,17 +6726,15 @@ struct external_constructor<value_t::array>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, const std::vector<bool>& arr)
     {
-        typename BasicJsonType::array_t elements;
-        elements.reserve(arr.size());
-        for (const bool x : arr)
-        {
-            elements.push_back(x);
-        }
-        const typename BasicJsonType::json_value value(std::move(elements));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value = value;
-        j.set_parents();
+        j.m_data.m_value = value_t::array;
+        j.m_data.m_value.array->reserve(arr.size());
+        for (const bool x : arr)
+        {
+            j.m_data.m_value.array->push_back(x);
+            j.set_parent(j.m_data.m_value.array->back());
+        }
         j.assert_invariant();
     }
 
@@ -6756,12 +6742,11 @@ struct external_constructor<value_t::array>
              enable_if_t<std::is_convertible<T, BasicJsonType>::value, int> = 0>
     static void construct(BasicJsonType& j, const std::valarray<T>& arr)
     {
-        typename BasicJsonType::array_t elements(arr.size());
-        std::copy(std::begin(arr), std::end(arr), elements.begin());
-        const typename BasicJsonType::json_value value(std::move(elements));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value = value;
+        j.m_data.m_value = value_t::array;
+        j.m_data.m_value.array->resize(arr.size());
+        std::copy(std::begin(arr), std::end(arr), j.m_data.m_value.array->begin());
         j.set_parents();
         j.assert_invariant();
     }
@@ -6773,16 +6758,14 @@ struct external_constructor<value_t::array>
              enable_if_t<is_compatible_range_view<std::remove_cvref_t<CompatibleArrayType>>::value, int> = 0>
     static void construct(BasicJsonType& j, CompatibleArrayType && arr)
     {
-        typename BasicJsonType::array_t elements;
-        for (auto&& x : std::forward<CompatibleArrayType>(arr))
-        {
-            elements.push_back(x);
-        }
-        const typename BasicJsonType::json_value value(std::move(elements));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::array;
-        j.m_data.m_value = value;
-        j.set_parents();
+        j.m_data.m_value = value_t::array;
+        for (auto&& x : std::forward<CompatibleArrayType>(arr))
+        {
+            j.m_data.m_value.array->push_back(x);
+            j.set_parent(j.m_data.m_value.array->back());
+        }
         j.assert_invariant();
     }
 #endif
@@ -6794,10 +6777,9 @@ struct external_constructor<value_t::object>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, const typename BasicJsonType::object_t& obj)
     {
-        const typename BasicJsonType::json_value value(obj);
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::object;
-        j.m_data.m_value = value;
+        j.m_data.m_value = obj;
         j.set_parents();
         j.assert_invariant();
     }
@@ -6805,10 +6787,9 @@ struct external_constructor<value_t::object>
     template<typename BasicJsonType>
     static void construct(BasicJsonType& j, typename BasicJsonType::object_t&& obj)
     {
-        const typename BasicJsonType::json_value value(std::move(obj));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::object;
-        j.m_data.m_value = value;
+        j.m_data.m_value = std::move(obj);
         j.set_parents();
         j.assert_invariant();
     }
@@ -6820,10 +6801,9 @@ struct external_constructor<value_t::object>
         using std::begin;
         using std::end;
 
-        auto* created = j.template create<typename BasicJsonType::object_t>(begin(obj), end(obj));
         j.m_data.m_value.destroy(j.m_data.m_type);
         j.m_data.m_type = value_t::object;
-        j.m_data.m_value.object = created;
+        j.m_data.m_value.object = j.template create<typename BasicJsonType::object_t>(begin(obj), end(obj));
         j.set_parents();
         j.assert_invariant();
     }
@@ -26470,13 +26450,28 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
                         compare_keys(current.lhs_object_it->first, current.rhs_object_it->first,
                                      std::integral_constant<bool, Ordered> {});
 
-                    if (key_result != compare_result::equal)
-                    {
-                        return key_result;
-                    }
-
                     left = &(current.lhs_object_it->second);
                     right = &(current.rhs_object_it->second);
+
+                    if (key_result != compare_result::equal)
+                    {
+                        // An object type without a fixed order of its entries -
+                        // std::unordered_map, say - may enumerate two equal
+                        // objects differently, and its operator== does not care.
+                        // Equality then finds the entry by its key; an ordering,
+                        // or an object type that compares its entries in
+                        // sequence (ordered_map), is decided by the key itself.
+                        const auto* rhs_object = current.rhs_value->m_data.m_value.object;
+                        const auto found = (!Ordered && !detail::is_ordered_map<object_t>::value)
+                                           ? rhs_object->find(current.lhs_object_it->first)
+                                           : rhs_object->cend();
+                        if (found == rhs_object->cend())
+                        {
+                            return key_result;
+                        }
+                        right = &(found->second);
+                    }
+
                     ++current.lhs_object_it;
                     ++current.rhs_object_it;
                 }
@@ -26665,8 +26660,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         if (is_an_object)
         {
             // the initializer list is a list of pairs -> create an object
-            m_data.m_value = value_t::object;
             m_data.m_type = value_t::object;
+            m_data.m_value = value_t::object;
 
             for (auto& element_ref : init)
             {
@@ -26688,8 +26683,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
             }
 #endif
             // the initializer list describes an array -> create an array
-            m_data.m_value.array = create<array_t>(init.begin(), init.end());
             m_data.m_type = value_t::array;
+            m_data.m_value.array = create<array_t>(init.begin(), init.end());
         }
 
         set_parents();
@@ -26702,8 +26697,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     static basic_json binary(const typename binary_t::container_type& init)
     {
         auto res = basic_json();
-        res.m_data.m_value = init;
         res.m_data.m_type = value_t::binary;
+        res.m_data.m_value = init;
         return res;
     }
 
@@ -26713,8 +26708,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     static basic_json binary(const typename binary_t::container_type& init, typename binary_t::subtype_type subtype)
     {
         auto res = basic_json();
-        res.m_data.m_value = binary_t(init, subtype);
         res.m_data.m_type = value_t::binary;
+        res.m_data.m_value = binary_t(init, subtype);
         return res;
     }
 
@@ -26724,8 +26719,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     static basic_json binary(typename binary_t::container_type&& init)
     {
         auto res = basic_json();
-        res.m_data.m_value = std::move(init);
         res.m_data.m_type = value_t::binary;
+        res.m_data.m_value = std::move(init);
         return res;
     }
 
@@ -26735,8 +26730,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
     static basic_json binary(typename binary_t::container_type&& init, typename binary_t::subtype_type subtype)
     {
         auto res = basic_json();
-        res.m_data.m_value = binary_t(std::move(init), subtype);
         res.m_data.m_type = value_t::binary;
+        res.m_data.m_value = binary_t(std::move(init), subtype);
         return res;
     }
 
@@ -27793,8 +27788,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // implicitly convert a null value to an empty array
         if (is_null())
         {
-            m_data.m_value.array = create<array_t>();
             m_data.m_type = value_t::array;
+            m_data.m_value.array = create<array_t>();
             assert_invariant();
         }
 
@@ -27853,8 +27848,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // implicitly convert a null value to an empty object
         if (is_null())
         {
-            m_data.m_value.object = create<object_t>();
             m_data.m_type = value_t::object;
+            m_data.m_value.object = create<object_t>();
             assert_invariant();
         }
 
@@ -27906,8 +27901,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // implicitly convert a null value to an empty object
         if (is_null())
         {
-            m_data.m_value.object = create<object_t>();
             m_data.m_type = value_t::object;
+            m_data.m_value.object = create<object_t>();
             assert_invariant();
         }
 
@@ -28842,8 +28837,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // transform a null object into an array
         if (is_null())
         {
-            m_data.m_value = value_t::array;
             m_data.m_type = value_t::array;
+            m_data.m_value = value_t::array;
             assert_invariant();
         }
 
@@ -28875,8 +28870,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // transform a null object into an array
         if (is_null())
         {
-            m_data.m_value = value_t::array;
             m_data.m_type = value_t::array;
+            m_data.m_value = value_t::array;
             assert_invariant();
         }
 
@@ -28907,8 +28902,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // transform a null object into an object
         if (is_null())
         {
-            m_data.m_value = value_t::object;
             m_data.m_type = value_t::object;
+            m_data.m_value = value_t::object;
             assert_invariant();
         }
 
@@ -28963,8 +28958,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // transform a null object into an array
         if (is_null())
         {
-            m_data.m_value = value_t::array;
             m_data.m_type = value_t::array;
+            m_data.m_value = value_t::array;
             assert_invariant();
         }
 
@@ -28988,8 +28983,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // transform a null object into an object
         if (is_null())
         {
-            m_data.m_value = value_t::object;
             m_data.m_type = value_t::object;
+            m_data.m_value = value_t::object;
             assert_invariant();
         }
 
@@ -29170,8 +29165,8 @@ class basic_json // NOLINT(cppcoreguidelines-special-member-functions,hicpp-spec
         // implicitly convert a null value to an empty object
         if (is_null())
         {
-            m_data.m_value.object = create<object_t>();
             m_data.m_type = value_t::object;
+            m_data.m_value.object = create<object_t>();
             assert_invariant();
         }
 

tests/src/unit-allocator.cpp

@@ -388,120 +388,3 @@ TEST_CASE("bad my_allocator::construct")
         j["test"].push_back("should not leak");
     }
 }
-
-// the no-exceptions CI job skips every CHECK_THROWS_AS, which would leave
-// next_construct_fails set for the next allocation outside a check
-#if !defined(JSON_NOEXCEPTION)
-TEST_CASE("a failed allocation leaves the value unchanged")
-{
-    // create JSON type using the throwing allocator
-    using my_json = nlohmann::basic_json<std::map,
-          std::vector,
-          std::string,
-          bool,
-          std::int64_t,
-          std::uint64_t,
-          double,
-          my_allocator>;
-
-    // Each of these creates a string, array, object, or binary value. The
-    // value must be created before the type is changed: otherwise, a failed
-    // creation left a value of the new type without anything behind it (an
-    // assertion in its destructor, a null pointer everywhere else) or, when
-    // an old value was destroyed first, with a pointer to that destroyed one.
-
-    SECTION("creating a binary value")
-    {
-        const std::vector<std::uint8_t> bytes = {1, 2, 3};
-        my_json _;
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(_ = my_json::binary(bytes), std::bad_alloc&);
-        next_construct_fails = true;
-        CHECK_THROWS_AS(_ = my_json::binary(bytes, 42), std::bad_alloc&);
-        next_construct_fails = true;
-        CHECK_THROWS_AS(_ = my_json::binary(std::vector<std::uint8_t>(bytes)), std::bad_alloc&);
-        next_construct_fails = true;
-        CHECK_THROWS_AS(_ = my_json::binary(std::vector<std::uint8_t>(bytes), 42), std::bad_alloc&);
-        next_construct_fails = false;
-    }
-
-    SECTION("turning a null value into an array or object")
-    {
-        my_json j;
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(j[0], std::bad_alloc&);
-        CHECK(j.is_null());
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(j["key"], std::bad_alloc&);
-        CHECK(j.is_null());
-
-#ifdef JSON_HAS_CPP_17
-        next_construct_fails = true;
-        CHECK_THROWS_AS(j[std::string_view("key")], std::bad_alloc&);
-        CHECK(j.is_null());
-#endif
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(j.push_back(my_json(1)), std::bad_alloc&);
-        CHECK(j.is_null());
-
-        const my_json one = 1;
-        next_construct_fails = true;
-        CHECK_THROWS_AS(j.push_back(one), std::bad_alloc&);
-        CHECK(j.is_null());
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(j.push_back(my_json::object_t::value_type("key", 1)), std::bad_alloc&);
-        CHECK(j.is_null());
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(j.emplace_back(1), std::bad_alloc&);
-        CHECK(j.is_null());
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(j.emplace("key", 1), std::bad_alloc&);
-        CHECK(j.is_null());
-
-        const my_json object = {{"key", 1}};
-        next_construct_fails = true;
-        CHECK_THROWS_AS(j.update(object), std::bad_alloc&);
-        CHECK(j.is_null());
-
-        next_construct_fails = false;
-    }
-
-    SECTION("converting into an existing value")
-    {
-        // to_json replaces the value it is given; the old one must survive a
-        // failed creation of the new one
-        my_json j = "old";
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(nlohmann::to_json(j, std::string("new")), std::bad_alloc&);
-        CHECK(j == "old");
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(nlohmann::to_json(j, std::vector<int> {1, 2}), std::bad_alloc&);
-        CHECK(j == "old");
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(nlohmann::to_json(j, std::vector<bool> {true, false}), std::bad_alloc&);
-        CHECK(j == "old");
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(nlohmann::to_json(j, std::map<std::string, int> {{"a", 1}}), std::bad_alloc&);
-        CHECK(j == "old");
-
-        next_construct_fails = true;
-        CHECK_THROWS_AS(nlohmann::to_json(j, my_json::binary_t({1, 2})), std::bad_alloc&);
-        CHECK(j == "old");
-
-        next_construct_fails = false;
-        nlohmann::to_json(j, std::vector<int> {1, 2});
-        CHECK(j == my_json({1, 2}));
-    }
-}
-#endif

tests/src/unit-comparison.cpp

@@ -16,6 +16,9 @@
 #include "doctest_compatibility.h"
 
 #include <cstdint>
+#include <map>
+#include <string>
+#include <vector>
 
 #define JSON_TESTS_PRIVATE
 #include <nlohmann/json.hpp>
@@ -735,3 +738,132 @@ TEST_CASE("regression #3868 - heterogeneous comparisons compile under C++20 (P24
     }
 }
 #endif
+
+namespace
+{
+// orders keys ascending or descending, as chosen when a map is created
+template<class Key>
+class directed_less
+{
+  public:
+    directed_less() = default;
+
+    explicit directed_less(const bool descending) noexcept
+        : m_descending(descending)
+    {}
+
+    bool operator()(const Key& lhs, const Key& rhs) const
+    {
+        return m_descending ? rhs < lhs : lhs < rhs;
+    }
+
+  private:
+    bool m_descending = false;
+};
+
+// An object type that, like std::unordered_map, enumerates its entries in no
+// fixed order - ascending or descending by key, depending on how the map was
+// created - and whose operator== does not depend on that order.
+// std::unordered_map itself cannot be used here: the standard does not
+// require it to accept an incomplete mapped type such as basic_json, and
+// libstdc++ 6 to 9 as well as the EDG front ends of icpc and nvc++ reject
+// basic_json<std::unordered_map>. std::map, the default object type, works
+// with all supported compilers.
+template<class Key, class Value, class /*Compare*/, class Allocator>
+struct unordered_object_t : std::map<Key, Value, directed_less<Key>, Allocator>
+{
+    using base_type = std::map<Key, Value, directed_less<Key>, Allocator>;
+    using base_type::base_type;
+
+    friend bool operator==(const unordered_object_t& lhs, const unordered_object_t& rhs)
+    {
+        if (lhs.size() != rhs.size())
+        {
+            return false;
+        }
+        for (const auto& entry : lhs)
+        {
+            const auto it = rhs.find(entry.first);
+            if (it == rhs.end() || !(it->second == entry.second))
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    friend bool operator!=(const unordered_object_t& lhs, const unordered_object_t& rhs)
+    {
+        return !(lhs == rhs);
+    }
+};
+using unordered_json = nlohmann::basic_json<unordered_object_t>;
+
+// the entries "0" to "9", enumerated in ascending or in descending order
+unordered_json make_unordered_object(const bool descending)
+{
+    unordered_json j = unordered_json::object_t(directed_less<std::string>(descending));
+    for (int i = 0; i < 10; ++i)
+    {
+        j[std::to_string(i)] = i;
+    }
+    return j;
+}
+
+template<typename Json>
+Json nest(Json j, const std::size_t depth)
+{
+    for (std::size_t i = 0; i < depth; ++i)
+    {
+        Json outer = Json::object();
+        outer["x"] = std::move(j);
+        j = std::move(outer);
+    }
+    return j;
+}
+} // namespace
+
+TEST_CASE("equality of objects whose entries have no fixed order")
+{
+    // Values nested deeper than a bound are compared without the call stack,
+    // entry by entry. That must agree with the object type's own operator==,
+    // which for unordered_object_t (as for std::unordered_map) does not
+    // depend on the order of the entries, and for ordered_map does.
+    REQUIRE(make_unordered_object(true).begin().key() == "9");
+    REQUIRE(make_unordered_object(false).begin().key() == "0");
+
+    for (const std::size_t depth : std::vector<std::size_t> {0, 200})
+    {
+        CAPTURE(depth);
+
+        const unordered_json descending = nest(make_unordered_object(true), depth);
+        const unordered_json ascending = nest(make_unordered_object(false), depth);
+        CHECK(descending == ascending);
+        CHECK_FALSE(descending != ascending);
+
+        // a copy is equal to its original
+        const unordered_json copy = descending; // NOLINT(performance-unnecessary-copy-initialization)
+        CHECK(copy == descending);
+
+        // a different value, a different key, or another entry still count
+        unordered_json other_value = make_unordered_object(true);
+        other_value["5"] = 42;
+        CHECK_FALSE(nest(other_value, depth) == ascending);
+
+        unordered_json other_key = make_unordered_object(true);
+        other_key.erase("5");
+        other_key["50"] = 5;
+        CHECK_FALSE(nest(other_key, depth) == ascending);
+
+        unordered_json more_entries = make_unordered_object(true);
+        more_entries["10"] = 10;
+        CHECK_FALSE(nest(more_entries, depth) == ascending);
+        CHECK_FALSE(ascending == nest(more_entries, depth));
+
+        // ordered_json compares its entries in sequence
+        const nlohmann::ordered_json ab = nest(nlohmann::ordered_json({{"a", 1}, {"b", 2}}), depth);
+        const nlohmann::ordered_json ba = nest(nlohmann::ordered_json({{"b", 2}, {"a", 1}}), depth);
+        CHECK_FALSE(ab == ba);
+        CHECK(ab != ba);
+    }
+}