Merge branch 'develop' into feature/mixing-policy

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";
     }
 }
 

include/boost/unordered/detail/foa.hpp

@@ -24,6 +24,7 @@
 #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>
@@ -768,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.
  */
@@ -784,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:
@@ -848,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},
@@ -1153,7 +1190,7 @@ _STL_RESTORE_DEPRECATED_WARNING
  */
 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
@@ -1173,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>;
 
@@ -1556,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

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