Merge pull request #146 from cmazakas/feature/rehash-doc-updates

Rehash Doc Updates

.appveyor.yml

@@ -40,52 +40,11 @@ environment:
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2015
       B2_TOOLSET: msvc-12.0,msvc-14.0
 
-    - FLAVOR: Visual Studio 2017 C++14/17
+    - FLAVOR: Visual Studio 2017
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
-      B2_CXXSTD: 14,17
+      B2_CXXSTD: 14,17,latest
       B2_TOOLSET: msvc-14.1
 
-    - FLAVOR: Visual Studio 2017 C++2a Strict
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
-      B2_CXXFLAGS: -permissive-
-      B2_CXXSTD: 2a
-      B2_TOOLSET: msvc-14.1
-
-    - FLAVOR: Visual Studio 2019
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      B2_CXXFLAGS: -permissive-
-      B2_CXXSTD: 14,17
-      B2_TOOLSET: msvc-14.2
-
-    - FLAVOR: Visual Studio 2022
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
-      B2_CXXFLAGS: -permissive-
-      B2_CXXSTD: 14,17
-      B2_TOOLSET: msvc-14.3
-
-    # C++20 Jobs split out from above due to build timeout
-    - FLAVOR: Visual Studio 2019 C++2a
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      B2_CXXFLAGS: -permissive-
-      B2_CXXSTD: 2a
-      B2_TOOLSET: msvc-14.2
-
-    - FLAVOR: Visual Studio 2022 C++20
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
-      B2_CXXFLAGS: -permissive-
-      B2_CXXSTD: 20
-      B2_TOOLSET: msvc-14.3
-
-    - FLAVOR: clang-cl C++11, C++14
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      B2_CXXSTD: 11,14
-      B2_TOOLSET: clang-win
-    # Extra job as compilation takes to long
-    - FLAVOR: clang-cl C++17, C++latest
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      B2_CXXSTD: 17,latest
-      B2_TOOLSET: clang-win
-
     - FLAVOR: cygwin (32-bit)
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
       ADDPATH: C:\cygwin\bin;
@@ -100,30 +59,42 @@ environment:
       B2_CXXSTD: 03,11,14,1z
       B2_TOOLSET: gcc
 
-    # (Currently) the images up to 2017 use an older Cygwin
-    # This tests that the library works with more recent versions
     - FLAVOR: cygwin (64-bit, latest)
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
       ADDPATH: C:\cygwin64\bin;
       B2_ADDRESS_MODEL: 64
-      B2_CXXSTD: 03,11,14,1z
+      B2_CXXSTD: 03,11
       B2_TOOLSET: gcc
-      MAYFAIL: true
+      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
 
-    - FLAVOR: mingw32
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2015
-      B2_ADDRESS_MODEL: 32
-      ADDPATH: C:\mingw\bin;
-      B2_CXXSTD: 03,11,14,1z
-      B2_TOOLSET: gcc
-      MAYFAIL: true
-
-    - FLAVOR: mingw64
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
+    - FLAVOR: cygwin (64-bit, latest)
+      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
+      ADDPATH: C:\cygwin64\bin;
       B2_ADDRESS_MODEL: 64
+      B2_CXXSTD: 14,1z
+      B2_TOOLSET: gcc
+      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
+
+    - FLAVOR: mingw-w64, 32 bit
+      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
+      ADDPATH: C:\mingw-w64\i686-8.1.0-posix-dwarf-rt_v6-rev0\mingw32\bin;
       B2_CXXSTD: 03,11,14,17,2a
       B2_TOOLSET: gcc
+      B2_ADDRESS_MODEL: 32
+
+    - FLAVOR: mingw-w64, 64 bit
+      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
+      ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
+      B2_CXXSTD: 03,11,14
+      B2_TOOLSET: gcc
+      B2_ADDRESS_MODEL: 64
+
+    - FLAVOR: mingw-w64, 64 bit
+      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
+      ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
+      B2_CXXSTD: 17,2a
+      B2_TOOLSET: gcc
+      B2_ADDRESS_MODEL: 64
 
     #- FLAVOR: CodeCov (VS 2019)
     #  APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019

.drone.jsonnet

@@ -0,0 +1,184 @@
+# Copyright 2022 Peter Dimov
+# Distributed under the Boost Software License, Version 1.0.
+# https://www.boost.org/LICENSE_1_0.txt
+
+local library = "unordered";
+
+local triggers =
+{
+    branch: [ "master", "develop", "feature/*", "bugfix/*" ]
+};
+
+local ubsan = { UBSAN: '1', UBSAN_OPTIONS: 'print_stacktrace=1' };
+local asan = { ASAN: '1' };
+
+local linux_pipeline(name, image, environment, packages = "", sources = [], arch = "amd64") =
+{
+    name: name,
+    kind: "pipeline",
+    type: "docker",
+    trigger: triggers,
+    platform:
+    {
+        os: "linux",
+        arch: arch
+    },
+    steps:
+    [
+        {
+            name: "everything",
+            image: image,
+            environment: environment,
+            commands:
+            [
+                'set -e',
+                'uname -a',
+                'wget -O - https://apt.llvm.org/llvm-snapshot.gpg.key | apt-key add -',
+            ] +
+            (if sources != [] then [ ('apt-add-repository "' + source + '"') for source in sources ] else []) +
+            (if packages != "" then [ 'apt-get update', 'apt-get -y install ' + packages ] else []) +
+            [
+                'export LIBRARY=' + library,
+                './.drone/drone.sh',
+            ]
+        }
+    ]
+};
+
+local macos_pipeline(name, environment, xcode_version = "12.2", osx_version = "catalina", arch = "amd64") =
+{
+    name: name,
+    kind: "pipeline",
+    type: "exec",
+    trigger: triggers,
+    platform: {
+        "os": "darwin",
+        "arch": arch
+    },
+    node: {
+        "os": osx_version
+    },
+    steps: [
+        {
+            name: "everything",
+            environment: environment + { "DEVELOPER_DIR": "/Applications/Xcode-" + xcode_version + ".app/Contents/Developer" },
+            commands:
+            [
+                'uname -a',
+                'export LIBRARY=' + library,
+                './.drone/drone.sh',
+            ]
+        }
+    ]
+};
+
+local windows_pipeline(name, image, environment, arch = "amd64") =
+{
+    name: name,
+    kind: "pipeline",
+    type: "docker",
+    trigger: triggers,
+    platform:
+    {
+        os: "windows",
+        arch: arch
+    },
+    "steps":
+    [
+        {
+            name: "everything",
+            image: image,
+            environment: environment,
+            commands:
+            [
+                'echo $env:DRONE_STAGE_MACHINE',
+                'cmd /C .drone\\\\drone.bat ' + library,
+            ]
+        }
+    ]
+};
+
+[
+    linux_pipeline(
+        "Linux 14.04 GCC 4.4 32/64",
+        "cppalliance/droneubuntu1404:1",
+        { TOOLSET: 'gcc', COMPILER: 'g++-4.4', CXXSTD: '98,0x', ADDRMD: '32,64' },
+        "g++-4.4-multilib",
+        [ "ppa:ubuntu-toolchain-r/test" ],
+    ),
+
+    linux_pipeline(
+        "Linux 14.04 GCC 4.6 32/64",
+        "cppalliance/droneubuntu1404:1",
+        { TOOLSET: 'gcc', COMPILER: 'g++-4.6', CXXSTD: '98,0x', ADDRMD: '32,64' },
+        "g++-4.6-multilib",
+        [ "ppa:ubuntu-toolchain-r/test" ],
+    ),
+
+    linux_pipeline(
+        "Linux 14.04 GCC 4.7 32/64",
+        "cppalliance/droneubuntu1404:1",
+        { TOOLSET: 'gcc', COMPILER: 'g++-4.7', CXXSTD: '98,0x', ADDRMD: '32,64' },
+        "g++-4.7-multilib",
+        [ "ppa:ubuntu-toolchain-r/test" ],
+    ),
+
+    linux_pipeline(
+        "Linux 14.04 GCC 4.8* 32/64",
+        "cppalliance/droneubuntu1404:1",
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11', ADDRMD: '32,64' },
+    ),
+
+    linux_pipeline(
+        "Linux 14.04 GCC 4.9 32/64",
+        "cppalliance/droneubuntu1404:1",
+        { TOOLSET: 'gcc', COMPILER: 'g++-4.9', CXXSTD: '03,11', ADDRMD: '32,64' },
+        "g++-4.9-multilib",
+        [ "ppa:ubuntu-toolchain-r/test" ],
+    ),
+
+    linux_pipeline(
+        "Linux 20.04 GCC 9* ARM64 32",
+        "cppalliance/droneubuntu2004:multiarch",
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32' },
+        arch="arm64",
+    ),
+
+    linux_pipeline(
+        "Linux 20.04 GCC 9* ARM64 64",
+        "cppalliance/droneubuntu2004:multiarch",
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '64' },
+        arch="arm64",
+    ),
+
+    linux_pipeline(
+        "Linux 20.04 GCC 9* S390x 32",
+        "cppalliance/droneubuntu2004:multiarch",
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32' },
+        arch="s390x",
+    ),
+
+    linux_pipeline(
+        "Linux 20.04 GCC 9* S390x 64",
+        "cppalliance/droneubuntu2004:multiarch",
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '64' },
+        arch="s390x",
+    ),
+
+    macos_pipeline(
+        "MacOS 10.15 Xcode 12.2 UBSAN",
+        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11,14,1z' } + ubsan,
+    ),
+
+    macos_pipeline(
+        "MacOS 12.4 Xcode 13.4.1 ASAN",
+        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11,14,1z' } + asan,
+        xcode_version = "13.4.1", osx_version = "monterey",
+    ),
+
+    windows_pipeline(
+        "Windows VS2017 msvc-14.1",
+        "cppalliance/dronevs2017",
+        { TOOLSET: 'msvc-14.1', CXXSTD: '14,17,latest' },
+    ),
+]

.drone/drone.bat

@@ -0,0 +1,23 @@
+@REM Copyright 2022 Peter Dimov
+@REM Distributed under the Boost Software License, Version 1.0.
+@REM https://www.boost.org/LICENSE_1_0.txt
+
+@ECHO ON
+
+set LIBRARY=%1
+set DRONE_BUILD_DIR=%CD%
+
+set BOOST_BRANCH=develop
+if "%DRONE_BRANCH%" == "master" set BOOST_BRANCH=master
+cd ..
+git clone -b %BOOST_BRANCH% --depth 1 https://github.com/boostorg/boost.git boost-root
+cd boost-root
+git submodule update --init tools/boostdep
+xcopy /s /e /q %DRONE_BUILD_DIR% libs\%LIBRARY%\
+python tools/boostdep/depinst/depinst.py %LIBRARY%
+cmd /c bootstrap
+b2 -d0 headers
+
+if not "%CXXSTD%" == "" set CXXSTD=cxxstd=%CXXSTD%
+if not "%ADDRMD%" == "" set ADDRMD=address-model=%ADDRMD%
+b2 -j3 libs/%LIBRARY%/test toolset=%TOOLSET% %CXXSTD% %ADDRMD% variant=debug,release embed-manifest-via=linker

.drone/drone.sh

@@ -0,0 +1,25 @@
+#!/bin/bash
+
+# Copyright 2022 Peter Dimov
+# Distributed under the Boost Software License, Version 1.0.
+# https://www.boost.org/LICENSE_1_0.txt
+
+set -ex
+export PATH=~/.local/bin:/usr/local/bin:$PATH
+
+DRONE_BUILD_DIR=$(pwd)
+
+BOOST_BRANCH=develop
+if [ "$DRONE_BRANCH" = "master" ]; then BOOST_BRANCH=master; fi
+
+cd ..
+git clone -b $BOOST_BRANCH --depth 1 https://github.com/boostorg/boost.git boost-root
+cd boost-root
+git submodule update --init tools/boostdep
+cp -r $DRONE_BUILD_DIR/* libs/$LIBRARY
+python tools/boostdep/depinst/depinst.py $LIBRARY
+./bootstrap.sh
+./b2 -d0 headers
+
+echo "using $TOOLSET : : $COMPILER ;" > ~/user-config.jam
+./b2 -j3 libs/$LIBRARY/test toolset=$TOOLSET cxxstd=$CXXSTD variant=debug,release ${ADDRMD:+address-model=$ADDRMD} ${UBSAN:+undefined-sanitizer=norecover debug-symbols=on} ${ASAN:+address-sanitizer=norecover debug-symbols=on} ${LINKFLAGS:+linkflags=$LINKFLAGS}

.github/workflows/ci.yml

@@ -42,16 +42,16 @@ jobs:
       matrix:
         include:
           # Linux, gcc
-          - { compiler: gcc-4.8,   cxxstd: '03,11',          os: ubuntu-18.04 }
+          - { compiler: gcc-4.8,   cxxstd: '03,11',          os: ubuntu-18.04, install: 'g++-4.8-multilib', address-model: '32,64' }
           - { compiler: gcc-4.9,   cxxstd: '03,11',          os: ubuntu-20.04, container: 'ubuntu:16.04' }
-          - { compiler: gcc-5,     cxxstd: '03,11,14,1z',    os: ubuntu-18.04 }
-          - { compiler: gcc-6,     cxxstd: '03,11,14,17',    os: ubuntu-18.04 }
-          - { compiler: gcc-7,     cxxstd: '03,11,14,17',    os: ubuntu-18.04 }
-          - { compiler: gcc-8,     cxxstd: '03,11,14,17,2a', os: ubuntu-18.04 }
-          - { compiler: gcc-9,     cxxstd: '03,11,14,17,2a', os: ubuntu-18.04 }
-          - { compiler: gcc-10,    cxxstd: '03,11,14,17,20', os: ubuntu-20.04 }
-          - { compiler: gcc-11,    cxxstd: '03,11,14,17,20', os: ubuntu-20.04 }
-          - { compiler: gcc-12,    cxxstd: '03,11,14,17,20', os: ubuntu-22.04 }
+          - { compiler: gcc-5,     cxxstd: '03,11,14,1z',    os: ubuntu-18.04, install: 'g++-5-multilib', address-model: '32,64' }
+          - { compiler: gcc-6,     cxxstd: '03,11,14,17',    os: ubuntu-18.04, install: 'g++-6-multilib', address-model: '32,64' }
+          - { compiler: gcc-7,     cxxstd: '03,11,14,17',    os: ubuntu-18.04, install: 'g++-7-multilib', address-model: '32,64' }
+          - { compiler: gcc-8,     cxxstd: '03,11,14,17,2a', os: ubuntu-18.04, install: 'g++-8-multilib', address-model: '32,64' }
+          - { compiler: gcc-9,     cxxstd: '03,11,14,17,2a', os: ubuntu-18.04, install: 'g++-9-multilib', address-model: '32,64' }
+          - { compiler: gcc-10,    cxxstd: '03,11,14,17,20', os: ubuntu-20.04, install: 'g++-10-multilib', address-model: '32,64' }
+          - { compiler: gcc-11,    cxxstd: '03,11,14,17,20', os: ubuntu-20.04, install: 'g++-11-multilib', address-model: '32,64' }
+          - { compiler: gcc-12,    cxxstd: '03,11,14,17,20', os: ubuntu-22.04, install: 'g++-12-multilib', address-model: '32,64' }
           - { name: GCC w/ sanitizers, sanitize: yes,
               compiler: gcc-12,    cxxstd: '03,11,14,17,20', os: ubuntu-22.04 }
           - { name: Collect coverage, coverage: yes,
@@ -65,8 +65,7 @@ jobs:
           - { compiler: clang-5.0, cxxstd: '03,11,14,1z',    os: ubuntu-18.04 }
           - { compiler: clang-6.0, cxxstd: '03,11,14,17',    os: ubuntu-18.04 }
           - { compiler: clang-7,   cxxstd: '03,11,14,17',    os: ubuntu-18.04 }
-          # Note: clang-8 does not fully support C++20, so it is not compatible with some libstdc++ versions in this mode
-          - { compiler: clang-8,   cxxstd: '03,11,14,17,2a', os: ubuntu-18.04, install: 'clang-8 g++-7', gcc_toolchain: 7 }
+          - { compiler: clang-8,   cxxstd: '03,11,14,17',    os: ubuntu-18.04 }
           - { compiler: clang-9,   cxxstd: '03,11,14,17,2a', os: ubuntu-20.04 }
           - { compiler: clang-10,  cxxstd: '03,11,14,17,20', os: ubuntu-20.04 }
           - { compiler: clang-11,  cxxstd: '03,11,14,17,20', os: ubuntu-20.04 }
@@ -81,7 +80,7 @@ jobs:
               compiler: clang-12,  cxxstd: '03,11,14,17,20', os: ubuntu-20.04, stdlib: libc++, install: 'clang-12 libc++-12-dev libc++abi-12-dev' }
 
           # OSX, clang
-          - { compiler: clang,     cxxstd: '03,11,14,17,2a', os: macos-10.15, sanitize: yes }
+          - { compiler: clang,     cxxstd: '03,11,14,17,2a', os: macos-11, sanitize: yes }
 
     timeout-minutes: 120
     runs-on: ${{matrix.os}}
@@ -226,11 +225,11 @@ jobs:
       fail-fast: false
       matrix:
         include:
-          - { toolset: msvc-14.0, cxxstd: '14,latest',      addrmd: '32,64', os: windows-2019 }
-          - { toolset: msvc-14.2, cxxstd: '14,17,20',       addrmd: '32,64', os: windows-2019 }
-          - { toolset: msvc-14.3, cxxstd: '14,17,20,latest',addrmd: '32,64', os: windows-2022 }
-          - { toolset: clang-win, cxxstd: '14,17,latest',   addrmd: '32,64', os: windows-2022 }
-          - { toolset: gcc,       cxxstd: '03,11,14,17,2a', addrmd: '64',    os: windows-2019 }
+          - { toolset: msvc-14.0, cxxstd: '14,latest',       addrmd: '32,64', os: windows-2019 }
+          - { toolset: msvc-14.2, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2019 }
+          - { toolset: msvc-14.3, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2022 }
+          - { toolset: clang-win, cxxstd: '14,17,latest',    addrmd: '32,64', os: windows-2022 }
+          - { toolset: gcc,       cxxstd: '03,11,14,17,2a',  addrmd: '64',    os: windows-2019 }
 
     runs-on: ${{matrix.os}}
 

CMakeLists.txt

@@ -18,7 +18,6 @@ target_link_libraries(boost_unordered
     Boost::config
     Boost::container_hash
     Boost::core
-    Boost::iterator
     Boost::move
     Boost::mp11
     Boost::predef

benchmark/string.cpp

@@ -14,6 +14,12 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
+#endif
 #include <unordered_map>
 #include <vector>
 #include <memory>
@@ -137,7 +143,14 @@ template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::s
     {
         if( it->second & 1 )
         {
-            map.erase( it++ );
+            if constexpr( std::is_void_v< decltype( map.erase( it ) ) > )
+            {
+                map.erase( it++ );
+            }
+            else
+            {
+                it = map.erase( it );
+            }
         }
         else
         {
@@ -159,13 +172,9 @@ template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::stead
 
     print_time( t1, "Consecutive erase",  0, map.size() );
 
+    for( unsigned i = 1; i <= N; ++i )
     {
-        boost::detail::splitmix64 rng;
-
-        for( unsigned i = 1; i <= N; ++i )
-        {
-            map.erase( indices2[ i ] );
-        }
+        map.erase( indices2[ i ] );
     }
 
     print_time( t1, "Random erase",  0, map.size() );
@@ -295,6 +304,26 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
+#ifdef HAVE_TSL_HOPSCOTCH
+
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
 // fnv1a_hash
 
 template<int Bits> struct fnv1a_hash_impl;
@@ -363,6 +392,26 @@ template<class K, class V> using absl_flat_hash_map_fnv1a =
 
 #endif
 
+#ifdef HAVE_TSL_HOPSCOTCH
+
+template<class K, class V> using tsl_hopscotch_map_fnv1a =
+    tsl::hopscotch_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map_fnv1a =
+    tsl::hopscotch_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map_fnv1a =
+    tsl::robin_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map_fnv1a =
+    tsl::robin_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
 //
 
 int main()
@@ -382,6 +431,20 @@ int main()
 
 #endif
 
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
+#endif
+
 #endif
 
     test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
@@ -393,13 +456,27 @@ int main()
     test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
     test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map_fnv1a>( "tsl::hopscotch_map, FNV-1a" );
+    test<tsl_hopscotch_pg_map_fnv1a>( "tsl::hopscotch_pg_map, FNV-1a" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map_fnv1a>( "tsl::robin_map, FNV-1a" );
+    test<tsl_robin_pg_map_fnv1a>( "tsl::robin_pg_map, FNV-1a" );
+
 #endif
 
     std::cout << "---\n\n";
 
     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( 31 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/string_view.cpp

@@ -14,6 +14,12 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
+#endif
 #include <unordered_map>
 #include <string_view>
 #include <vector>
@@ -138,7 +144,14 @@ template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::s
     {
         if( it->second & 1 )
         {
-            map.erase( it++ );
+            if constexpr( std::is_void_v< decltype( map.erase( it ) ) > )
+            {
+                map.erase( it++ );
+            }
+            else
+            {
+                it = map.erase( it );
+            }
         }
         else
         {
@@ -160,13 +173,9 @@ template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::stead
 
     print_time( t1, "Consecutive erase",  0, map.size() );
 
+    for( unsigned i = 1; i <= N; ++i )
     {
-        boost::detail::splitmix64 rng;
-
-        for( unsigned i = 1; i <= N; ++i )
-        {
-            map.erase( indices2[ i ] );
-        }
+        map.erase( indices2[ i ] );
     }
 
     print_time( t1, "Random erase",  0, map.size() );
@@ -296,6 +305,26 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
+#ifdef HAVE_TSL_HOPSCOTCH
+
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
 // fnv1a_hash
 
 template<int Bits> struct fnv1a_hash_impl;
@@ -364,6 +393,26 @@ template<class K, class V> using absl_flat_hash_map_fnv1a =
 
 #endif
 
+#ifdef HAVE_TSL_HOPSCOTCH
+
+template<class K, class V> using tsl_hopscotch_map_fnv1a =
+    tsl::hopscotch_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map_fnv1a =
+    tsl::hopscotch_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map_fnv1a =
+    tsl::robin_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map_fnv1a =
+    tsl::robin_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
 //
 
 int main()
@@ -383,6 +432,20 @@ int main()
 
 #endif
 
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
+#endif
+
 #endif
 
     test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
@@ -394,13 +457,27 @@ int main()
     test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
     test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map_fnv1a>( "tsl::hopscotch_map, FNV-1a" );
+    test<tsl_hopscotch_pg_map_fnv1a>( "tsl::hopscotch_pg_map, FNV-1a" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map_fnv1a>( "tsl::robin_map, FNV-1a" );
+    test<tsl_robin_pg_map_fnv1a>( "tsl::robin_pg_map, FNV-1a" );
+
 #endif
 
     std::cout << "---\n\n";
 
     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( 31 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uint32.cpp

@@ -8,12 +8,19 @@
 #include <boost/multi_index_container.hpp>
 #include <boost/multi_index/hashed_index.hpp>
 #include <boost/multi_index/member.hpp>
+#include <boost/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
 #ifdef HAVE_ABSEIL
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
+#endif
 #include <unordered_map>
 #include <vector>
 #include <memory>
@@ -62,7 +69,7 @@ static void init_indices()
 
     for( unsigned i = 1; i <= N*2; ++i )
     {
-        indices3.push_back( (std::uint32_t)i << 11 );
+        indices3.push_back( boost::endian::endian_reverse( static_cast<std::uint32_t>( i ) ) );
     }
 }
 
@@ -87,7 +94,7 @@ template<class Map> BOOST_NOINLINE void test_insert( Map& map, std::chrono::stea
         map.insert( { indices3[ i ], i } );
     }
 
-    print_time( t1, "Consecutive shifted insert",  0, map.size() );
+    print_time( t1, "Consecutive reversed insert",  0, map.size() );
 
     std::cout << std::endl;
 }
@@ -133,7 +140,7 @@ template<class Map> BOOST_NOINLINE void test_lookup( Map& map, std::chrono::stea
         }
     }
 
-    print_time( t1, "Consecutive shifted lookup",  s, map.size() );
+    print_time( t1, "Consecutive reversed lookup",  s, map.size() );
 
     std::cout << std::endl;
 }
@@ -146,7 +153,14 @@ template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::s
     {
         if( it->second & 1 )
         {
-            map.erase( it++ );
+            if constexpr( std::is_void_v< decltype( map.erase( it ) ) > )
+            {
+                map.erase( it++ );
+            }
+            else
+            {
+                it = map.erase( it );
+            }
         }
         else
         {
@@ -168,13 +182,9 @@ template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::stead
 
     print_time( t1, "Consecutive erase",  0, map.size() );
 
+    for( unsigned i = 1; i <= N; ++i )
     {
-        boost::detail::splitmix64 rng;
-
-        for( unsigned i = 1; i <= N; ++i )
-        {
-            map.erase( indices2[ i ] );
-        }
+        map.erase( indices2[ i ] );
     }
 
     print_time( t1, "Random erase",  0, map.size() );
@@ -184,7 +194,7 @@ template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::stead
         map.erase( indices3[ i ] );
     }
 
-    print_time( t1, "Consecutive shifted erase",  0, map.size() );
+    print_time( t1, "Consecutive reversed erase",  0, map.size() );
 
     std::cout << std::endl;
 }
@@ -311,6 +321,26 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
+#ifdef HAVE_TSL_HOPSCOTCH
+
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
 int main()
 {
     init_indices();
@@ -324,6 +354,20 @@ int main()
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
 #endif
 
     std::cout << "---\n\n";

benchmark/uint64.cpp

@@ -8,12 +8,19 @@
 #include <boost/multi_index_container.hpp>
 #include <boost/multi_index/hashed_index.hpp>
 #include <boost/multi_index/member.hpp>
+#include <boost/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
 #ifdef HAVE_ABSEIL
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
+#ifdef HAVE_TSL_HOPSCOTCH
+# include "tsl/hopscotch_map.h"
+#endif
+#ifdef HAVE_TSL_ROBIN
+# include "tsl/robin_map.h"
+#endif
 #include <unordered_map>
 #include <vector>
 #include <memory>
@@ -62,7 +69,7 @@ static void init_indices()
 
     for( unsigned i = 1; i <= N*2; ++i )
     {
-        indices3.push_back( (std::uint64_t)i << 40 );
+        indices3.push_back( boost::endian::endian_reverse( static_cast<std::uint64_t>( i ) ) );
     }
 }
 
@@ -87,7 +94,7 @@ template<class Map> BOOST_NOINLINE void test_insert( Map& map, std::chrono::stea
         map.insert( { indices3[ i ], i } );
     }
 
-    print_time( t1, "Consecutive shifted insert",  0, map.size() );
+    print_time( t1, "Consecutive reversed insert",  0, map.size() );
 
     std::cout << std::endl;
 }
@@ -133,7 +140,7 @@ template<class Map> BOOST_NOINLINE void test_lookup( Map& map, std::chrono::stea
         }
     }
 
-    print_time( t1, "Consecutive shifted lookup",  s, map.size() );
+    print_time( t1, "Consecutive reversed lookup",  s, map.size() );
 
     std::cout << std::endl;
 }
@@ -146,7 +153,14 @@ template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::s
     {
         if( it->second & 1 )
         {
-            map.erase( it++ );
+            if constexpr( std::is_void_v< decltype( map.erase( it ) ) > )
+            {
+                map.erase( it++ );
+            }
+            else
+            {
+                it = map.erase( it );
+            }
         }
         else
         {
@@ -168,13 +182,9 @@ template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::stead
 
     print_time( t1, "Consecutive erase",  0, map.size() );
 
+    for( unsigned i = 1; i <= N; ++i )
     {
-        boost::detail::splitmix64 rng;
-
-        for( unsigned i = 1; i <= N; ++i )
-        {
-            map.erase( indices2[ i ] );
-        }
+        map.erase( indices2[ i ] );
     }
 
     print_time( t1, "Random erase",  0, map.size() );
@@ -184,7 +194,7 @@ template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::stead
         map.erase( indices3[ i ] );
     }
 
-    print_time( t1, "Consecutive shifted erase",  0, map.size() );
+    print_time( t1, "Consecutive reversed erase",  0, map.size() );
 
     std::cout << std::endl;
 }
@@ -311,6 +321,26 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
+#ifdef HAVE_TSL_HOPSCOTCH
+
+template<class K, class V> using tsl_hopscotch_map =
+    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_hopscotch_pg_map =
+    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+template<class K, class V> using tsl_robin_map =
+    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+template<class K, class V> using tsl_robin_pg_map =
+    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
 int main()
 {
     init_indices();
@@ -324,6 +354,20 @@ int main()
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
+#endif
+
+#ifdef HAVE_TSL_HOPSCOTCH
+
+    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
+    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
+
+#endif
+
+#ifdef HAVE_TSL_ROBIN
+
+    test<tsl_robin_map>( "tsl::robin_map" );
+    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
+
 #endif
 
     std::cout << "---\n\n";

doc/unordered/unordered_map.adoc

@@ -1566,7 +1566,9 @@ Effects:;; Changes the container's maximum load factor, using `z` as a hint.
 void rehash(size_type n);
 ```
 
-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.
+Changes the number of buckets so that there are at least `n` buckets, and so that the load factor is less than or equal to the maximum load factor. When applicable, this will either grow or shrink the `bucket_count()` associated with the container.
+
+When `size() == 0`, `rehash(0)` will deallocate the underlying buckets array.
 
 Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.
 
@@ -1580,6 +1582,10 @@ Throws:;; The function has no effect if an exception is thrown, unless it is thr
 void reserve(size_type n);
 ```
 
+Equivalent to `a.rehash(ceil(n / a.max_load_factor()))`, or `a.rehash(1)` if `n > 0` and `a.max_load_factor() == std::numeric_limits<float>::infinity()`.
+
+Similar to `rehash`, this function can be used to grow or shrink the number of buckets in the container.
+
 Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.
 
 [horizontal]

doc/unordered/unordered_multimap.adoc

@@ -1345,7 +1345,9 @@ Effects:;; Changes the container's maximum load factor, using `z` as a hint.
 void rehash(size_type n);
 ```
 
-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.
+Changes the number of buckets so that there are at least `n` buckets, and so that the load factor is less than or equal to the maximum load factor. When applicable, this will either grow or shrink the `bucket_count()` associated with the container.
+
+When `size() == 0`, `rehash(0)` will deallocate the underlying buckets array.
 
 Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.
 
@@ -1359,6 +1361,10 @@ Throws:;; The function has no effect if an exception is thrown, unless it is thr
 void reserve(size_type n);
 ```
 
+Equivalent to `a.rehash(ceil(n / a.max_load_factor()))`, or `a.rehash(1)` if `n > 0` and `a.max_load_factor() == std::numeric_limits<float>::infinity()`.
+
+Similar to `rehash`, this function can be used to grow or shrink the number of buckets in the container.
+
 Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.
 
 [horizontal]

doc/unordered/unordered_multiset.adoc

@@ -1306,7 +1306,9 @@ Effects:;; Changes the container's maximum load factor, using `z` as a hint.
 void rehash(size_type n);
 ```
 
-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.
+Changes the number of buckets so that there are at least `n` buckets, and so that the load factor is less than or equal to the maximum load factor. When applicable, this will either grow or shrink the `bucket_count()` associated with the container.
+
+When `size() == 0`, `rehash(0)` will deallocate the underlying buckets array.
 
 Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.
 
@@ -1320,11 +1322,16 @@ Throws:;; The function has no effect if an exception is thrown, unless it is thr
 void reserve(size_type n);
 ```
 
+Equivalent to `a.rehash(ceil(n / a.max_load_factor()))`, or `a.rehash(1)` if `n > 0` and `a.max_load_factor() == std::numeric_limits<float>::infinity()`.
+
+Similar to `rehash`, this function can be used to grow or shrink the number of buckets in the container.
+
 Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.
 
 [horizontal]
 Throws:;; The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.
 
+
 ---
 
 === Equality Comparisons

doc/unordered/unordered_set.adoc

@@ -1329,7 +1329,9 @@ Effects:;; Changes the container's maximum load factor, using `z` as a hint.
 void rehash(size_type n);
 ```
 
-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.
+Changes the number of buckets so that there are at least `n` buckets, and so that the load factor is less than or equal to the maximum load factor. When applicable, this will either grow or shrink the `bucket_count()` associated with the container.
+
+When `size() == 0`, `rehash(0)` will deallocate the underlying buckets array.
 
 Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.
 
@@ -1343,11 +1345,16 @@ Throws:;; The function has no effect if an exception is thrown, unless it is thr
 void reserve(size_type n);
 ```
 
+Equivalent to `a.rehash(ceil(n / a.max_load_factor()))`, or `a.rehash(1)` if `n > 0` and `a.max_load_factor() == std::numeric_limits<float>::infinity()`.
+
+Similar to `rehash`, this function can be used to grow or shrink the number of buckets in the container.
+
 Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.
 
 [horizontal]
 Throws:;; The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.
 
+
 === Equality Comparisons
 
 ==== operator==

include/boost/unordered/detail/fca.hpp

@@ -113,10 +113,7 @@ to normal separate chaining implementations.
 
 */
 
-#include <boost/config.hpp>
-#if defined(BOOST_HAS_PRAGMA_ONCE)
-#pragma once
-#endif
+#include <boost/unordered/detail/prime_fmod.hpp>
 
 #include <boost/core/addressof.hpp>
 #include <boost/core/allocator_access.hpp>
@@ -124,289 +121,20 @@ to normal separate chaining implementations.
 #include <boost/core/empty_value.hpp>
 #include <boost/core/no_exceptions_support.hpp>
 #include <boost/cstdint.hpp>
-
-// `iterator_facade` has transitive dependencies on Boost.MPL; one of the
-// headers is generating a `-Wsign-conversion` warning which has an open PR to
-// address the issue but merging does not seem likely so for now create a rote
-// workaround.
-//
-// TODO: eventually remove this once MPL is fixed or we decide to migrate off of
-// the Boost.Iterator dependency.
-//
-#if defined(BOOST_GCC)
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wsign-conversion"
-#pragma GCC diagnostic ignored "-Wconversion"
-#include <boost/iterator/iterator_facade.hpp>
-#pragma GCC diagnostic pop
-#else
-#include <boost/iterator/iterator_facade.hpp>
-#endif
-
 #include <boost/move/core.hpp>
 #include <boost/move/utility_core.hpp>
-#include <boost/preprocessor/seq/enum.hpp>
-#include <boost/preprocessor/seq/for_each.hpp>
-#include <boost/preprocessor/seq/size.hpp>
 #include <boost/swap.hpp>
 #include <boost/type_traits/aligned_storage.hpp>
 #include <boost/type_traits/alignment_of.hpp>
 
-#include <climits>
+#include <boost/config.hpp>
+
+#include <iterator>
 
 namespace boost {
   namespace unordered {
     namespace detail {
 
-#if defined(SIZE_MAX)
-#if ((((SIZE_MAX >> 16) >> 16) >> 16) >> 15) != 0
-#define BOOST_UNORDERED_FCA_HAS_64B_SIZE_T
-#endif
-#elif defined(UINTPTR_MAX) /* used as proxy for std::size_t */
-#if ((((UINTPTR_MAX >> 16) >> 16) >> 16) >> 15) != 0
-#define BOOST_UNORDERED_FCA_HAS_64B_SIZE_T
-#endif
-#endif
-
-#if !defined(BOOST_NO_INT64_T) &&                                              \
-  (defined(BOOST_HAS_INT128) || (defined(BOOST_MSVC) && defined(_WIN64)))
-#define BOOST_UNORDERED_FCA_FASTMOD_SUPPORT
-#endif
-
-      template <class = void> struct prime_fmod_size
-      {
-        // Because we compile for C++03, we don't have access to any inline
-        // initialization for array data members so the definitions must exist
-        // out-of-line. To keep the library header-only, we introduce a dummy
-        // template parameter which permits the definition to be included in
-        // multiple TUs without conflict.
-        //
-        static std::size_t sizes[];
-        static std::size_t const sizes_len;
-        static std::size_t (*positions[])(std::size_t);
-
-#if defined(BOOST_UNORDERED_FCA_FASTMOD_SUPPORT)
-        static uint64_t inv_sizes32[];
-        static std::size_t const inv_sizes32_len;
-#endif /* defined(BOOST_UNORDERED_FCA_FASTMOD_SUPPORT) */
-
-        static inline std::size_t size_index(std::size_t n)
-        {
-          std::size_t i = 0;
-          for (; i < (sizes_len - 1); ++i) {
-            if (sizes[i] >= n) {
-              break;
-            }
-          }
-          return i;
-        }
-
-        static inline std::size_t size(std::size_t size_index)
-        {
-          return sizes[size_index];
-        }
-
-        template <std::size_t Size> static std::size_t modulo(std::size_t hash)
-        {
-          return hash % Size;
-        }
-
-#if defined(BOOST_UNORDERED_FCA_FASTMOD_SUPPORT)
-        // We emulate the techniques taken from:
-        // Faster Remainder by Direct Computation: Applications to Compilers and
-        // Software Libraries
-        // https://arxiv.org/abs/1902.01961
-        //
-        // In essence, use fancy math to directly calculate the remainder (aka
-        // modulo) exploiting how compilers transform division
-        //
-
-#if defined(_MSC_VER)
-        static inline uint64_t get_remainder(uint64_t fractional, uint32_t d)
-        {
-          // use fancy msvc instrinsic when available instead of using `>> 64`
-          //
-          return __umulh(fractional, d);
-        }
-#else
-        static inline uint64_t get_remainder(uint64_t fractional, uint32_t d)
-        {
-          __extension__ typedef unsigned __int128 uint128;
-          return static_cast<uint64_t>(((uint128)fractional * d) >> 64);
-        }
-#endif /* defined(_MSC_VER) */
-
-        static inline uint32_t fast_modulo(uint32_t a, uint64_t M, uint32_t d)
-        {
-          uint64_t fractional = M * a;
-          return (uint32_t)(get_remainder(fractional, d));
-        }
-#endif /* defined(BOOST_UNORDERED_FCA_FASTMOD_SUPPORT) */
-
-        static inline std::size_t position(
-          std::size_t hash, std::size_t size_index)
-        {
-#if defined(BOOST_UNORDERED_FCA_FASTMOD_SUPPORT)
-#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
-          std::size_t sizes_under_32bit = inv_sizes32_len;
-          if (BOOST_LIKELY(size_index < sizes_under_32bit)) {
-            return fast_modulo(uint32_t(hash) + uint32_t(hash >> 32),
-              inv_sizes32[size_index], uint32_t(sizes[size_index]));
-          } else {
-            return positions[size_index - sizes_under_32bit](hash);
-          }
-#else
-          return fast_modulo(
-            hash, inv_sizes32[size_index], uint32_t(sizes[size_index]));
-#endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
-#else
-          return positions[size_index](hash);
-#endif /* defined(BOOST_UNORDERED_FCA_FASTMOD_SUPPORT) */
-        }
-      }; // prime_fmod_size
-
-#define BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT_INCOMPLETE                      \
-  (13ul)(29ul)(53ul)(97ul)(193ul)(389ul)(769ul)(1543ul)(3079ul)(6151ul)(       \
-    12289ul)(24593ul)(49157ul)(98317ul)(196613ul)(393241ul)(786433ul)(         \
-    1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul)(50331653ul)(      \
-    100663319ul)(201326611ul)(402653189ul)(805306457ul)(1610612741ul)(         \
-    3221225473ul)
-
-#if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
-
-#define BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT                                 \
-  BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT_INCOMPLETE(4294967291ul)
-
-#define BOOST_UNORDERED_PRIME_FMOD_SIZES_64BIT
-
-#else
-
-#define BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT                                 \
-  BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT_INCOMPLETE
-
-// The original sequence here is this:
-// (6442450939ul)
-// (12884901893ul)
-// (25769803751ul)
-// (51539607551ul)
-// (103079215111ul)
-// (206158430209ul)
-// (412316860441ul)
-// (824633720831ul)
-// (1649267441651ul)
-//
-// but this causes problems on versions of mingw where the `long` type is 32
-// bits, even for 64-bit targets. We work around this by replacing the literals
-// with compile-time arithmetic, using bitshifts to reconstruct the number.
-//
-
-// clang-format off
-#define BOOST_UNORDERED_PRIME_FMOD_SIZES_64BIT                                   \
-  ((boost::ulong_long_type(1ul) << 32)   + boost::ulong_long_type(2147483643ul)) \
-  ((boost::ulong_long_type(3ul) << 32)   + boost::ulong_long_type(5ul))          \
-  ((boost::ulong_long_type(5ul) << 32)   + boost::ulong_long_type(4294967271ul)) \
-  ((boost::ulong_long_type(11ul) << 32)  + boost::ulong_long_type(4294967295ul)) \
-  ((boost::ulong_long_type(24ul) << 32)  + boost::ulong_long_type(7ul))          \
-  ((boost::ulong_long_type(48ul) << 32)  + boost::ulong_long_type(1ul))          \
-  ((boost::ulong_long_type(96ul) << 32)  + boost::ulong_long_type(25ul))         \
-  ((boost::ulong_long_type(191ul) << 32) + boost::ulong_long_type(4294967295ul)) \
-  ((boost::ulong_long_type(383ul) << 32) + boost::ulong_long_type(4294967283ul))
-      // clang-format on
-
-#endif /* BOOST_UNORDERED_FCA_HAS_64B_SIZE_T */
-
-#define BOOST_UNORDERED_PRIME_FMOD_SIZES                                       \
-  BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT BOOST_UNORDERED_PRIME_FMOD_SIZES_64BIT
-
-      template <class T>
-      std::size_t prime_fmod_size<T>::sizes[] = {
-        BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIME_FMOD_SIZES)};
-
-      template <class T>
-      std::size_t const prime_fmod_size<T>::sizes_len = BOOST_PP_SEQ_SIZE(
-        BOOST_UNORDERED_PRIME_FMOD_SIZES);
-
-// Similarly here, we have to re-express the integer initialization using
-// arithmetic such that each literal can fit in a 32-bit value.
-//
-#if defined(BOOST_UNORDERED_FCA_FASTMOD_SUPPORT)
-      // clang-format off
-        template <class T>
-        uint64_t prime_fmod_size<T>::inv_sizes32[] = {
-          (boost::ulong_long_type(330382099ul) << 32) + boost::ulong_long_type(2973438898ul) /* = 1418980313362273202 */,
-          (boost::ulong_long_type(148102320ul) << 32) + boost::ulong_long_type(2369637129ul) /* = 636094623231363849 */,
-          (boost::ulong_long_type(81037118ul) << 32)  + boost::ulong_long_type(3403558990ul) /* = 348051774975651918 */,
-          (boost::ulong_long_type(44278013ul) << 32)  + boost::ulong_long_type(1549730468ul) /* = 190172619316593316 */,
-          (boost::ulong_long_type(22253716ul) << 32)  + boost::ulong_long_type(2403401389ul) /* = 95578984837873325 */,
-          (boost::ulong_long_type(11041047ul) << 32)  + boost::ulong_long_type(143533612ul)  /* = 47420935922132524 */,
-          (boost::ulong_long_type(5585133ul) << 32)   + boost::ulong_long_type(106117528ul)  /* = 23987963684927896 */,
-          (boost::ulong_long_type(2783517ul) << 32)   + boost::ulong_long_type(1572687312ul) /* = 11955116055547344 */,
-          (boost::ulong_long_type(1394922ul) << 32)   + boost::ulong_long_type(3428720239ul) /* = 5991147799191151 */,
-          (boost::ulong_long_type(698255ul) << 32)    + boost::ulong_long_type(552319807ul)  /* = 2998982941588287 */,
-          (boost::ulong_long_type(349496ul) << 32)    + boost::ulong_long_type(3827689953ul) /* = 1501077717772769 */,
-          (boost::ulong_long_type(174641ul) << 32)    + boost::ulong_long_type(3699438549ul) /* = 750081082979285 */,
-          (boost::ulong_long_type(87372ul) << 32)     + boost::ulong_long_type(1912757574ul) /* = 375261795343686 */,
-          (boost::ulong_long_type(43684ul) << 32)     + boost::ulong_long_type(3821029929ul) /* = 187625172388393 */,
-          (boost::ulong_long_type(21844ul) << 32)     + boost::ulong_long_type(3340590800ul) /* = 93822606204624 */,
-          (boost::ulong_long_type(10921ul) << 32)     + boost::ulong_long_type(4175852267ul) /* = 46909513691883 */,
-          (boost::ulong_long_type(5461ul) << 32)      + boost::ulong_long_type(1401829642ul) /* = 23456218233098 */,
-          (boost::ulong_long_type(2730ul) << 32)      + boost::ulong_long_type(2826028947ul) /* = 11728086747027 */,
-          (boost::ulong_long_type(1365ul) << 32)      + boost::ulong_long_type(1411150351ul) /* = 5864041509391 */,
-          (boost::ulong_long_type(682ul) << 32)       + boost::ulong_long_type(2857253105ul) /* = 2932024948977 */,
-          (boost::ulong_long_type(341ul) << 32)       + boost::ulong_long_type(1431073224ul) /* = 1466014921160 */,
-          (boost::ulong_long_type(170ul) << 32)       + boost::ulong_long_type(2862758116ul) /* = 733007198436 */,
-          (boost::ulong_long_type(85ul) << 32)        + boost::ulong_long_type(1431619357ul) /* = 366503839517 */,
-          (boost::ulong_long_type(42ul) << 32)        + boost::ulong_long_type(2863269661ul) /* = 183251896093 */,
-          (boost::ulong_long_type(21ul) << 32)        + boost::ulong_long_type(1431647119ul) /* = 91625960335 */,
-          (boost::ulong_long_type(10ul) << 32)        + boost::ulong_long_type(2863310962ul) /* = 45812983922 */,
-          (boost::ulong_long_type(5ul) << 32)         + boost::ulong_long_type(1431653234ul) /* = 22906489714 */,
-          (boost::ulong_long_type(2ul) << 32)         + boost::ulong_long_type(2863311496ul) /* = 11453246088 */,
-          (boost::ulong_long_type(1ul) << 32)         + boost::ulong_long_type(1431655764ul) /* = 5726623060 */,
-#if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
-        };
-#else
-          (boost::ulong_long_type(1ul) << 32)         + boost::ulong_long_type(6ul)          /* 4294967302 */
-        };
-      // clang-format on
-#endif /* !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
-
-      template <class T>
-      std::size_t const
-        prime_fmod_size<T>::inv_sizes32_len = sizeof(inv_sizes32) /
-                                              sizeof(inv_sizes32[0]);
-
-#endif /* defined(BOOST_UNORDERED_FCA_FASTMOD_SUPPORT) */
-
-#define BOOST_UNORDERED_PRIME_FMOD_POSITIONS_ELEMENT(z, _, n)                  \
-  prime_fmod_size<T>::template modulo<n>,
-
-      template <class T>
-      std::size_t (*prime_fmod_size<T>::positions[])(std::size_t) = {
-#if !defined(BOOST_UNORDERED_FCA_FASTMOD_SUPPORT)
-        BOOST_PP_SEQ_FOR_EACH(BOOST_UNORDERED_PRIME_FMOD_POSITIONS_ELEMENT, ~,
-          BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT)
-#endif
-
-#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
-          BOOST_PP_SEQ_FOR_EACH(BOOST_UNORDERED_PRIME_FMOD_POSITIONS_ELEMENT, ~,
-            BOOST_UNORDERED_PRIME_FMOD_SIZES_64BIT)
-#endif
-      };
-
-#undef BOOST_UNORDERED_PRIME_FMOD_POSITIONS_ELEMENT
-#undef BOOST_UNORDERED_PRIME_FMOD_SIZES
-#undef BOOST_UNORDERED_PRIME_FMOD_SIZES_64BIT
-#undef BOOST_UNORDERED_PRIME_FMOD_SIZES_34BIT
-#undef BOOST_UNORDERED_PRIME_FMOD_SIZES_34BIT_INCOMPLETE
-
-#ifdef BOOST_UNORDERED_FCA_FASTMOD_SUPPORT
-#undef BOOST_UNORDERED_FCA_FASTMOD_SUPPORT
-#endif
-
-#ifdef BOOST_UNORDERED_FCA_HAS_64B_SIZE_T
-#undef BOOST_UNORDERED_FCA_HAS_64B_SIZE_T
-#endif
-
       template <class ValueType, class VoidPtr> struct node
       {
         typedef ValueType value_type;
@@ -472,10 +200,7 @@ namespace boost {
         return ~(~(std::size_t(0)) >> (sizeof(std::size_t) * 8 - n));
       }
 
-      template <class Bucket>
-      struct grouped_bucket_iterator
-          : public boost::iterator_facade<grouped_bucket_iterator<Bucket>,
-              Bucket, boost::forward_traversal_tag>
+      template <class Bucket> struct grouped_bucket_iterator
       {
       public:
         typedef typename Bucket::bucket_pointer bucket_pointer;
@@ -483,8 +208,12 @@ namespace boost {
           typename boost::pointer_traits<bucket_pointer>::template rebind_to<
             bucket_group<Bucket> >::type bucket_group_pointer;
 
+        typedef Bucket value_type;
         typedef typename boost::pointer_traits<bucket_pointer>::difference_type
           difference_type;
+        typedef Bucket& reference;
+        typedef Bucket* pointer;
+        typedef std::forward_iterator_tag iterator_category;
 
       private:
         bucket_pointer p;
@@ -493,9 +222,38 @@ namespace boost {
       public:
         grouped_bucket_iterator() : p(), pbg() {}
 
-      private:
-        friend class boost::iterator_core_access;
+        reference operator*() const BOOST_NOEXCEPT { return dereference(); }
+        pointer operator->() const BOOST_NOEXCEPT
+        {
+          return boost::to_address(p);
+        }
 
+        grouped_bucket_iterator& operator++() BOOST_NOEXCEPT
+        {
+          increment();
+          return *this;
+        }
+
+        grouped_bucket_iterator operator++(int) BOOST_NOEXCEPT
+        {
+          grouped_bucket_iterator old = *this;
+          increment();
+          return old;
+        }
+
+        bool operator==(
+          grouped_bucket_iterator const& other) const BOOST_NOEXCEPT
+        {
+          return equal(other);
+        }
+
+        bool operator!=(
+          grouped_bucket_iterator const& other) const BOOST_NOEXCEPT
+        {
+          return !equal(other);
+        }
+
+      private:
         template <typename, typename, typename>
         friend class grouped_bucket_array;
 
@@ -533,12 +291,8 @@ namespace boost {
 
       template <class Node> struct const_grouped_local_bucket_iterator;
 
-      template <class Node>
-      struct grouped_local_bucket_iterator
-          : public boost::iterator_facade<grouped_local_bucket_iterator<Node>,
-              typename Node::value_type, boost::forward_traversal_tag>
+      template <class Node> struct grouped_local_bucket_iterator
       {
-
         typedef typename Node::node_pointer node_pointer;
 
       public:
@@ -551,9 +305,39 @@ namespace boost {
 
         grouped_local_bucket_iterator() : p() {}
 
-      private:
-        friend class boost::iterator_core_access;
+        reference operator*() const BOOST_NOEXCEPT { return dereference(); }
 
+        pointer operator->() const BOOST_NOEXCEPT
+        {
+          return boost::to_address(p);
+        }
+
+        grouped_local_bucket_iterator& operator++() BOOST_NOEXCEPT
+        {
+          increment();
+          return *this;
+        }
+
+        grouped_local_bucket_iterator operator++(int) BOOST_NOEXCEPT
+        {
+          grouped_local_bucket_iterator old = *this;
+          increment();
+          return old;
+        }
+
+        bool operator==(
+          grouped_local_bucket_iterator const& other) const BOOST_NOEXCEPT
+        {
+          return equal(other);
+        }
+
+        bool operator!=(
+          grouped_local_bucket_iterator const& other) const BOOST_NOEXCEPT
+        {
+          return !equal(other);
+        }
+
+      private:
         template <typename, typename, typename>
         friend class grouped_bucket_array;
 
@@ -573,11 +357,7 @@ namespace boost {
         node_pointer p;
       };
 
-      template <class Node>
-      struct const_grouped_local_bucket_iterator
-          : public boost::iterator_facade<
-              const_grouped_local_bucket_iterator<Node>,
-              typename Node::value_type const, boost::forward_traversal_tag>
+      template <class Node> struct const_grouped_local_bucket_iterator
       {
         typedef typename Node::node_pointer node_pointer;
 
@@ -596,9 +376,39 @@ namespace boost {
         {
         }
 
-      private:
-        friend class boost::iterator_core_access;
+        reference operator*() const BOOST_NOEXCEPT { return dereference(); }
 
+        pointer operator->() const BOOST_NOEXCEPT
+        {
+          return boost::to_address(p);
+        }
+
+        const_grouped_local_bucket_iterator& operator++() BOOST_NOEXCEPT
+        {
+          increment();
+          return *this;
+        }
+
+        const_grouped_local_bucket_iterator operator++(int) BOOST_NOEXCEPT
+        {
+          const_grouped_local_bucket_iterator old = *this;
+          increment();
+          return old;
+        }
+
+        bool operator==(
+          const_grouped_local_bucket_iterator const& other) const BOOST_NOEXCEPT
+        {
+          return equal(other);
+        }
+
+        bool operator!=(
+          const_grouped_local_bucket_iterator const& other) const BOOST_NOEXCEPT
+        {
+          return !equal(other);
+        }
+
+      private:
         template <typename, typename, typename>
         friend class grouped_bucket_array;
 
@@ -684,11 +494,33 @@ namespace boost {
         group_pointer groups;
 
       public:
+        static std::size_t bucket_count_for(std::size_t num_buckets)
+        {
+          if (num_buckets == 0) {
+            return 0;
+          }
+          return size_policy::size(size_policy::size_index(num_buckets));
+        }
+
+        grouped_bucket_array()
+            : empty_value<node_allocator_type>(
+                empty_init_t(), node_allocator_type()),
+              size_index_(0), size_(0), buckets(), groups()
+        {
+        }
+
         grouped_bucket_array(size_type n, const Allocator& al)
             : empty_value<node_allocator_type>(empty_init_t(), al),
-              size_index_(size_policy::size_index(n)),
-              size_(size_policy::size(size_index_)), buckets(), groups()
+              size_index_(0),
+              size_(0), buckets(), groups()
         {
+          if (n == 0) {
+            return;
+          }
+
+          size_index_ = size_policy::size_index(n);
+          size_ = size_policy::size(size_index_);
+
           bucket_allocator_type bucket_alloc = this->get_bucket_allocator();
           group_allocator_type group_alloc = this->get_group_allocator();
 
@@ -836,7 +668,7 @@ namespace boost {
 
         size_type bucket_count() const { return size_; }
 
-        iterator begin() const { return ++at(size_); }
+        iterator begin() const { return size_ == 0 ? end() : ++at(size_); }
 
         iterator end() const
         {
@@ -850,6 +682,10 @@ namespace boost {
 
         local_iterator begin(size_type n) const
         {
+          if (size_ == 0) {
+            return this->end(n);
+          }
+
           return local_iterator(
             (buckets + static_cast<difference_type>(n))->next);
         }
@@ -860,12 +696,16 @@ namespace boost {
 
         iterator at(size_type n) const
         {
-          std::size_t const N = group::N;
+          if (size_ > 0) {
+            std::size_t const N = group::N;
 
-          iterator pbg(buckets + static_cast<difference_type>(n),
-            groups + static_cast<difference_type>(n / N));
+            iterator pbg(buckets + static_cast<difference_type>(n),
+              groups + static_cast<difference_type>(n / N));
 
-          return pbg;
+            return pbg;
+          } else {
+            return this->end();
+          }
         }
 
         span<Bucket> raw()

include/boost/unordered/detail/implementation.hpp

@@ -15,7 +15,6 @@
 #endif
 
 #include <boost/assert.hpp>
-#include <boost/config.hpp>
 #include <boost/core/allocator_traits.hpp>
 #include <boost/core/bit.hpp>
 #include <boost/core/no_exceptions_support.hpp>
@@ -60,15 +59,6 @@
 #include <type_traits>
 #endif
 
-#if __SSE2__
-#include <emmintrin.h>
-#endif
-
-#if defined(__SSE2__) || \
-    defined(_M_X64) || (defined(_M_IX86_FP) && _M_IX86_FP >= 2)
-#define BOOST_UNORDERED_SSE2_SUPPORTED
-#endif
-
 ////////////////////////////////////////////////////////////////////////////////
 // Configuration
 //
@@ -210,7 +200,7 @@ namespace boost {
       template <typename Types> struct table;
 
       static const float minimum_max_load_factor = 1e-3f;
-      static const std::size_t default_bucket_count = 11;
+      static const std::size_t default_bucket_count = 0;
 
       struct move_tag
       {
@@ -1707,10 +1697,9 @@ namespace boost {
       };
 
       template <typename T>
-      struct rv_ref
-        : boost::detail::if_true<boost::is_class<T>::value>::
-            BOOST_NESTED_TEMPLATE then<boost::unordered::detail::rv_ref_impl<T>,
-              please_ignore_this_overload>::type
+      struct rv_ref : boost::conditional<boost::is_class<T>::value,
+                        boost::unordered::detail::rv_ref_impl<T>,
+                        please_ignore_this_overload>::type
       {
       };
 
@@ -1740,10 +1729,7 @@ namespace boost {
       namespace iterator_detail {
         template <class Node, class Bucket> class c_iterator;
 
-        template <class Node, class Bucket>
-        class iterator
-            : public boost::iterator_facade<iterator<Node, Bucket>,
-                typename Node::value_type, boost::forward_traversal_tag>
+        template <class Node, class Bucket> class iterator
         {
         public:
           typedef typename Node::value_type value_type;
@@ -1755,6 +1741,50 @@ namespace boost {
 
           iterator() : p(), itb(){};
 
+          reference operator*() const BOOST_NOEXCEPT { return dereference(); }
+          pointer operator->() const BOOST_NOEXCEPT
+          {
+            pointer x = boost::addressof(p->value());
+            return x;
+          }
+
+          iterator& operator++() BOOST_NOEXCEPT
+          {
+            increment();
+            return *this;
+          }
+
+          iterator operator++(int) BOOST_NOEXCEPT
+          {
+            iterator old = *this;
+            increment();
+            return old;
+          }
+
+          bool operator==(iterator const& other) const BOOST_NOEXCEPT
+          {
+            return equal(other);
+          }
+
+          bool operator!=(iterator const& other) const BOOST_NOEXCEPT
+          {
+            return !equal(other);
+          }
+
+          bool operator==(
+            boost::unordered::detail::iterator_detail::c_iterator<Node,
+              Bucket> const& other) const BOOST_NOEXCEPT
+          {
+            return equal(other);
+          }
+
+          bool operator!=(
+            boost::unordered::detail::iterator_detail::c_iterator<Node,
+              Bucket> const& other) const BOOST_NOEXCEPT
+          {
+            return !equal(other);
+          }
+
         private:
           typedef typename Node::node_pointer node_pointer;
           typedef grouped_bucket_iterator<Bucket> bucket_iterator;
@@ -1764,7 +1794,6 @@ namespace boost {
 
           template <class Types> friend struct boost::unordered::detail::table;
           template <class N, class B> friend class c_iterator;
-          friend class boost::iterator_core_access;
 
           iterator(node_pointer p_, bucket_iterator itb_) : p(p_), itb(itb_) {}
 
@@ -1775,6 +1804,13 @@ namespace boost {
             return (p == x.p);
           }
 
+          bool equal(
+            const boost::unordered::detail::iterator_detail::c_iterator<Node,
+              Bucket>& x) const BOOST_NOEXCEPT
+          {
+            return (p == x.p);
+          }
+
           void increment() BOOST_NOEXCEPT
           {
             p = p->next;
@@ -1784,10 +1820,7 @@ namespace boost {
           }
         };
 
-        template <class Node, class Bucket>
-        class c_iterator
-            : public boost::iterator_facade<c_iterator<Node, Bucket>,
-                typename Node::value_type const, boost::forward_traversal_tag>
+        template <class Node, class Bucket> class c_iterator
         {
         public:
           typedef typename Node::value_type value_type;
@@ -1798,7 +1831,51 @@ namespace boost {
           typedef std::forward_iterator_tag iterator_category;
 
           c_iterator() : p(), itb(){};
-          c_iterator(iterator<Node, Bucket> it) : p(it.p), itb(it.itb){};
+          c_iterator(iterator<Node, Bucket> it) : p(it.p), itb(it.itb) {}
+
+          reference operator*() const BOOST_NOEXCEPT { return dereference(); }
+          pointer operator->() const BOOST_NOEXCEPT
+          {
+            pointer x = boost::addressof(p->value());
+            return x;
+          }
+
+          c_iterator& operator++() BOOST_NOEXCEPT
+          {
+            increment();
+            return *this;
+          }
+
+          c_iterator operator++(int) BOOST_NOEXCEPT
+          {
+            c_iterator old = *this;
+            increment();
+            return old;
+          }
+
+          bool operator==(c_iterator const& other) const BOOST_NOEXCEPT
+          {
+            return equal(other);
+          }
+
+          bool operator!=(c_iterator const& other) const BOOST_NOEXCEPT
+          {
+            return !equal(other);
+          }
+
+          bool operator==(
+            boost::unordered::detail::iterator_detail::iterator<Node,
+              Bucket> const& other) const BOOST_NOEXCEPT
+          {
+            return equal(other);
+          }
+
+          bool operator!=(
+            boost::unordered::detail::iterator_detail::iterator<Node,
+              Bucket> const& other) const BOOST_NOEXCEPT
+          {
+            return !equal(other);
+          }
 
         private:
           typedef typename Node::node_pointer node_pointer;
@@ -1808,7 +1885,7 @@ namespace boost {
           bucket_iterator itb;
 
           template <class Types> friend struct boost::unordered::detail::table;
-          friend class boost::iterator_core_access;
+          template <class, class> friend class iterator;
 
           c_iterator(node_pointer p_, bucket_iterator itb_) : p(p_), itb(itb_)
           {
@@ -1977,12 +2054,14 @@ namespace boost {
 
         std::size_t bucket_size(std::size_t index) const
         {
-          bucket_iterator itb = buckets_.at(index);
-          node_pointer n = itb->next;
           std::size_t count = 0;
-          while (n) {
-            ++count;
-            n = n->next;
+          if (size_ > 0) {
+            bucket_iterator itb = buckets_.at(index);
+            node_pointer n = itb->next;
+            while (n) {
+              ++count;
+              n = n->next;
+            }
           }
           return count;
         }
@@ -1992,13 +2071,18 @@ namespace boost {
 
         void recalculate_max_load()
         {
-          using namespace std;
-
           // From 6.3.1/13:
           // Only resize when size >= mlf_ * count
-          max_load_ = boost::unordered::detail::double_to_size(
-            floor(static_cast<double>(mlf_) *
-                 static_cast<double>(buckets_.bucket_count())));
+          std::size_t const bc = buckets_.bucket_count();
+
+          // it's important we do the `bc == 0` check here because the `mlf_`
+          // can be specified to be infinity. The operation `n * INF` is `INF`
+          // for all `n > 0` but NaN for `n == 0`.
+          //
+          max_load_ =
+            bc == 0 ? 0
+                    : boost::unordered::detail::double_to_size(
+                        static_cast<double>(mlf_) * static_cast<double>(bc));
         }
 
         void max_load_factor(float z)
@@ -2011,6 +2095,12 @@ namespace boost {
         ////////////////////////////////////////////////////////////////////////
         // Constructors
 
+        table()
+            : functions(hasher(), key_equal()), size_(0), mlf_(1.0f),
+              max_load_(0)
+        {
+        }
+
         table(std::size_t num_buckets, hasher const& hf, key_equal const& eq,
           node_allocator_type const& a)
             : functions(hf, eq), size_(0), mlf_(1.0f), max_load_(0),
@@ -2282,7 +2372,6 @@ namespace boost {
         template <typename UniqueType>
         void move_assign(table& x, UniqueType is_unique, false_type)
         {
-          reserve(x.size_);
           if (node_alloc() == x.node_alloc()) {
             move_assign_equal_alloc(x);
           } else {
@@ -2311,7 +2400,9 @@ namespace boost {
           {
             mlf_ = x.mlf_;
             recalculate_max_load();
-            this->reserve_for_insert(x.size_);
+            if (x.size_ > 0) {
+              this->reserve_for_insert(x.size_);
+            }
             this->clear_impl();
           }
           BOOST_CATCH(...)
@@ -2343,11 +2434,14 @@ namespace boost {
         node_pointer find_node_impl(
           Key const& x, bucket_iterator itb) const
         {
-          key_equal const& pred = this->key_eq();
-          node_pointer p = itb->next;
-          for (; p; p = p->next) {
-            if (pred(x, extractor::extract(p->value()))) {
-              break;
+          node_pointer p = node_pointer();
+          if (itb != buckets_.end()) {
+            key_equal const& pred = this->key_eq();
+            p = itb->next;
+            for (; p; p = p->next) {
+              if (pred(x, extractor::extract(p->value()))) {
+                break;
+              }
             }
           }
           return p;
@@ -2376,55 +2470,29 @@ namespace boost {
         inline iterator transparent_find(
           Key const& k, Hash const& h, Pred const& pred) const
         {
-#if 0
-          std::size_t const key_hash = h(k);
-          bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
-          for (node_pointer p = itb->next; p; p = p->next) {
-            if (BOOST_LIKELY(pred(k, extractor::extract(p->value())))) {
-              return iterator(p, itb);
-            }
-          }
-#else
-          std::size_t const key_hash = h(k);
-          bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
-
-          node_pointer p = itb->next;
-          if (p) {
-            for (;;) {
-              node_pointer p1 = p->next;
-              if (p1) {
-
-#if defined(BOOST_GCC)||defined(BOOST_CLANG)
-                __builtin_prefetch((const char*)p1, 0);
-#elif defined(BOOST_UNORDERED_SSE2_SUPPORTED)
-                _mm_prefetch((const char*)p1, _MM_HINT_T0);
-#endif  
-
-                if (BOOST_LIKELY(pred(k, extractor::extract(p->value())))) {
-                  return iterator(p, itb);
-                }
-                p = p1;
-              }
-              else{
-                if (BOOST_LIKELY(pred(k, extractor::extract(p->value())))) {
-                  return iterator(p, itb);
-                }
-                break;
+          if (size_ > 0) {
+            std::size_t const key_hash = h(k);
+            bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
+            for (node_pointer p = itb->next; p; p = p->next) {
+              if (BOOST_LIKELY(pred(k, extractor::extract(p->value())))) {
+                return iterator(p, itb);
               }
             }
           }
-#endif
+
           return this->end();
         }
 
         template <class Key>
         node_pointer* find_prev(Key const& key, bucket_iterator itb)
         {
-          key_equal pred = this->key_eq();
-          for (node_pointer* pp = boost::addressof(itb->next); *pp;
-               pp = boost::addressof((*pp)->next)) {
-            if (pred(key, extractor::extract((*pp)->value()))) {
-              return pp;
+          if (size_ > 0) {
+            key_equal pred = this->key_eq();
+            for (node_pointer* pp = boost::addressof(itb->next); *pp;
+                pp = boost::addressof((*pp)->next)) {
+              if (pred(key, extractor::extract((*pp)->value()))) {
+                return pp;
+              }
             }
           }
           typedef node_pointer* node_pointer_pointer;
@@ -2456,6 +2524,17 @@ namespace boost {
           new_buckets.insert_node(itnewb, p);
         }
 
+        static std::size_t min_buckets(std::size_t num_elements, float mlf)
+        {
+          std::size_t num_buckets = static_cast<std::size_t>(
+            std::ceil(static_cast<float>(num_elements) / mlf));
+
+          if (num_buckets == 0 && num_elements > 0) { // mlf == inf
+            num_buckets = 1;
+          }
+          return num_buckets;
+        }
+
         void rehash(std::size_t);
         void reserve(std::size_t);
         void reserve_for_insert(std::size_t);
@@ -2881,6 +2960,23 @@ namespace boost {
           return 1;
         }
 
+        iterator erase_node(c_iterator pos) {
+          c_iterator next = pos;
+          ++next;
+          
+          bucket_iterator itb = pos.itb;
+          node_pointer* pp = boost::addressof(itb->next);
+          while (*pp != pos.p) {
+            pp = boost::addressof((*pp)->next);
+          }
+
+          buckets_.extract_node_after(itb, pp);
+          this->delete_node(pos.p);
+          --size_;
+
+          return iterator(next.p, next.itb);
+        }
+
         iterator erase_nodes_range(c_iterator first, c_iterator last)
         {
           if (first == last) {
@@ -3347,22 +3443,18 @@ namespace boost {
       template <typename Types>
       inline void table<Types>::rehash(std::size_t num_buckets)
       {
-        std::size_t bc = (std::max)(num_buckets,
-          static_cast<std::size_t>(1.0f + static_cast<float>(size_) / mlf_));
+        num_buckets = (std::max)(
+          min_buckets(size_, mlf_), buckets_.bucket_count_for(num_buckets));
 
-        if (bc <= buckets_.bucket_count()) {
-          return;
+        if (num_buckets != this->bucket_count()) {
+          this->rehash_impl(num_buckets);
         }
-
-        this->rehash_impl(bc);
       }
 
       template <class Types>
       inline void table<Types>::reserve(std::size_t num_elements)
       {
-        std::size_t const num_buckets = static_cast<std::size_t>(
-          std::ceil(static_cast<float>(num_elements) / mlf_));
-
+        std::size_t num_buckets = min_buckets(num_elements, mlf_);
         this->rehash(num_buckets);
       }
 
@@ -3449,8 +3541,8 @@ namespace boost {
                   sizeof(choice2::type)
         };
 
-        typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE
-          then<Key const&, no_key>::type type;
+        typedef
+          typename boost::conditional<value, Key const&, no_key>::type type;
       };
 
       template <class ValueType> struct set_extractor

include/boost/unordered/detail/prime_fmod.hpp

@@ -0,0 +1,262 @@
+// Copyright (C) 2022 Joaquin M Lopez Munoz.
+// Copyright (C) 2022 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)
+
+#ifndef BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP
+#define BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP
+
+#include <boost/cstdint.hpp>
+#include <boost/preprocessor/seq/enum.hpp>
+#include <boost/preprocessor/seq/for_each.hpp>
+#include <boost/preprocessor/seq/size.hpp>
+
+#include <boost/config.hpp>
+
+#include <climits>
+#include <cstddef>
+
+#if defined(SIZE_MAX)
+#if ((((SIZE_MAX >> 16) >> 16) >> 16) >> 15) != 0
+#define BOOST_UNORDERED_FCA_HAS_64B_SIZE_T
+#endif
+#elif defined(UINTPTR_MAX) /* used as proxy for std::size_t */
+#if ((((UINTPTR_MAX >> 16) >> 16) >> 16) >> 15) != 0
+#define BOOST_UNORDERED_FCA_HAS_64B_SIZE_T
+#endif
+#endif
+
+#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) && defined(_MSC_VER)
+#include <intrin.h>
+#endif
+
+namespace boost {
+  namespace unordered {
+    namespace detail {
+      template <class = void> struct prime_fmod_size
+      {
+        // Because we compile for C++03, we don't have access to any inline
+        // initialization for array data members so the definitions must exist
+        // out-of-line. To keep the library header-only, we introduce a dummy
+        // template parameter which permits the definition to be included in
+        // multiple TUs without conflict.
+        //
+        static std::size_t sizes[];
+        static std::size_t const sizes_len;
+        static std::size_t (*positions[])(std::size_t);
+
+#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+        static boost::uint64_t inv_sizes32[];
+        static std::size_t const inv_sizes32_len;
+#endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
+
+        static inline std::size_t size_index(std::size_t n)
+        {
+          std::size_t i = 0;
+          for (; i < (sizes_len - 1); ++i) {
+            if (sizes[i] >= n) {
+              break;
+            }
+          }
+          return i;
+        }
+
+        static inline std::size_t size(std::size_t size_index)
+        {
+          return sizes[size_index];
+        }
+
+        template <std::size_t Size> static std::size_t modulo(std::size_t hash)
+        {
+          return hash % Size;
+        }
+
+#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+        // We emulate the techniques taken from:
+        // Faster Remainder by Direct Computation: Applications to Compilers and
+        // Software Libraries
+        // https://arxiv.org/abs/1902.01961
+        //
+        // In essence, use fancy math to directly calculate the remainder (aka
+        // modulo) exploiting how compilers transform division
+        //
+
+        static inline boost::uint64_t get_remainder(
+          boost::uint64_t fractional, boost::uint32_t d)
+        {
+#if defined(_MSC_VER)
+          // use MSVC intrinsics when available to avoid promotion to 128 bits
+
+          return __umulh(fractional, d);
+#elif defined(BOOST_HAS_INT128)
+          return static_cast<boost::uint64_t>(
+            ((boost::uint128_type)fractional * d) >> 64);
+#else
+          // portable implementation in the absence of boost::uint128_type on 64
+          // bits, which happens at least in GCC 4.5 and prior
+
+          boost::uint64_t r1 = (fractional & UINT32_MAX) * d;
+          boost::uint64_t r2 = (fractional >> 32) * d;
+          r2 += r1 >> 32;
+          return r2 >> 32;
+#endif /* defined(_MSC_VER) */
+        }
+
+        static inline boost::uint32_t fast_modulo(
+          boost::uint32_t a, boost::uint64_t M, boost::uint32_t d)
+        {
+          boost::uint64_t fractional = M * a;
+          return (boost::uint32_t)(get_remainder(fractional, d));
+        }
+#endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
+
+        static inline std::size_t position(
+          std::size_t hash, std::size_t size_index)
+        {
+#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+          std::size_t sizes_under_32bit = inv_sizes32_len;
+          if (BOOST_LIKELY(size_index < sizes_under_32bit)) {
+            return fast_modulo(
+              boost::uint32_t(hash) + boost::uint32_t(hash >> 32),
+              inv_sizes32[size_index], boost::uint32_t(sizes[size_index]));
+          } else {
+            return positions[size_index - sizes_under_32bit](hash);
+          }
+#else
+          return positions[size_index](hash);
+#endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
+        }
+      }; // prime_fmod_size
+
+#define BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT_INCOMPLETE                      \
+  (13ul)(29ul)(53ul)(97ul)(193ul)(389ul)(769ul)(1543ul)(3079ul)(6151ul)(       \
+    12289ul)(24593ul)(49157ul)(98317ul)(196613ul)(393241ul)(786433ul)(         \
+    1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul)(50331653ul)(      \
+    100663319ul)(201326611ul)(402653189ul)(805306457ul)(1610612741ul)(         \
+    3221225473ul)
+
+#if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+
+#define BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT                                 \
+  BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT_INCOMPLETE(4294967291ul)
+
+#define BOOST_UNORDERED_PRIME_FMOD_SIZES_64BIT
+
+#else
+
+#define BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT                                 \
+  BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT_INCOMPLETE
+
+// The original sequence here is this:
+// (6442450939ul)
+// (12884901893ul)
+// (25769803751ul)
+// (51539607551ul)
+// (103079215111ul)
+// (206158430209ul)
+// (412316860441ul)
+// (824633720831ul)
+// (1649267441651ul)
+//
+// but this causes problems on versions of mingw where the `long` type is 32
+// bits, even for 64-bit targets. We work around this by replacing the literals
+// with compile-time arithmetic, using bitshifts to reconstruct the number.
+//
+
+// clang-format off
+#define BOOST_UNORDERED_PRIME_FMOD_SIZES_64BIT                                   \
+  ((boost::ulong_long_type(1ul) << 32)   + boost::ulong_long_type(2147483643ul)) \
+  ((boost::ulong_long_type(3ul) << 32)   + boost::ulong_long_type(5ul))          \
+  ((boost::ulong_long_type(5ul) << 32)   + boost::ulong_long_type(4294967271ul)) \
+  ((boost::ulong_long_type(11ul) << 32)  + boost::ulong_long_type(4294967295ul)) \
+  ((boost::ulong_long_type(24ul) << 32)  + boost::ulong_long_type(7ul))          \
+  ((boost::ulong_long_type(48ul) << 32)  + boost::ulong_long_type(1ul))          \
+  ((boost::ulong_long_type(96ul) << 32)  + boost::ulong_long_type(25ul))         \
+  ((boost::ulong_long_type(191ul) << 32) + boost::ulong_long_type(4294967295ul)) \
+  ((boost::ulong_long_type(383ul) << 32) + boost::ulong_long_type(4294967283ul))
+      // clang-format on
+
+#endif /* BOOST_UNORDERED_FCA_HAS_64B_SIZE_T */
+
+#define BOOST_UNORDERED_PRIME_FMOD_SIZES                                       \
+  BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT BOOST_UNORDERED_PRIME_FMOD_SIZES_64BIT
+
+      template <class T>
+      std::size_t prime_fmod_size<T>::sizes[] = {
+        BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIME_FMOD_SIZES)};
+
+      template <class T>
+      std::size_t const prime_fmod_size<T>::sizes_len = BOOST_PP_SEQ_SIZE(
+        BOOST_UNORDERED_PRIME_FMOD_SIZES);
+
+// Similarly here, we have to re-express the integer initialization using
+// arithmetic such that each literal can fit in a 32-bit value.
+//
+#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+      // clang-format off
+        template <class T>
+        boost::uint64_t prime_fmod_size<T>::inv_sizes32[] = {
+          (boost::ulong_long_type(330382099ul) << 32) + boost::ulong_long_type(2973438898ul) /* = 1418980313362273202 */,
+          (boost::ulong_long_type(148102320ul) << 32) + boost::ulong_long_type(2369637129ul) /* = 636094623231363849 */,
+          (boost::ulong_long_type(81037118ul) << 32)  + boost::ulong_long_type(3403558990ul) /* = 348051774975651918 */,
+          (boost::ulong_long_type(44278013ul) << 32)  + boost::ulong_long_type(1549730468ul) /* = 190172619316593316 */,
+          (boost::ulong_long_type(22253716ul) << 32)  + boost::ulong_long_type(2403401389ul) /* = 95578984837873325 */,
+          (boost::ulong_long_type(11041047ul) << 32)  + boost::ulong_long_type(143533612ul)  /* = 47420935922132524 */,
+          (boost::ulong_long_type(5585133ul) << 32)   + boost::ulong_long_type(106117528ul)  /* = 23987963684927896 */,
+          (boost::ulong_long_type(2783517ul) << 32)   + boost::ulong_long_type(1572687312ul) /* = 11955116055547344 */,
+          (boost::ulong_long_type(1394922ul) << 32)   + boost::ulong_long_type(3428720239ul) /* = 5991147799191151 */,
+          (boost::ulong_long_type(698255ul) << 32)    + boost::ulong_long_type(552319807ul)  /* = 2998982941588287 */,
+          (boost::ulong_long_type(349496ul) << 32)    + boost::ulong_long_type(3827689953ul) /* = 1501077717772769 */,
+          (boost::ulong_long_type(174641ul) << 32)    + boost::ulong_long_type(3699438549ul) /* = 750081082979285 */,
+          (boost::ulong_long_type(87372ul) << 32)     + boost::ulong_long_type(1912757574ul) /* = 375261795343686 */,
+          (boost::ulong_long_type(43684ul) << 32)     + boost::ulong_long_type(3821029929ul) /* = 187625172388393 */,
+          (boost::ulong_long_type(21844ul) << 32)     + boost::ulong_long_type(3340590800ul) /* = 93822606204624 */,
+          (boost::ulong_long_type(10921ul) << 32)     + boost::ulong_long_type(4175852267ul) /* = 46909513691883 */,
+          (boost::ulong_long_type(5461ul) << 32)      + boost::ulong_long_type(1401829642ul) /* = 23456218233098 */,
+          (boost::ulong_long_type(2730ul) << 32)      + boost::ulong_long_type(2826028947ul) /* = 11728086747027 */,
+          (boost::ulong_long_type(1365ul) << 32)      + boost::ulong_long_type(1411150351ul) /* = 5864041509391 */,
+          (boost::ulong_long_type(682ul) << 32)       + boost::ulong_long_type(2857253105ul) /* = 2932024948977 */,
+          (boost::ulong_long_type(341ul) << 32)       + boost::ulong_long_type(1431073224ul) /* = 1466014921160 */,
+          (boost::ulong_long_type(170ul) << 32)       + boost::ulong_long_type(2862758116ul) /* = 733007198436 */,
+          (boost::ulong_long_type(85ul) << 32)        + boost::ulong_long_type(1431619357ul) /* = 366503839517 */,
+          (boost::ulong_long_type(42ul) << 32)        + boost::ulong_long_type(2863269661ul) /* = 183251896093 */,
+          (boost::ulong_long_type(21ul) << 32)        + boost::ulong_long_type(1431647119ul) /* = 91625960335 */,
+          (boost::ulong_long_type(10ul) << 32)        + boost::ulong_long_type(2863310962ul) /* = 45812983922 */,
+          (boost::ulong_long_type(5ul) << 32)         + boost::ulong_long_type(1431653234ul) /* = 22906489714 */,
+          (boost::ulong_long_type(2ul) << 32)         + boost::ulong_long_type(2863311496ul) /* = 11453246088 */,
+          (boost::ulong_long_type(1ul) << 32)         + boost::ulong_long_type(1431655764ul) /* = 5726623060 */,
+        };
+      // clang-format on
+
+      template <class T>
+      std::size_t const
+        prime_fmod_size<T>::inv_sizes32_len = sizeof(inv_sizes32) /
+                                              sizeof(inv_sizes32[0]);
+
+#endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */
+
+#define BOOST_UNORDERED_PRIME_FMOD_POSITIONS_ELEMENT(z, _, n)                  \
+  prime_fmod_size<T>::template modulo<n>,
+
+      template <class T>
+      std::size_t (*prime_fmod_size<T>::positions[])(std::size_t) = {
+#if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+        BOOST_PP_SEQ_FOR_EACH(BOOST_UNORDERED_PRIME_FMOD_POSITIONS_ELEMENT, ~,
+          BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT)
+#else
+        BOOST_PP_SEQ_FOR_EACH(BOOST_UNORDERED_PRIME_FMOD_POSITIONS_ELEMENT, ~,
+          BOOST_UNORDERED_PRIME_FMOD_SIZES_64BIT)
+#endif
+      };
+
+#undef BOOST_UNORDERED_PRIME_FMOD_POSITIONS_ELEMENT
+#undef BOOST_UNORDERED_PRIME_FMOD_SIZES
+#undef BOOST_UNORDERED_PRIME_FMOD_SIZES_64BIT
+#undef BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT
+#undef BOOST_UNORDERED_PRIME_FMOD_SIZES_32BIT_INCOMPLETE
+    } // namespace detail
+  }   // namespace unordered
+} // namespace boost
+
+#endif // BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP

include/boost/unordered/unordered_map.hpp

@@ -1664,8 +1664,6 @@ namespace boost {
 
     template <class K, class T, class H, class P, class A>
     unordered_map<K, T, H, P, A>::unordered_map()
-        : table_(boost::unordered::detail::default_bucket_count, hasher(),
-            key_equal(), allocator_type())
     {
     }
 
@@ -1856,18 +1854,14 @@ namespace boost {
     typename unordered_map<K, T, H, P, A>::iterator
     unordered_map<K, T, H, P, A>::erase(iterator position)
     {
-      const_iterator last = position;
-      ++last;
-      return table_.erase_nodes_range(position, last);
+      return table_.erase_node(position);
     }
 
     template <class K, class T, class H, class P, class A>
     typename unordered_map<K, T, H, P, A>::iterator
     unordered_map<K, T, H, P, A>::erase(const_iterator position)
     {
-      const_iterator last = position;
-      ++last;
-      return table_.erase_nodes_range(position, last);
+      return table_.erase_node(position);
     }
 
     template <class K, class T, class H, class P, class A>
@@ -2073,6 +2067,10 @@ namespace boost {
     template <class K, class T, class H, class P, class A>
     float unordered_map<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT
     {
+      if (table_.size_ == 0) {
+        return 0.0f;
+      }
+
       BOOST_ASSERT(table_.bucket_count() != 0);
       return static_cast<float>(table_.size_) /
              static_cast<float>(table_.bucket_count());
@@ -2147,8 +2145,6 @@ namespace boost {
 
     template <class K, class T, class H, class P, class A>
     unordered_multimap<K, T, H, P, A>::unordered_multimap()
-        : table_(boost::unordered::detail::default_bucket_count, hasher(),
-            key_equal(), allocator_type())
     {
     }
 
@@ -2340,9 +2336,7 @@ namespace boost {
     unordered_multimap<K, T, H, P, A>::erase(iterator position)
     {
       BOOST_ASSERT(position != this->end());
-      iterator next = position;
-      ++next;
-      return table_.erase_nodes_range(position, next);
+      return table_.erase_node(position);
     }
 
     template <class K, class T, class H, class P, class A>
@@ -2350,9 +2344,7 @@ namespace boost {
     unordered_multimap<K, T, H, P, A>::erase(const_iterator position)
     {
       BOOST_ASSERT(position != this->end());
-      const_iterator next = position;
-      ++next;
-      return table_.erase_nodes_range(position, next);
+      return table_.erase_node(position);
     }
 
     template <class K, class T, class H, class P, class A>
@@ -2514,6 +2506,10 @@ namespace boost {
     template <class K, class T, class H, class P, class A>
     float unordered_multimap<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT
     {
+      if (table_.size_ == 0) {
+        return 0.0f;
+      }
+
       BOOST_ASSERT(table_.bucket_count() != 0);
       return static_cast<float>(table_.size_) /
              static_cast<float>(table_.bucket_count());

include/boost/unordered/unordered_set.hpp

@@ -1266,8 +1266,6 @@ namespace boost {
     ////////////////////////////////////////////////////////////////////////////
     template <class T, class H, class P, class A>
     unordered_set<T, H, P, A>::unordered_set()
-        : table_(boost::unordered::detail::default_bucket_count, hasher(),
-            key_equal(), allocator_type())
     {
     }
 
@@ -1457,9 +1455,7 @@ namespace boost {
     typename unordered_set<T, H, P, A>::iterator
     unordered_set<T, H, P, A>::erase(const_iterator position)
     {
-      const_iterator last = position;
-      ++last;
-      return table_.erase_nodes_range(position, last);
+      return table_.erase_node(position);
     }
 
     template <class T, class H, class P, class A>
@@ -1588,6 +1584,10 @@ namespace boost {
     template <class T, class H, class P, class A>
     float unordered_set<T, H, P, A>::load_factor() const BOOST_NOEXCEPT
     {
+      if (table_.size_ == 0) {
+        return 0.0f;
+      }
+
       BOOST_ASSERT(table_.bucket_count() != 0);
       return static_cast<float>(table_.size_) /
              static_cast<float>(table_.bucket_count());
@@ -1662,8 +1662,6 @@ namespace boost {
 
     template <class T, class H, class P, class A>
     unordered_multiset<T, H, P, A>::unordered_multiset()
-        : table_(boost::unordered::detail::default_bucket_count, hasher(),
-            key_equal(), allocator_type())
     {
     }
 
@@ -1853,10 +1851,7 @@ namespace boost {
     unordered_multiset<T, H, P, A>::erase(const_iterator position)
     {
       BOOST_ASSERT(position != this->end());
-      iterator next = position;
-      ++next;
-      table_.erase_nodes_range(position, next);
-      return next;
+      return table_.erase_node(position);
     }
 
     template <class T, class H, class P, class A>
@@ -1991,6 +1986,10 @@ namespace boost {
     template <class T, class H, class P, class A>
     float unordered_multiset<T, H, P, A>::load_factor() const BOOST_NOEXCEPT
     {
+      if (table_.size_ == 0) {
+        return 0.0f;
+      }
+
       BOOST_ASSERT(table_.bucket_count() != 0);
       return static_cast<float>(table_.size_) /
              static_cast<float>(table_.bucket_count());

test/CMakeLists.txt

@@ -6,6 +6,12 @@ include(BoostTestJamfile OPTIONAL RESULT_VARIABLE HAVE_BOOST_TEST)
 
 if(HAVE_BOOST_TEST)
 
-boost_test_jamfile(FILE Jamfile.v2 LINK_LIBRARIES Boost::unordered Boost::core)
+boost_test_jamfile(
+  FILE Jamfile.v2 
+  LINK_LIBRARIES 
+    Boost::unordered 
+    Boost::core
+    Boost::concept_check
+)
 
 endif()

test/Jamfile.v2

@@ -24,11 +24,15 @@ project
         <toolset>clang:<cxxflags>$(clang-flags)
         <toolset>msvc:<cxxflags>$(msvc-flags)
 
+        <toolset>gcc-4.4:<cxxflags>-Wno-strict-aliasing
+        <toolset>gcc-4.4:<cxxflags>-fno-deduce-init-list
+
         <toolset>gcc:<warnings-as-errors>on
         <toolset>clang:<warnings-as-errors>on
         <toolset>msvc:<warnings-as-errors>on
     ;
 
+run unordered/prime_fmod_tests.cpp ;
 run unordered/fwd_set_test.cpp ;
 run unordered/fwd_map_test.cpp ;
 run unordered/allocator_traits.cpp ;

test/cmake_subdir_test/CMakeLists.txt

@@ -18,7 +18,6 @@ assert
 config
 container_hash
 core
-iterator
 move
 mp11
 predef
@@ -29,24 +28,10 @@ type_traits
 
 # Secondary dependencies
 
-static_assert
-concept_check
-conversion
 detail
-function_types
-fusion
-mpl
-optional
-smart_ptr
-utility
-winapi
-typeof
-functional
-io
-function
-bind
 integer
-type_index
+static_assert
+winapi
 )
 
 foreach(dep IN LISTS deps)

test/exception/insert_exception_tests.cpp

@@ -95,7 +95,7 @@ void insert_rehash_exception_test(
   T*, Inserter insert, test::random_generator gen)
 {
   for (int i = 0; i < 5; ++i) {
-    T x;
+    T x(1);
     rehash_prep(x);
 
     test::random_values<T> v2(5, gen);
@@ -393,7 +393,7 @@ template <typename T>
 void insert_range_rehash_exception_test(T*, test::random_generator gen)
 {
   for (int i = 0; i < 5; ++i) {
-    T x;
+    T x(1);
     rehash_prep(x);
 
     test::random_values<T> v2(5, gen);

test/helpers/random_values.hpp

@@ -9,8 +9,8 @@
 #include "./generators.hpp"
 #include "./list.hpp"
 #include "./metafunctions.hpp"
+#include <boost/type_traits/conditional.hpp>
 #include <algorithm>
-#include <boost/detail/select_type.hpp>
 
 namespace test {
   template <class X> struct unordered_generator_set
@@ -69,9 +69,8 @@ namespace test {
 
   template <class X>
   struct unordered_generator_base
-    : public boost::detail::if_true<test::is_set<X>::value>::
-        BOOST_NESTED_TEMPLATE then<test::unordered_generator_set<X>,
-          test::unordered_generator_map<X> >
+      : public boost::conditional<test::is_set<X>::value,
+          test::unordered_generator_set<X>, test::unordered_generator_map<X> >
   {
   };
 

test/unordered/assign_tests.cpp

@@ -45,6 +45,7 @@ namespace assign_tests {
       BOOST_TEST(x.empty());
       BOOST_TEST(test::equivalent(x.hash_function(), hf));
       BOOST_TEST(test::equivalent(x.key_eq(), eq));
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
     }
 
     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "assign_tests1.2\n";
@@ -94,6 +95,7 @@ namespace assign_tests {
       BOOST_TEST(test::equivalent(x1.key_eq(), eq1));
       BOOST_TEST(test::equivalent(x2.hash_function(), hf1));
       BOOST_TEST(test::equivalent(x2.key_eq(), eq1));
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
       test::check_container(x1, x2);
     }
 

test/unordered/constructor_tests.cpp

@@ -35,6 +35,7 @@ namespace constructor_tests {
 
       T x(0, hf, eq);
       BOOST_TEST(x.empty());
+      BOOST_TEST_EQ(x.bucket_count(), 0u);
       BOOST_TEST(test::equivalent(x.hash_function(), hf));
       BOOST_TEST(test::equivalent(x.key_eq(), eq));
       BOOST_TEST(test::equivalent(x.get_allocator(), al));
@@ -73,6 +74,7 @@ namespace constructor_tests {
 
       T x;
       BOOST_TEST(x.empty());
+      BOOST_TEST_EQ(x.bucket_count(), 0u);
       BOOST_TEST(test::equivalent(x.hash_function(), hf));
       BOOST_TEST(test::equivalent(x.key_eq(), eq));
       BOOST_TEST(test::equivalent(x.get_allocator(), al));
@@ -140,6 +142,7 @@ namespace constructor_tests {
 
       T x(0, hf, eq, al);
       BOOST_TEST(x.empty());
+      BOOST_TEST_EQ(x.bucket_count(), 0u);
       BOOST_TEST(test::equivalent(x.hash_function(), hf));
       BOOST_TEST(test::equivalent(x.key_eq(), eq));
       BOOST_TEST(test::equivalent(x.get_allocator(), al));
@@ -166,6 +169,7 @@ namespace constructor_tests {
 
       T x(al);
       BOOST_TEST(x.empty());
+      BOOST_TEST_EQ(x.bucket_count(), 0u);
       BOOST_TEST(test::equivalent(x.hash_function(), hf));
       BOOST_TEST(test::equivalent(x.key_eq(), eq));
       BOOST_TEST(test::equivalent(x.get_allocator(), al));
@@ -325,6 +329,7 @@ namespace constructor_tests {
 
       T x(list);
       BOOST_TEST(x.empty());
+      BOOST_TEST_EQ(x.bucket_count(), 0u);
       BOOST_TEST(test::equivalent(x.hash_function(), hf));
       BOOST_TEST(test::equivalent(x.key_eq(), eq));
       BOOST_TEST(test::equivalent(x.get_allocator(), al));
@@ -380,6 +385,104 @@ namespace constructor_tests {
 #endif
   }
 
+  template <class T>
+  void no_alloc_default_construct_test(T*, test::random_generator)
+  {
+    UNORDERED_SUB_TEST("Construct 1")
+    {
+      T x;
+      BOOST_TEST_EQ(x.bucket_count(), 0u);
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+    }
+
+    UNORDERED_SUB_TEST("Construct 2")
+    {
+      {
+        T x(0);
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+      }
+
+      {
+        T x(1);
+        BOOST_TEST_GT(x.bucket_count(), 0u);
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+      }
+    }
+
+    UNORDERED_SUB_TEST("Construct 3")
+    {
+      test::random_values<T> v;
+      T x(v.begin(), v.end());
+      BOOST_TEST_EQ(x.bucket_count(), 0u);
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+    }
+
+    UNORDERED_SUB_TEST("Construct 4")
+    {
+      {
+        test::random_values<T> v;
+        T x(v.begin(), v.end(), 0);
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+      }
+
+      {
+        test::random_values<T> v;
+        T x(v.begin(), v.end(), 1);
+        BOOST_TEST_GT(x.bucket_count(), 0u);
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+      }
+    }
+
+    UNORDERED_SUB_TEST("Construct 5")
+    {
+      typename T::allocator_type al;
+
+      {
+        T x(al);
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+      }
+    }
+
+    UNORDERED_SUB_TEST("Construct 6")
+    {
+      typename T::allocator_type al;
+
+      T x(0, al);
+      BOOST_TEST_EQ(x.bucket_count(), 0u);
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+    }
+
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+    UNORDERED_SUB_TEST("Initializer list 1")
+    {
+      std::initializer_list<typename T::value_type> list;
+      T x(list);
+      BOOST_TEST_EQ(x.bucket_count(), 0u);
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+    }
+
+    UNORDERED_SUB_TEST("Initializer list 2")
+    {
+      {
+        std::initializer_list<typename T::value_type> list;
+        T x(list, 0);
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+      }
+
+      {
+        std::initializer_list<typename T::value_type> list;
+        T x(list, 1);
+        BOOST_TEST_GT(x.bucket_count(), 0u);
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+      }
+    }
+#endif
+  }
+
   template <class T>
   void map_constructor_test(T*, test::random_generator const& generator)
   {
@@ -422,6 +525,10 @@ namespace constructor_tests {
     ((test_map_std_alloc)(test_map)(test_multimap))(
       (default_generator)(generate_collisions)(limited_range)))
 
+  UNORDERED_TEST(no_alloc_default_construct_test,
+    ((test_set)(test_multiset)(test_map)(test_multimap))(
+      (default_generator)(generate_collisions)(limited_range)))
+
 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 
   UNORDERED_AUTO_TEST (test_default_initializer_list) {

test/unordered/copy_tests.cpp

@@ -43,6 +43,23 @@ namespace copy_tests {
       BOOST_TEST(x.max_load_factor() == y.max_load_factor());
       BOOST_TEST(test::selected_count(y.get_allocator()) ==
                  (allocator_type::is_select_on_copy));
+      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::selected_count(y.get_allocator()) ==
+                 (allocator_type::is_select_on_copy));
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
       test::check_equivalent_keys(y);
     }
 
@@ -91,6 +108,22 @@ namespace copy_tests {
 
     typedef typename T::allocator_type allocator_type;
 
+    {
+      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::selected_count(y.get_allocator()) ==
+                 (allocator_type::is_select_on_copy));
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
+      test::check_equivalent_keys(y);
+    }
+
     {
       test::check_instances check_;
 
@@ -106,6 +139,21 @@ namespace copy_tests {
       test::check_equivalent_keys(y);
     }
 
+    {
+      test::check_instances check_;
+
+      T x(0, hf, eq, al);
+      T y(x, al2);
+      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(), al2));
+      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_;
 
@@ -120,6 +168,22 @@ namespace copy_tests {
       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::selected_count(y.get_allocator()) ==
+                 (allocator_type::is_select_on_copy));
+      BOOST_TEST(test::equivalent(y.get_allocator(), al));
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
+    }
+
     {
       test::check_instances check_;
 
@@ -135,6 +199,21 @@ namespace copy_tests {
       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, al2);
+      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(), al2));
+      BOOST_TEST(test::detail::tracker.count_allocations == 0);
+    }
+
     {
       test::check_instances check_;
 

test/unordered/erase_if.cpp

@@ -1,4 +1,4 @@
-// Copyright 2021 Christian Mazakas.
+// Copyright 2021-2022 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,9 +11,10 @@
 
 #include "../helpers/test.hpp"
 
+#include <boost/config.hpp>
 #include <string>
 
-#if BOOST_CXX_VERSION >= 201103L
+#if !defined(BOOST_NO_CXX11_REF_QUALIFIERS)
 #define UNORDERED_LVALUE_QUAL &
 #else
 #define UNORDERED_LVALUE_QUAL

test/unordered/move_tests.cpp

@@ -18,6 +18,9 @@
 #include "../helpers/equivalent.hpp"
 #include "../helpers/invariants.hpp"
 
+#include <boost/core/ignore_unused.hpp>
+#include <iterator>
+
 #if defined(BOOST_MSVC)
 #pragma warning(disable : 4127) // conditional expression is constant
 #endif
@@ -70,6 +73,10 @@ namespace move_tests {
       BOOST_TEST(test::equivalent(y.get_allocator(), al));
       BOOST_TEST(y.max_load_factor() == 1.0);
       test::check_equivalent_keys(y);
+#if defined(BOOST_UNORDERED_USE_MOVE) ||                                       \
+  !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+#endif
     }
 
     {
@@ -87,7 +94,7 @@ namespace move_tests {
   }
 
   template <class T>
-  void move_assign_tests1(T*, test::random_generator const& generator)
+  void move_assign_tests1(T* p, test::random_generator const& generator)
   {
     {
       test::check_instances check_;
@@ -98,6 +105,19 @@ namespace move_tests {
       y = create(v, count);
 #if BOOST_UNORDERED_TEST_MOVING && defined(BOOST_HAS_NRVO)
       BOOST_TEST(count == test::global_object_count);
+#endif
+      test::check_container(y, v);
+      test::check_equivalent_keys(y);
+    }
+
+    {
+      test::random_values<T> v;
+
+      T y;
+      y = empty(p);
+#if defined(BOOST_UNORDERED_USE_MOVE) ||                                       \
+  !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
 #endif
       test::check_container(y, v);
       test::check_equivalent_keys(y);
@@ -233,6 +253,32 @@ namespace move_tests {
 #endif
     }
 
+    {
+      test::random_values<T> v;
+      T y(0, hf, eq, al1);
+      T x(0, hf, eq, al2);
+      x.max_load_factor(0.25);
+
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+
+      y = boost::move(x);
+#if defined(BOOST_UNORDERED_USE_MOVE) ||                                       \
+  !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+#endif
+      test::check_container(y, v);
+      test::check_equivalent_keys(y);
+      BOOST_TEST(y.max_load_factor() == 0.25);
+
+      if (BOOST_UNORDERED_TEST_MOVING
+            ? (bool)allocator_type::is_propagate_on_move
+            : (bool)allocator_type::is_propagate_on_assign) {
+        BOOST_TEST(test::equivalent(y.get_allocator(), al2));
+      } else {
+        BOOST_TEST(test::equivalent(y.get_allocator(), al1));
+      }
+    }
+
     {
       test::check_instances check_;
 
@@ -298,17 +344,533 @@ namespace move_tests {
     }
   }
 
+  template <class T> T const& get_key(T const& t) { return t; }
+
+  template <class K, class V> K const& get_key(std::pair<K const, V> const& kv)
+  {
+    return kv.first;
+  }
+
+  template <class T> T const& get_value(T const& t) { return t; }
+
+  template <class K, class V> K const& get_value(std::pair<K const, V> const& kv)
+  {
+    return kv.second;
+  }
+
+  template <class T>
+  static void insert_range(T& y, test::random_values<T> const& v)
+  {
+    y.insert(v.begin(), v.end());
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T>
+  static void insert_single(T& y, test::random_values<T> const& v)
+  {
+    y.insert(*v.begin());
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T>
+  static void insert_single_hint(T& y, test::random_values<T> const& v)
+  {
+    y.insert(y.end(), *v.begin());
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T> struct insert_or_assign_invoker
+  {
+    void operator()(T&, test::random_values<T> const&) {}
+  };
+
+  template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+  struct insert_or_assign_invoker<
+    boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> >
+  {
+    void operator()(boost::unordered_map<Key, T, Hash, KeyEqual, Allocator>& y,
+      test::random_values<
+        boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> > const& v)
+    {
+      typedef typename boost::unordered_map<Key, T, Hash, KeyEqual,
+        Allocator>::size_type size_type;
+
+      y.insert_or_assign(get_key(*v.begin()), get_value(*v.begin()));
+      BOOST_TEST_EQ(
+        y.size(), static_cast<size_type>(std::distance(y.begin(), y.end())));
+    }
+  };
+
+  template <class T>
+  static void insert_or_assign(T& y, test::random_values<T> const& v)
+  {
+    insert_or_assign_invoker<T>()(y, v);
+  }
+
+  template <class T> struct insert_or_assign_hint_invoker
+  {
+    void operator()(T&, test::random_values<T> const&) {}
+  };
+
+  template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+  struct insert_or_assign_hint_invoker<
+    boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> >
+  {
+    void operator()(boost::unordered_map<Key, T, Hash, KeyEqual, Allocator>& y,
+      test::random_values<
+        boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> > const& v)
+    {
+      typedef typename boost::unordered_map<Key, T, Hash, KeyEqual,
+        Allocator>::size_type size_type;
+      y.insert_or_assign(y.end(), get_key(*v.begin()), get_value(*v.begin()));
+      BOOST_TEST_EQ(
+        y.size(), static_cast<size_type>(std::distance(y.begin(), y.end())));
+    }
+  };
+
+  template <class T>
+  static void insert_or_assign_hint(T& y, test::random_values<T> const& v)
+  {
+    insert_or_assign_hint_invoker<T>()(y, v);
+  }
+
+  template <class T> struct try_emplace_invoker
+  {
+    void operator()(T&, test::random_values<T> const&) {}
+  };
+
+  template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+  struct try_emplace_invoker<
+    boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> >
+  {
+    void operator()(boost::unordered_map<Key, T, Hash, KeyEqual, Allocator>& y,
+      test::random_values<
+        boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> > const& v)
+    {
+      typedef typename boost::unordered_map<Key, T, Hash, KeyEqual,
+        Allocator>::size_type size_type;
+      y.try_emplace(get_key(*v.begin()), get_value(*v.begin()));
+      BOOST_TEST_EQ(
+        y.size(), static_cast<size_type>(std::distance(y.begin(), y.end())));
+    }
+  };
+
+  template <class T>
+  static void try_emplace(T& y, test::random_values<T> const& v)
+  {
+    try_emplace_invoker<T>()(y, v);
+  }
+
+  template <class T> struct try_emplace_hint_invoker
+  {
+    void operator()(T&, test::random_values<T> const&) {}
+  };
+
+  template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+  struct try_emplace_hint_invoker<
+    boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> >
+  {
+    void operator()(boost::unordered_map<Key, T, Hash, KeyEqual, Allocator>& y,
+      test::random_values<
+        boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> > const& v)
+    {
+      typedef typename boost::unordered_map<Key, T, Hash, KeyEqual,
+        Allocator>::size_type size_type;
+      y.try_emplace(y.end(), get_key(*v.begin()), get_value(*v.begin()));
+      BOOST_TEST_EQ(
+        y.size(), static_cast<size_type>(std::distance(y.begin(), y.end())));
+    }
+  };
+
+  template <class T>
+  static void try_emplace_hint(T& y, test::random_values<T> const& v)
+  {
+    try_emplace_hint_invoker<T>()(y, v);
+  }
+
+  template <class T> struct at_invoker
+  {
+    void operator()(T&, test::random_values<T> const&) {}
+  };
+
+  template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+  struct at_invoker<boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> >
+  {
+    void operator()(boost::unordered_map<Key, T, Hash, KeyEqual, Allocator>& y,
+      test::random_values<
+        boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> > const& v)
+    {
+      BOOST_TRY { y.at(get_key(*v.begin())); }
+      BOOST_CATCH(...) {}
+      BOOST_CATCH_END
+    }
+  };
+
+  template <class T> static void at(T& y, test::random_values<T> const& v)
+  {
+    at_invoker<T>()(y, v);
+  }
+
+  template <class T> struct index_operator_invoker
+  {
+    void operator()(T&, test::random_values<T> const&) {}
+  };
+
+  template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+  struct index_operator_invoker<
+    boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> >
+  {
+    void operator()(boost::unordered_map<Key, T, Hash, KeyEqual, Allocator>& y,
+      test::random_values<
+        boost::unordered_map<Key, T, Hash, KeyEqual, Allocator> > const& v)
+    {
+      typedef typename boost::unordered_map<Key, T, Hash, KeyEqual,
+        Allocator>::size_type size_type;
+      y[get_key(*v.begin())] = get_value(*v.begin());
+      BOOST_TEST_EQ(
+        y.size(), static_cast<size_type>(std::distance(y.begin(), y.end())));
+    }
+  };
+
+  template <class T>
+  static void index_operator(T& y, test::random_values<T> const& v)
+  {
+    index_operator_invoker<T>()(y, v);
+  }
+
+  template <class T> static void clear(T& y, test::random_values<T> const&)
+  {
+    y.clear();
+    BOOST_TEST(y.empty());
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T> static void capacity(T& y, test::random_values<T> const&)
+  {
+    (void)y.empty();
+    (void)y.size();
+    (void)y.max_size();
+    (void)y.load_factor();
+    (void)y.max_load_factor();
+    (void)y.hash_function();
+    (void)y.key_eq();
+    (void)y.get_allocator();
+  }
+
+  template <class T> static void iterators(T& y, test::random_values<T> const&)
+  {
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T>
+  static void erase_range(T& y, test::random_values<T> const&)
+  {
+    y.erase(y.begin(), y.end());
+    BOOST_TEST(y.empty());
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T>
+  static void erase_key(T& y, test::random_values<T> const& v)
+  {
+    y.erase(get_key(*v.begin()));
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T> static void lookup(T& y, test::random_values<T> const& v)
+  {
+    (void)y.count(get_key(*v.begin()));
+    (void)y.find(get_key(*v.begin()));
+    (void)y.contains(get_key(*v.begin()));
+    (void)y.equal_range(get_key(*v.begin()));
+  }
+
+  template <class T> static void reserve(T& y, test::random_values<T> const&)
+  {
+    y.reserve(1337);
+    BOOST_TEST_GT(y.bucket_count(), 1337u);
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T>
+  static void copy_assignment(T& y, test::random_values<T> const& v)
+  {
+    T x(v.begin(), v.end());
+    y = x;
+    BOOST_TEST_EQ(y.size(), x.size());
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T>
+  static void move_assignment(T& y, test::random_values<T> const& v)
+  {
+    T x(v.begin(), v.end());
+    std::size_t const size = x.size();
+    y = boost::move(x);
+    BOOST_TEST_GE(y.size(), size);
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T> static void equal(T& y, test::random_values<T> const& v)
+  {
+    T x(v.begin(), v.end());
+    (void)(y == x);
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T> static void extract(T& y, test::random_values<T> const& v)
+  {
+    (void)y.extract(get_key(*v.begin()));
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T> static void merge(T& y, test::random_values<T> const& v)
+  {
+    T x(v.begin(), v.end());
+    if (y.get_allocator() == x.get_allocator()) {
+      y.merge(x);
+    }
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class X> bool pred(X const&) { return true; }
+
+  template <class T>
+  static void erase_with_pred(T& y, test::random_values<T> const&)
+  {
+    erase_if(y, pred<typename T::value_type>);
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T>
+  static void container_swap(T& y, test::random_values<T> const& v)
+  {
+    T x(v.begin(), v.end());
+    if (boost::allocator_propagate_on_container_swap<
+          typename T::allocator_type>::type::value ||
+        x.get_allocator() == y.get_allocator()) {
+      y.swap(x);
+    }
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+  }
+
+  template <class T> static void buckets(T& y, test::random_values<T> const& v)
+  {
+    (void)y.begin(0);
+    (void)y.end(0);
+    (void)y.bucket_count();
+    (void)y.max_bucket_count();
+    (void)y.bucket_size(0);
+    (void)y.bucket(get_key(*v.begin()));
+  }
+
+  template <class T>
+  static void double_move_construct(T& y, test::random_values<T> const&)
+  {
+    T x = boost::move(y);
+    x.clear();
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+    BOOST_TEST_EQ(x.size(),
+      static_cast<typename T::size_type>(std::distance(x.begin(), x.end())));
+  }
+
+  template <class T>
+  static void double_move_assign(T& y, test::random_values<T> const&)
+  {
+    T x;
+    x = boost::move(y);
+    x.clear();
+    BOOST_TEST_EQ(y.size(),
+      static_cast<typename T::size_type>(std::distance(y.begin(), y.end())));
+    BOOST_TEST_EQ(x.size(),
+      static_cast<typename T::size_type>(std::distance(x.begin(), x.end())));
+  }
+
+  template <class T>
+  static void post_move_tests(T* ptr, test::random_generator const& generator)
+  {
+    // clang-format off
+    void (*fps[])(T&, test::random_values<T> const&) = {
+      insert_range<T>,
+      insert_single<T>,
+      insert_single_hint<T>,
+      insert_or_assign<T>,
+      insert_or_assign_hint<T>,
+      try_emplace<T>,
+      try_emplace_hint<T>,
+      at<T>,
+      index_operator<T>,
+      clear<T>,
+      capacity<T>,
+      iterators<T>,
+      erase_range<T>,
+      erase_key<T>,
+      lookup<T>,
+      reserve<T>,
+      copy_assignment<T>,
+      move_assignment<T>,
+      equal<T>,
+      extract<T>,
+      merge<T>,
+      erase_with_pred<T>,
+      container_swap<T>,
+      buckets<T>,
+      double_move_construct<T>,
+      double_move_assign<T>
+    };
+    // clang-format on
+
+    std::size_t const len = (sizeof(fps) / sizeof(*(fps)));
+
+    for (std::size_t i = 0; i < len; ++i) {
+      test::check_instances check_;
+
+      test::random_values<T> const v(1000, generator);
+      test::object_count count;
+      T y(create(v, count));
+
+      unsigned num_allocs = test::detail::tracker.count_allocations;
+      (void)num_allocs;
+
+      T x(boost::move(y));
+
+#if defined(BOOST_UNORDERED_USE_MOVE) ||                                       \
+  !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+      BOOST_TEST(y.empty());
+      BOOST_TEST(y.begin() == y.end());
+      BOOST_TEST_EQ(y.bucket_count(), 0u);
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, num_allocs);
+#endif
+
+      fps[i](y, v);
+
+      test::check_container(x, v);
+      test::check_equivalent_keys(x);
+    }
+
+    for (std::size_t i = 0; i < len; ++i) {
+      typename T::hasher hf(1);
+      typename T::key_equal eq(1);
+      typename T::allocator_type al1(1);
+      typename T::allocator_type al2(2);
+
+      test::check_instances check_;
+
+      test::random_values<T> v(1000, generator);
+      test::object_count count;
+      T y(v.begin(), v.end(), 0, hf, eq, al1);
+      T x(boost::move(y), al2);
+
+      BOOST_TEST_NOT(y.empty());
+      BOOST_TEST(y.begin() != y.end());
+
+      fps[i](y, v);
+
+      test::check_container(x, v);
+      test::check_equivalent_keys(x);
+    }
+
+    for (std::size_t i = 0; i < len; ++i) {
+      test::check_instances check_;
+
+      test::random_values<T> v(1000, generator);
+      test::object_count count;
+      T y(create(v, count));
+
+      unsigned num_allocs = test::detail::tracker.count_allocations;
+      (void)num_allocs;
+
+      T x(empty(ptr));
+      x = boost::move(y);
+
+#if defined(BOOST_UNORDERED_USE_MOVE) ||                                       \
+  !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+      BOOST_TEST(y.empty());
+      BOOST_TEST(y.begin() == y.end());
+      BOOST_TEST_EQ(y.bucket_count(), 0u);
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, num_allocs);
+#endif
+
+      fps[i](y, v);
+
+      test::check_container(x, v);
+      test::check_equivalent_keys(x);
+    }
+
+    for (std::size_t i = 0; i < len; ++i) {
+      typename T::hasher hf(1);
+      typename T::key_equal eq(1);
+      typename T::allocator_type al1(1);
+      typename T::allocator_type al2(2);
+
+      test::check_instances check_;
+
+      test::random_values<T> v(1000, generator);
+      test::object_count count;
+      T y(v.begin(), v.end(), 0, hf, eq, al1);
+
+      unsigned num_allocs = test::detail::tracker.count_allocations;
+      (void)num_allocs;
+
+      T x(al2);
+      x = boost::move(y);
+
+      bool b = boost::allocator_propagate_on_container_move_assignment<
+        typename T::allocator_type>::type::value;
+      if (b) {
+#if defined(BOOST_UNORDERED_USE_MOVE) ||                                       \
+  !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+        BOOST_TEST(y.empty());
+        BOOST_TEST(y.begin() == y.end());
+        BOOST_TEST_EQ(y.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, num_allocs);
+#else
+        BOOST_TEST_NOT(y.empty());
+        BOOST_TEST(y.begin() != y.end());
+
+#endif
+      } else {
+        BOOST_TEST_NOT(y.empty());
+        BOOST_TEST(y.begin() != y.end());
+      }
+
+      fps[i](y, v);
+
+      test::check_container(x, v);
+      test::check_equivalent_keys(x);
+    }
+  }
+
   boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
-    std::allocator<test::object> >* test_map_std_alloc;
+    std::allocator<std::pair<test::object const, test::object> > >*
+    test_map_std_alloc;
 
   boost::unordered_set<test::object, test::hash, test::equal_to,
     test::allocator2<test::object> >* test_set;
   boost::unordered_multiset<test::object, test::hash, test::equal_to,
     test::allocator1<test::object> >* test_multiset;
   boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
-    test::allocator1<test::object> >* test_map;
+    test::allocator1<std::pair<test::object const, test::object> > >* test_map;
   boost::unordered_multimap<test::object, test::object, test::hash,
-    test::equal_to, test::allocator2<test::object> >* test_multimap;
+    test::equal_to,
+    test::allocator2<std::pair<test::object const, test::object> > >*
+    test_multimap;
 
   boost::unordered_set<test::object, test::hash, test::equal_to,
     test::cxx11_allocator<test::object, test::propagate_move> >*
@@ -317,11 +879,12 @@ namespace move_tests {
     test::cxx11_allocator<test::object, test::propagate_move> >*
     test_multiset_prop_move;
   boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
-    test::cxx11_allocator<test::object, test::propagate_move> >*
-    test_map_prop_move;
+    test::cxx11_allocator<std::pair<test::object const, test::object>,
+      test::propagate_move> >* test_map_prop_move;
   boost::unordered_multimap<test::object, test::object, test::hash,
-    test::equal_to, test::cxx11_allocator<test::object, test::propagate_move> >*
-    test_multimap_prop_move;
+    test::equal_to,
+    test::cxx11_allocator<std::pair<test::object const, test::object>,
+      test::propagate_move> >* test_multimap_prop_move;
 
   boost::unordered_set<test::object, test::hash, test::equal_to,
     test::cxx11_allocator<test::object, test::no_propagate_move> >*
@@ -330,12 +893,12 @@ namespace move_tests {
     test::cxx11_allocator<test::object, test::no_propagate_move> >*
     test_multiset_no_prop_move;
   boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
-    test::cxx11_allocator<test::object, test::no_propagate_move> >*
-    test_map_no_prop_move;
+    test::cxx11_allocator<std::pair<test::object const, test::object>,
+      test::no_propagate_move> >* test_map_no_prop_move;
   boost::unordered_multimap<test::object, test::object, test::hash,
     test::equal_to,
-    test::cxx11_allocator<test::object, test::no_propagate_move> >*
-    test_multimap_no_prop_move;
+    test::cxx11_allocator<std::pair<test::object const, test::object>,
+      test::no_propagate_move> >* test_multimap_no_prop_move;
 
   using test::default_generator;
   using test::generate_collisions;
@@ -367,6 +930,12 @@ namespace move_tests {
       test_set_no_prop_move)(test_multiset_no_prop_move)(test_map_no_prop_move)(
       test_multimap_no_prop_move))(
       (default_generator)(generate_collisions)(limited_range)))
+  UNORDERED_TEST(post_move_tests,
+    ((test_set)(test_multiset)(test_map)(test_multimap)(test_set_prop_move)(
+      test_multiset_prop_move)(test_map_prop_move)(test_multimap_prop_move)(
+      test_set_no_prop_move)(test_multiset_no_prop_move)(test_map_no_prop_move)(
+      test_multimap_no_prop_move))(
+      (default_generator)(generate_collisions)(limited_range)))
 }
 
 RUN_TESTS()

test/unordered/noexcept_tests.cpp

@@ -11,6 +11,7 @@
 // clang-format on
 
 #include "../helpers/test.hpp"
+#include "../helpers/fwd.hpp"
 
 #if defined(BOOST_MSVC)
 #pragma warning(push)
@@ -189,7 +190,8 @@ namespace noexcept_tests {
 
 #if !defined(BOOST_NO_SFINAE_EXPR) && !defined(BOOST_NO_CXX11_NOEXCEPT) &&     \
   !defined(BOOST_NO_CXX11_DECLTYPE) &&                                         \
-  !defined(BOOST_NO_CXX11_FUNCTION_TEMPLATE_DEFAULT_ARGS)
+  !defined(BOOST_NO_CXX11_FUNCTION_TEMPLATE_DEFAULT_ARGS) &&                   \
+  !BOOST_WORKAROUND(BOOST_GCC_VERSION, < 40700)
     BOOST_TEST(have_is_nothrow_swap);
 #endif
 
@@ -246,37 +248,65 @@ namespace noexcept_tests {
     throwing_test_exception = false;
   }
 
-  UNORDERED_AUTO_TEST (test_nothrow_move_assign_when_noexcept) {
-    typedef boost::unordered_set<int, hash_nothrow_move_assign,
-      equal_to_nothrow_move_assign>
-      throwing_set;
+  template <class T>
+  void test_nothrow_move_assign_when_noexcept(T*, test::random_generator const&)
+  {
+    {
+      if (have_is_nothrow_move_assign) {
+        BOOST_TEST(boost::is_nothrow_move_assignable<T>::value);
+      }
 
-    if (have_is_nothrow_move_assign) {
-      BOOST_TEST(boost::is_nothrow_move_assignable<throwing_set>::value);
+      throwing_test_exception = false;
+
+      T x1;
+      T x2;
+      x1.insert(10);
+      x1.insert(50);
+      for (int i = 0; i < 100; ++i) {
+        x2.insert(i);
+      }
+
+      try {
+        throwing_test_exception = true;
+
+        x2 = boost::move(x1);
+        BOOST_TEST(x2.size() == 2);
+        BOOST_TEST(*x2.begin() == 10 || *x2.begin() == 50);
+        BOOST_TEST(have_is_nothrow_move_assign);
+      } catch (test_exception) {
+        BOOST_TEST(!have_is_nothrow_move_assign);
+      }
+
+      throwing_test_exception = false;
     }
 
-    throwing_test_exception = false;
+    {
+      if (have_is_nothrow_move_assign) {
+        BOOST_TEST(boost::is_nothrow_move_assignable<T>::value);
+      }
 
-    throwing_set x1;
-    throwing_set x2;
-    x1.insert(10);
-    x1.insert(50);
-    for (int i = 0; i < 100; ++i) {
-      x2.insert(i);
+      throwing_test_exception = false;
+
+      T x1;
+      T x2;
+      x1.insert(10);
+      x1.insert(50);
+      for (int i = 0; i < 100; ++i) {
+        x2.insert(i);
+      }
+
+      try {
+        throwing_test_exception = true;
+
+        x1 = boost::move(x2);
+        BOOST_TEST(x1.size() == 100);
+        BOOST_TEST(have_is_nothrow_move_assign);
+      } catch (test_exception) {
+        BOOST_TEST(!have_is_nothrow_move_assign);
+      }
+
+      throwing_test_exception = false;
     }
-
-    try {
-      throwing_test_exception = true;
-
-      x2 = boost::move(x1);
-      BOOST_TEST(x2.size() == 2);
-      BOOST_TEST(*x2.begin() == 10 || *x2.begin() == 50);
-      BOOST_TEST(have_is_nothrow_move_assign);
-    } catch (test_exception) {
-      BOOST_TEST(!have_is_nothrow_move_assign);
-    }
-
-    throwing_test_exception = false;
   }
 
   UNORDERED_AUTO_TEST (test_nothrow_swap_when_noexcept) {
@@ -317,4 +347,80 @@ namespace noexcept_tests {
 #pragma warning(pop)
 #endif
 
+template <class T> class allocator1
+{
+  BOOST_COPYABLE_AND_MOVABLE(allocator1)
+  allocator1 operator=(BOOST_COPY_ASSIGN_REF(allocator1));
+  allocator1 operator=(BOOST_RV_REF(allocator1));
+
+public:
+  typedef T value_type;
+
+  allocator1() {}
+  allocator1(allocator1 const&) {}
+
+  template <class U> allocator1(allocator1<U> const&) {}
+
+  T* allocate(std::size_t n)
+  {
+    noexcept_tests::test_throw("Allocate");
+    return static_cast<T*>(::operator new(n * sizeof(T)));
+  }
+
+  void deallocate(T* p, std::size_t) { ::operator delete(p); }
+
+  friend bool operator==(allocator1 const&, allocator1 const&) { return true; }
+  friend bool operator!=(allocator1 const&, allocator1 const&) { return false; }
+};
+
+template <class T> class allocator2
+{
+  BOOST_COPYABLE_AND_MOVABLE(allocator2)
+  allocator2 operator=(BOOST_COPY_ASSIGN_REF(allocator2));
+public:
+  typedef T value_type;
+  typedef boost::true_type propagate_on_container_move_assignment;
+
+  allocator2() {}
+  allocator2(allocator2 const&) {}
+
+  template <class U> allocator2(allocator2<U> const&) {}
+
+  allocator2& operator=(BOOST_RV_REF(allocator2)) { return *this; }
+
+  T* allocate(std::size_t n)
+  {
+    noexcept_tests::test_throw("Allocate");
+    return static_cast<T*>(::operator new(n * sizeof(T)));
+  }
+
+  void deallocate(T* p, std::size_t) { ::operator delete(p); }
+
+  friend bool operator==(allocator2 const&, allocator2 const&) { return true; }
+  friend bool operator!=(allocator2 const&, allocator2 const&) { return false; }
+};
+
+UNORDERED_AUTO_TEST (prelim_allocator_checks) {
+  BOOST_TEST(boost::allocator_is_always_equal<allocator1<int> >::type::value);
+  BOOST_TEST(!boost::allocator_propagate_on_container_move_assignment<
+             allocator1<int> >::type::value);
+
+  BOOST_TEST(boost::allocator_is_always_equal<allocator2<int> >::type::value);
+  BOOST_TEST(boost::allocator_propagate_on_container_move_assignment<
+             allocator2<int> >::type::value);
+}
+
+boost::unordered_set<int, noexcept_tests::hash_nothrow_move_assign,
+  noexcept_tests::equal_to_nothrow_move_assign, allocator1<int> >*
+  throwing_set_alloc1;
+
+boost::unordered_set<int, noexcept_tests::hash_nothrow_move_assign,
+  noexcept_tests::equal_to_nothrow_move_assign, allocator2<int> >*
+  throwing_set_alloc2;
+
+using test::default_generator;
+
+UNORDERED_TEST(test_nothrow_move_assign_when_noexcept,
+  ((throwing_set_alloc1)(throwing_set_alloc2))((default_generator)))
+
 RUN_TESTS()

test/unordered/prime_fmod_tests.cpp

@@ -0,0 +1,215 @@
+// Copyright 2022 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 <boost/unordered/detail/prime_fmod.hpp>
+
+#include <boost/core/detail/splitmix64.hpp>
+#include <boost/core/lightweight_test.hpp>
+
+#include <limits>
+
+#if defined(BOOST_MSVC)
+// conditional expression is constant
+#pragma warning(disable : 4127)
+#endif
+
+void macros_test()
+{
+  if (std::numeric_limits<std::size_t>::digits >= 64) {
+#if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+    BOOST_ERROR("std::numeric_limits<size_t>::digits >= 64, but "
+                "BOOST_UNORDERED_FCA_HAS_64B_SIZE_T is not defined");
+#endif
+  }
+  else {
+#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+    BOOST_ERROR("std::numeric_limits<size_t>::digits < 64, but "
+                "BOOST_UNORDERED_FCA_HAS_64B_SIZE_T is defined");
+#endif
+  }
+}
+
+// Pretty inefficient, but the test is fast enough.
+// Might be too slow if we had larger primes?
+bool is_prime(std::size_t x)
+{
+  if (x == 2) {
+    return true;
+  }
+
+  if (x == 1 || x % 2 == 0) {
+    return false;
+  }
+
+  // y*y <= x is susceptible to overflow, so instead make sure to use y <= (x/y)
+  for (std::size_t y = 3; y <= (x / y); y += 2) {
+    if (x % y == 0) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+void prime_sizes_test()
+{
+  // just some basic sanity checks
+  //
+  BOOST_TEST(!is_prime(0));
+  BOOST_TEST(!is_prime(1));
+  BOOST_TEST(is_prime(2));
+  BOOST_TEST(is_prime(3));
+  BOOST_TEST(is_prime(13));
+  BOOST_TEST(!is_prime(4));
+  BOOST_TEST(!is_prime(100));
+  BOOST_TEST(!is_prime(49));
+
+  std::size_t* sizes = boost::unordered::detail::prime_fmod_size<>::sizes;
+  std::size_t sizes_len =
+    boost::unordered::detail::prime_fmod_size<>::sizes_len;
+
+  // prove every number in our sizes array is prime
+  //
+  BOOST_TEST_GT(sizes_len, 0u);
+
+  for (std::size_t i = 0; i < sizes_len; ++i) {
+    BOOST_TEST(is_prime(sizes[i]));
+  }
+
+  // prove that every subsequent number in the sequence is larger than the
+  // previous
+  //
+  for (std::size_t i = 1; i < sizes_len; ++i) {
+    BOOST_TEST_GT(sizes[i], sizes[i - 1]);
+  }
+
+#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+  // now we wish to prove that if we do have the reciprocals stored, we have the
+  // correct amount of them, i.e. one for every entry in sizes[] that fits in 32
+  // bits
+  //
+  boost::uint64_t* inv_sizes32 =
+    boost::unordered::detail::prime_fmod_size<>::inv_sizes32;
+
+  std::size_t inv_sizes32_len =
+    boost::unordered::detail::prime_fmod_size<>::inv_sizes32_len;
+
+  std::size_t count = 0;
+  for (std::size_t i = 0; i < sizes_len; ++i) {
+    if (sizes[i] <= UINT32_MAX) {
+      ++count;
+    }
+  }
+
+  BOOST_TEST_GT(inv_sizes32_len, 0u);
+  BOOST_TEST_EQ(inv_sizes32_len, count);
+
+  // these values should also be monotonically decreasing
+  //
+  for (std::size_t i = 1; i < inv_sizes32_len; ++i) {
+    BOOST_TEST_LT(inv_sizes32[i], inv_sizes32[i - 1]);
+  }
+
+  // now make sure the values in inv_sizes32 are what they should be as derived
+  // from the paper
+  //
+  for (std::size_t i = 0; i < inv_sizes32_len; ++i) {
+    std::size_t const size = sizes[i];
+    BOOST_TEST_LE(size, UINT_MAX);
+
+    boost::uint32_t d = static_cast<boost::uint32_t>(sizes[i]);
+    boost::uint64_t M = ((boost::ulong_long_type(0xffffffff) << 32) +
+                          boost::ulong_long_type(0xffffffff)) /
+                          d +
+                        1;
+
+    BOOST_TEST_EQ(inv_sizes32[i], M);
+  }
+#endif
+}
+
+void get_remainder_test()
+{
+#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+  struct
+  {
+    // boost::unordered::detail::prime_fmod_size<>::get_remainder
+    // uses several internal implementations depending on the availability of
+    // certain intrinsics or 128 bit integer support, defaulting to a slow,
+    // portable routine. The following is a transcription of the portable
+    // routine used here for verification purposes.
+    //
+    boost::uint64_t operator()(boost::uint64_t f, boost::uint32_t d)
+    {
+      boost::uint64_t r1 = (f & UINT32_MAX) * d;
+      boost::uint64_t r2 = (f >> 32) * d;
+
+      r2 += r1 >> 32;
+
+      return r2 >> 32;
+    }
+  } get_remainder;
+
+  boost::detail::splitmix64 rng;
+
+  for (std::size_t i = 0; i < 1000000u; ++i) {
+    boost::uint64_t f = rng();
+    boost::uint32_t d = static_cast<uint32_t>(rng());
+
+    boost::uint64_t r1 =
+      boost::unordered::detail::prime_fmod_size<>::get_remainder(f, d);
+
+    boost::uint64_t r2 = get_remainder(f, d);
+
+    if (!BOOST_TEST_EQ(r1, r2)) {
+      std::cerr << "f: " << f << ", d: " << d << std::endl;
+      return;
+    }
+  }
+#endif
+}
+
+void modulo_test()
+{
+  std::size_t* sizes = boost::unordered::detail::prime_fmod_size<>::sizes;
+
+  std::size_t const sizes_len =
+    boost::unordered::detail::prime_fmod_size<>::sizes_len;
+
+  boost::detail::splitmix64 rng;
+
+  for (std::size_t i = 0; i < 1000000u; ++i) {
+    std::size_t hash = static_cast<std::size_t>(rng());
+
+    for (std::size_t j = 0; j < sizes_len; ++j) {
+      std::size_t h = hash;
+
+#if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
+      if (sizes[j] <= UINT_MAX) {
+        h = boost::uint32_t(h) + boost::uint32_t(h >> 32);
+      }
+#endif
+      std::size_t p1 =
+        boost::unordered::detail::prime_fmod_size<>::position(hash, j);
+
+      std::size_t p2 = h % sizes[j];
+
+      if (!BOOST_TEST_EQ(p1, p2)) {
+        std::cerr << "hash: " << hash << ", j: " << j << ", h: " << h
+                  << ", sizes[" << j << "]: " << sizes[j] << std::endl;
+        return;
+      }
+    }
+  }
+}
+
+int main()
+{
+  macros_test();
+  prime_sizes_test();
+  get_remainder_test();
+  modulo_test();
+
+  return boost::report_errors();
+}

test/unordered/rehash_tests.cpp

@@ -81,6 +81,300 @@ namespace rehash_tests {
     BOOST_TEST(postcondition(x, 0));
   }
 
+  template <class X> void rehash_empty_tracking(X*, test::random_generator)
+  {
+    // valid for all load factors
+    float const max_load_factors[] = {
+      0.5f, 1.0f, 1e6f, std::numeric_limits<float>::infinity()};
+
+    std::size_t const max_load_factors_len =
+      sizeof(max_load_factors) / sizeof(*max_load_factors);
+
+    for (std::size_t i = 0; i < max_load_factors_len; ++i) {
+      X x;
+      BOOST_TEST_EQ(x.size(), 0u);
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+
+      x.max_load_factor(max_load_factors[i]);
+
+      {
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+
+        x.rehash(0);
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+      }
+
+      {
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+
+        x.rehash(1000);
+        BOOST_TEST_GE(x.bucket_count(), 1000u);
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+
+        x.rehash(0);
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+      }
+
+      {
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+
+        x.rehash(1000);
+        BOOST_TEST_GE(x.bucket_count(), 1000u);
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+
+        x.rehash(10);
+        BOOST_TEST_GE(x.bucket_count(), 10u);
+        BOOST_TEST_LT(x.bucket_count(), 1000u);
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+      }
+
+      {
+        BOOST_TEST_GT(x.bucket_count(), 0u);
+        BOOST_TEST_LT(x.bucket_count(), 1000u);
+
+        x.rehash(1000);
+        BOOST_TEST_GE(x.bucket_count(), 1000u);
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+
+        x.rehash(0);
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+      }
+    }
+
+    for (std::size_t i = 0; i < max_load_factors_len; ++i) {
+      typedef typename X::size_type size_type;
+
+      X x;
+      BOOST_TEST_EQ(x.size(), 0u);
+      BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+
+      float const mlf = max_load_factors[i];
+      x.max_load_factor(mlf);
+
+      {
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+
+        x.reserve(0);
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+      }
+
+      {
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+
+        x.reserve(1000);
+        BOOST_TEST_GE(
+          x.bucket_count(), static_cast<size_type>(std::ceil(1000 / mlf)));
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+
+        x.reserve(0);
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+      }
+
+      {
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+
+        x.reserve(1000);
+        BOOST_TEST_GE(
+          x.bucket_count(), static_cast<size_type>(std::ceil(1000 / mlf)));
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+
+        x.reserve(10);
+        BOOST_TEST_GE(
+          x.bucket_count(), static_cast<size_type>(std::ceil(10 / mlf)));
+        BOOST_TEST_LT(x.bucket_count(), 1000u);
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+      }
+
+      {
+        BOOST_TEST_GT(x.bucket_count(), 0u);
+        BOOST_TEST_LT(x.bucket_count(), 1000u);
+
+        x.reserve(1000);
+        BOOST_TEST_GE(
+          x.bucket_count(), static_cast<size_type>(std::ceil(1000 / mlf)));
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+
+        x.reserve(0);
+        BOOST_TEST_EQ(x.bucket_count(), 0u);
+        BOOST_TEST_EQ(test::detail::tracker.count_allocations, 0u);
+      }
+    }
+  }
+
+  template <class X>
+  void rehash_nonempty_tracking(X*, test::random_generator generator)
+  {
+    test::random_values<X> const v(1000, generator);
+
+    typedef typename X::size_type size_type;
+
+    float const max_load_factors[] = {0.5f, 1.0f, 1e2f};
+
+    size_type const max_load_factors_len =
+      sizeof(max_load_factors) / sizeof(*max_load_factors);
+
+    for (size_type i = 0; i < max_load_factors_len; ++i) {
+      float const mlf = max_load_factors[i];
+
+      X x(v.begin(), v.end());
+      BOOST_TEST_GT(x.size(), 0u);
+      BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+
+      x.max_load_factor(mlf);
+
+      size_type bucket_count = x.bucket_count();
+
+      {
+        BOOST_TEST_GT(x.bucket_count(), 0u);
+
+        x.rehash(0);
+        BOOST_TEST_GE(x.bucket_count(),
+          static_cast<size_type>(
+            std::floor(static_cast<float>(x.size()) / x.max_load_factor())));
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+
+        bucket_count = x.bucket_count();
+      }
+
+      {
+        BOOST_TEST_GT(bucket_count, 0u);
+
+        x.rehash(2 * x.bucket_count());
+        BOOST_TEST_GT(x.bucket_count(), bucket_count);
+
+        bucket_count = x.bucket_count();
+      }
+
+      {
+        float const old_mlf = x.max_load_factor();
+
+        BOOST_TEST_GT(bucket_count, 0u);
+
+        x.rehash(bucket_count / 4);
+        BOOST_TEST_LT(x.bucket_count(), bucket_count);
+
+        x.max_load_factor(std::numeric_limits<float>::infinity());
+        x.rehash(0);
+        BOOST_TEST_GT(x.bucket_count(), 0u);
+
+        x.max_load_factor(old_mlf);
+      }
+
+      {
+        std::size_t const max_load =
+          static_cast<std::size_t>(static_cast<double>(x.max_load_factor()) *
+                                   static_cast<double>(x.bucket_count()));
+
+        while (x.size() < max_load) {
+          test::random_values<X> const t(max_load, generator);
+          typename test::random_values<X>::const_iterator pos = t.begin();
+          typename test::random_values<X>::const_iterator end = t.end();
+          for (; pos != end; ++pos) {
+            x.insert(*pos);
+            if (x.size() == max_load) {
+              break;
+            }
+          }
+        }
+
+        while (x.size() > max_load) {
+          x.erase(x.begin());
+        }
+
+        BOOST_TEST_EQ(x.size(), max_load);
+
+        bucket_count = x.bucket_count();
+        x.rehash(x.bucket_count());
+        BOOST_TEST_EQ(x.bucket_count(), bucket_count);
+      }
+    }
+
+    for (size_type i = 0; i < max_load_factors_len; ++i) {
+      X x(v.begin(), v.end());
+      BOOST_TEST_GT(x.size(), 0u);
+      BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+
+      float const mlf = max_load_factors[i];
+      x.max_load_factor(mlf);
+
+      size_type bucket_count = x.bucket_count();
+
+      {
+        BOOST_TEST_GT(x.bucket_count(), 0u);
+
+        x.reserve(0);
+        BOOST_TEST_GE(x.bucket_count(),
+          static_cast<size_type>(
+            std::floor(static_cast<float>(x.size()) / x.max_load_factor())));
+        BOOST_TEST_GT(test::detail::tracker.count_allocations, 0u);
+
+        bucket_count = x.bucket_count();
+      }
+
+      {
+        BOOST_TEST_GT(x.bucket_count(), 0u);
+
+        x.reserve(
+          2 * (static_cast<size_type>(
+                std::floor(static_cast<float>(x.size()) / x.max_load_factor()) +
+                std::floor(static_cast<float>(x.size()) * x.max_load_factor()))));
+
+        BOOST_TEST_GT(x.bucket_count(), bucket_count);
+
+        bucket_count = x.bucket_count();
+        BOOST_TEST_GT(bucket_count, 1u);
+      }
+
+      {
+        float const old_mlf = x.max_load_factor();
+
+        BOOST_TEST_GT(bucket_count, 4u);
+
+        x.reserve(bucket_count / 4);
+        BOOST_TEST_LT(x.bucket_count(), bucket_count);
+
+        x.max_load_factor(std::numeric_limits<float>::infinity());
+        x.reserve(0);
+        BOOST_TEST_GT(x.bucket_count(), 0u);
+
+        x.max_load_factor(old_mlf);
+      }
+
+      {
+        std::size_t const max_load =
+          static_cast<std::size_t>(static_cast<double>(x.max_load_factor()) *
+                                   static_cast<double>(x.bucket_count()));
+
+        while (x.size() < max_load) {
+          test::random_values<X> const t(max_load, generator);
+          typename test::random_values<X>::const_iterator pos = t.begin();
+          typename test::random_values<X>::const_iterator end = t.end();
+          for (; pos != end; ++pos) {
+            x.insert(*pos);
+            if (x.size() == max_load) {
+              break;
+            }
+          }
+        }
+
+        while (x.size() > max_load) {
+          x.erase(x.begin());
+        }
+
+        BOOST_TEST_EQ(x.size(), max_load);
+
+        bucket_count = x.bucket_count();
+        x.reserve(x.size());
+        BOOST_TEST_EQ(x.bucket_count(), bucket_count);
+      }
+    }
+  }
+
   template <class X> void rehash_test1(X*, test::random_generator generator)
   {
     test::random_values<X> v(1000, generator);
@@ -199,6 +493,18 @@ namespace rehash_tests {
     test::allocator2<test::movable> >* test_map_ptr;
   boost::unordered_multimap<int, int>* int_multimap_ptr;
 
+  boost::unordered_set<test::object, test::hash, test::equal_to,
+    test::allocator1<test::object> >* test_set_tracking;
+  boost::unordered_multiset<test::object, test::hash, test::equal_to,
+    test::allocator1<test::object> >* test_multiset_tracking;
+  boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
+    test::allocator1<std::pair<test::object const, test::object> > >*
+    test_map_tracking;
+  boost::unordered_multimap<test::object, test::object, test::hash,
+    test::equal_to,
+    test::allocator1<std::pair<test::object const, test::object> > >*
+    test_multimap_tracking;
+
   using test::default_generator;
   using test::generate_collisions;
   using test::limited_range;
@@ -224,6 +530,12 @@ namespace rehash_tests {
   UNORDERED_TEST(reserve_test2,
     ((int_set_ptr)(test_multiset_ptr)(test_map_ptr)(int_multimap_ptr))(
       (default_generator)(generate_collisions)(limited_range)))
+  UNORDERED_TEST(rehash_empty_tracking,
+    ((test_set_tracking)(test_multiset_tracking)(test_map_tracking)(test_multimap_tracking))(
+      (default_generator)(generate_collisions)(limited_range)))
+  UNORDERED_TEST(rehash_nonempty_tracking,
+    ((test_set_tracking)(test_multiset_tracking)(test_map_tracking)(test_multimap_tracking))(
+      (default_generator)(generate_collisions)(limited_range)))
 }
 
 RUN_TESTS()

test/unordered/scary_tests.cpp

@@ -224,7 +224,7 @@ template <class C1, class C2> void scary_test()
   typename C2::const_iterator cbegin(x.cbegin());
   BOOST_TEST(cbegin == x.cend());
 
-  BOOST_ASSERT(x.bucket_count() > 0);
+  BOOST_TEST_EQ(x.bucket_count(), 0u);
 
   typename C2::local_iterator lbegin(x.begin(0));
   BOOST_TEST(lbegin == x.end(0));

test/unordered/scoped_allocator.cpp

@@ -1,12 +1,13 @@
 
-// Copyright 2021 Christian Mazakas.
+// Copyright 2021-2022 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 <boost/config.hpp>
 #include <boost/config/pragma_message.hpp>
+#include <boost/config/workaround.hpp>
 
-#if BOOST_CXX_VERSION <= 199711L
+#if BOOST_CXX_VERSION <= 199711L || BOOST_WORKAROUND(BOOST_GCC_VERSION, < 40800)
 
 BOOST_PRAGMA_MESSAGE(
   "scoped allocator adaptor tests only work under C++11 and above")