Merge branch 'develop' into feature/mixing-policy

Exception Guarantees

benchmark/uint32.cpp

@@ -289,8 +289,20 @@ 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_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+template<class K, class V> using boost_unordered_flat_map_xmx =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_xmx2 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx2_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_xmx3 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx3_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_mulx =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::mulx_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_mulx2 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::mulx2_mix>;
 
 #ifdef HAVE_ABSEIL
 
@@ -315,7 +327,12 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
+
+    test<boost_unordered_flat_map_xmx>( "boost::unordered_flat_map, xmx" );
+    test<boost_unordered_flat_map_xmx2>( "boost::unordered_flat_map, xmx2" );
+    test<boost_unordered_flat_map_xmx3>( "boost::unordered_flat_map, xmx3" );
+    test<boost_unordered_flat_map_mulx>( "boost::unordered_flat_map, mulx" );
+    test<boost_unordered_flat_map_mulx2>( "boost::unordered_flat_map, mulx2" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE
 
@@ -334,7 +351,7 @@ int main()
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 34 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uint64.cpp

@@ -289,8 +289,20 @@ 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_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+template<class K, class V> using boost_unordered_flat_map_xmx =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_xmx2 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx2_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_xmx3 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx3_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_mulx =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::mulx_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_mulx2 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::mulx2_mix>;
 
 #ifdef HAVE_ABSEIL
 
@@ -325,7 +337,12 @@ int main()
 #endif
 
     test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
+
+    test<boost_unordered_flat_map_xmx>( "boost::unordered_flat_map, xmx" );
+    test<boost_unordered_flat_map_xmx2>( "boost::unordered_flat_map, xmx2" );
+    test<boost_unordered_flat_map_xmx3>( "boost::unordered_flat_map, xmx3" );
+    test<boost_unordered_flat_map_mulx>( "boost::unordered_flat_map, mulx" );
+    test<boost_unordered_flat_map_mulx2>( "boost::unordered_flat_map, mulx2" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE
 
@@ -344,7 +361,7 @@ int main()
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 34 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uuid.cpp

@@ -340,8 +340,20 @@ 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_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+template<class K, class V> using boost_unordered_flat_map_xmx =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_xmx2 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx2_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_xmx3 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx3_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_mulx =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::mulx_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_mulx2 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::mulx2_mix>;
 
 #ifdef HAVE_ABSEIL
 
@@ -366,7 +378,12 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
+
+    test<boost_unordered_flat_map_xmx>( "boost::unordered_flat_map, xmx" );
+    test<boost_unordered_flat_map_xmx2>( "boost::unordered_flat_map, xmx2" );
+    test<boost_unordered_flat_map_xmx3>( "boost::unordered_flat_map, xmx3" );
+    test<boost_unordered_flat_map_mulx>( "boost::unordered_flat_map, mulx" );
+    test<boost_unordered_flat_map_mulx2>( "boost::unordered_flat_map, mulx2" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE
 
@@ -385,7 +402,7 @@ int main()
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 34 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/word_size.cpp

@@ -181,8 +181,20 @@ 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_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+template<class K, class V> using boost_unordered_flat_map_xmx =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_xmx2 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx2_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_xmx3 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::xmx3_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_mulx =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::mulx_mix>;
+
+template<class K, class V> using boost_unordered_flat_map_mulx2 =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>, boost::unordered::detail::foa::mulx2_mix>;
 
 #ifdef HAVE_ABSEIL
 
@@ -207,7 +219,12 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
+
+    test<boost_unordered_flat_map_xmx>( "boost::unordered_flat_map, xmx" );
+    test<boost_unordered_flat_map_xmx2>( "boost::unordered_flat_map, xmx2" );
+    test<boost_unordered_flat_map_xmx3>( "boost::unordered_flat_map, xmx3" );
+    test<boost_unordered_flat_map_mulx>( "boost::unordered_flat_map, mulx" );
+    test<boost_unordered_flat_map_mulx2>( "boost::unordered_flat_map, mulx2" );
 
 #ifdef HAVE_ANKERL_UNORDERED_DENSE
 
@@ -226,7 +243,7 @@ int main()
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 34 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

doc/unordered/unordered_flat_map.adoc

@@ -98,9 +98,8 @@ namespace boost {
     xref:#unordered_flat_map_destructor[~unordered_flat_map]();
     unordered_flat_map& xref:#unordered_flat_map_copy_assignment[operator++=++](const unordered_flat_map& other);
     unordered_flat_map& xref:#unordered_flat_map_move_assignment[operator++=++](unordered_flat_map&& other)
-      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value &&
-               boost::is_nothrow_move_assignable_v<Hash> &&
-               boost::is_nothrow_move_assignable_v<Pred>);
+      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
+              boost::allocator_traits<Allocator>::propagate_on_container_move_assignment::value);
     unordered_flat_map& xref:#unordered_flat_map_initializer_list_assignment[operator++=++](std::initializer_list<value_type>);
     allocator_type xref:#unordered_flat_map_get_allocator[get_allocator]() const noexcept;
 
@@ -154,9 +153,8 @@ namespace boost {
     template<class K> size_type xref:#unordered_flat_map_transparent_erase_by_key[erase](K&& k);
     iterator  xref:#unordered_flat_map_erase_range[erase](const_iterator first, const_iterator last);
     void      xref:#unordered_flat_map_swap[swap](unordered_flat_map& other)
-      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value &&
-               boost::is_nothrow_swappable_v<Hash> &&
-               boost::is_nothrow_swappable_v<Pred>);
+      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
+               boost::allocator_traits<Allocator>::propagate_on_container_swap::value);
     void      xref:#unordered_flat_map_clear[clear]() noexcept;
 
     template<class H2, class P2>
@@ -606,11 +604,10 @@ Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInse
 ==== Move Assignment
 ```c++
 unordered_flat_map& operator=(unordered_flat_map&& other)
-  noexcept(boost::allocator_traits<Allocator>::is_always_equal::value &&
-           boost::is_nothrow_move_assignable_v<Hash> &&
-           boost::is_nothrow_move_assignable_v<Pred>);
+  noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
+           boost::allocator_traits<Allocator>::propagate_on_container_move_assignment::value);
 ```
-The move assignment operator. Destroys previously existing elements, move-assigns the hash function and predicate from `other`,
+The move assignment operator. Destroys previously existing elements, swaps the hash function and predicate from `other`,
 and move-assigns the allocator from `other` if `Alloc::propagate_on_container_move_assignment` exists and `Alloc::propagate_on_container_move_assignment::value` is `true`.
 If at this point the allocator is equal to `other.get_allocator()`, the internal bucket array of `other` is transferred directly to the new container;
 otherwise, inserts move-constructed copies of the elements of `other`.
@@ -1043,9 +1040,8 @@ Throws:;; Nothing in this implementation (neither the `hasher` nor the `key_equa
 ==== swap
 ```c++
 void swap(unordered_flat_map& other)
-  noexcept(boost::allocator_traits<Allocator>::is_always_equal::value &&
-           boost::is_nothrow_swappable_v<Hash> &&
-           boost::is_nothrow_swappable_v<Pred>);
+  noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
+           boost::allocator_traits<Allocator>::propagate_on_container_swap::value);
 ```
 
 Swaps the contents of the container with the parameter.

doc/unordered/unordered_flat_set.adoc

@@ -93,9 +93,8 @@ namespace boost {
     xref:#unordered_flat_set_destructor[~unordered_flat_set]();
     unordered_flat_set& xref:#unordered_flat_set_copy_assignment[operator++=++](const unordered_flat_set& other);
     unordered_flat_set& xref:#unordered_flat_set_move_assignment[operator++=++](unordered_flat_set&& other)
-      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value &&
-               boost::is_nothrow_move_assignable_v<Hash> &&
-               boost::is_nothrow_move_assignable_v<Pred>);
+      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
+               boost::allocator_traits<Allocator>::propagate_on_container_move_assignment::value);
     unordered_flat_set& xref:#unordered_flat_set_initializer_list_assignment[operator++=++](std::initializer_list<value_type>);
     allocator_type xref:#unordered_flat_set_get_allocator[get_allocator]() const noexcept;
 
@@ -128,9 +127,8 @@ namespace boost {
     template<class K> size_type xref:#unordered_flat_set_transparent_erase_by_key[erase](K&& k);
     iterator  xref:#unordered_flat_set_erase_range[erase](const_iterator first, const_iterator last);
     void      xref:#unordered_flat_set_swap[swap](unordered_flat_set& other)
-      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value &&
-               boost::is_nothrow_swappable_v<Hash> &&
-               boost::is_nothrow_swappable_v<Pred>);
+      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
+               boost::allocator_traits<Allocator>::propagate_on_container_swap::value);
     void      xref:#unordered_flat_set_clear[clear]() noexcept;
 
     template<class H2, class P2>
@@ -565,11 +563,10 @@ Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInse
 ==== Move Assignment
 ```c++
 unordered_flat_set& operator=(unordered_flat_set&& other)
-  noexcept(boost::allocator_traits<Allocator>::is_always_equal::value &&
-           boost::is_nothrow_move_assignable_v<Hash> &&
-           boost::is_nothrow_move_assignable_v<Pred>);
+  noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
+           boost::allocator_traits<Allocator>::propagate_on_container_move_assignment::value);
 ```
-The move assignment operator. Destroys previously existing elements, move-assigns the hash function and predicate from `other`,
+The move assignment operator. Destroys previously existing elements, swaps the hash function and predicate from `other`,
 and move-assigns the allocator from `other` if `Alloc::propagate_on_container_move_assignment` exists and `Alloc::propagate_on_container_move_assignment::value` is `true`.
 If at this point the allocator is equal to `other.get_allocator()`, the internal bucket array of `other` is transferred directly to the new container;
 otherwise, inserts move-constructed copies of the elements of `other`.
@@ -863,9 +860,8 @@ Throws:;; Nothing in this implementation (neither the `hasher` nor the `key_equa
 ==== swap
 ```c++
 void swap(unordered_flat_set& other)
-  noexcept(boost::allocator_traits<Allocator>::is_always_equal::value &&
-           boost::is_nothrow_swappable_v<Hash> &&
-           boost::is_nothrow_swappable_v<Pred>);
+  noexcept(boost::allocator_traits<Allocator>::is_always_equal::value ||
+           boost::allocator_traits<Allocator>::propagate_on_container_swap::value);
 ```
 
 Swaps the contents of the container with the parameter.

include/boost/unordered/detail/foa.hpp

@@ -21,8 +21,10 @@
 #include <boost/core/pointer_traits.hpp>
 #include <boost/cstdint.hpp>
 #include <boost/predef.h>
+#include <boost/type_traits/has_trivial_copy.hpp>
 #include <boost/type_traits/is_nothrow_swappable.hpp>
 #include <boost/unordered/detail/xmx.hpp>
+#include <boost/unordered/detail/mulx.hpp>
 #include <boost/unordered/hash_traits.hpp>
 #include <climits>
 #include <cmath>
@@ -30,6 +32,7 @@
 #include <cstring>
 #include <iterator>
 #include <limits>
+#include <memory>
 #include <tuple>
 #include <type_traits>
 #include <utility>
@@ -67,6 +70,12 @@
   }while(0)
 #endif
 
+#define BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED(Hash, Pred)                    \
+  static_assert(boost::is_nothrow_swappable<Hash>::value,                      \
+    "Template parameter Hash is required to be nothrow Swappable.");           \
+  static_assert(boost::is_nothrow_swappable<Pred>::value,                      \
+    "Template parameter Pred is required to be nothrow Swappable");
+
 namespace boost{
 namespace unordered{
 namespace detail{
@@ -760,6 +769,42 @@ struct xmx_mix
   }
 };
 
+struct xmx2_mix
+{
+  template<typename Hash,typename T>
+  static inline std::size_t mix(const Hash& h,const T& x)
+  {
+    return xmx2(h(x));
+  }
+};
+
+struct xmx3_mix
+{
+  template<typename Hash,typename T>
+  static inline std::size_t mix(const Hash& h,const T& x)
+  {
+    return xmx3(h(x));
+  }
+};
+
+struct mulx_mix
+{
+  template<typename Hash,typename T>
+  static inline std::size_t mix(const Hash& h,const T& x)
+  {
+    return mulx(h(x));
+  }
+};
+
+struct mulx2_mix
+{
+  template<typename Hash,typename T>
+  static inline std::size_t mix(const Hash& h,const T& x)
+  {
+    return mulx2(h(x));
+  }
+};
+
 /* boost::core::countr_zero has a potentially costly check for
  * the case x==0.
  */
@@ -776,7 +821,7 @@ inline unsigned int unchecked_countr_zero(int x)
 #endif
 }
 
-template<typename,typename,typename,typename>
+template<typename,typename,typename,typename,typename>
 class table;
 
 /* table_iterator keeps two pointers:
@@ -840,7 +885,7 @@ public:
 
 private:
   template<typename,typename,bool> friend class table_iterator;
-  template<typename,typename,typename,typename> friend class table;
+  template<typename,typename,typename,typename,typename> friend class table;
 
   table_iterator(Group* pg,std::size_t n,const Value* p_):
     pc{reinterpret_cast<unsigned char*>(const_cast<Group*>(pg))+n},
@@ -1022,6 +1067,49 @@ inline void prefetch(const void* p)
 #endif    
 }
 
+struct try_emplace_args_t{};
+
+template<typename Allocator>
+struct is_std_allocator:std::false_type{};
+
+template<typename T>
+struct is_std_allocator<std::allocator<T>>:std::true_type{};
+
+/* std::allocator::construct marked as deprecated */
+#if defined(_LIBCPP_SUPPRESS_DEPRECATED_PUSH)
+_LIBCPP_SUPPRESS_DEPRECATED_PUSH
+#elif defined(_STL_DISABLE_DEPRECATED_WARNING)
+_STL_DISABLE_DEPRECATED_WARNING
+#elif defined(_MSC_VER)
+#pragma warning(push)
+#pragma warning(disable:4996)
+#endif
+
+template<typename Allocator,typename Ptr,typename... Args>
+struct alloc_has_construct
+{
+private:
+  template<typename Allocator2>
+  static decltype(
+    std::declval<Allocator2&>().construct(
+      std::declval<Ptr>(),std::declval<Args&&>()...),
+    std::true_type{}
+  ) check(int);
+
+  template<typename> static std::false_type check(...);
+
+public:
+  static constexpr bool value=decltype(check<Allocator>(0))::value;
+};
+
+#if defined(_LIBCPP_SUPPRESS_DEPRECATED_POP)
+_LIBCPP_SUPPRESS_DEPRECATED_POP
+#elif defined(_STL_RESTORE_DEPRECATED_WARNING)
+_STL_RESTORE_DEPRECATED_WARNING
+#elif defined(_MSC_VER)
+#pragma warning(pop)
+#endif
+
 #if defined(BOOST_GCC)
 /* GCC's -Wshadow triggers at scenarios like this: 
  *
@@ -1102,7 +1190,7 @@ inline void prefetch(const void* p)
  */
 constexpr static float const mlf = 0.875f;
 
-template<typename TypePolicy,typename Hash,typename Pred,typename Allocator>
+template<typename TypePolicy,typename Hash,typename Pred,typename Allocator,typename MixPolicy=xmx_mix>
 class 
 
 #if defined(_MSC_VER)&&_MSC_FULL_VER>=190023918
@@ -1122,7 +1210,7 @@ table:empty_value<Hash,0>,empty_value<Pred,1>,empty_value<Allocator,2>
   using mix_policy=typename std::conditional<
     hash_is_avalanching<Hash>::value,
     no_mix,
-    xmx_mix
+    MixPolicy
   >::type;
   using alloc_traits=boost::allocator_traits<Allocator>;
 
@@ -1180,9 +1268,7 @@ public:
   table(const table& x,const Allocator& al_):
     table{std::size_t(std::ceil(float(x.size())/mlf)),x.h(),x.pred(),al_}
   {
-    x.for_all_elements([this](value_type* p){
-      unchecked_insert(*p);
-    });
+    copy_elements_from(x);
   }
 
   table(table&& x,const Allocator& al_):
@@ -1217,22 +1303,35 @@ public:
 
   table& operator=(const table& x)
   {
+    BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED(Hash, Pred)
+
     static constexpr auto pocca=
       alloc_traits::propagate_on_container_copy_assignment::value;
 
     if(this!=std::addressof(x)){
-      clear();
-      h()=x.h();
-      pred()=x.pred();
+      // if copy construction here winds up throwing, the container is still
+      // left intact so we perform these operations first
+      hasher    tmp_h=x.h();
+      key_equal tmp_p=x.pred();
+
+      // already noexcept, clear() before we swap the Hash, Pred just in case
+      // the clear() impl relies on them at some point in the future
+      clear(); 
+
+      // because we've asserted at compile-time that Hash and Pred are nothrow
+      // swappable, we can safely mutate our source container and maintain
+      // consistency between the Hash, Pred compatibility
+      using std::swap;
+      swap(h(),tmp_h);
+      swap(pred(),tmp_p);
+
       if_constexpr<pocca>([&,this]{
         if(al()!=x.al())reserve(0);
         copy_assign_if<pocca>(al(),x.al());
       });
       /* noshrink: favor memory reuse over tightness */
-      noshrink_reserve(x.size()); 
-      x.for_all_elements([this](value_type* p){
-        unchecked_insert(*p);
-      });
+      noshrink_reserve(x.size());
+      copy_elements_from(x);
     }
     return *this;
   }
@@ -1244,19 +1343,32 @@ public:
 
   table& operator=(table&& x)
     noexcept(
-      alloc_traits::is_always_equal::value&&
-      std::is_nothrow_move_assignable<Hash>::value&&
-      std::is_nothrow_move_assignable<Pred>::value)
+      alloc_traits::propagate_on_container_move_assignment::value||
+      alloc_traits::is_always_equal::value)
   {
+    BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED(Hash, Pred)
+
     static constexpr auto pocma=
       alloc_traits::propagate_on_container_move_assignment::value;
 
     if(this!=std::addressof(x)){
+      /* Given ambiguity in implementation strategies briefly discussed here:
+       * https://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2227
+       *
+       * we opt into requiring nothrow swappability and eschew the move
+       * operations associated with Hash, Pred.
+       *
+       * To this end, we ensure that the user never has to consider the
+       * moved-from state of their Hash, Pred objects
+       */
+
+      using std::swap;
+
       clear();
-      h()=std::move(x.h());
-      pred()=std::move(x.pred());
+      swap(h(),x.h());
+      swap(pred(),x.pred());
+
       if(pocma||al()==x.al()){
-        using std::swap;
         reserve(0);
         move_assign_if<pocma>(al(),x.al());
         swap(size_,x.size_);
@@ -1319,12 +1431,10 @@ public:
 
   template<typename Key,typename... Args>
   BOOST_FORCEINLINE std::pair<iterator,bool> try_emplace(
-    Key&& k,Args&&... args)
+    Key&& x,Args&&... args)
   {
     return emplace_impl(
-      std::piecewise_construct,
-      std::forward_as_tuple(std::forward<Key>(k)),
-      std::forward_as_tuple(std::forward<Args>(args)...));
+      try_emplace_args_t{},std::forward<Key>(x),std::forward<Args>(args)...);
   }
 
   BOOST_FORCEINLINE std::pair<iterator,bool>
@@ -1373,16 +1483,15 @@ public:
 
   void swap(table& x)
     noexcept(
-      alloc_traits::is_always_equal::value&&
-      boost::is_nothrow_swappable<Hash>::value&&
-      boost::is_nothrow_swappable<Pred>::value)
+      alloc_traits::propagate_on_container_swap::value||
+      alloc_traits::is_always_equal::value)
   {
+    BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED(Hash, Pred)
+
     static constexpr auto pocs=
       alloc_traits::propagate_on_container_swap::value;
 
     using std::swap;
-    swap(h(),x.h());
-    swap(pred(),x.pred());
     if_constexpr<pocs>([&,this]{
       swap_if<pocs>(al(),x.al());
     },
@@ -1390,6 +1499,9 @@ public:
       BOOST_ASSERT(al()==x.al());
       (void)this; /* makes sure captured this is used */
     });
+
+    swap(h(),x.h());
+    swap(pred(),x.pred());
     swap(size_,x.size_);
     swap(arrays,x.arrays);
     swap(ml,x.ml);
@@ -1481,7 +1593,7 @@ public:
   }
 
 private:
-  template<typename,typename,typename,typename> friend class table;
+  template<typename,typename,typename,typename,typename> friend class table;
   using arrays_type=table_arrays<value_type,group_type,size_policy>;
 
   struct clear_on_exit
@@ -1513,6 +1625,37 @@ private:
     alloc_traits::construct(al(),p,std::forward<Args>(args)...);
   }
 
+  template<typename... Args>
+  void construct_element(value_type* p,try_emplace_args_t,Args&&... args)
+  {
+    construct_element_from_try_emplace_args(
+      p,
+      std::integral_constant<bool,std::is_same<key_type,value_type>::value>{},
+      std::forward<Args>(args)...);
+  }
+
+  template<typename Key,typename... Args>
+  void construct_element_from_try_emplace_args(
+    value_type* p,std::false_type,Key&& x,Args&&... args)
+  {
+    alloc_traits::construct(
+      al(),p,
+      std::piecewise_construct,
+      std::forward_as_tuple(std::forward<Key>(x)),
+      std::forward_as_tuple(std::forward<Args>(args)...));
+  }
+
+  /* This overload allows boost::unordered_flat_set to internally use
+   * try_emplace to implement heterogeneous insert (P2363).
+   */
+
+  template<typename Key>
+  void construct_element_from_try_emplace_args(
+    value_type* p,std::true_type,Key&& x)
+  {
+    alloc_traits::construct(al(),p,std::forward<Key>(x));
+  }
+
   void destroy_element(value_type* p)noexcept
   {
     alloc_traits::destroy(al(),p);
@@ -1525,6 +1668,82 @@ private:
     value_type *p;
   };
 
+  void copy_elements_from(const table& x)
+  {
+    BOOST_ASSERT(empty());
+    BOOST_ASSERT(this!=std::addressof(x));
+    if(arrays.groups_size_mask==x.arrays.groups_size_mask){
+      fast_copy_elements_from(x);
+    }
+    else{
+      x.for_all_elements([this](const value_type* p){
+        unchecked_insert(*p);
+      });
+    }
+  }
+
+  void fast_copy_elements_from(const table& x)
+  {
+    if(arrays.elements){
+      copy_elements_array_from(x);
+      std::memcpy(
+        arrays.groups,x.arrays.groups,
+        (arrays.groups_size_mask+1)*sizeof(group_type));
+      size_=x.size();
+    }
+  }
+
+  void copy_elements_array_from(const table& x)
+  {
+    copy_elements_array_from(
+      x,
+      std::integral_constant<
+        bool,
+#if BOOST_WORKAROUND(BOOST_LIBSTDCXX_VERSION,<50000)
+        /* std::is_trivially_copy_constructible not provided */
+        boost::has_trivial_copy<value_type>::value
+#else
+        std::is_trivially_copy_constructible<value_type>::value
+#endif
+        &&(
+          is_std_allocator<Allocator>::value||
+          !alloc_has_construct<Allocator,value_type*,const value_type&>::value)
+      >{}
+    );
+  }
+
+  void copy_elements_array_from(const table& x,std::true_type /* -> memcpy */)
+  {
+    /* reinterpret_cast: GCC may complain about value_type not being trivially
+     * copy-assignable when we're relying on trivial copy constructibility.
+     */
+    std::memcpy(
+      reinterpret_cast<unsigned char*>(arrays.elements),
+      reinterpret_cast<unsigned char*>(x.arrays.elements),
+      x.capacity()*sizeof(value_type));
+  }
+
+  void copy_elements_array_from(const table& x,std::false_type /* -> manual */)
+  {
+    std::size_t num_constructed=0;
+    BOOST_TRY{
+      x.for_all_elements([&,this](const value_type* p){
+        construct_element(arrays.elements+(p-x.arrays.elements),*p);
+        ++num_constructed;
+      });
+    }
+    BOOST_CATCH(...){
+      if(num_constructed){
+        x.for_all_elements_while([&,this](const value_type* p){
+          destroy_element(arrays.elements+(p-x.arrays.elements));
+          return --num_constructed!=0;
+        });
+      }
+      BOOST_RETHROW
+    }
+    BOOST_CATCH_END
+  }
+
   void recover_slot(unsigned char* pc)
   {
     /* If this slot potentially caused overflow, we decrease the maximum load so
@@ -1561,12 +1780,11 @@ private:
     return type_policy::extract(x);
   }
 
-  template<typename Arg1,typename Arg2>
-  static inline auto key_from(
-    std::piecewise_construct_t,const Arg1& k,const Arg2&)
-    ->decltype(std::get<0>(k))
+  template<typename Key,typename... Args>
+  static inline const Key& key_from(
+    try_emplace_args_t,const Key& x,const Args&...)
   {
-    return std::get<0>(k);
+    return x;
   }
 
   template<typename Key>
@@ -1727,17 +1945,13 @@ private:
     }
     BOOST_CATCH(...){
       if(num_destroyed){
-        for(auto pg=arrays.groups;;++pg){
-          auto mask=pg->match_occupied();
-          while(mask){
-            auto nz=unchecked_countr_zero(mask);
-            recover_slot(pg,nz);
-            if(!(--num_destroyed))goto continue_;
-            mask&=mask-1;
+        for_all_elements_while(
+          [&,this](group_type* pg,unsigned int n,value_type*){
+            recover_slot(pg,n);
+            return --num_destroyed!=0;
           }
-        }
+        );
       }
-      continue_:
       for_all_elements(new_arrays_,[this](value_type* p){
         destroy_element(p);
       });
@@ -1867,13 +2081,35 @@ private:
   static auto for_all_elements(const arrays_type& arrays_,F f)
     ->decltype(f(nullptr),void())
   {
-    for_all_elements(
-      arrays_,[&](group_type*,unsigned int,value_type* p){return f(p);});
+    for_all_elements_while(arrays_,[&](value_type* p){f(p);return true;});
   }
 
   template<typename F>
   static auto for_all_elements(const arrays_type& arrays_,F f)
     ->decltype(f(nullptr,0,nullptr),void())
+  {
+    for_all_elements_while(
+      arrays_,[&](group_type* pg,unsigned int n,value_type* p)
+        {f(pg,n,p);return true;});
+  }
+
+  template<typename F>
+  void for_all_elements_while(F f)const
+  {
+    for_all_elements_while(arrays,f);
+  }
+
+  template<typename F>
+  static auto for_all_elements_while(const arrays_type& arrays_,F f)
+    ->decltype(f(nullptr),void())
+  {
+    for_all_elements_while(
+      arrays_,[&](group_type*,unsigned int,value_type* p){return f(p);});
+  }
+
+  template<typename F>
+  static auto for_all_elements_while(const arrays_type& arrays_,F f)
+    ->decltype(f(nullptr,0,nullptr),void())
   {
     auto p=arrays_.elements;
     if(!p){return;}
@@ -1882,7 +2118,7 @@ private:
       auto mask=pg->match_really_occupied();
       while(mask){
         auto n=unchecked_countr_zero(mask);
-        f(pg,n,p+n);
+        if(!f(pg,n,p+n))return;
         mask&=mask-1;
       }
     }
@@ -1912,6 +2148,7 @@ private:
 
 #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

include/boost/unordered/detail/mulx.hpp

@@ -0,0 +1,135 @@
+#ifndef BOOST_UNORDERED_DETAIL_MULX_HPP
+#define BOOST_UNORDERED_DETAIL_MULX_HPP
+
+// Copyright 2022 Peter Dimov.
+// Copyright 2022 Joaquin M Lopez Munoz.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/cstdint.hpp>
+#include <climits>
+#include <cstddef>
+
+#if defined(_MSC_VER) && !defined(__clang__)
+# include <intrin.h>
+#endif
+
+namespace boost {
+namespace unordered {
+namespace detail {
+
+// Bit mixer based on the mulx primitive
+
+#if defined(_MSC_VER) && defined(_M_X64) && !defined(__clang__)
+
+__forceinline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
+{
+    boost::uint64_t r2;
+    boost::uint64_t r = _umul128( x, y, &r2 );
+    return r ^ r2;
+}
+
+#elif defined(_MSC_VER) && defined(_M_ARM64) && !defined(__clang__)
+
+__forceinline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
+{
+    boost::uint64_t r = x * y;
+    boost::uint64_t r2 = __umulh( x, y );
+    return r ^ r2;
+}
+
+#elif defined(__SIZEOF_INT128__)
+
+inline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
+{
+    __uint128_t r = (__uint128_t)x * y;
+    return (boost::uint64_t)r ^ (boost::uint64_t)( r >> 64 );
+}
+
+#else
+
+inline boost::uint64_t mulx64( boost::uint64_t x, boost::uint64_t y )
+{
+    boost::uint64_t x1 = (boost::uint32_t)x;
+    boost::uint64_t x2 = x >> 32;
+
+    boost::uint64_t y1 = (boost::uint32_t)y;
+    boost::uint64_t y2 = y >> 32;
+
+    boost::uint64_t r3 = x2 * y2;
+
+    boost::uint64_t r2a = x1 * y2;
+
+    r3 += r2a >> 32;
+
+    boost::uint64_t r2b = x2 * y1;
+
+    r3 += r2b >> 32;
+
+    boost::uint64_t r1 = x1 * y1;
+
+    boost::uint64_t r2 = (r1 >> 32) + (boost::uint32_t)r2a + (boost::uint32_t)r2b;
+
+    r1 = (r2 << 32) + (boost::uint32_t)r1;
+    r3 += r2 >> 32;
+
+    return r1 ^ r3;
+}
+
+#endif
+
+inline boost::uint32_t mulx32( boost::uint32_t x, boost::uint32_t y )
+{
+    boost::uint64_t r = (boost::uint64_t)x * y;
+    return (boost::uint32_t)r ^ (boost::uint32_t)(r >> 32);
+}
+
+#if defined(SIZE_MAX)
+#if ((((SIZE_MAX >> 16) >> 16) >> 16) >> 15) != 0
+#define BOOST_UNORDERED_64B_ARCHITECTURE /* >64 bits assumed as 64 bits */
+#endif
+#elif defined(UINTPTR_MAX) /* used as proxy for std::size_t */
+#if ((((UINTPTR_MAX >> 16) >> 16) >> 16) >> 15) != 0
+#define BOOST_UNORDERED_64B_ARCHITECTURE
+#endif
+#endif
+
+// phi multipliers
+
+inline std::size_t mulx( std::size_t x ) noexcept
+{
+#if defined(BOOST_UNORDERED_64B_ARCHITECTURE)
+
+    return (std::size_t)mulx64( (boost::uint64_t)x, 0x9E3779B97F4A7C15ull );
+
+#else /* 32 bits assumed */
+
+    return mulx32( x, 0x9E3779B9u );
+
+#endif
+}
+
+// multipliers from https://arxiv.org/abs/2001.05304
+
+inline std::size_t mulx2( std::size_t x ) noexcept
+{
+#if defined(BOOST_UNORDERED_64B_ARCHITECTURE)
+
+    return (std::size_t)mulx64( (boost::uint64_t)x, 0xDEFBA91144F2B375ull );
+
+#else /* 32 bits assumed */
+
+    return mulx32( x, 0xE817FB2Du );
+
+#endif
+}
+
+#ifdef BOOST_UNORDERED_64B_ARCHITECTURE
+#undef BOOST_UNORDERED_64B_ARCHITECTURE
+#endif
+
+} // namespace detail
+} // namespace unordered
+} // namespace boost
+
+#endif // #ifndef BOOST_UNORDERED_DETAIL_MULX_HPP

include/boost/unordered/detail/xmx.hpp

@@ -64,6 +64,56 @@ static inline std::size_t xmx(std::size_t x)noexcept
 #endif
 }
 
+// alternative multipliers (phi)
+
+static inline std::size_t xmx2( std::size_t x ) noexcept
+{
+#if defined(BOOST_UNORDERED_64B_ARCHITECTURE)
+
+  boost::uint64_t z=(boost::uint64_t)x;
+
+  z ^= z >> 23;
+  z *= 0x9E3779B97F4A7C15ull;
+  z ^= z >> 23;
+
+  return (std::size_t)z;
+
+#else /* 32 bits assumed */
+
+  x ^= x >> 18;
+  x *= 0x9E3779B9u;
+  x ^= x >> 16;
+
+  return x;
+
+#endif
+}
+
+// alternative multipliers (https://arxiv.org/abs/2001.05304)
+
+static inline std::size_t xmx3( std::size_t x ) noexcept
+{
+#if defined(BOOST_UNORDERED_64B_ARCHITECTURE)
+
+  boost::uint64_t z=(boost::uint64_t)x;
+
+  z ^= z >> 23;
+  z *= 0xF1357AEA2E62A9C5ull;
+  z ^= z >> 23;
+
+  return (std::size_t)z;
+
+#else /* 32 bits assumed */
+
+  x ^= x >> 18;
+  x *= 0x93D765DDu;
+  x ^= x >> 16;
+
+  return x;
+
+#endif
+}
+
 #ifdef BOOST_UNORDERED_64B_ARCHITECTURE
 #undef BOOST_UNORDERED_64B_ARCHITECTURE
 #endif

include/boost/unordered/unordered_flat_map.hpp

@@ -32,7 +32,7 @@ namespace boost {
 #pragma warning(disable : 4714) /* marked as __forceinline not inlined */
 #endif
 
-    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator, class MixPolicy>
     class unordered_flat_map
     {
       struct map_types
@@ -61,13 +61,13 @@ namespace boost {
 
       using table_type = detail::foa::table<map_types, Hash, KeyEqual,
         typename boost::allocator_rebind<Allocator,
-          typename map_types::value_type>::type>;
+          typename map_types::value_type>::type, MixPolicy>;
 
       table_type table_;
 
-      template <class K, class V, class H, class KE, class A, class Pred>
-      typename unordered_flat_map<K, V, H, KE, A>::size_type friend erase_if(
-        unordered_flat_map<K, V, H, KE, A>& set, Pred pred);
+      template <class K, class V, class H, class KE, class A, class MP, class Pred>
+      typename unordered_flat_map<K, V, H, KE, A, MP>::size_type friend erase_if(
+        unordered_flat_map<K, V, H, KE, A, MP>& set, Pred pred);
 
     public:
       using key_type = Key;
@@ -387,7 +387,7 @@ namespace boost {
 
       template <class H2, class P2>
       void merge(
-        unordered_flat_map<key_type, mapped_type, H2, P2, allocator_type>&
+        unordered_flat_map<key_type, mapped_type, H2, P2, allocator_type, MixPolicy>&
           source)
       {
         table_.merge(source.table_);
@@ -395,7 +395,7 @@ namespace boost {
 
       template <class H2, class P2>
       void merge(
-        unordered_flat_map<key_type, mapped_type, H2, P2, allocator_type>&&
+        unordered_flat_map<key_type, mapped_type, H2, P2, allocator_type, MixPolicy>&&
           source)
       {
         table_.merge(std::move(source.table_));
@@ -579,10 +579,10 @@ namespace boost {
       key_equal key_eq() const { return table_.key_eq(); }
     };
 
-    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator, class MixPolicy>
     bool operator==(
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& lhs,
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& rhs)
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy> const& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy> const& rhs)
     {
       if (&lhs == &rhs) {
         return true;
@@ -599,27 +599,27 @@ namespace boost {
       })();
     }
 
-    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator, class MixPolicy>
     bool operator!=(
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& lhs,
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& rhs)
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy> const& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy> const& rhs)
     {
       return !(lhs == rhs);
     }
 
-    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
-    void swap(unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>& lhs,
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>& rhs)
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator, class MixPolicy>
+    void swap(unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy>& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy>& rhs)
       noexcept(noexcept(lhs.swap(rhs)))
     {
       lhs.swap(rhs);
     }
 
-    template <class Key, class T, class Hash, class KeyEqual, class Allocator,
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator, class MixPolicy,
       class Pred>
-    typename unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>::size_type
+    typename unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy>::size_type
     erase_if(
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>& map, Pred pred)
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy>& map, Pred pred)
     {
       return erase_if(map.table_, pred);
     }

include/boost/unordered/unordered_flat_map_fwd.hpp

@@ -18,24 +18,28 @@
 
 namespace boost {
   namespace unordered {
+
+    namespace detail { namespace foa { struct xmx_mix; } }
+
     template <class Key, class T, class Hash = boost::hash<Key>,
       class KeyEqual = std::equal_to<Key>,
-      class Allocator = std::allocator<std::pair<const Key, T> > >
+      class Allocator = std::allocator<std::pair<const Key, T> >,
+      class MixPolicy = detail::foa::xmx_mix >
     class unordered_flat_map;
 
-    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator, class MixPolicy>
     bool operator==(
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& lhs,
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& rhs);
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy> const& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy> const& rhs);
 
-    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator, class MixPolicy>
     bool operator!=(
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& lhs,
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& rhs);
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy> const& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy> const& rhs);
 
-    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
-    void swap(unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>& lhs,
-      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>& rhs)
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator, class MixPolicy>
+    void swap(unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy>& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator, MixPolicy>& rhs)
       noexcept(noexcept(lhs.swap(rhs)));
   } // namespace unordered
 

test/exception/assign_exception_tests.cpp

@@ -60,6 +60,9 @@ template <class T> struct assign_base : public test::exception_base
   test::random_values<T> x_values, y_values;
   T x, y;
 
+  int t1;
+  int t2;
+
   typedef typename T::hasher hasher;
   typedef typename T::key_equal key_equal;
   typedef typename T::allocator_type allocator_type;
@@ -67,7 +70,10 @@ template <class T> struct assign_base : public test::exception_base
   assign_base(int tag1, int tag2, float mlf1 = 1.0, float mlf2 = 1.0)
       : x_values(), y_values(),
         x(0, hasher(tag1), key_equal(tag1), allocator_type(tag1)),
-        y(0, hasher(tag2), key_equal(tag2), allocator_type(tag2))
+        y(0, hasher(tag2), key_equal(tag2), allocator_type(tag2)),
+        t1(tag1),
+        t2(tag2)
+
   {
     x.max_load_factor(mlf1);
     y.max_load_factor(mlf2);
@@ -89,6 +95,22 @@ template <class T> struct assign_base : public test::exception_base
   {
     test::check_equivalent_keys(x1);
 
+    if (x1.hash_function() == hasher(t1)) {
+      BOOST_TEST(x1.key_eq() == key_equal(t1));
+    }
+
+    if (x1.hash_function() == hasher(t2)) {
+      BOOST_TEST(x1.key_eq() == key_equal(t2));
+    }
+
+    if (x1.key_eq() == key_equal(t1)) {
+      BOOST_TEST(x1.hash_function() == hasher(t1));
+    }
+
+    if (x1.key_eq() == key_equal(t2)) {
+      BOOST_TEST(x1.hash_function() == hasher(t2));
+    }
+
     // If the container is empty at the point of the exception, the
     // internal structure is hidden, this exposes it, at the cost of
     // messing up the data.

test/exception/move_assign_exception_tests.cpp

@@ -20,6 +20,7 @@ template <class T> struct move_assign_base : public test::exception_base
 {
   test::random_values<T> x_values, y_values;
   T x, y;
+  int t1, t2;
 
   typedef typename T::hasher hasher;
   typedef typename T::key_equal key_equal;
@@ -28,7 +29,9 @@ template <class T> struct move_assign_base : public test::exception_base
   move_assign_base(int tag1, int tag2, float mlf1 = 1.0, float mlf2 = 1.0)
       : x_values(), y_values(),
         x(0, hasher(tag1), key_equal(tag1), allocator_type(tag1)),
-        y(0, hasher(tag2), key_equal(tag2), allocator_type(tag2))
+        y(0, hasher(tag2), key_equal(tag2), allocator_type(tag2)),
+        t1(tag1),
+        t2(tag2)
   {
     x.max_load_factor(mlf1);
     y.max_load_factor(mlf2);
@@ -52,6 +55,22 @@ template <class T> struct move_assign_base : public test::exception_base
   {
     test::check_equivalent_keys(x1);
 
+    if (x1.hash_function() == hasher(t1)) {
+      BOOST_TEST(x1.key_eq() == key_equal(t1));
+    }
+
+    if (x1.hash_function() == hasher(t2)) {
+      BOOST_TEST(x1.key_eq() == key_equal(t2));
+    }
+
+    if (x1.key_eq() == key_equal(t1)) {
+      BOOST_TEST(x1.hash_function() == hasher(t1));
+    }
+
+    if (x1.key_eq() == key_equal(t2)) {
+      BOOST_TEST(x1.hash_function() == hasher(t2));
+    }
+
     // If the container is empty at the point of the exception, the
     // internal structure is hidden, this exposes it, at the cost of
     // messing up the data.

test/exception/swap_exception_tests.cpp

@@ -4,15 +4,40 @@
 // 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 "./containers.hpp"
+#define BOOST_ENABLE_ASSERT_HANDLER
+#include <boost/assert.hpp>
 
-#if defined(BOOST_UNORDERED_FOA_TESTS)
-#define BOOST_UNORDERED_FOA_WEAK_GUARANTEE_SWAP_EXCEPTIONS_TESTS
-#endif
+#include "./containers.hpp"
 
 #include "../helpers/invariants.hpp"
 #include "../helpers/random_values.hpp"
 #include "../helpers/tracker.hpp"
+#include "../objects/test.hpp"
+
+#include <sstream>
+
+namespace boost {
+  void assertion_failed(
+    char const* expr, char const* function, char const* file, long line)
+  {
+    std::stringstream ss;
+    ss << expr << "\nin " << function << " failed at : " << file << ", line "
+       << line;
+
+    throw std::runtime_error(ss.str());
+  }
+
+  void assertion_failed_msg(char const* expr, char const* msg,
+    char const* function, char const* file, long line)
+  {
+    std::stringstream ss;
+    ss << expr << "\nin " << function << " failed at : " << file << ", line "
+       << line << "\n"
+       << msg;
+
+    throw std::runtime_error(ss.str());
+  }
+} // namespace boost
 
 #if defined(BOOST_MSVC)
 #pragma warning(disable : 4512) // assignment operator could not be generated
@@ -39,15 +64,10 @@ template <class T> struct self_swap_base : public test::exception_base
 
   void check BOOST_PREVENT_MACRO_SUBSTITUTION(T const& x) const
   {
-    std::string scope(test::scope);
+    (void)x;
 
-    // TODO: In C++11 exceptions are only allowed in the swap function.
-    BOOST_TEST(scope == "hash::hash(hash)" ||
-               scope == "hash::operator=(hash)" ||
-               scope == "equal_to::equal_to(equal_to)" ||
-               scope == "equal_to::operator=(equal_to)");
-
-    test::check_equivalent_keys(x);
+    BOOST_ERROR("An exception leaked when it should not have. Allocator "
+                "equality assertion must precede all other ops");
   }
 };
 
@@ -140,11 +160,133 @@ template <class T> struct swap_test4 : swap_base<T>
   swap_test4() : swap_base<T>(10, 10, 1, 2) {}
 };
 
+template <class T> struct unequal_alloc_swap_base : public test::exception_base
+{
+  const test::random_values<T> x_values, y_values;
+  const T initial_x, initial_y;
+
+  typedef typename T::hasher hasher;
+  typedef typename T::key_equal key_equal;
+  typedef typename T::allocator_type allocator_type;
+
+  unequal_alloc_swap_base(unsigned int count1, unsigned int count2)
+      : x_values(count1, test::limited_range),
+        y_values(count2, test::limited_range),
+        initial_x(x_values.begin(), x_values.end(), 0, allocator_type(1337)),
+        initial_y(y_values.begin(), y_values.end(), 0, allocator_type(7331))
+  {
+  }
+
+  struct data_type
+  {
+    data_type(T const& x_, T const& y_) : x(x_), y(y_) {}
+
+    T x, y;
+  };
+
+  data_type init() const { return data_type(initial_x, initial_y); }
+
+  void run(data_type& d) const
+  {
+    bool assert_threw = false;
+
+    BOOST_TEST(d.x.get_allocator() != d.y.get_allocator());
+
+    try {
+      d.x.swap(d.y);
+    } catch (std::runtime_error&) {
+      assert_threw = true;
+    }
+
+    DISABLE_EXCEPTIONS;
+    BOOST_TEST(assert_threw);
+    test::check_container(d.x, this->x_values);
+    test::check_equivalent_keys(d.x);
+    test::check_container(d.y, this->y_values);
+    test::check_equivalent_keys(d.y);
+  }
+
+  void check BOOST_PREVENT_MACRO_SUBSTITUTION(data_type const& d) const
+  {
+    std::string scope(test::scope);
+
+    // TODO: In C++11 exceptions are only allowed in the swap function.
+    BOOST_TEST(scope == "hash::hash(hash)" ||
+               scope == "hash::operator=(hash)" ||
+               scope == "equal_to::equal_to(equal_to)" ||
+               scope == "equal_to::operator=(equal_to)");
+
+    test::check_equivalent_keys(d.x);
+    test::check_equivalent_keys(d.y);
+  }
+};
+
+template <class T> struct unequal_alloc_swap_test1 : unequal_alloc_swap_base<T>
+{
+  unequal_alloc_swap_test1() : unequal_alloc_swap_base<T>(0, 0) {}
+};
+
+template <class T> struct unequal_alloc_swap_test2 : unequal_alloc_swap_base<T>
+{
+  unequal_alloc_swap_test2() : unequal_alloc_swap_base<T>(0, 10) {}
+};
+
+template <class T> struct unequal_alloc_swap_test3 : unequal_alloc_swap_base<T>
+{
+  unequal_alloc_swap_test3() : unequal_alloc_swap_base<T>(10, 0) {}
+};
+
+template <class T> struct unequal_alloc_swap_test4 : unequal_alloc_swap_base<T>
+{
+  unequal_alloc_swap_test4() : unequal_alloc_swap_base<T>(10, 10) {}
+};
+
+#if defined(BOOST_UNORDERED_FOA_TESTS)
+
+using unordered_flat_set = boost::unordered_flat_set<int, boost::hash<int>,
+  std::equal_to<int>, test::allocator1<int> >;
+using unordered_flat_map = boost::unordered_flat_map<int, int, boost::hash<int>,
+  std::equal_to<int>, test::allocator1<std::pair<int const, int> > >;
+
+#define SWAP_CONTAINER_SEQ (unordered_flat_set)(unordered_flat_map)
+
+#else
+
+typedef boost::unordered_set<int, boost::hash<int>, std::equal_to<int>,
+  test::allocator1<int> >
+  unordered_set;
+typedef boost::unordered_map<int, int, boost::hash<int>, std::equal_to<int>,
+  test::allocator1<std::pair<int const, int> > >
+  unordered_map;
+typedef boost::unordered_multiset<int, boost::hash<int>, std::equal_to<int>,
+  test::allocator1<int> >
+  unordered_multiset;
+typedef boost::unordered_multimap<int, int, boost::hash<int>,
+  std::equal_to<int>, test::allocator1<std::pair<int const, int> > >
+  unordered_multimap;
+
+#define SWAP_CONTAINER_SEQ                                                     \
+  (unordered_set)(unordered_map)(unordered_multiset)(unordered_multimap)
+#endif
+
+// FOA containers deliberately choose to not offer the strong exception
+// guarantee so we can't reliably test what happens if swapping one of the data
+// members throws
+//
 // clang-format off
+#if !defined(BOOST_UNORDERED_FOA_TESTS)
 EXCEPTION_TESTS(
   (self_swap_test1)(self_swap_test2)
   (swap_test1)(swap_test2)(swap_test3)(swap_test4),
   CONTAINER_SEQ)
+#endif
+
+// want to prove that when assertions are defined as throwing operations that we
+// uphold invariants
+EXCEPTION_TESTS(
+  (unequal_alloc_swap_test1)(unequal_alloc_swap_test2)
+  (unequal_alloc_swap_test3)(unequal_alloc_swap_test4),
+  SWAP_CONTAINER_SEQ)
 // clang-format on
 
 RUN_TESTS()

test/helpers/invariants.hpp

@@ -54,20 +54,10 @@ namespace test {
       if (test::has_unique_keys<X>::value && count != 1)
         BOOST_ERROR("Non-unique key.");
 
-#if !defined(BOOST_UNORDERED_FOA_WEAK_GUARANTEE_SWAP_EXCEPTIONS_TESTS)
-      // we conditionally compile this check because our FOA implementation only
-      // exhibits the weak guarantee when swapping throws
-      //
-      // in this case, the hasher may be changed before the predicate and the
-      // arrays are swapped in which case, we can can find an element by
-      // iteration but unfortunately, it's in the wrong slot according to the
-      // new hash function so count(key) can wind up returning nothing when
-      // there really is something
       if (x1.count(key) != count) {
         BOOST_ERROR("Incorrect output of count.");
         std::cerr << x1.count(key) << "," << count << "\n";
       }
-#endif
 
 #ifndef BOOST_UNORDERED_FOA_TESTS
       // Check that the keys are in the correct bucket and are

test/objects/exception.hpp

@@ -227,8 +227,21 @@ namespace test {
         }
         return x1.tag_ != x2.tag_;
       }
+
+#if defined(BOOST_UNORDERED_FOA_TESTS)
+      friend void swap(hash&, hash&) noexcept;
+#endif
     };
 
+#if defined(BOOST_UNORDERED_FOA_TESTS)
+      void swap(hash& lhs, hash& rhs) noexcept
+      {
+        int tag = lhs.tag_;
+        lhs.tag_ = rhs.tag_;
+        rhs.tag_ = tag;
+      }
+#endif
+
     class less
     {
       int tag_;
@@ -364,8 +377,20 @@ namespace test {
       }
 
       friend less create_compare(equal_to x) { return less(x.tag_); }
+#if defined(BOOST_UNORDERED_FOA_TESTS)
+      friend void swap(equal_to&, equal_to&) noexcept;
+#endif
     };
 
+#if defined(BOOST_UNORDERED_FOA_TESTS)
+    void swap(equal_to& lhs, equal_to& rhs) noexcept
+    {
+      int tag = lhs.tag_;
+      lhs.tag_ = rhs.tag_;
+      rhs.tag_ = tag;
+    }
+#endif
+
     template <class T> class allocator
     {
     public:

test/objects/minimal.hpp

@@ -206,6 +206,11 @@ namespace test {
       hash& operator=(hash const&) { return *this; }
       ~hash() {}
 
+#if defined(BOOST_UNORDERED_FOA_TESTS)
+      hash(hash&&) = default;
+      hash& operator=(hash&&) = default;
+#endif
+
       std::size_t operator()(T const&) const { return 0; }
 #if BOOST_UNORDERED_CHECK_ADDR_OPERATOR_NOT_USED
       ampersand_operator_used operator&() const
@@ -224,6 +229,11 @@ namespace test {
       equal_to& operator=(equal_to const&) { return *this; }
       ~equal_to() {}
 
+#if defined(BOOST_UNORDERED_FOA_TESTS)
+      equal_to(equal_to&&) = default;
+      equal_to& operator=(equal_to&&) = default;
+#endif
+
       bool operator()(T const&, T const&) const { return true; }
 #if BOOST_UNORDERED_CHECK_ADDR_OPERATOR_NOT_USED
       ampersand_operator_used operator&() const

test/objects/test.hpp

@@ -230,18 +230,18 @@ namespace test {
 
     std::size_t operator()(int x) const
     {
-      int result;
+      unsigned result;
       switch (type_) {
       case 1:
-        result = x;
+        result = static_cast<unsigned>(x);
         break;
       case 2:
-        result = x * 7;
+        result = static_cast<unsigned>(x) * 7;
         break;
       default:
-        result = x * 256;
+        result = static_cast<unsigned>(x) * 256;
       }
-      return static_cast<std::size_t>(result);
+      return result;
     }
 
     friend bool operator==(hash const& x1, hash const& x2)

test/unordered/copy_tests.cpp

@@ -225,11 +225,227 @@ namespace copy_tests {
     }
   }
 
+  template <class T>
+  void copy_construct_tests_std_allocator1(
+    T*, test::random_generator const& generator)
+  {
+    typename T::hasher hf;
+    typename T::key_equal eq;
+    typename T::allocator_type al;
+
+    {
+      test::check_instances check_;
+
+      T x;
+      T y(x);
+      BOOST_TEST(y.empty());
+      BOOST_TEST(test::equivalent(y.hash_function(), hf));
+      BOOST_TEST(test::equivalent(y.key_eq(), eq));
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+      BOOST_TEST(x.max_load_factor() == y.max_load_factor());
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
+      test::check_equivalent_keys(y);
+    }
+
+    {
+      test::check_instances check_;
+
+      T x(0);
+      T y(x);
+      BOOST_TEST(y.empty());
+      BOOST_TEST(test::equivalent(y.hash_function(), hf));
+      BOOST_TEST(test::equivalent(y.key_eq(), eq));
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+      BOOST_TEST(x.max_load_factor() == y.max_load_factor());
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
+      test::check_equivalent_keys(y);
+    }
+
+    {
+      test::check_instances check_;
+
+      test::random_values<T> v(1000, generator);
+
+      T x(v.begin(), v.end());
+      T y(x);
+      test::unordered_equivalence_tester<T> equivalent(x);
+      BOOST_TEST(equivalent(y));
+      test::check_equivalent_keys(y);
+    }
+
+    {
+      test::check_instances check_;
+
+      // In this test I drop the original containers max load factor, so it
+      // is much lower than the load factor. The hash table is not allowed
+      // to rehash, but the destination container should probably allocate
+      // enough buckets to decrease the load factor appropriately.
+      test::random_values<T> v(1000, generator);
+      T x(v.begin(), v.end());
+      x.max_load_factor(x.load_factor() / 4);
+      T y(x);
+      test::unordered_equivalence_tester<T> equivalent(x);
+      BOOST_TEST(equivalent(y));
+      // This isn't guaranteed:
+      BOOST_TEST(y.load_factor() < y.max_load_factor());
+      test::check_equivalent_keys(y);
+    }
+  }
+
+  template <class T>
+  void copy_construct_tests_std_allocator2(
+    T*, test::random_generator const& generator)
+  {
+    typename T::hasher hf(1);
+    typename T::key_equal eq(1);
+    typename T::allocator_type al;
+
+    {
+      test::check_instances check_;
+
+      T x(0, hf, eq, al);
+      T y(x);
+      BOOST_TEST(y.empty());
+      BOOST_TEST(test::equivalent(y.hash_function(), hf));
+      BOOST_TEST(test::equivalent(y.key_eq(), eq));
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+      BOOST_TEST(x.max_load_factor() == y.max_load_factor());
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
+      test::check_equivalent_keys(y);
+    }
+
+    {
+      test::check_instances check_;
+
+      T x(10000, hf, eq, al);
+      T y(x);
+      BOOST_TEST(y.empty());
+      BOOST_TEST(test::equivalent(y.hash_function(), hf));
+      BOOST_TEST(test::equivalent(y.key_eq(), eq));
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+      BOOST_TEST(x.max_load_factor() == y.max_load_factor());
+      test::check_equivalent_keys(y);
+    }
+
+    {
+      test::check_instances check_;
+
+      T x(0, hf, eq, al);
+      T y(x, al);
+      BOOST_TEST(y.empty());
+      BOOST_TEST(test::equivalent(y.hash_function(), hf));
+      BOOST_TEST(test::equivalent(y.key_eq(), eq));
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+      BOOST_TEST(x.max_load_factor() == y.max_load_factor());
+      BOOST_TEST(test::selected_count(y.get_allocator()) == 0);
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
+      test::check_equivalent_keys(y);
+    }
+
+    {
+      test::check_instances check_;
+
+      T x(1000, hf, eq, al);
+      T y(x, al);
+      BOOST_TEST(y.empty());
+      BOOST_TEST(test::equivalent(y.hash_function(), hf));
+      BOOST_TEST(test::equivalent(y.key_eq(), eq));
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+      BOOST_TEST(x.max_load_factor() == y.max_load_factor());
+      BOOST_TEST(test::selected_count(y.get_allocator()) == 0);
+      test::check_equivalent_keys(y);
+    }
+
+    {
+      test::check_instances check_;
+
+      test::random_values<T> v;
+
+      T x(v.begin(), v.end(), 0, hf, eq, al);
+      T y(x);
+      test::unordered_equivalence_tester<T> equivalent(x);
+      BOOST_TEST(equivalent(y));
+      test::check_equivalent_keys(y);
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
+    }
+
+    {
+      test::check_instances check_;
+
+      test::random_values<T> v(1000, generator);
+
+      T x(v.begin(), v.end(), 0, hf, eq, al);
+      T y(x);
+      test::unordered_equivalence_tester<T> equivalent(x);
+      BOOST_TEST(equivalent(y));
+      test::check_equivalent_keys(y);
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+    }
+
+    {
+      test::check_instances check_;
+
+      test::random_values<T> v;
+
+      T x(v.begin(), v.end(), 0, hf, eq, al);
+      T y(x, al);
+      test::unordered_equivalence_tester<T> equivalent(x);
+      BOOST_TEST(equivalent(y));
+      test::check_equivalent_keys(y);
+      BOOST_TEST(test::selected_count(y.get_allocator()) == 0);
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
+    }
+
+    {
+      test::check_instances check_;
+
+      test::random_values<T> v(500, generator);
+
+      T x(v.begin(), v.end(), 0, hf, eq, al);
+      T y(x, al);
+      test::unordered_equivalence_tester<T> equivalent(x);
+      BOOST_TEST(equivalent(y));
+      test::check_equivalent_keys(y);
+      BOOST_TEST(test::selected_count(y.get_allocator()) == 0);
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+    }
+  }
+
   using test::default_generator;
   using test::generate_collisions;
   using test::limited_range;
 
 #ifdef BOOST_UNORDERED_FOA_TESTS
+  template <class T> struct allocator
+  {
+    using value_type = T;
+
+    allocator() = default;
+    allocator(allocator const&) = default;
+    allocator(allocator&&) = default;
+
+    template <class U> allocator(allocator<U> const&) {}
+
+    T* allocate(std::size_t n)
+    {
+      return static_cast<T*>(::operator new(sizeof(value_type) * n));
+    }
+
+    void deallocate(T* p, std::size_t) { ::operator delete(p); }
+
+    friend inline bool operator==(allocator const&, allocator const&)
+    {
+      return true;
+    }
+
+    friend inline bool operator!=(allocator const&, allocator const&)
+    {
+      return false;
+    }
+  };
+
   boost::unordered_flat_set<test::object, test::hash, test::equal_to,
     test::allocator1<test::object> >* test_set;
   boost::unordered_flat_map<test::object, test::object, test::hash,
@@ -249,13 +465,50 @@ namespace copy_tests {
     test::equal_to, test::cxx11_allocator<test::object, test::no_select_copy> >*
     test_map_no_select_copy;
 
+  boost::unordered_flat_set<int, test::hash, test::equal_to,
+    test::allocator1<int> >* test_set_trivially_copyable;
+  boost::unordered_flat_map<int, int, test::hash, test::equal_to,
+    test::allocator1<std::pair<int const, int> > >* test_map_trivially_copyable;
+
+  boost::unordered_flat_set<int, test::hash, test::equal_to,
+    std::allocator<int> >* test_set_trivially_copyable_std_allocator;
+  boost::unordered_flat_map<int, int, test::hash, test::equal_to,
+    std::allocator<std::pair<int const, int> > >*
+    test_map_trivially_copyable_std_allocator;
+
+  boost::unordered_flat_set<int, test::hash, test::equal_to, allocator<int> >*
+    test_set_trivially_copyable_no_construct;
+  boost::unordered_flat_map<int, int, test::hash, test::equal_to,
+    allocator<std::pair<int const, int> > >*
+    test_map_trivially_copyable_no_construct;
+
+  // clang-format off
   UNORDERED_TEST(copy_construct_tests1,
-    ((test_set)(test_map)(test_set_select_copy)(test_map_select_copy)(test_set_no_select_copy)(test_map_no_select_copy))(
-      (default_generator)(generate_collisions)(limited_range)))
+    ((test_set)(test_map)(test_set_select_copy)(test_map_select_copy)
+     (test_set_no_select_copy)(test_map_no_select_copy)
+     (test_set_trivially_copyable)(test_map_trivially_copyable))
+    ((default_generator)(generate_collisions)(limited_range)))
 
   UNORDERED_TEST(copy_construct_tests2,
-    ((test_set)(test_map)(test_set_select_copy)(test_map_select_copy)(test_set_no_select_copy)(test_map_no_select_copy))(
-      (default_generator)(generate_collisions)(limited_range)))
+    ((test_set)(test_map)(test_set_select_copy)(test_map_select_copy)
+     (test_set_no_select_copy)(test_map_no_select_copy)
+     (test_set_trivially_copyable)(test_map_trivially_copyable))
+    ((default_generator)(generate_collisions)(limited_range)))
+
+  UNORDERED_TEST(copy_construct_tests_std_allocator1,
+    ((test_set_trivially_copyable_std_allocator)
+     (test_map_trivially_copyable_std_allocator)
+     (test_set_trivially_copyable_no_construct)
+     (test_map_trivially_copyable_no_construct))
+    ((default_generator)(generate_collisions)(limited_range)))
+
+  UNORDERED_TEST(copy_construct_tests_std_allocator2,
+    ((test_set_trivially_copyable_std_allocator)
+     (test_map_trivially_copyable_std_allocator)
+     (test_set_trivially_copyable_no_construct)
+     (test_map_trivially_copyable_no_construct))
+    ((default_generator)(generate_collisions)(limited_range)))
+  // clang-format on
 #else
   boost::unordered_set<test::object, test::hash, test::equal_to,
     test::allocator1<test::object> >* test_set;

test/unordered/noexcept_tests.cpp

@@ -437,13 +437,11 @@ UNORDERED_AUTO_TEST (prelim_allocator_checks) {
 using test::default_generator;
 
 #ifdef BOOST_UNORDERED_FOA_TESTS
-boost::unordered_flat_set<int, noexcept_tests::hash_nothrow_move_assign,
-  noexcept_tests::equal_to_nothrow_move_assign, allocator1<int> >*
-  throwing_set_alloc1;
+boost::unordered_flat_set<int, noexcept_tests::hash_nothrow_swap,
+  noexcept_tests::equal_to_nothrow_swap, allocator1<int> >* throwing_set_alloc1;
 
-boost::unordered_flat_set<int, noexcept_tests::hash_nothrow_move_assign,
-  noexcept_tests::equal_to_nothrow_move_assign, allocator2<int> >*
-  throwing_set_alloc2;
+boost::unordered_flat_set<int, noexcept_tests::hash_nothrow_swap,
+  noexcept_tests::equal_to_nothrow_swap, allocator2<int> >* throwing_set_alloc2;
 
 UNORDERED_TEST(test_nothrow_move_assign_when_noexcept,
   ((throwing_set_alloc1)(throwing_set_alloc2))((default_generator)))