Merge pull request #185 from boostorg/fix/uses-allocator

Update changelog to reflect planned C++03 deprecation

.drone.jsonnet

@@ -6,7 +6,7 @@ local library = "unordered";
 
 local triggers =
 {
-    branch: [ "master", "develop", "feature/*", "bugfix/*" ]
+    branch: [ "master", "develop", "feature/*", "bugfix/*", "fix/*", "pr/*" ]
 };
 
 local ubsan = { UBSAN: '1', UBSAN_OPTIONS: 'print_stacktrace=1' };

.github/workflows/ci.yml

@@ -75,7 +75,7 @@ jobs:
           - { compiler: clang,     cxxstd: '03,11,14,17,2a',    os: macos-11, }
           - { compiler: clang,     cxxstd: '03,11,14,17,2a',    os: macos-12, sanitize: yes }
 
-    timeout-minutes: 120
+    timeout-minutes: 180
     runs-on: ${{matrix.os}}
     container: ${{matrix.container}}
     env: {B2_USE_CCACHE: 1}

benchmark/string.cpp

@@ -1,4 +1,5 @@
 // Copyright 2021 Peter Dimov.
+// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt
 
@@ -6,6 +7,7 @@
 #define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
@@ -272,6 +274,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_node_map =
+    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using boost_unordered_flat_map =
     boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
@@ -345,6 +350,9 @@ std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 template<class K, class V> using boost_unordered_map_fnv1a =
     boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_node_map_fnv1a =
+    boost::unordered_node_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using boost_unordered_flat_map_fnv1a =
     boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
@@ -373,6 +381,7 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_node_map>( "boost::unordered_node_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE
@@ -390,6 +399,7 @@ int main()
 
     test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
     test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
+    test<boost_unordered_node_map_fnv1a>( "boost::unordered_node_map, FNV-1a" );
     test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE

benchmark/string_view.cpp

@@ -1,4 +1,5 @@
 // Copyright 2021 Peter Dimov.
+// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt
 
@@ -6,6 +7,7 @@
 #define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
@@ -273,6 +275,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_node_map =
+    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using boost_unordered_flat_map =
     boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
@@ -346,6 +351,9 @@ std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 template<class K, class V> using boost_unordered_map_fnv1a =
     boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_node_map_fnv1a =
+    boost::unordered_node_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using boost_unordered_flat_map_fnv1a =
     boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
@@ -374,6 +382,7 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_node_map>( "boost::unordered_node_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE
@@ -391,6 +400,7 @@ int main()
 
     test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
     test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
+    test<boost_unordered_node_map_fnv1a>( "boost::unordered_node_map, FNV-1a" );
     test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE

benchmark/uint32.cpp

@@ -1,4 +1,5 @@
 // Copyright 2021 Peter Dimov.
+// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt
 
@@ -6,6 +7,7 @@
 #define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
@@ -289,6 +291,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_node_map =
+    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using boost_unordered_flat_map =
     boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
@@ -315,6 +320,7 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_node_map>( "boost::unordered_node_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE

benchmark/uint64.cpp

@@ -1,4 +1,5 @@
 // Copyright 2021 Peter Dimov.
+// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt
 
@@ -6,6 +7,7 @@
 #define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
@@ -289,6 +291,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_node_map =
+    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using boost_unordered_flat_map =
     boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
@@ -325,6 +330,7 @@ int main()
 #endif
 
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_node_map>( "boost::unordered_node_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE

benchmark/uuid.cpp

@@ -1,4 +1,5 @@
 // Copyright 2021, 2022 Peter Dimov.
+// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt
 
@@ -6,6 +7,7 @@
 #define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
@@ -340,6 +342,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_node_map =
+    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using boost_unordered_flat_map =
     boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
@@ -366,6 +371,7 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_node_map>( "boost::unordered_node_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE

benchmark/word_count.cpp

@@ -1,4 +1,5 @@
 // Copyright 2021, 2022 Peter Dimov.
+// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt
 
@@ -6,6 +7,7 @@
 #define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/regex.hpp>
 #ifdef HAVE_ABSEIL
@@ -227,6 +229,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_node_map =
+    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using boost_unordered_flat_map =
     boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
@@ -300,6 +305,9 @@ std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 template<class K, class V> using boost_unordered_map_fnv1a =
     boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_node_map_fnv1a =
+    boost::unordered_node_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using boost_unordered_flat_map_fnv1a =
     boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
@@ -328,6 +336,7 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_node_map>( "boost::unordered_node_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE
@@ -345,6 +354,7 @@ int main()
 
     test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
     test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
+    test<boost_unordered_node_map_fnv1a>( "boost::unordered_node_map, FNV-1a" );
     test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE

benchmark/word_size.cpp

@@ -1,4 +1,5 @@
 // Copyright 2021, 2022 Peter Dimov.
+// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt
 
@@ -6,6 +7,7 @@
 #define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/regex.hpp>
 #ifdef HAVE_ABSEIL
@@ -181,6 +183,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_node_map =
+    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using boost_unordered_flat_map =
     boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
@@ -207,6 +212,7 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_node_map>( "boost::unordered_node_map" );
     test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE

doc/unordered/benchmarks.adoc

@@ -278,13 +278,14 @@ max load factor 5
 
 |===
 
-== boost::unordered_flat_map
+== boost::unordered_(flat|node)_map
 
 All benchmarks were created using:
 
 * `https://abseil.io/docs/cpp/guides/container[absl::flat_hash_map^]<uint64_t, uint64_t>`
-* `boost::unordered_flat_map<uint64_t, uint64_t>`
 * `boost::unordered_map<uint64_t, uint64_t>`
+* `boost::unordered_flat_map<uint64_t, uint64_t>`
+* `boost::unordered_node_map<uint64_t, uint64_t>`
 
 The source code can be https://github.com/boostorg/boost_unordered_benchmarks/tree/boost_unordered_flat_map[found here^].
 

doc/unordered/buckets.adoc

@@ -134,7 +134,8 @@ h|*Method* h|*Description*
 |Changes the number of buckets so that there at least `n` buckets, and so that the load factor is less than the maximum load factor.
 
 2+^h| *Open-addressing containers only* +
-`boost::unordered_flat_set`, `boost::unordered_flat_map` 
+`boost::unordered_flat_set`, `boost::unordered_flat_map` +
+`boost::unordered_node_set`, `boost::unordered_node_map` +
 h|*Method* h|*Description*
 
 |`size_type max_load() const`
@@ -160,8 +161,9 @@ change the number of buckets when this happens. Iterators can be
 invalidated by calls to `insert`, `rehash` and `reserve`.
 
 As for pointers and references,
-they are never invalidated for closed-addressing containers (`boost::unordered_[multi]set`, `boost::unordered_[multi]map`),
-but they will when rehashing occurs for open-addressing
+they are never invalidated for node-based containers 
+(`boost::unordered_[multi]set`, `boost::unordered_[multi]map`, `boost::unordered_node_set`, `boost::unordered_node_map`),
+but they will when rehashing occurs for
 `boost::unordered_flat_set` and `boost::unordered_flat_map`: this is because
 these containers store elements directly into their holding buckets, so
 when allocating a new bucket array the elements must be transferred by means of move construction.
@@ -252,15 +254,16 @@ xref:#rationale_boostunordered_multiset_and_boostunordered_multimap[correspondin
 
 == Open Addressing Implementation
 
-The diagram shows the basic internal layout of `boost::unordered_flat_map` and
-`boost:unordered_flat_set`.
+The diagram shows the basic internal layout of `boost::unordered_flat_map`/`unordered_node_map` and
+`boost:unordered_flat_set`/`unordered_node_set`.
 
 
 [#img-foa-layout]
 .Open-addressing layout used by Boost.Unordered.
 image::foa.png[align=center]
 
-As with all open-addressing containers, elements are stored directly in the bucket array.
+As with all open-addressing containers, elements (or pointers to the element nodes in the case of
+`boost::unordered_node_map` and `boost::unordered_node_set`) are stored directly in the bucket array.
 This array is logically divided into 2^_n_^ _groups_ of 15 elements each.
 In addition to the bucket array, there is an associated _metadata array_ with 2^_n_^
 16-byte words.

doc/unordered/changes.adoc

@@ -6,10 +6,19 @@
 :github-pr-url: https://github.com/boostorg/unordered/pull
 :cpp: C++
 
-== Release 1.82.0
+== Release 1.82.0 - Major update
 
+* {cpp}03 support is planned for deprecation. Boost 1.84.0 will no longer support
+  {cpp}03 mode and {cpp}11 will become the new minimum for using the library.
+* Added node-based, open-addressing containers
+  `boost::unordered_node_map` and `boost::unordered_node_set`.
 * Extended heterogeneous lookup to more member functions as specified in
-  https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2363r3.html[P2363].
+  https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2363r5.html[P2363].
+* Replaced the previous post-mixing process for open-addressing containers with 
+  a new algorithm based on extended multiplication by a constant.
+* Fixed bug in internal emplace() impl where stack-local types were not properly
+  constructed using the Allocator of the container which breaks uses-allocator
+  construction.
 
 == Release 1.81.0 - Major update
 

doc/unordered/comparison.adoc

@@ -33,8 +33,8 @@
 
 |Iterators, pointers and references to the container's elements are never invalidated.
 |<<buckets_iterator_invalidation,Iterators can be invalidated by calls to insert or rehash>>. +
-**Closed-addressing containers:** Pointers and references to the container's elements are never invalidated. +
-**Open-addressing containers:** Pointers and references to the container's elements are invalidated when rehashing occurs.
+**Node-based containers:** Pointers and references to the container's elements are never invalidated. +
+**Flat containers:** Pointers and references to the container's elements are invalidated when rehashing occurs.
 
 |Iterators iterate through the container in the order defined by the comparison object.
 |Iterators iterate through the container in an arbitrary order, that can change as elements are inserted, although equivalent elements are always adjacent.

doc/unordered/compliance.adoc

@@ -5,9 +5,9 @@
 
 :cpp: C++
 
-== Closed-addressing containers: unordered_[multi]set, unordered_[multi]map
+== Closed-addressing containers
 
-The intent of Boost.Unordered is to provide a conformant
+`unordered_[multi]set` and `unordered_[multi]map` are intended to provide a conformant
 implementation of the {cpp}20 standard that will work with {cpp}98 upwards.
 This wide compatibility does mean some compromises have to be made.
 With a compiler and library that fully support {cpp}11, the differences should
@@ -117,27 +117,31 @@ Variadic constructor arguments for `emplace` are only used when both
 rvalue references and variadic template parameters are available.
 Otherwise `emplace` can only take up to 10 constructors arguments.
 
-== Open-addressing containers: unordered_flat_set, unordered_flat_map
+== Open-addressing containers
 
 The C++ standard does not currently provide any open-addressing container
-specification to adhere to, so `boost::unordered_flat_set` and
-`boost::unordered_flat_map` take inspiration from `std::unordered_set` and
+specification to adhere to, so `boost::unordered_flat_set`/`unordered_node_set` and
+`boost::unordered_flat_map`/`unordered_node_map` take inspiration from `std::unordered_set` and
 `std::unordered_map`, respectively, and depart from their interface where
 convenient or as dictated by their internal data structure, which is
-radically different from that imposed by the standard (closed addressing, node based).
+radically different from that imposed by the standard (closed addressing).
 
-`unordered_flat_set` and `unordered_flat_map` only work with reasonably
+Open-addressing containers provided by Boost.Unordered only work with reasonably
 compliant C++11 (or later) compilers. Language-level features such as move semantics
 and variadic template parameters are then not emulated. 
-`unordered_flat_set` and `unordered_flat_map` are fully https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^].
+The containers are fully https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^].
 
 The main differences with C++ unordered associative containers are:
 
-* `value_type` must be move-constructible.
-* Pointer stability is not kept under rehashing.
-* `begin()` is not constant-time.
-* `erase(iterator)` returns `void` instead of an iterator to the following element.
-* There is no API for bucket handling (except `bucket_count`) or node extraction/insertion.
-* The maximum load factor of the container is managed internally and can't be set by the user. The maximum load,
-exposed through the public function `max_load`, may decrease on erasure under high-load conditions.
+* In general:
+  ** `begin()` is not constant-time.
+  ** `erase(iterator)` returns `void` instead of an iterator to the following element.
+  ** There is no API for bucket handling (except `bucket_count`).
+  ** The maximum load factor of the container is managed internally and can't be set by the user. The maximum load,
+     exposed through the public function `max_load`, may decrease on erasure under high-load conditions.
+* Flat containers (`boost::unordered_flat_set` and `boost::unordered_flat_map`):
+  ** `value_type` must be move-constructible.
+  ** Pointer stability is not kept under rehashing.
+  ** There is no API for node extraction/insertion.
 
+//-

doc/unordered/copyright.adoc

@@ -9,10 +9,10 @@ Copyright (C) 2003, 2004 Jeremy B. Maitin-Shepard
 
 Copyright (C) 2005-2008 Daniel James
 
-Copyright (C) 2022 Christian Mazakas
+Copyright (C) 2022-2023 Christian Mazakas
 
-Copyright (C) 2022 Joaquín M López Muñoz
+Copyright (C) 2022-2023 Joaquín M López Muñoz
 
-Copyright (C) 2022 Peter Dimov
+Copyright (C) 2022-2023 Peter Dimov
 
 Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

doc/unordered/intro.adoc

@@ -106,8 +106,69 @@ namespace boost {
 }
 ----
 
-`boost::unordered_flat_set` and `boost::unordered_flat_map` require a
-reasonably compliant C++11 compiler.
+Starting in Boost 1.82, the containers `boost::unordered_node_set` and `boost::unordered_node_map`
+are introduced: they use open addressing like `boost::unordered_flat_set` and `boost::unordered_flat_map`,
+but internally store element _nodes_, like `boost::unordered_set` and `boost::unordered_map`,
+which provide stability of pointers and references to the elements:
+
+[source,c++]
+----
+// #include <boost/unordered/unordered_node_set.hpp>
+//
+// Note: no multiset version
+
+namespace boost {
+    template <
+        class Key,
+        class Hash = boost::hash<Key>,
+        class Pred = std::equal_to<Key>,
+        class Alloc = std::allocator<Key> >
+    class unordered_node_set;
+}
+----
+
+[source,c++]
+----
+// #include <boost/unordered/unordered_node_map.hpp>
+//
+// Note: no multimap version
+
+namespace boost {
+    template <
+        class Key, class Mapped,
+        class Hash = boost::hash<Key>,
+        class Pred = std::equal_to<Key>,
+        class Alloc = std::allocator<std::pair<Key const, Mapped> > >
+    class unordered_node_map;
+}
+----
+
+These are all the containers provided by Boost.Unordered:
+
+[caption=, title='Table {counter:table-counter}. Boost.Unordered containers']
+[cols="1,1,.^1", frame=all, grid=rows]
+|===
+^h|
+^h|*Node-based*
+^h|*Flat*
+
+^.^h|*Closed addressing*
+^| `boost::unordered_set` +
+`boost::unordered_map` +
+`boost::unordered_multiset` +
+`boost::unordered_multimap`
+^| 
+
+^.^h|*Open addressing*
+^| `boost::unordered_node_set` +
+`boost::unordered_node_map`
+^| `boost::unordered_flat_set` +
+`boost::unordered_flat_map`
+
+|===
+
+Closed-addressing containers are pass:[C++]98-compatible. Open-addressing containers require a
+reasonably compliant pass:[C++]11 compiler.
 
 Boost.Unordered containers are used in a similar manner to the normal associative
 containers:

doc/unordered/rationale.adoc

@@ -4,9 +4,10 @@
 
 = Implementation Rationale
 
-== boost::unordered_[multi]set and boost::unordered_[multi]map
+== Closed-addressing containers 
 
-These containers adhere to the standard requirements for unordered associative
+`boost::unordered_[multi]set` and `boost::unordered_[multi]map`
+adhere to the standard requirements for unordered associative
 containers, so the interface was fixed. But there are
 still some implementation decisions to make. The priorities are
 conformance to the standard and portability.
@@ -64,8 +65,8 @@ of bits in the hash value, so it was only used when `size_t` was 64 bit.
 
 Since release 1.79.0, https://en.wikipedia.org/wiki/Hash_function#Fibonacci_hashing[Fibonacci hashing]
 is used instead. With this implementation, the bucket number is determined
-by using `(h * m) >> (w - k)`, where `h` is the hash value, `m` is the golden
-ratio multiplied by `2^w`, `w` is the word size (32 or 64), and `2^k` is the
+by using `(h * m) >> (w - k)`, where `h` is the hash value, `m` is `2^w` divided
+by the golden ratio, `w` is the word size (32 or 64), and `2^k` is the
 number of buckets. This provides a good compromise between speed and
 distribution.
 
@@ -73,7 +74,7 @@ Since release 1.80.0, prime numbers are chosen for the number of buckets in
 tandem with sophisticated modulo arithmetic. This removes the need for "mixing"
 the result of the user's hash function as was used for release 1.79.0.
 
-== boost::unordered_flat_set and boost::unordered_flat_map
+== Open-addresing containers 
 
 The C++ standard specification of unordered associative containers impose
 severe limitations on permissible implementations, the most important being
@@ -81,29 +82,32 @@ that closed addressing is implicitly assumed. Slightly relaxing this specificati
 opens up the possibility of providing container variations taking full
 advantage of open-addressing techniques.
 
-The design of `boost::unordered_flat_set` and `boost::unordered_flat_map` has been
+The design of `boost::unordered_flat_set`/`unordered_node_set` and `boost::unordered_flat_map`/`unordered_node_map` has been
 guided by Peter Dimov's https://pdimov.github.io/articles/unordered_dev_plan.html[Development Plan for Boost.Unordered^].
 We discuss here the most relevant principles.
 
 === Hash function
 
 Given its rich functionality and cross-platform interoperability,
-`boost::hash` remains the default hash function of `boost::unordered_flat_set` and `boost::unordered_flat_map`.
+`boost::hash` remains the default hash function of open-addressing containers.
 As it happens, `boost::hash` for integral and other basic types does not possess
 the statistical properties required by open addressing; to cope with this,
 we implement a post-mixing stage:
 
-*  64-bit architectures: we use the `xmx` function defined in
-Jon Maiga's http://jonkagstrom.com/bit-mixer-construction/index.html[The construct of a bit mixer^].
-*  32-bit architectures: the mixer used was selected from a set generated with https://github.com/skeeto/hash-prospector[Hash Function Prospector^]
-as the best overall performer in our internal benchmarks. Score assigned by Hash Prospector is 333.7934929677524.
+{nbsp}{nbsp}{nbsp}{nbsp} _a_ <- _h_ *mulx* _C_, +
+{nbsp}{nbsp}{nbsp}{nbsp} _h_ <- *high*(_a_) *xor* *low*(_a_),
+
+where *mulx* is an _extended multiplication_ (128 bits in 64-bit architectures, 64 bits in 32-bit environments),
+and *high* and *low* are the upper and lower halves of an extended word, respectively.
+In 64-bit architectures, _C_ is the integer part of 2^64^&#8725;https://en.wikipedia.org/wiki/Golden_ratio[_&phi;_],
+whereas in 32 bits _C_ = 0xE817FB2Du has been obtained from https://arxiv.org/abs/2001.05304[Steele and Vigna (2021)^].
 
 When using a hash function directly suitable for open addressing, post-mixing can be opted out by via a dedicated <<hash_traits_hash_is_avalanching,`hash_is_avalanching`>>trait.
 `boost::hash` specializations for string types are marked as avalanching.
 
 === Platform interoperability
 
-The observable behavior of `boost::unordered_flat_set` and `boost::unordered_flat_map` is deterministically
+The observable behavior of `boost::unordered_flat_set`/`unordered_node_set` and `boost::unordered_flat_map`/`unordered_node_map` is deterministically
 identical across different compilers as long as their ``std::size_type``s are the same size and the user-provided
 hash function and equality predicate are also interoperable
 &#8212;this includes elements being ordered in exactly the same way for the same sequence of

doc/unordered/ref.adoc

@@ -8,3 +8,5 @@ include::unordered_multiset.adoc[]
 include::hash_traits.adoc[]
 include::unordered_flat_map.adoc[]
 include::unordered_flat_set.adoc[]
+include::unordered_node_map.adoc[]
+include::unordered_node_set.adoc[]

include/boost/unordered/detail/foa.hpp

@@ -1,6 +1,7 @@
 /* Fast open-addressing hash table.
  *
  * Copyright 2022-2023 Joaquin M Lopez Munoz.
+ * Copyright 2023 Christian Mazakas.
  * Distributed under the Boost Software License, Version 1.0.
  * (See accompanying file LICENSE_1_0.txt or copy at
  * http://www.boost.org/LICENSE_1_0.txt)
@@ -11,8 +12,6 @@
 #ifndef BOOST_UNORDERED_DETAIL_FOA_HPP
 #define BOOST_UNORDERED_DETAIL_FOA_HPP
 
-#include <iostream>
-
 #include <boost/assert.hpp>
 #include <boost/config.hpp>
 #include <boost/config/workaround.hpp>
@@ -40,12 +39,24 @@
 #include <type_traits>
 #include <utility>
 
-#if defined(__SSE2__)||\
+#if !defined(BOOST_UNORDERED_DISABLE_SSE2)
+#if defined(BOOST_UNORDERED_ENABLE_SSE2)|| \
+    defined(__SSE2__)|| \
     defined(_M_X64)||(defined(_M_IX86_FP)&&_M_IX86_FP>=2)
 #define BOOST_UNORDERED_SSE2
-#include <emmintrin.h>
-#elif defined(__ARM_NEON)&&!defined(__ARM_BIG_ENDIAN)
+#endif
+#endif
+
+#if !defined(BOOST_UNORDERED_DISABLE_NEON)
+#if defined(BOOST_UNORDERED_ENABLE_NEON)||\
+    (defined(__ARM_NEON)&&!defined(__ARM_BIG_ENDIAN))
 #define BOOST_UNORDERED_LITTLE_ENDIAN_NEON
+#endif
+#endif
+
+#if defined(BOOST_UNORDERED_SSE2)
+#include <emmintrin.h>
+#elif defined(BOOST_UNORDERED_LITTLE_ENDIAN_NEON)
 #include <arm_neon.h>
 #endif
 
@@ -927,7 +938,6 @@ struct table_arrays
   template<typename Allocator>
   static table_arrays new_(Allocator& al,std::size_t n)
   {
-    // using alloc_traits=boost::allocator_traits<Allocator>;
     using storage_allocator=
       typename boost::allocator_rebind<Allocator, Value>::type;
     using storage_traits=boost::allocator_traits<storage_allocator>;
@@ -967,13 +977,13 @@ struct table_arrays
   static void delete_(Allocator& al,table_arrays& arrays)noexcept
   {
     using storage_alloc=typename boost::allocator_rebind<Allocator,Value>::type;
-    using alloc_traits=boost::allocator_traits<storage_alloc>;
-    using pointer=typename alloc_traits::pointer;
+    using storage_traits=boost::allocator_traits<storage_alloc>;
+    using pointer=typename storage_traits::pointer;
     using pointer_traits=boost::pointer_traits<pointer>;
 
     auto sal=storage_alloc(al);
     if(arrays.elements){
-      alloc_traits::deallocate(
+      storage_traits::deallocate(
         sal,pointer_traits::pointer_to(*arrays.elements),
         buffer_size(arrays.groups_size_mask+1));
     }
@@ -1113,51 +1123,85 @@ _STL_RESTORE_DEPRECATED_WARNING
 #pragma warning(disable:4702)
 #endif
 
+/* We expose the hard-coded max load factor so that tests can use it without
+ * needing to pull it from an instantiated class template such as the table
+ * class
+ */
+constexpr static float const mlf = 0.875f;
+
+template <class T>
+union uninitialized_storage
+{
+  T t_;
+  uninitialized_storage(){}
+  ~uninitialized_storage(){}
+};
+
 /* foa::table interface departs in a number of ways from that of C++ unordered
  * associative containers because it's not for end-user consumption
- * (boost::unordered_flat_[map|set] wrappers complete it as appropriate) and,
- * more importantly, because of fundamental restrictions imposed by open
- * addressing:
- * 
- *   - value_type must be moveable.
- *   - Pointer stability is not kept under rehashing.
+ * (boost::unordered_[flat|node]_[map|set]) wrappers complete it as
+ * appropriate).
+ *
+ * The table supports two main modes of operation: node-based and flat. In the
+ * node-based case, buckets store pointers to individually heap-allocated
+ * elements. For flat, buckets directly store elements.
+ *
+ * For both tables:
+ *
  *   - begin() is not O(1).
  *   - No bucket API.
  *   - Load factor is fixed and can't be set by the user.
- *   - No extract API.
  * 
+ * For the inline table:
+ *
+ *   - value_type must be moveable.
+ *   - Pointer stability is not kept under rehashing.
+ *   - No extract API.
+ *
  * The TypePolicy template parameter is used to generate instantiations
  * suitable for either maps or sets, and introduces non-standard init_type:
- * 
+ *
  *   - TypePolicy::key_type and TypePolicy::value_type have the obvious
  *     meaning.
+ *
  *   - TypePolicy::init_type is the type implicitly converted to when
  *     writing x.insert({...}). For maps, this is std::pair<Key,T> rather
  *     than std::pair<const Key,T> so that, for instance, x.insert({"hello",0})
  *     produces a cheaply moveable std::string&& ("hello") rather than
  *     a copyable const std::string&&. foa::table::insert is extended to accept
  *     both init_type and value_type references.
- *   - TypePolicy::move(value_type&) returns a temporary object for value
- *     transfer on rehashing, move copy/assignment, and merge. For maps, this
- *     object is a std::pair<Key&&,T&&>, which is generally cheaper to move
- *     than std::pair<const Key,T>&& because of the constness in Key.
+ *
+ *   - TypePolicy::construct and TypePolicy::destroy are used for the
+ *     construction and destruction of the internal types: value_type, init_type
+ *     and element_type.
+ * 
+ *   - TypePolicy::move is used to provide move semantics for the internal
+ *     types used by the container during rehashing and emplace. These types
+ *     are init_type, value_type and emplace_type. During insertion, a
+ *     stack-local type will be created based on the constructibility of the
+ *     value_type and the supplied arguments. TypePolicy::move is used here
+ *     for transfer of ownership. Similarly, TypePolicy::move is also used
+ *     during rehashing when elements are moved to the new table.
+ *
  *   - TypePolicy::extract returns a const reference to the key part of
- *     a value of type value_type, init_type or
+ *     a value of type value_type, init_type, element_type or
  *     decltype(TypePolicy::move(...)).
- * 
- *  try_emplace, erase and find support heterogenous lookup by default, that is,
- *  without checking for any ::is_transparent typedefs --the checking is done by
- *  boost::unordered_flat_[map|set].
- * 
- *  At the moment, we're not supporting allocators with fancy pointers.
- *  Allocator::pointer must be convertible to/from regular pointers.
+ *
+ *   - TypePolicy::element_type is the type that table_arrays uses when
+ *     allocating buckets. For flat containers, this is value_type. For node
+ *     containers, this is a strong typedef to value_type*.
+ *
+ *   - TypePolicy::value_from returns a mutable reference to value_type from
+ *     a given element_type. This is used when elements of the table themselves
+ *     need to be moved, such as during move construction/assignment when
+ *     allocators are unequal and there is no propagation. For all other cases,
+ *     the element_type itself is moved.
+ *
+ * try_emplace, erase and find support heterogenous lookup by default, that is,
+ * without checking for any ::is_transparent typedefs --the checking is done by
+ * boost::unordered_[flat|node]_[map|set].
  */
 
-/* We pull this out so the tests don't have to rely on a magic constant or
- * instantiate the table class template as it can be quite gory.
- */
-constexpr static float const mlf = 0.875f;
-
 template<typename TypePolicy,typename Hash,typename Pred,typename Allocator>
 class 
 
@@ -1388,18 +1432,25 @@ public:
   template<typename... Args>
   BOOST_FORCEINLINE std::pair<iterator,bool> emplace(Args&&... args)
   {
-    /* We dispatch based on whether or not the value_type is constructible from
-     * an rvalue refernce to the deduced emplace_type. We do this specifically
-     * for the csae of the node-based containers. To this end, we're able to
-     * avoid allocating a node when a duplicate element is attempted to be
-     * inserted. For immovable types, we instead dispatch to the routine that
-     * unconditionally allocates via `type_policy::construct()`.
-     */
-    return emplace_dispatch(
+    using emplace_type=typename std::conditional<
+      std::is_constructible<init_type,Args...>::value,
+      init_type,
+      value_type
+    >::type;
+
+    using insert_type=typename std::conditional<
       std::is_constructible<
-        value_type,
-        emplace_type<Args...>&&>{},
-      std::forward<Args>(args)...);
+        value_type,emplace_type>::value,
+      emplace_type,element_type
+    >::type;
+
+    uninitialized_storage<insert_type> s;
+    auto                              *p=std::addressof(s.t_);
+
+    type_policy::construct(al(),p,std::forward<Args>(args)...);
+
+    destroy_on_exit<insert_type> guard{al(),p};
+    return emplace_impl(type_policy::move(*p));
   }
 
   template<typename Key,typename... Args>
@@ -1511,7 +1562,7 @@ public:
   element_type extract(const_iterator pos)
   {
     BOOST_ASSERT(pos!=end());
-    erase_on_exit e{*this,iterator{const_iterator_cast_tag{},pos}};
+    erase_on_exit e{*this,pos};
     (void)e;
     return std::move(*pos.p);
   }
@@ -1584,15 +1635,6 @@ private:
   template<typename,typename,typename,typename> friend class table;
   using arrays_type=table_arrays<element_type,group_type,size_policy>;
 
-  template<typename... Args>
-  using emplace_type = typename std::conditional<
-      std::is_constructible<
-        init_type,Args...
-      >::value,
-      init_type,
-      value_type
-    >::type;
-
   struct clear_on_exit
   {
     ~clear_on_exit(){x.clear();}
@@ -1601,14 +1643,22 @@ private:
 
   struct erase_on_exit
   {
-    erase_on_exit(table& x_,iterator it_):x{x_},it{it_}{}
+    erase_on_exit(table& x_,const_iterator it_):x{x_},it{it_}{}
     ~erase_on_exit(){if(!rollback_)x.erase(it);}
 
     void rollback(){rollback_=true;}
 
-    table&   x;
-    iterator it;
-    bool     rollback_=false;
+    table&         x;
+    const_iterator it;
+    bool           rollback_=false;
+  };
+
+  template <class T>
+  struct destroy_on_exit
+  {
+    Allocator &a;
+    T         *p;
+    ~destroy_on_exit(){type_policy::destroy(a,p);};
   };
 
   Hash&            h(){return hash_base::get();}
@@ -1874,29 +1924,6 @@ private:
 #pragma warning(pop) /* C4800 */
 #endif
 
-  template<typename... Args>
-  BOOST_FORCEINLINE std::pair<iterator,bool> emplace_dispatch(
-    std::true_type,Args&&... args
-  ) {
-    using emplace_type_t = emplace_type<Args...>;
-    return emplace_impl(emplace_type_t(std::forward<Args>(args)...));
-  }
-
-  template<typename... Args>
-  BOOST_FORCEINLINE std::pair<iterator,bool> emplace_dispatch(
-    std::false_type,Args&&... args
-  ) {
-    alignas(element_type)
-    unsigned char buf[sizeof(element_type)];
-    element_type* p = reinterpret_cast<element_type*>(buf);
-
-    type_policy::construct(al(),p,std::forward<Args>(args)...);
-    destroy_element_on_exit d{this,p};
-    (void)d;
-
-    return emplace_impl(type_policy::move(*p));
-  }
-
   template<typename... Args>
   BOOST_FORCEINLINE std::pair<iterator,bool> emplace_impl(Args&&... args)
   {
@@ -2180,13 +2207,7 @@ private:
 } /* namespace unordered */
 } /* namespace boost */
 
+#undef BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED
 #undef BOOST_UNORDERED_ASSUME
 #undef BOOST_UNORDERED_HAS_BUILTIN
-#undef BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED
-#ifdef BOOST_UNORDERED_LITTLE_ENDIAN_NEON
-#undef BOOST_UNORDERED_LITTLE_ENDIAN_NEON
-#endif
-#ifdef BOOST_UNORDERED_SSE2
-#undef BOOST_UNORDERED_SSE2
-#endif
 #endif

include/boost/unordered/detail/foa/element_type.hpp

@@ -0,0 +1,60 @@
+/* Copyright 2023 Christian Mazakas.
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or copy at
+ * http://www.boost.org/LICENSE_1_0.txt)
+ *
+ * See https://www.boost.org/libs/unordered for library home page.
+ */
+
+#ifndef BOOST_UNORDERED_DETAIL_FOA_ELEMENT_TYPE_HPP
+#define BOOST_UNORDERED_DETAIL_FOA_ELEMENT_TYPE_HPP
+
+namespace boost{
+namespace unordered{
+namespace detail{
+namespace foa{
+
+template<class T>
+struct element_type
+{
+  using value_type=T;
+  value_type* p;
+
+  /*
+   * we use a deleted copy constructor here so the type is no longer
+   * trivially copy-constructible which inhibits our memcpy
+   * optimizations when copying the tables
+   */
+  element_type() = default;
+  element_type(value_type* p_):p(p_){}
+  element_type(element_type const&) = delete;
+  element_type(element_type&& rhs) noexcept
+  {
+    p = rhs.p;
+    rhs.p = nullptr;
+  }
+
+  element_type& operator=(element_type const&)=delete;
+  element_type& operator=(element_type&& rhs)noexcept
+  {
+    if (this!=&rhs){
+      p=rhs.p;
+      rhs.p=nullptr;
+    }
+    return *this;
+  }
+
+  void swap(element_type& rhs)noexcept
+  {
+    auto tmp=p;
+    p=rhs.p;
+    rhs.p=tmp;
+  }
+};
+
+}
+}
+}
+}
+
+#endif // BOOST_UNORDERED_DETAIL_FOA_ELEMENT_TYPE_HPP

include/boost/unordered/detail/foa/node_handle.hpp

@@ -45,20 +45,30 @@ struct node_handle_base
 
   private:
     using node_value_type=typename type_policy::value_type;
-    node_value_type* p_=nullptr;
+    element_type p_;
     BOOST_ATTRIBUTE_NO_UNIQUE_ADDRESS opt_storage<Allocator> a_;
 
   protected:
-    node_value_type& element()noexcept
+    node_value_type& data()noexcept
     {
-      BOOST_ASSERT(!empty());
-      return *p_;
+      return *(p_.p);
     }
 
-    node_value_type const& element()const noexcept
+    node_value_type const& data()const noexcept
+    {
+      return *(p_.p);
+    }
+
+    element_type& element()noexcept
     {
       BOOST_ASSERT(!empty());
-      return *p_;
+      return p_;
+    }
+
+    element_type const& element()const noexcept
+    {
+      BOOST_ASSERT(!empty());
+      return p_;
     }
 
     Allocator& al()noexcept
@@ -73,110 +83,114 @@ struct node_handle_base
       return a_.t_;
     }
 
-    void emplace(node_value_type* p,Allocator a)
-    {
-      BOOST_ASSERT(empty());
-      p_=p;
-      new(&a_.t_)Allocator(a);
-    }
-
     void emplace(element_type&& x,Allocator a)
     {
-      emplace(x.p,a);
+      BOOST_ASSERT(empty());
+      auto* p=x.p;
+      p_.p=p;
+      new(&a_.t_)Allocator(a);
       x.p=nullptr;
     }
 
-    void clear()
+    void reset()
     {
-      al().~Allocator();
-      p_=nullptr;
+      a_.t_.~Allocator();
+      p_.p=nullptr;
     }
 
   public:
-    constexpr node_handle_base()noexcept{}
+    constexpr node_handle_base()noexcept:p_{nullptr}{}
 
     node_handle_base(node_handle_base&& nh) noexcept
     {
+      p_.p = nullptr;
       if (!nh.empty()){
-        emplace(nh.p_,nh.al());
-        nh.clear();
+        emplace(std::move(nh.p_),nh.al());
+        nh.reset();
       }
     }
 
     node_handle_base& operator=(node_handle_base&& nh)noexcept
     {
-      bool const pocma=
-        boost::allocator_propagate_on_container_move_assignment<
-          Allocator>::type::value;
+      if(this!=&nh){
+        if(empty()){
+          if(nh.empty()){                      /* empty(),  nh.empty() */
+            /* nothing to do */
+          }else{                               /* empty(), !nh.empty() */
+            emplace(std::move(nh.p_),std::move(nh.al()));
+            nh.reset();
+          }
+        }else{
+          if(nh.empty()){                      /* !empty(),  nh.empty() */
+            type_policy::destroy(al(),&p_);
+            reset();
+          }else{                               /* !empty(), !nh.empty() */
+            bool const pocma=
+              boost::allocator_propagate_on_container_move_assignment<
+                Allocator>::type::value;
 
-      BOOST_ASSERT(
-        pocma
-        ||empty()
-        ||nh.empty()
-        ||(al()==nh.al()));
+            BOOST_ASSERT(pocma||al()==nh.al());
 
-      if(!empty()){
-        type_policy::destroy(al(),p_);
-        if (pocma&&!nh.empty()){al()=std::move(nh.al());}
+            type_policy::destroy(al(),&p_);
+            if(pocma){
+              al()=std::move(nh.al());
+            }
+
+            p_=std::move(nh.p_);
+            nh.reset();
+          }
+        }
+      }else{
+        if(empty()){                           /* empty(),  nh.empty() */
+          /* nothing to do */
+        }else{                                 /* !empty(), !nh.empty() */
+          type_policy::destroy(al(),&p_);
+          reset();
+        }
       }
-
-      if(!nh.empty()){
-        if(empty()){new(&a_.t_)Allocator(std::move(nh.al()));}
-        p_=nh.p_;
-
-        nh.p_=nullptr;
-        nh.a_.t_.~Allocator();
-      }else if (!empty()){
-        a_.t_.~Allocator();
-        p_=nullptr;
-      }
-
       return *this;
     }
 
     ~node_handle_base()
     {
       if(!empty()){
-        type_policy::destroy(al(),p_);
-        a_.t_.~Allocator();
+        type_policy::destroy(al(),&p_);
+        reset();
       }
     }
 
     allocator_type get_allocator()const noexcept{return al();}
     explicit operator bool()const noexcept{ return !empty();}
-    BOOST_ATTRIBUTE_NODISCARD bool empty()const noexcept{return p_==nullptr;}
+    BOOST_ATTRIBUTE_NODISCARD bool empty()const noexcept{return p_.p==nullptr;}
 
     void swap(node_handle_base& nh) noexcept(
       boost::allocator_is_always_equal<Allocator>::type::value||
       boost::allocator_propagate_on_container_swap<Allocator>::type::value)
     {
-      using std::swap;
+      if(this!=&nh){
+        if(empty()){
+          if(nh.empty()) {
+            /* nothing to do here */
+          } else {
+            emplace(std::move(nh.p_), nh.al());
+            nh.reset();
+          }
+        }else{
+          if(nh.empty()){
+            nh.emplace(std::move(p_),al());
+            reset();
+          }else{
+            bool const pocs=
+              boost::allocator_propagate_on_container_swap<
+                Allocator>::type::value;
 
-      bool const pocs=
-        boost::allocator_propagate_on_container_swap<Allocator>::type::value;
+            BOOST_ASSERT(pocs || al()==nh.al());
 
-      if (!empty()&&!nh.empty()){
-        BOOST_ASSERT(pocs || al()==nh.al());
-
-        node_value_type *p=p_;
-        p_=nh.p_;
-        nh.p_=p;
-
-        if(pocs){
-          swap(al(),nh.al());
+            using std::swap;
+            p_.swap(nh.p_);
+            if(pocs)swap(al(),nh.al());
+          }
         }
-
-        return;
-      }
-
-      if (empty()&&nh.empty()){return;}
-
-      if (empty()){
-        emplace(nh.p_,nh.al());
-        nh.clear();
-      }else{
-        nh.emplace(p_,al());
-        clear();
       }
     }
 

include/boost/unordered/detail/requires_cxx11.hpp

@@ -0,0 +1,21 @@
+#ifndef BOOST_UNORDERED_DETAIL_REQUIRES_CXX11_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_REQUIRES_CXX11_HPP_INCLUDED
+
+// Copyright 2023 Peter Dimov
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#include <boost/config.hpp>
+#include <boost/config/pragma_message.hpp>
+
+#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || \
+    defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || \
+    defined(BOOST_NO_CXX11_DECLTYPE) || \
+    defined(BOOST_NO_CXX11_CONSTEXPR) || \
+    defined(BOOST_NO_CXX11_NOEXCEPT)
+
+BOOST_PRAGMA_MESSAGE("C++03 support is deprecated in Boost.Unordered 1.82 and will be removed in Boost.Unordered 1.84.")
+
+#endif
+
+#endif // #ifndef BOOST_UNORDERED_DETAIL_REQUIRES_CXX11_HPP_INCLUDED

include/boost/unordered/unordered_flat_map.hpp

@@ -53,6 +53,11 @@ namespace boost {
           return kv.first;
         }
 
+        static moved_type move(init_type& x)
+        {
+          return {std::move(x.first), std::move(x.second)};
+        }
+
         static moved_type move(element_type& x)
         {
           // TODO: we probably need to launder here
@@ -60,19 +65,24 @@ namespace boost {
             std::move(const_cast<raw_mapped_type&>(x.second))};
         }
 
-        template <class A>
-        static void construct(A& al, element_type* p, moved_type&& x)
-        {
-          boost::allocator_construct(al, p, std::move(x));
-        }
-
         template <class A, class... Args>
-        static void construct(A& al, element_type* p, Args&&... args)
+        static void construct(A& al, init_type* p, Args&&... args)
         {
           boost::allocator_construct(al, p, std::forward<Args>(args)...);
         }
 
-        template <class A> static void destroy(A& al, element_type* p) noexcept
+        template <class A, class... Args>
+        static void construct(A& al, value_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
+        template <class A> static void destroy(A& al, init_type* p) noexcept
+        {
+          boost::allocator_destroy(al, p);
+        }
+
+        template <class A> static void destroy(A& al, value_type* p) noexcept
         {
           boost::allocator_destroy(al, p);
         }

include/boost/unordered/unordered_flat_set.hpp

@@ -45,25 +45,13 @@ namespace boost {
 
         static element_type&& move(element_type& x) { return std::move(x); }
 
-        template <class A>
-        static void construct(A& al, element_type* p, element_type const& copy)
-        {
-          boost::allocator_construct(al, p, copy);
-        }
-
-        template <class A>
-        static void construct(A& al, element_type* p, Key&& x)
-        {
-          boost::allocator_construct(al, p, std::move(x));
-        }
-
         template <class A, class... Args>
-        static void construct(A& al, element_type* p, Args&&... args)
+        static void construct(A& al, value_type* p, Args&&... args)
         {
           boost::allocator_construct(al, p, std::forward<Args>(args)...);
         }
 
-        template <class A> static void destroy(A& al, element_type* p) noexcept
+        template <class A> static void destroy(A& al, value_type* p) noexcept
         {
           boost::allocator_destroy(al, p);
         }

include/boost/unordered/unordered_map.hpp

@@ -15,6 +15,7 @@
 #pragma once
 #endif
 
+#include <boost/unordered/detail/requires_cxx11.hpp>
 #include <boost/core/explicit_operator_bool.hpp>
 #include <boost/functional/hash.hpp>
 #include <boost/move/move.hpp>

include/boost/unordered/unordered_node_map.hpp

@@ -11,6 +11,7 @@
 #endif
 
 #include <boost/unordered/detail/foa.hpp>
+#include <boost/unordered/detail/foa/element_type.hpp>
 #include <boost/unordered/detail/foa/node_handle.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/unordered_node_map_fwd.hpp>
@@ -45,23 +46,7 @@ namespace boost {
         using value_type = std::pair<Key const, T>;
         using moved_type = std::pair<raw_key_type&&, raw_mapped_type&&>;
 
-        struct element_type
-        {
-          value_type* p;
-
-          /*
-           * we use a deleted copy constructor here so the type is no longer
-           * trivially copy-constructible which inhibits our memcpy
-           * optimizations when copying the tables
-           */
-          element_type() = default;
-          element_type(element_type const&) = delete;
-          element_type(element_type&& rhs) noexcept
-          {
-            p = rhs.p;
-            rhs.p = nullptr;
-          }
-        };
+        using element_type=foa::element_type<value_type>;
 
         static value_type& value_from(element_type const& x) { return *(x.p); }
 
@@ -77,6 +62,11 @@ namespace boost {
         }
 
         static element_type&& move(element_type& x) { return std::move(x); }
+        static moved_type move(init_type& x)
+        {
+          return {std::move(x.first), std::move(x.second)};
+        }
+
         static moved_type move(value_type& x)
         {
           return {std::move(const_cast<raw_key_type&>(x.first)),
@@ -96,6 +86,18 @@ namespace boost {
           construct(al, p, *copy.p);
         }
 
+        template <class A, class... Args>
+        static void construct(A& al, init_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
+        template <class A, class... Args>
+        static void construct(A& al, value_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
         template <class A, class... Args>
         static void construct(A& al, element_type* p, Args&&... args)
         {
@@ -106,10 +108,11 @@ namespace boost {
           }
           BOOST_CATCH(...)
           {
-            boost::allocator_deallocate(al,
-              boost::pointer_traits<
-                typename boost::allocator_pointer<A>::type>::pointer_to(*p->p),
-              1);
+            using pointer_type = typename boost::allocator_pointer<A>::type;
+            using pointer_traits = boost::pointer_traits<pointer_type>;
+
+            boost::allocator_deallocate(
+              al, pointer_traits::pointer_to(*(p->p)), 1);
             BOOST_RETHROW
           }
           BOOST_CATCH_END
@@ -118,27 +121,32 @@ namespace boost {
         template <class A> static void destroy(A& al, value_type* p) noexcept
         {
           boost::allocator_destroy(al, p);
-          boost::allocator_deallocate(al,
-            boost::pointer_traits<
-              typename boost::allocator_pointer<A>::type>::pointer_to(*p),
-            1);
+        }
+
+        template <class A> static void destroy(A& al, init_type* p) noexcept
+        {
+          boost::allocator_destroy(al, p);
         }
 
         template <class A> static void destroy(A& al, element_type* p) noexcept
         {
           if (p->p) {
-            destroy(al,p->p);
+            using pointer_type = typename boost::allocator_pointer<A>::type;
+            using pointer_traits = boost::pointer_traits<pointer_type>;
+
+            destroy(al, p->p);
+            boost::allocator_deallocate(
+              al, pointer_traits::pointer_to(*(p->p)), 1);
           }
         }
       };
 
-      template <class NodeMapTypes, class Allocator>
+      template <class TypePolicy, class Allocator>
       struct node_map_handle
-          : public detail::foa::node_handle_base<NodeMapTypes, Allocator>
+          : public detail::foa::node_handle_base<TypePolicy, Allocator>
       {
       private:
-        using base_type =
-          detail::foa::node_handle_base<NodeMapTypes, Allocator>;
+        using base_type = detail::foa::node_handle_base<TypePolicy, Allocator>;
 
         using typename base_type::type_policy;
 
@@ -146,8 +154,8 @@ namespace boost {
         friend class boost::unordered::unordered_node_map;
 
       public:
-        using key_type = typename NodeMapTypes::key_type;
-        using mapped_type = typename NodeMapTypes::mapped_type;
+        using key_type = typename TypePolicy::key_type;
+        using mapped_type = typename TypePolicy::mapped_type;
 
         constexpr node_map_handle() noexcept = default;
         node_map_handle(node_map_handle&& nh) noexcept = default;
@@ -157,13 +165,13 @@ namespace boost {
         key_type& key() const
         {
           BOOST_ASSERT(!this->empty());
-          return const_cast<key_type&>(this->element().first);
+          return const_cast<key_type&>(this->data().first);
         }
 
         mapped_type& mapped() const
         {
           BOOST_ASSERT(!this->empty());
-          return const_cast<mapped_type&>(this->element().second);
+          return const_cast<mapped_type&>(this->data().second);
         }
       };
     } // namespace detail
@@ -402,12 +410,9 @@ namespace boost {
 
         BOOST_ASSERT(get_allocator() == nh.get_allocator());
 
-        typename map_types::element_type x;
-        x.p=std::addressof(nh.element());
-
-        auto itp = table_.insert(std::move(x));
+        auto itp = table_.insert(std::move(nh.element()));
         if (itp.second) {
-          nh.clear();
+          nh.reset();
           return {itp.first, true, node_type{}};
         } else {
           return {itp.first, false, std::move(nh)};
@@ -422,8 +427,13 @@ namespace boost {
 
         BOOST_ASSERT(get_allocator() == nh.get_allocator());
 
-        auto itp = table_.insert(map_types::move(nh.element()));
-        return itp.first;
+        auto itp = table_.insert(std::move(nh.element()));
+        if (itp.second) {
+          nh.reset();
+          return itp.first;
+        } else {
+          return itp.first;
+        }
       }
 
       template <class M>
@@ -594,7 +604,7 @@ namespace boost {
       node_type extract(key_type const& key)
       {
         auto pos = find(key);
-        return pos!=end()?extract(pos):node_type();
+        return pos != end() ? extract(pos) : node_type();
       }
 
       template <class K>
@@ -605,7 +615,7 @@ namespace boost {
       extract(K const& key)
       {
         auto pos = find(key);
-        return pos!=end()?extract(pos):node_type();
+        return pos != end() ? extract(pos) : node_type();
       }
 
       template <class H2, class P2>

include/boost/unordered/unordered_node_set.hpp

@@ -11,6 +11,7 @@
 #endif
 
 #include <boost/unordered/detail/foa.hpp>
+#include <boost/unordered/detail/foa/element_type.hpp>
 #include <boost/unordered/detail/foa/node_handle.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/unordered_node_set_fwd.hpp>
@@ -41,23 +42,7 @@ namespace boost {
 
         static Key const& extract(value_type const& key) { return key; }
 
-        struct element_type
-        {
-          value_type* p;
-
-          /*
-           * we use a deleted copy constructor here so the type is no longer
-           * trivially copy-constructible which inhibits our memcpy
-           * optimizations when copying the tables
-           */
-          element_type() = default;
-          element_type(element_type const&) = delete;
-          element_type(element_type&& rhs) noexcept
-          {
-            p = rhs.p;
-            rhs.p = nullptr;
-          }
-        };
+        using element_type=foa::element_type<value_type>;
 
         static value_type& value_from(element_type const& x) { return *x.p; }
         static Key const& extract(element_type const& k) { return *k.p; }
@@ -78,6 +63,12 @@ namespace boost {
           x.p = nullptr;
         }
 
+        template <class A, class... Args>
+        static void construct(A& al, value_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
         template <class A, class... Args>
         static void construct(A& al, element_type* p, Args&&... args)
         {
@@ -100,27 +91,26 @@ namespace boost {
         template <class A> static void destroy(A& al, value_type* p) noexcept
         {
           boost::allocator_destroy(al, p);
-          boost::allocator_deallocate(al,
-            boost::pointer_traits<
-              typename boost::allocator_pointer<A>::type>::pointer_to(*p),
-            1);
         }
 
         template <class A> static void destroy(A& al, element_type* p) noexcept
         {
           if (p->p) {
             destroy(al, p->p);
+            boost::allocator_deallocate(al,
+              boost::pointer_traits<typename boost::allocator_pointer<
+                A>::type>::pointer_to(*(p->p)),
+              1);
           }
         }
       };
 
-      template <class NodeSetTypes, class Allocator>
+      template <class TypePolicy, class Allocator>
       struct node_set_handle
-          : public detail::foa::node_handle_base<NodeSetTypes, Allocator>
+          : public detail::foa::node_handle_base<TypePolicy, Allocator>
       {
       private:
-        using base_type =
-          detail::foa::node_handle_base<NodeSetTypes, Allocator>;
+        using base_type = detail::foa::node_handle_base<TypePolicy, Allocator>;
 
         using typename base_type::type_policy;
 
@@ -128,7 +118,7 @@ namespace boost {
         friend class boost::unordered::unordered_node_set;
 
       public:
-        using value_type = typename NodeSetTypes::value_type;
+        using value_type = typename TypePolicy::value_type;
 
         constexpr node_set_handle() noexcept = default;
         node_set_handle(node_set_handle&& nh) noexcept = default;
@@ -137,7 +127,7 @@ namespace boost {
         value_type& value() const
         {
           BOOST_ASSERT(!this->empty());
-          return const_cast<value_type&>(this->element());
+          return const_cast<value_type&>(this->data());
         }
       };
     } // namespace detail
@@ -390,12 +380,9 @@ namespace boost {
 
         BOOST_ASSERT(get_allocator() == nh.get_allocator());
 
-        typename set_types::element_type x;
-        x.p=std::addressof(nh.element());
-
-        auto itp = table_.insert(std::move(x));
+        auto itp = table_.insert(std::move(nh.element()));
         if (itp.second) {
-          nh.clear();
+          nh.reset();
           return {itp.first, true, node_type{}};
         } else {
           return {itp.first, false, std::move(nh)};
@@ -410,8 +397,13 @@ namespace boost {
 
         BOOST_ASSERT(get_allocator() == nh.get_allocator());
 
-        auto itp = table_.insert(set_types::move(nh.element()));
-        return itp.first;
+        auto itp = table_.insert(std::move(nh.element()));
+        if (itp.second) {
+          nh.reset();
+          return itp.first;
+        } else {
+          return itp.first;
+        }
       }
 
       template <class... Args>
@@ -470,7 +462,7 @@ namespace boost {
       node_type extract(key_type const& key)
       {
         auto pos = find(key);
-        return pos!=end()?extract(pos):node_type();
+        return pos != end() ? extract(pos) : node_type();
       }
 
       template <class K>
@@ -481,7 +473,7 @@ namespace boost {
       extract(K const& key)
       {
         auto pos = find(key);
-        return pos!=end()?extract(pos):node_type();
+        return pos != end() ? extract(pos) : node_type();
       }
 
       template <class H2, class P2>

include/boost/unordered/unordered_set.hpp

@@ -15,6 +15,7 @@
 #pragma once
 #endif
 
+#include <boost/unordered/detail/requires_cxx11.hpp>
 #include <boost/core/explicit_operator_bool.hpp>
 #include <boost/functional/hash.hpp>
 #include <boost/move/move.hpp>

test/Jamfile.v2

@@ -144,6 +144,7 @@ build_foa init_type_insert_tests ;
 build_foa max_load_tests ;
 build_foa extract_tests ;
 build_foa node_handle_tests ;
+build_foa uses_allocator ;
 
 run unordered/hash_is_avalanching_test.cpp ;
 

test/unordered/insert_tests.cpp

@@ -220,7 +220,7 @@ namespace insert_tests {
       test::check_instances check_;
 
       X x;
-      iterator pos = x.begin();
+      const_iterator pos = x.begin();
       tracker_type tracker = test::create_ordered(x);
 
       test::random_values<X> v(1000, generator);
@@ -248,7 +248,7 @@ namespace insert_tests {
       test::check_instances check_;
 
       X x;
-      iterator pos = x.begin();
+      const_iterator pos = x.begin();
       tracker_type tracker = test::create_ordered(x);
 
       test::random_values<X> v(1000, generator);

test/unordered/max_load_tests.cpp

@@ -1,3 +1,8 @@
+
+// Copyright 2022-2023 Christian Mazakas.
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or move at http://www.boost.org/LICENSE_1_0.txt)
+
 #if !defined(BOOST_UNORDERED_FOA_TESTS)
 #error "max_load_tests is currently only supported by open-addressed containers"
 #else

test/unordered/node_handle_tests.cpp

@@ -337,8 +337,12 @@ static void insert_node_handle_unique(Container1& c1, Container2& c2)
     (boost::is_same<node_type, typename Container2::node_type>::value));
 
   typedef typename Container1::iterator iterator1;
+  typedef typename Container2::iterator iterator2;
   typedef typename Container2::insert_return_type insert_return_type2;
 
+  Container1 c1_copy(c1);
+  Container2 c2_copy;
+
   iterator1 r1 = insert_empty_node(c1);
   insert_return_type2 r2 = c2.insert(node_type());
   BOOST_TEST(r1 == c1.end());
@@ -367,6 +371,24 @@ static void insert_node_handle_unique(Container1& c1, Container2& c2)
       node_handle_compare(r.node, v);
     }
   }
+
+  while (!c1_copy.empty()) {
+    value_type v = *c1_copy.begin();
+    value_type const* v_ptr = boost::to_address(c1_copy.begin());
+    std::size_t count = c2_copy.count(test::get_key<Container1>(v));
+    iterator2 pos =
+      c2_copy.insert(c2_copy.begin(), c1_copy.extract(c1_copy.begin()));
+    if (!count) {
+      BOOST_TEST_EQ(c2_copy.count(test::get_key<Container1>(v)), count + 1);
+      BOOST_TEST(pos != c2.end());
+      BOOST_TEST(boost::to_address(pos) == v_ptr);
+    } else {
+      BOOST_TEST_EQ(c2_copy.count(test::get_key<Container1>(v)), count);
+      BOOST_TEST(pos != c2_copy.end());
+      BOOST_TEST(
+        test::get_key<Container2>(*pos) == test::get_key<Container2>(v));
+    }
+  }
 }
 
 template <typename Container1, typename Container2>

test/unordered/noexcept_tests.cpp

@@ -1,6 +1,6 @@
 
 // Copyright 2013 Daniel James.
-// Copyright 2022 Christian Mazakas.
+// Copyright 2022-2023 Christian Mazakas.
 // Distributed under the Boost Software License, Version 1.0. (See accompanying
 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 

test/unordered/scary_tests.cpp

@@ -1,4 +1,4 @@
-// Copyright 2022 Christian Mazakas.
+// Copyright 2022-2023 Christian Mazakas.
 // Distributed under the Boost Software License, Version 1.0. (See accompanying
 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 

test/unordered/transparent_tests.cpp

@@ -1833,7 +1833,6 @@ multiset_extract_const_overload_compile_test()
 
 template <class UnorderedSet> void test_set_transparent_extract(UnorderedSet*)
 {
-#ifndef BOOST_UNORDERED_FOA_TESTS
   typedef typename UnorderedSet::node_type node_type;
 
   count_reset();
@@ -1877,7 +1876,6 @@ template <class UnorderedSet> void test_set_transparent_extract(UnorderedSet*)
   BOOST_TEST_EQ(set.size(), set_size);
 
   BOOST_TEST_EQ(key::count_, expected_key_count);
-#endif
 }
 
 template <class UnorderedSet>

test/unordered/uses_allocator.cpp

@@ -0,0 +1,189 @@
+
+// Copyright 2023 Christian Mazakas.
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include "../helpers/test.hpp"
+
+#include <boost/unordered/detail/implementation.hpp>
+#include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/unordered/unordered_flat_set.hpp>
+#include <boost/unordered/unordered_node_map.hpp>
+#include <boost/unordered/unordered_node_set.hpp>
+
+#include <boost/config.hpp>
+#include <boost/config/pragma_message.hpp>
+#include <boost/config/workaround.hpp>
+
+#if BOOST_CXX_VERSION <= 199711L ||                                            \
+  BOOST_WORKAROUND(BOOST_GCC_VERSION, < 40800) ||                              \
+  (defined(BOOST_LIBSTDCXX_VERSION) && BOOST_CXX_VERSION > 201703L) ||         \
+  (defined(BOOST_MSVC_FULL_VER) && BOOST_MSVC_FULL_VER >= 192000000 &&         \
+    BOOST_MSVC_FULL_VER < 193000000)
+
+// automatically disable this test for C++03 builds so we can use the STL's
+// scoped_allocator_adaptor
+// we remove C++20 support for libstdc++ builds because of:
+// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108952
+//
+// msvc-14.2 w/ C++20 is similarly affected
+//
+
+
+BOOST_PRAGMA_MESSAGE("uses_allocator tests require C++11, scoped_allocator")
+
+int main() {}
+
+#else
+
+#include <memory>
+#include <scoped_allocator>
+#include <unordered_map>
+#include <vector>
+
+template <class T> struct allocator
+{
+  typedef T value_type;
+
+  int tag_ = -1;
+
+  allocator() = default;
+  allocator(int tag) : tag_{tag} {}
+  allocator(allocator const&) = default;
+  allocator(allocator&&) = default;
+
+  template <class U> allocator(allocator<U> const& rhs) : tag_{rhs.tag_} {}
+
+  BOOST_ATTRIBUTE_NODISCARD T* allocate(std::size_t n)
+  {
+    return static_cast<T*>(::operator new(n * sizeof(T)));
+  }
+
+  void deallocate(T* p, std::size_t) noexcept { ::operator delete(p); }
+
+  allocator& operator=(allocator const& rhs)
+  {
+    tag_ = rhs.tag_;
+    return *this;
+  }
+
+  allocator& operator=(allocator&& rhs) noexcept
+  {
+    tag_ = rhs.tag_;
+    return *this;
+  }
+
+  bool operator==(allocator const&) const { return true; }
+  bool operator!=(allocator const&) const { return false; }
+};
+
+struct raii_tracker
+{
+  static int count;
+  static int copy_count;
+  static int move_count;
+  static int alloc_move_count;
+
+  using allocator_type = allocator<int>;
+
+  allocator_type a_;
+
+  raii_tracker(allocator_type a) : a_(a) { ++count; }
+  raii_tracker(int, allocator_type const& a) : a_(a) { ++count; }
+
+  raii_tracker(raii_tracker const&) { ++copy_count; }
+  raii_tracker(raii_tracker&&) noexcept { ++move_count; }
+  raii_tracker(raii_tracker&&, allocator_type const& a) noexcept : a_(a)
+  {
+    ++alloc_move_count;
+  }
+
+  allocator_type get_allocator() const noexcept { return a_; }
+
+  friend bool operator==(raii_tracker const&, raii_tracker const&)
+  {
+    return true;
+  }
+};
+
+int raii_tracker::count = 0;
+int raii_tracker::copy_count = 0;
+int raii_tracker::move_count = 0;
+int raii_tracker::alloc_move_count = 0;
+
+static void reset_counts()
+{
+  raii_tracker::count = 0;
+  raii_tracker::copy_count = 0;
+  raii_tracker::move_count = 0;
+  raii_tracker::alloc_move_count = 0;
+}
+
+std::size_t hash_value(raii_tracker const&) { return 0; }
+
+using map_allocator_type = std::scoped_allocator_adaptor<
+  allocator<std::pair<raii_tracker const, raii_tracker> >, allocator<int> >;
+
+using set_allocator_type =
+  std::scoped_allocator_adaptor<allocator<raii_tracker>, allocator<int> >;
+
+using map_type = boost::unordered_flat_map<raii_tracker, raii_tracker,
+  boost::hash<raii_tracker>, std::equal_to<raii_tracker>, map_allocator_type>;
+
+using node_map_type = boost::unordered_node_map<raii_tracker, raii_tracker,
+  boost::hash<raii_tracker>, std::equal_to<raii_tracker>, map_allocator_type>;
+
+using set_type = boost::unordered_flat_set<raii_tracker,
+  boost::hash<raii_tracker>, std::equal_to<raii_tracker>, set_allocator_type>;
+
+using node_set_type = boost::unordered_node_set<raii_tracker,
+  boost::hash<raii_tracker>, std::equal_to<raii_tracker>, set_allocator_type>;
+
+map_type* flat_map;
+node_map_type* node_map;
+
+set_type* flat_set;
+node_set_type* node_set;
+
+template <class X> static void map_uses_allocator_construction(X*)
+{
+  reset_counts();
+
+  map_allocator_type alloc(
+    allocator<std::pair<raii_tracker const, raii_tracker> >{12},
+    allocator<int>{34});
+
+  X map(1, alloc);
+  map.emplace(
+    std::piecewise_construct, std::make_tuple(1337), std::make_tuple(7331));
+
+  BOOST_TEST_EQ(raii_tracker::count, 2);
+  BOOST_TEST_EQ(raii_tracker::move_count, 0);
+  BOOST_TEST_EQ(raii_tracker::alloc_move_count, 2);
+
+  BOOST_TEST_EQ(map.begin()->first.get_allocator().tag_, 34);
+  BOOST_TEST_EQ(map.begin()->second.get_allocator().tag_, 34);
+}
+
+template <class X> static void set_uses_allocator_construction(X*)
+{
+  reset_counts();
+
+  set_allocator_type alloc(allocator<raii_tracker>{12}, allocator<int>{34});
+
+  X set(1, alloc);
+  set.emplace();
+
+  BOOST_TEST_EQ(raii_tracker::count, 1);
+  BOOST_TEST_EQ(raii_tracker::move_count, 0);
+  BOOST_TEST_EQ(raii_tracker::alloc_move_count, 1);
+
+  BOOST_TEST_EQ(set.begin()->get_allocator().tag_, 34);
+}
+
+UNORDERED_TEST(map_uses_allocator_construction, ((flat_map)(node_map)))
+UNORDERED_TEST(set_uses_allocator_construction, ((flat_set)(node_set)))
+
+RUN_TESTS()
+
+#endif