removed overzealous inlines

(possible performance impact)

.appveyor.yml

@@ -40,52 +40,16 @@ 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_TOOLSET: msvc-14.1
 
-    - FLAVOR: Visual Studio 2017 C++2a Strict
+    - FLAVOR: Visual Studio 2017
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
-      B2_CXXFLAGS: -permissive-
-      B2_CXXSTD: 2a
+      B2_CXXSTD: latest
       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 +64,65 @@ 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
       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
+    - FLAVOR: cygwin (64-bit, latest)
+      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
+      ADDPATH: C:\cygwin64\bin;
+      B2_ADDRESS_MODEL: 64
+      B2_CXXSTD: 11
+      B2_TOOLSET: gcc
+      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
+
+    - FLAVOR: cygwin (64-bit, latest)
+      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
+      ADDPATH: C:\cygwin64\bin;
+      B2_ADDRESS_MODEL: 64
+      B2_CXXSTD: 14
+      B2_TOOLSET: gcc
+      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
+
+    - FLAVOR: cygwin (64-bit, latest)
+      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
+      ADDPATH: C:\cygwin64\bin;
+      B2_ADDRESS_MODEL: 64
+      B2_CXXSTD: 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
+      B2_TOOLSET: gcc
       B2_ADDRESS_MODEL: 32
-      ADDPATH: C:\mingw\bin;
-      B2_CXXSTD: 03,11,14,1z
-      B2_TOOLSET: gcc
-      MAYFAIL: true
 
-    - FLAVOR: mingw64
+    - 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: 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_ADDRESS_MODEL: 64
-      B2_CXXSTD: 03,11,14,17,2a
+      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

@@ -47,6 +47,7 @@
 #include <boost/type_traits/make_void.hpp>
 #include <boost/type_traits/remove_const.hpp>
 #include <boost/unordered/detail/fca.hpp>
+#include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/detail/fwd.hpp>
 #include <boost/utility/addressof.hpp>
 #include <boost/utility/enable_if.hpp>
@@ -200,7 +201,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
       {
@@ -618,39 +619,6 @@ namespace boost {
 
 #endif
 
-////////////////////////////////////////////////////////////////////////////
-// Type checkers used for the transparent member functions added by C++20 and up
-
-      template <class, class = void> struct is_transparent : public false_type
-      {
-      };
-
-      template <class T>
-      struct is_transparent<T,
-        typename boost::make_void<typename T::is_transparent>::type>
-          : public true_type
-      {
-      };
-
-      template <class, class A, class B> struct are_transparent
-      {
-        static bool const value =
-          is_transparent<A>::value && is_transparent<B>::value;
-      };
-
-      template <class Key, class UnorderedMap> struct transparent_non_iterable
-      {
-        typedef typename UnorderedMap::hasher hash;
-        typedef typename UnorderedMap::key_equal key_equal;
-        typedef typename UnorderedMap::iterator iterator;
-        typedef typename UnorderedMap::const_iterator const_iterator;
-
-        static bool const value =
-          are_transparent<Key, hash, key_equal>::value &&
-          !boost::is_convertible<Key, iterator>::value &&
-          !boost::is_convertible<Key, const_iterator>::value;
-      };
-
 ////////////////////////////////////////////////////////////////////////////
 // Explicitly call a destructor
 
@@ -1697,10 +1665,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
       {
       };
 
@@ -1730,10 +1697,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;
@@ -1745,6 +1709,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;
@@ -1754,7 +1762,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_) {}
 
@@ -1765,6 +1772,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;
@@ -1774,10 +1788,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;
@@ -1788,7 +1799,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;
@@ -1798,7 +1853,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_)
           {
@@ -1967,12 +2022,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;
         }
@@ -1982,13 +2039,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)
@@ -2001,6 +2063,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),
@@ -2272,7 +2340,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 {
@@ -2301,7 +2368,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(...)
@@ -2333,11 +2402,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;
@@ -2362,38 +2434,33 @@ namespace boost {
             k, this->hash_function(), this->key_eq());
         }
 
-#if defined(BOOST_MSVC)
-#pragma warning(push)
-#pragma warning(                                                               \
-  disable : 4714) // function 'function' marked as __forceinline not inlined
-#endif
         template <class Key, class Hash, class Pred>
-        BOOST_FORCEINLINE iterator transparent_find(
+        inline iterator transparent_find(
           Key const& k, Hash const& h, Pred const& pred) const
         {
-          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);
+          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);
+              }
             }
           }
 
           return this->end();
         }
 
-#if defined(BOOST_MSVC)
-#pragma warning(pop)
-#endif
-
         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;
@@ -2425,6 +2492,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);
@@ -2850,6 +2928,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) {
@@ -3316,22 +3411,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);
       }
 
@@ -3418,8 +3509,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/detail/type_traits.hpp

@@ -0,0 +1,59 @@
+// 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_TYPE_TRAITS_HPP
+#define BOOST_UNORDERED_DETAIL_TYPE_TRAITS_HPP
+
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
+#endif
+
+#include <boost/type_traits/integral_constant.hpp>
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/type_traits/make_void.hpp>
+
+namespace boost {
+  namespace unordered {
+    namespace detail {
+      ////////////////////////////////////////////////////////////////////////////
+      // Type checkers used for the transparent member functions added by C++20
+      // and up
+
+      template <class, class = void>
+      struct is_transparent : public boost::false_type
+      {
+      };
+
+      template <class T>
+      struct is_transparent<T,
+        typename boost::make_void<typename T::is_transparent>::type>
+          : public boost::true_type
+      {
+      };
+
+      template <class, class A, class B> struct are_transparent
+      {
+        static bool const value =
+          is_transparent<A>::value && is_transparent<B>::value;
+      };
+
+      template <class Key, class UnorderedMap> struct transparent_non_iterable
+      {
+        typedef typename UnorderedMap::hasher hash;
+        typedef typename UnorderedMap::key_equal key_equal;
+        typedef typename UnorderedMap::iterator iterator;
+        typedef typename UnorderedMap::const_iterator const_iterator;
+
+        static bool const value =
+          are_transparent<Key, hash, key_equal>::value &&
+          !boost::is_convertible<Key, iterator>::value &&
+          !boost::is_convertible<Key, const_iterator>::value;
+      };
+    } // namespace detail
+  }   // namespace unordered
+} // namespace boost
+
+#endif // BOOST_UNORDERED_DETAIL_TYPE_TRAITS_HPP

include/boost/unordered/detail/xmx.hpp

@@ -0,0 +1,75 @@
+/* 32b/64b xmx mix function.
+ *
+ * Copyright 2022 Peter Dimov.
+ * Copyright 2022 Joaquin M Lopez Munoz.
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or copy at
+ * http://www.boost.org/LICENSE_1_0.txt)
+ *
+ * See https://www.boost.org/libs/unordered for library home page.
+ */
+
+#ifndef BOOST_UNORDERED_DETAIL_XMX_HPP
+#define BOOST_UNORDERED_DETAIL_XMX_HPP
+
+#include <boost/cstdint.hpp>
+#include <climits>
+#include <cstddef>
+
+namespace boost{
+namespace unordered{
+namespace detail{
+
+/* Bit mixer for improvement of statistical properties of hash functions.
+ * The implementation is different on 64bit and 32bit architectures:
+ * 
+ *   - 64bit: same as xmx function in
+ *     http://jonkagstrom.com/bit-mixer-construction/index.html
+ *   - 32bit: generated by Hash Function Prospector
+ *     (https://github.com/skeeto/hash-prospector) and selected as the
+ *     best overall performer in benchmarks of Boost.Unordered flat containers.
+ *     Score assigned by Hash Prospector: 333.7934929677524
+ */
+
+#if defined(SIZE_MAX)
+#if ((((SIZE_MAX >> 16) >> 16) >> 16) >> 15) != 0
+#define BOOST_UNORDERED_64B_ARCHITECTURE /* >64 bits assumed as 64 bits */
+#endif
+#elif defined(UINTPTR_MAX) /* used as proxy for std::size_t */
+#if ((((UINTPTR_MAX >> 16) >> 16) >> 16) >> 15) != 0
+#define BOOST_UNORDERED_64B_ARCHITECTURE
+#endif
+#endif
+
+static inline std::size_t xmx(std::size_t x)noexcept
+{
+#if defined(BOOST_UNORDERED_64B_ARCHITECTURE)
+
+  boost::uint64_t z=(boost::uint64_t)x;
+
+  z^=z>>23;
+  z*=0xff51afd7ed558ccdull;
+  z^=z>>23;
+
+  return (std::size_t)z;
+
+#else /* 32 bits assumed */
+
+  x^=x>>18;
+  x*=0x56b5aaadu;
+  x^=x>>16;
+
+  return x;
+
+#endif
+}
+
+#ifdef BOOST_UNORDERED_64B_ARCHITECTURE
+#undef BOOST_UNORDERED_64B_ARCHITECTURE
+#endif
+
+} /* namespace detail */
+} /* namespace unordered */
+} /* namespace boost */
+
+#endif

include/boost/unordered/hash_traits.hpp

@@ -0,0 +1,44 @@
+/* Hash function characterization.
+ *
+ * Copyright 2022 Joaquin M Lopez Munoz.
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or copy at
+ * http://www.boost.org/LICENSE_1_0.txt)
+ *
+ * See https://www.boost.org/libs/unordered for library home page.
+ */
+
+#ifndef BOOST_UNORDERED_HASH_TRAITS_HPP
+#define BOOST_UNORDERED_HASH_TRAITS_HPP
+
+#include <boost/type_traits/make_void.hpp>
+#include <type_traits>
+
+namespace boost{
+namespace unordered{
+
+namespace detail{
+
+template<typename Hash,typename=void>
+struct hash_is_avalanching_impl:std::false_type{};
+
+template<typename Hash>
+struct hash_is_avalanching_impl<Hash,void_t<typename Hash::is_avalanching>>:
+  std::true_type{};
+
+} /* namespace detail */
+
+/* Each trait can be partially specialized by users for concrete hash functions
+ * when actual characterization differs from default.
+ */
+
+/* Derived from std::true_type if the type Hash::is_avalanching is present,
+ * derived from std::false_type otherwise.
+ */
+template<typename Hash>
+struct hash_is_avalanching:detail::hash_is_avalanching_impl<Hash>::type{};
+
+} /* namespace unordered */
+} /* namespace boost */
+
+#endif

include/boost/unordered/unordered_flat_map.hpp

@@ -0,0 +1,619 @@
+// 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_UNORDERED_FLAT_MAP_HPP_INCLUDED
+#define BOOST_UNORDERED_UNORDERED_FLAT_MAP_HPP_INCLUDED
+
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
+#endif
+
+#include <boost/unordered/detail/foa.hpp>
+#include <boost/unordered/detail/type_traits.hpp>
+#include <boost/unordered/unordered_flat_map_fwd.hpp>
+
+#include <boost/core/allocator_access.hpp>
+#include <boost/functional/hash.hpp>
+#include <boost/throw_exception.hpp>
+
+#include <initializer_list>
+#include <iterator>
+#include <stdexcept>
+#include <type_traits>
+#include <utility>
+
+namespace boost {
+  namespace unordered {
+
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#pragma warning(disable : 4714) /* marked as __forceinline not inlined */
+#endif
+
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    class unordered_flat_map
+    {
+      struct map_types
+      {
+        using key_type = Key;
+        using raw_key_type = typename std::remove_const<Key>::type;
+        using raw_mapped_type = typename std::remove_const<T>::type;
+
+        using init_type = std::pair<raw_key_type, raw_mapped_type>;
+        using moved_type = std::pair<raw_key_type&&, raw_mapped_type&&>;
+        using value_type = std::pair<Key const, T>;
+
+        template <class K, class V>
+        static raw_key_type const& extract(std::pair<K, V> const& kv)
+        {
+          return kv.first;
+        }
+
+        static moved_type move(value_type& x)
+        {
+          // TODO: we probably need to launder here
+          return {std::move(const_cast<raw_key_type&>(x.first)),
+            std::move(const_cast<raw_mapped_type&>(x.second))};
+        }
+      };
+
+      using table_type = detail::foa::table<map_types, Hash, KeyEqual,
+        typename boost::allocator_rebind<Allocator,
+          typename map_types::value_type>::type>;
+
+      table_type table_;
+
+      template <class K, class V, class H, class KE, class A, class Pred>
+      typename unordered_flat_map<K, V, H, KE, A>::size_type friend erase_if(
+        unordered_flat_map<K, V, H, KE, A>& set, Pred pred);
+
+    public:
+      using key_type = Key;
+      using mapped_type = T;
+      using value_type = typename map_types::value_type;
+      using init_type = typename map_types::init_type;
+      using size_type = std::size_t;
+      using difference_type = std::ptrdiff_t;
+      using hasher = Hash;
+      using key_equal = KeyEqual;
+      using allocator_type = Allocator;
+      using reference = value_type&;
+      using const_reference = value_type const&;
+      using pointer = typename boost::allocator_pointer<allocator_type>::type;
+      using const_pointer =
+        typename boost::allocator_const_pointer<allocator_type>::type;
+      using iterator = typename table_type::iterator;
+      using const_iterator = typename table_type::const_iterator;
+
+      unordered_flat_map() : unordered_flat_map(0) {}
+
+      explicit unordered_flat_map(size_type n, hasher const& h = hasher(),
+        key_equal const& pred = key_equal(),
+        allocator_type const& a = allocator_type())
+          : table_(n, h, pred, a)
+      {
+      }
+
+      unordered_flat_map(size_type n, allocator_type const& a)
+          : unordered_flat_map(n, hasher(), key_equal(), a)
+      {
+      }
+
+      unordered_flat_map(size_type n, hasher const& h, allocator_type const& a)
+          : unordered_flat_map(n, h, key_equal(), a)
+      {
+      }
+
+      explicit unordered_flat_map(allocator_type const& a)
+          : unordered_flat_map(0, a)
+      {
+      }
+
+      template <class Iterator>
+      unordered_flat_map(Iterator first, Iterator last, size_type n = 0,
+        hasher const& h = hasher(), key_equal const& pred = key_equal(),
+        allocator_type const& a = allocator_type())
+          : unordered_flat_map(n, h, pred, a)
+      {
+        this->insert(first, last);
+      }
+
+      template <class Iterator>
+      unordered_flat_map(
+        Iterator first, Iterator last, size_type n, allocator_type const& a)
+          : unordered_flat_map(first, last, n, hasher(), key_equal(), a)
+      {
+      }
+
+      template <class Iterator>
+      unordered_flat_map(Iterator first, Iterator last, size_type n,
+        hasher const& h, allocator_type const& a)
+          : unordered_flat_map(first, last, n, h, key_equal(), a)
+      {
+      }
+
+      unordered_flat_map(unordered_flat_map const& other) : table_(other.table_)
+      {
+      }
+
+      unordered_flat_map(
+        unordered_flat_map const& other, allocator_type const& a)
+          : table_(other.table_, a)
+      {
+      }
+
+      unordered_flat_map(unordered_flat_map&& other)
+        noexcept(std::is_nothrow_move_constructible<hasher>::value&&
+            std::is_nothrow_move_constructible<key_equal>::value&&
+              std::is_nothrow_move_constructible<allocator_type>::value)
+          : table_(std::move(other.table_))
+      {
+      }
+
+      unordered_flat_map(unordered_flat_map&& other, allocator_type const& al)
+          : table_(std::move(other.table_), al)
+      {
+      }
+
+      unordered_flat_map(std::initializer_list<value_type> ilist,
+        size_type n = 0, hasher const& h = hasher(),
+        key_equal const& pred = key_equal(),
+        allocator_type const& a = allocator_type())
+          : unordered_flat_map(ilist.begin(), ilist.end(), n, h, pred, a)
+      {
+      }
+
+      unordered_flat_map(std::initializer_list<value_type> init, size_type n,
+        allocator_type const& a)
+          : unordered_flat_map(init, n, hasher(), key_equal(), a)
+      {
+      }
+
+      unordered_flat_map(std::initializer_list<value_type> init, size_type n,
+        hasher const& h, allocator_type const& a)
+          : unordered_flat_map(init, n, h, key_equal(), a)
+      {
+      }
+
+      ~unordered_flat_map() = default;
+
+      unordered_flat_map& operator=(unordered_flat_map const& other)
+      {
+        table_ = other.table_;
+        return *this;
+      }
+
+      unordered_flat_map& operator=(unordered_flat_map&& other) noexcept(
+        noexcept(std::declval<table_type&>() = std::declval<table_type&&>()))
+      {
+        table_ = std::move(other.table_);
+        return *this;
+      }
+
+      allocator_type get_allocator() const noexcept
+      {
+        return table_.get_allocator();
+      }
+
+      /// Iterators
+      ///
+
+      iterator begin() noexcept { return table_.begin(); }
+      const_iterator begin() const noexcept { return table_.begin(); }
+      const_iterator cbegin() const noexcept { return table_.cbegin(); }
+
+      iterator end() noexcept { return table_.end(); }
+      const_iterator end() const noexcept { return table_.end(); }
+      const_iterator cend() const noexcept { return table_.cend(); }
+
+      /// Capacity
+      ///
+
+      BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
+      {
+        return table_.empty();
+      }
+
+      size_type size() const noexcept { return table_.size(); }
+
+      size_type max_size() const noexcept { return table_.max_size(); }
+
+      /// Modifiers
+      ///
+
+      void clear() noexcept { table_.clear(); }
+
+      template <class Ty>
+      BOOST_FORCEINLINE auto insert(Ty&& value)
+        -> decltype(table_.insert(std::forward<Ty>(value)))
+      {
+        return table_.insert(std::forward<Ty>(value));
+      }
+
+      BOOST_FORCEINLINE std::pair<iterator, bool> insert(init_type&& value)
+      {
+        return table_.insert(std::move(value));
+      }
+
+      template <class Ty>
+      BOOST_FORCEINLINE auto insert(const_iterator, Ty&& value)
+        -> decltype(table_.insert(std::forward<Ty>(value)).first)
+      {
+        return table_.insert(std::forward<Ty>(value)).first;
+      }
+
+      BOOST_FORCEINLINE iterator insert(const_iterator, init_type&& value)
+      {
+        return table_.insert(std::move(value)).first;
+      }
+
+      template <class InputIterator>
+      BOOST_FORCEINLINE void insert(InputIterator first, InputIterator last)
+      {
+        for (auto pos = first; pos != last; ++pos) {
+          table_.emplace(*pos);
+        }
+      }
+
+      void insert(std::initializer_list<value_type> ilist)
+      {
+        this->insert(ilist.begin(), ilist.end());
+      }
+
+      template <class M>
+      std::pair<iterator, bool> insert_or_assign(key_type const& key, M&& obj)
+      {
+        auto iter_bool_pair = table_.try_emplace(key, std::forward<M>(obj));
+        if (iter_bool_pair.second) {
+          return iter_bool_pair;
+        }
+        iter_bool_pair.first->second = std::forward<M>(obj);
+        return iter_bool_pair;
+      }
+
+      template <class M>
+      std::pair<iterator, bool> insert_or_assign(key_type&& key, M&& obj)
+      {
+        auto iter_bool_pair =
+          table_.try_emplace(std::move(key), std::forward<M>(obj));
+        if (iter_bool_pair.second) {
+          return iter_bool_pair;
+        }
+        iter_bool_pair.first->second = std::forward<M>(obj);
+        return iter_bool_pair;
+      }
+
+      template <class M>
+      iterator insert_or_assign(const_iterator, key_type const& key, M&& obj)
+      {
+        return this->insert_or_assign(key, std::forward<M>(obj)).first;
+      }
+
+      template <class M>
+      iterator insert_or_assign(const_iterator, key_type&& key, M&& obj)
+      {
+        return this->insert_or_assign(std::move(key), std::forward<M>(obj))
+          .first;
+      }
+
+      template <class... Args>
+      BOOST_FORCEINLINE std::pair<iterator, bool> emplace(Args&&... args)
+      {
+        return table_.emplace(std::forward<Args>(args)...);
+      }
+
+      template <class... Args>
+      BOOST_FORCEINLINE iterator emplace_hint(const_iterator, Args&&... args)
+      {
+        return table_.emplace(std::forward<Args>(args)...).first;
+      }
+
+      template <class... Args>
+      BOOST_FORCEINLINE std::pair<iterator, bool> try_emplace(
+        key_type const& key, Args&&... args)
+      {
+        return table_.try_emplace(key, std::forward<Args>(args)...);
+      }
+
+      template <class... Args>
+      BOOST_FORCEINLINE std::pair<iterator, bool> try_emplace(
+        key_type&& key, Args&&... args)
+      {
+        return table_.try_emplace(std::move(key), std::forward<Args>(args)...);
+      }
+
+      template <class... Args>
+      BOOST_FORCEINLINE iterator try_emplace(
+        const_iterator, key_type const& key, Args&&... args)
+      {
+        return table_.try_emplace(key, std::forward<Args>(args)...).first;
+      }
+
+      template <class... Args>
+      BOOST_FORCEINLINE iterator try_emplace(
+        const_iterator, key_type&& key, Args&&... args)
+      {
+        return table_.try_emplace(std::move(key), std::forward<Args>(args)...)
+          .first;
+      }
+
+      BOOST_FORCEINLINE void erase(iterator pos) { table_.erase(pos); }
+      BOOST_FORCEINLINE void erase(const_iterator pos)
+      {
+        return table_.erase(pos);
+      }
+      iterator erase(const_iterator first, const_iterator last)
+      {
+        while (first != last) {
+          this->erase(first++);
+        }
+        return iterator{detail::foa::const_iterator_cast_tag{}, last};
+      }
+
+      BOOST_FORCEINLINE size_type erase(key_type const& key)
+      {
+        return table_.erase(key);
+      }
+
+      template <class K>
+      BOOST_FORCEINLINE typename std::enable_if<
+        detail::transparent_non_iterable<K, unordered_flat_map>::value,
+        size_type>::type
+      erase(K const& key)
+      {
+        return table_.erase(key);
+      }
+
+      void swap(unordered_flat_map& rhs) noexcept(
+        noexcept(std::declval<table_type&>().swap(std::declval<table_type&>())))
+      {
+        table_.swap(rhs.table_);
+      }
+
+      template <class H2, class P2>
+      void merge(
+        unordered_flat_map<key_type, mapped_type, H2, P2, allocator_type>&
+          source)
+      {
+        table_.merge(source.table_);
+      }
+
+      template <class H2, class P2>
+      void merge(
+        unordered_flat_map<key_type, mapped_type, H2, P2, allocator_type>&&
+          source)
+      {
+        table_.merge(std::move(source.table_));
+      }
+
+      /// Lookup
+      ///
+
+      mapped_type& at(key_type const& key)
+      {
+        auto pos = table_.find(key);
+        if (pos != table_.end()) {
+          return pos->second;
+        }
+        // TODO: someday refactor this to conditionally serialize the key and
+        // include it in the error message
+        //
+        boost::throw_exception(
+          std::out_of_range("key was not found in unordered_flat_map"));
+      }
+
+      mapped_type const& at(key_type const& key) const
+      {
+        auto pos = table_.find(key);
+        if (pos != table_.end()) {
+          return pos->second;
+        }
+        boost::throw_exception(
+          std::out_of_range("key was not found in unordered_flat_map"));
+      }
+
+      mapped_type& operator[](key_type const& key)
+      {
+        return table_.try_emplace(key).first->second;
+      }
+
+      mapped_type& operator[](key_type&& key)
+      {
+        return table_.try_emplace(std::move(key)).first->second;
+      }
+
+      size_type count(key_type const& key) const
+      {
+        auto pos = table_.find(key);
+        return pos != table_.end() ? 1 : 0;
+      }
+
+      template <class K>
+      typename std::enable_if<
+        detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
+      count(K const& key) const
+      {
+        auto pos = table_.find(key);
+        return pos != table_.end() ? 1 : 0;
+      }
+
+      BOOST_FORCEINLINE iterator find(key_type const& key)
+      {
+        return table_.find(key);
+      }
+
+      BOOST_FORCEINLINE const_iterator find(key_type const& key) const
+      {
+        return table_.find(key);
+      }
+
+      template <class K>
+      BOOST_FORCEINLINE typename std::enable_if<
+        boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
+        iterator>::type
+      find(K const& key)
+      {
+        return table_.find(key);
+      }
+
+      template <class K>
+      BOOST_FORCEINLINE typename std::enable_if<
+        boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
+        const_iterator>::type
+      find(K const& key) const
+      {
+        return table_.find(key);
+      }
+
+      bool contains(key_type const& key) const
+      {
+        return this->find(key) != this->end();
+      }
+
+      template <class K>
+      typename std::enable_if<
+        boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
+        bool>::type
+      contains(K const& key) const
+      {
+        return this->find(key) != this->end();
+      }
+
+      std::pair<iterator, iterator> equal_range(key_type const& key)
+      {
+        auto pos = table_.find(key);
+        if (pos == table_.end()) {
+          return {pos, pos};
+        }
+
+        auto next = pos;
+        ++next;
+        return {pos, next};
+      }
+
+      std::pair<const_iterator, const_iterator> equal_range(
+        key_type const& key) const
+      {
+        auto pos = table_.find(key);
+        if (pos == table_.end()) {
+          return {pos, pos};
+        }
+
+        auto next = pos;
+        ++next;
+        return {pos, next};
+      }
+
+      template <class K>
+      typename std::enable_if<
+        detail::are_transparent<K, hasher, key_equal>::value,
+        std::pair<iterator, iterator> >::type
+      equal_range(K const& key)
+      {
+        auto pos = table_.find(key);
+        if (pos == table_.end()) {
+          return {pos, pos};
+        }
+
+        auto next = pos;
+        ++next;
+        return {pos, next};
+      }
+
+      template <class K>
+      typename std::enable_if<
+        detail::are_transparent<K, hasher, key_equal>::value,
+        std::pair<const_iterator, const_iterator> >::type
+      equal_range(K const& key) const
+      {
+        auto pos = table_.find(key);
+        if (pos == table_.end()) {
+          return {pos, pos};
+        }
+
+        auto next = pos;
+        ++next;
+        return {pos, next};
+      }
+
+      /// Hash Policy
+      ///
+
+      size_type bucket_count() const noexcept { return table_.capacity(); }
+
+      float load_factor() const noexcept { return table_.load_factor(); }
+
+      float max_load_factor() const noexcept
+      {
+        return table_.max_load_factor();
+      }
+
+      void max_load_factor(float) {}
+
+      void rehash(size_type n) { table_.rehash(n); }
+
+      void reserve(size_type n) { table_.reserve(n); }
+
+      /// Observers
+      ///
+
+      hasher hash_function() const { return table_.hash_function(); }
+
+      key_equal key_eq() const { return table_.key_eq(); }
+    };
+
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    bool operator==(
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& rhs)
+    {
+      if (&lhs == &rhs) {
+        return true;
+      }
+
+      return (lhs.size() == rhs.size()) && ([&] {
+        for (auto const& kvp : lhs) {
+          auto pos = rhs.find(kvp.first);
+          if ((pos == rhs.end()) || (*pos != kvp)) {
+            return false;
+          }
+        }
+        return true;
+      })();
+    }
+
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    bool operator!=(
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& rhs)
+    {
+      return !(lhs == rhs);
+    }
+
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    void swap(unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>& rhs)
+      noexcept(noexcept(lhs.swap(rhs)))
+    {
+      lhs.swap(rhs);
+    }
+
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator,
+      class Pred>
+    typename unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>::size_type
+    erase_if(
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>& map, Pred pred)
+    {
+      return erase_if(map.table_, pred);
+    }
+
+#if defined(BOOST_MSVC)
+#pragma warning(pop) /* C4714 */
+#endif
+
+  } // namespace unordered
+} // namespace boost
+
+#endif

include/boost/unordered/unordered_flat_map_fwd.hpp

@@ -0,0 +1,49 @@
+
+// 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_FLAT_MAP_FWD_HPP_INCLUDED
+#define BOOST_UNORDERED_FLAT_MAP_FWD_HPP_INCLUDED
+
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
+#endif
+
+#include <boost/functional/hash_fwd.hpp>
+#include <boost/unordered/detail/fwd.hpp>
+#include <functional>
+#include <memory>
+
+namespace boost {
+  namespace unordered {
+    template <class Key, class T, class Hash = boost::hash<Key>,
+      class KeyEqual = std::equal_to<Key>,
+      class Allocator = std::allocator<std::pair<const Key, T> > >
+    class unordered_flat_map;
+
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    bool operator==(
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& rhs);
+
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    bool operator!=(
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator> const& rhs);
+
+    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
+    void swap(unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>& lhs,
+      unordered_flat_map<Key, T, Hash, KeyEqual, Allocator>& rhs)
+      noexcept(noexcept(lhs.swap(rhs)));
+  } // namespace unordered
+
+  using boost::unordered::unordered_flat_map;
+
+  using boost::unordered::swap;
+  using boost::unordered::operator==;
+  using boost::unordered::operator!=;
+} // namespace boost
+
+#endif

include/boost/unordered/unordered_flat_set.hpp

@@ -0,0 +1,494 @@
+// 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_UNORDERED_FLAT_SET_HPP_INCLUDED
+#define BOOST_UNORDERED_UNORDERED_FLAT_SET_HPP_INCLUDED
+
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
+#endif
+
+#include <boost/unordered/detail/foa.hpp>
+#include <boost/unordered/detail/type_traits.hpp>
+#include <boost/unordered/unordered_flat_set_fwd.hpp>
+
+#include <boost/core/allocator_access.hpp>
+#include <boost/functional/hash.hpp>
+
+#include <initializer_list>
+#include <iterator>
+#include <type_traits>
+#include <utility>
+
+namespace boost {
+  namespace unordered {
+
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#pragma warning(disable : 4714) /* marked as __forceinline not inlined */
+#endif
+
+    template <class Key, class Hash, class KeyEqual, class Allocator>
+    class unordered_flat_set
+    {
+      struct set_types
+      {
+        using key_type = Key;
+        using init_type = Key;
+        using value_type = Key;
+        static Key const& extract(value_type const& key) { return key; }
+        static Key&& move(value_type& x) { return std::move(x); }
+      };
+
+      using table_type = detail::foa::table<set_types, Hash, KeyEqual,
+        typename boost::allocator_rebind<Allocator,
+          typename set_types::value_type>::type>;
+
+      table_type table_;
+
+      template <class K, class H, class KE, class A, class Pred>
+      typename unordered_flat_set<K, H, KE, A>::size_type friend erase_if(
+        unordered_flat_set<K, H, KE, A>& set, Pred pred);
+
+    public:
+      using key_type = Key;
+      using value_type = typename set_types::value_type;
+      using init_type = typename set_types::init_type;
+      using size_type = std::size_t;
+      using difference_type = std::ptrdiff_t;
+      using hasher = Hash;
+      using key_equal = KeyEqual;
+      using allocator_type = Allocator;
+      using reference = value_type&;
+      using const_reference = value_type const&;
+      using pointer = typename boost::allocator_pointer<allocator_type>::type;
+      using const_pointer =
+        typename boost::allocator_const_pointer<allocator_type>::type;
+      using iterator = typename table_type::iterator;
+      using const_iterator = typename table_type::const_iterator;
+
+      unordered_flat_set() : unordered_flat_set(0) {}
+
+      explicit unordered_flat_set(size_type n, hasher const& h = hasher(),
+        key_equal const& pred = key_equal(),
+        allocator_type const& a = allocator_type())
+          : table_(n, h, pred, a)
+      {
+      }
+
+      unordered_flat_set(size_type n, allocator_type const& a)
+          : unordered_flat_set(n, hasher(), key_equal(), a)
+      {
+      }
+
+      unordered_flat_set(size_type n, hasher const& h, allocator_type const& a)
+          : unordered_flat_set(n, h, key_equal(), a)
+      {
+      }
+
+      explicit unordered_flat_set(allocator_type const& a)
+          : unordered_flat_set(0, a)
+      {
+      }
+
+      template <class Iterator>
+      unordered_flat_set(Iterator first, Iterator last, size_type n = 0,
+        hasher const& h = hasher(), key_equal const& pred = key_equal(),
+        allocator_type const& a = allocator_type())
+          : unordered_flat_set(n, h, pred, a)
+      {
+        this->insert(first, last);
+      }
+
+      template <class InputIt>
+      unordered_flat_set(
+        InputIt first, InputIt last, size_type n, allocator_type const& a)
+          : unordered_flat_set(first, last, n, hasher(), key_equal(), a)
+      {
+      }
+
+      template <class Iterator>
+      unordered_flat_set(Iterator first, Iterator last, size_type n,
+        hasher const& h, allocator_type const& a)
+          : unordered_flat_set(first, last, n, h, key_equal(), a)
+      {
+      }
+
+      unordered_flat_set(unordered_flat_set const& other) : table_(other.table_)
+      {
+      }
+
+      unordered_flat_set(
+        unordered_flat_set const& other, allocator_type const& a)
+          : table_(other.table_, a)
+      {
+      }
+
+      unordered_flat_set(unordered_flat_set&& other)
+        noexcept(std::is_nothrow_move_constructible<hasher>::value&&
+            std::is_nothrow_move_constructible<key_equal>::value&&
+              std::is_nothrow_move_constructible<allocator_type>::value)
+          : table_(std::move(other.table_))
+      {
+      }
+
+      unordered_flat_set(unordered_flat_set&& other, allocator_type const& al)
+          : table_(std::move(other.table_), al)
+      {
+      }
+
+      unordered_flat_set(std::initializer_list<value_type> ilist,
+        size_type n = 0, hasher const& h = hasher(),
+        key_equal const& pred = key_equal(),
+        allocator_type const& a = allocator_type())
+          : unordered_flat_set(ilist.begin(), ilist.end(), n, h, pred, a)
+      {
+      }
+
+      unordered_flat_set(std::initializer_list<value_type> init, size_type n,
+        allocator_type const& a)
+          : unordered_flat_set(init, n, hasher(), key_equal(), a)
+      {
+      }
+
+      unordered_flat_set(std::initializer_list<value_type> init, size_type n,
+        hasher const& h, allocator_type const& a)
+          : unordered_flat_set(init, n, h, key_equal(), a)
+      {
+      }
+
+      ~unordered_flat_set() = default;
+
+      unordered_flat_set& operator=(unordered_flat_set const& other)
+      {
+        table_ = other.table_;
+        return *this;
+      }
+
+      unordered_flat_set& operator=(unordered_flat_set&& other) noexcept(
+        noexcept(std::declval<table_type&>() = std::declval<table_type&&>()))
+      {
+        table_ = std::move(other.table_);
+        return *this;
+      }
+
+      allocator_type get_allocator() const noexcept
+      {
+        return table_.get_allocator();
+      }
+
+      /// Iterators
+      ///
+
+      iterator begin() noexcept { return table_.begin(); }
+      const_iterator begin() const noexcept { return table_.begin(); }
+      const_iterator cbegin() const noexcept { return table_.cbegin(); }
+
+      iterator end() noexcept { return table_.end(); }
+      const_iterator end() const noexcept { return table_.end(); }
+      const_iterator cend() const noexcept { return table_.cend(); }
+
+      /// Capacity
+      ///
+
+      BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
+      {
+        return table_.empty();
+      }
+
+      size_type size() const noexcept { return table_.size(); }
+
+      size_type max_size() const noexcept { return table_.max_size(); }
+
+      /// Modifiers
+      ///
+
+      void clear() noexcept { table_.clear(); }
+
+      BOOST_FORCEINLINE std::pair<iterator, bool> insert(
+        value_type const& value)
+      {
+        return table_.insert(value);
+      }
+
+      BOOST_FORCEINLINE std::pair<iterator, bool> insert(value_type&& value)
+      {
+        return table_.insert(std::move(value));
+      }
+
+      BOOST_FORCEINLINE iterator insert(const_iterator, value_type const& value)
+      {
+        return table_.insert(value).first;
+      }
+
+      BOOST_FORCEINLINE iterator insert(const_iterator, value_type&& value)
+      {
+        return table_.insert(std::move(value)).first;
+      }
+
+      template <class InputIterator>
+      void insert(InputIterator first, InputIterator last)
+      {
+        for (auto pos = first; pos != last; ++pos) {
+          table_.emplace(*pos);
+        }
+      }
+
+      void insert(std::initializer_list<value_type> ilist)
+      {
+        this->insert(ilist.begin(), ilist.end());
+      }
+
+      template <class... Args>
+      BOOST_FORCEINLINE std::pair<iterator, bool> emplace(Args&&... args)
+      {
+        return table_.emplace(std::forward<Args>(args)...);
+      }
+
+      template <class... Args>
+      BOOST_FORCEINLINE iterator emplace_hint(const_iterator, Args&&... args)
+      {
+        return table_.emplace(std::forward<Args>(args)...).first;
+      }
+
+      BOOST_FORCEINLINE void erase(const_iterator pos)
+      {
+        return table_.erase(pos);
+      }
+      iterator erase(const_iterator first, const_iterator last)
+      {
+        while (first != last) {
+          this->erase(first++);
+        }
+        return iterator{detail::foa::const_iterator_cast_tag{}, last};
+      }
+
+      BOOST_FORCEINLINE size_type erase(key_type const& key)
+      {
+        return table_.erase(key);
+      }
+
+      template <class K>
+      BOOST_FORCEINLINE typename std::enable_if<
+        detail::transparent_non_iterable<K, unordered_flat_set>::value,
+        size_type>::type
+      erase(K const& key)
+      {
+        return table_.erase(key);
+      }
+
+      void swap(unordered_flat_set& rhs) noexcept(
+        noexcept(std::declval<table_type&>().swap(std::declval<table_type&>())))
+      {
+        table_.swap(rhs.table_);
+      }
+
+      template <class H2, class P2>
+      void merge(unordered_flat_set<key_type, H2, P2, allocator_type>& source)
+      {
+        table_.merge(source.table_);
+      }
+
+      template <class H2, class P2>
+      void merge(unordered_flat_set<key_type, H2, P2, allocator_type>&& source)
+      {
+        table_.merge(std::move(source.table_));
+      }
+
+      /// Lookup
+      ///
+
+      size_type count(key_type const& key) const
+      {
+        auto pos = table_.find(key);
+        return pos != table_.end() ? 1 : 0;
+      }
+
+      template <class K>
+      typename std::enable_if<
+        detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
+      count(K const& key) const
+      {
+        auto pos = table_.find(key);
+        return pos != table_.end() ? 1 : 0;
+      }
+
+      BOOST_FORCEINLINE iterator find(key_type const& key)
+      {
+        return table_.find(key);
+      }
+
+      BOOST_FORCEINLINE const_iterator find(key_type const& key) const
+      {
+        return table_.find(key);
+      }
+
+      template <class K>
+      BOOST_FORCEINLINE typename std::enable_if<
+        boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
+        iterator>::type
+      find(K const& key)
+      {
+        return table_.find(key);
+      }
+
+      template <class K>
+      BOOST_FORCEINLINE typename std::enable_if<
+        boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
+        const_iterator>::type
+      find(K const& key) const
+      {
+        return table_.find(key);
+      }
+
+      bool contains(key_type const& key) const
+      {
+        return this->find(key) != this->end();
+      }
+
+      template <class K>
+      typename std::enable_if<
+        boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
+        bool>::type
+      contains(K const& key) const
+      {
+        return this->find(key) != this->end();
+      }
+
+      std::pair<iterator, iterator> equal_range(key_type const& key)
+      {
+        auto pos = table_.find(key);
+        if (pos == table_.end()) {
+          return {pos, pos};
+        }
+
+        auto next = pos;
+        ++next;
+        return {pos, next};
+      }
+
+      std::pair<const_iterator, const_iterator> equal_range(
+        key_type const& key) const
+      {
+        auto pos = table_.find(key);
+        if (pos == table_.end()) {
+          return {pos, pos};
+        }
+
+        auto next = pos;
+        ++next;
+        return {pos, next};
+      }
+
+      template <class K>
+      typename std::enable_if<
+        detail::are_transparent<K, hasher, key_equal>::value,
+        std::pair<iterator, iterator> >::type
+      equal_range(K const& key)
+      {
+        auto pos = table_.find(key);
+        if (pos == table_.end()) {
+          return {pos, pos};
+        }
+
+        auto next = pos;
+        ++next;
+        return {pos, next};
+      }
+
+      template <class K>
+      typename std::enable_if<
+        detail::are_transparent<K, hasher, key_equal>::value,
+        std::pair<const_iterator, const_iterator> >::type
+      equal_range(K const& key) const
+      {
+        auto pos = table_.find(key);
+        if (pos == table_.end()) {
+          return {pos, pos};
+        }
+
+        auto next = pos;
+        ++next;
+        return {pos, next};
+      }
+
+      /// Hash Policy
+      ///
+
+      size_type bucket_count() const noexcept { return table_.capacity(); }
+
+      float load_factor() const noexcept { return table_.load_factor(); }
+
+      float max_load_factor() const noexcept
+      {
+        return table_.max_load_factor();
+      }
+
+      void max_load_factor(float) {}
+
+      void rehash(size_type n) { table_.rehash(n); }
+
+      void reserve(size_type n) { table_.reserve(n); }
+
+      /// Observers
+      ///
+
+      hasher hash_function() const { return table_.hash_function(); }
+
+      key_equal key_eq() const { return table_.key_eq(); }
+    };
+
+    template <class Key, class Hash, class KeyEqual, class Allocator>
+    bool operator==(
+      unordered_flat_set<Key, Hash, KeyEqual, Allocator> const& lhs,
+      unordered_flat_set<Key, Hash, KeyEqual, Allocator> const& rhs)
+    {
+      if (&lhs == &rhs) {
+        return true;
+      }
+
+      return (lhs.size() == rhs.size()) && ([&] {
+        for (auto const& key : lhs) {
+          auto pos = rhs.find(key);
+          if ((pos == rhs.end()) || (key != *pos)) {
+            return false;
+          }
+        }
+        return true;
+      })();
+    }
+
+    template <class Key, class Hash, class KeyEqual, class Allocator>
+    bool operator!=(
+      unordered_flat_set<Key, Hash, KeyEqual, Allocator> const& lhs,
+      unordered_flat_set<Key, Hash, KeyEqual, Allocator> const& rhs)
+    {
+      return !(lhs == rhs);
+    }
+
+    template <class Key, class Hash, class KeyEqual, class Allocator>
+    void swap(unordered_flat_set<Key, Hash, KeyEqual, Allocator>& lhs,
+      unordered_flat_set<Key, Hash, KeyEqual, Allocator>& rhs)
+      noexcept(noexcept(lhs.swap(rhs)))
+    {
+      lhs.swap(rhs);
+    }
+
+    template <class Key, class Hash, class KeyEqual, class Allocator,
+      class Pred>
+    typename unordered_flat_set<Key, Hash, KeyEqual, Allocator>::size_type
+    erase_if(unordered_flat_set<Key, Hash, KeyEqual, Allocator>& set, Pred pred)
+    {
+      return erase_if(set.table_, pred);
+    }
+
+#if defined(BOOST_MSVC)
+#pragma warning(pop) /* C4714 */
+#endif
+
+  } // namespace unordered
+} // namespace boost
+
+#endif

include/boost/unordered/unordered_flat_set_fwd.hpp

@@ -0,0 +1,49 @@
+
+// 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_FLAT_SET_FWD_HPP_INCLUDED
+#define BOOST_UNORDERED_FLAT_SET_FWD_HPP_INCLUDED
+
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
+#endif
+
+#include <boost/functional/hash_fwd.hpp>
+#include <boost/unordered/detail/fwd.hpp>
+#include <functional>
+#include <memory>
+
+namespace boost {
+  namespace unordered {
+    template <class Key, class Hash = boost::hash<Key>,
+      class KeyEqual = std::equal_to<Key>,
+      class Allocator = std::allocator<Key> >
+    class unordered_flat_set;
+
+    template <class Key, class Hash, class KeyEqual, class Allocator>
+    bool operator==(
+      unordered_flat_set<Key, Hash, KeyEqual, Allocator> const& lhs,
+      unordered_flat_set<Key, Hash, KeyEqual, Allocator> const& rhs);
+
+    template <class Key, class Hash, class KeyEqual, class Allocator>
+    bool operator!=(
+      unordered_flat_set<Key, Hash, KeyEqual, Allocator> const& lhs,
+      unordered_flat_set<Key, Hash, KeyEqual, Allocator> const& rhs);
+
+    template <class Key, class Hash, class KeyEqual, class Allocator>
+    void swap(unordered_flat_set<Key, Hash, KeyEqual, Allocator>& lhs,
+      unordered_flat_set<Key, Hash, KeyEqual, Allocator>& rhs)
+      noexcept(noexcept(lhs.swap(rhs)));
+  } // namespace unordered
+
+  using boost::unordered::unordered_flat_set;
+
+  using boost::unordered::swap;
+  using boost::unordered::operator==;
+  using boost::unordered::operator!=;
+} // namespace boost
+
+#endif

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 ;
@@ -43,6 +47,7 @@ run unordered/equivalent_keys_tests.cpp ;
 run unordered/constructor_tests.cpp ;
 run unordered/copy_tests.cpp ;
 run unordered/move_tests.cpp ;
+run unordered/post_move_tests.cpp ;
 run unordered/assign_tests.cpp ;
 run unordered/insert_tests.cpp ;
 run unordered/insert_stable_tests.cpp ;
@@ -91,3 +96,55 @@ run exception/swap_exception_tests.cpp : : : <define>BOOST_UNORDERED_SWAP_METHOD
 run exception/merge_exception_tests.cpp ;
 
 run quick.cpp ;
+
+import ../../config/checks/config : requires ;
+
+CPP11 = [ requires cxx11_constexpr cxx11_noexcept cxx11_decltype cxx11_alignas ] ;
+
+rule build_foa ( name )
+{
+  run unordered/$(name).cpp : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_$(name) ;
+}
+
+build_foa fwd_set_test ;
+build_foa fwd_map_test ;
+build_foa compile_set ;
+build_foa compile_map ;
+build_foa noexcept_tests ;
+run unordered/link_test_1.cpp unordered/link_test_2.cpp : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_link_test ;
+build_foa incomplete_test ;
+build_foa simple_tests ;
+build_foa equivalent_keys_tests ;
+build_foa constructor_tests ;
+build_foa copy_tests ;
+build_foa move_tests ;
+build_foa post_move_tests ;
+build_foa assign_tests ;
+build_foa insert_tests ;
+build_foa insert_hint_tests ;
+build_foa emplace_tests ;
+build_foa erase_tests ;
+build_foa merge_tests ;
+build_foa find_tests ;
+build_foa at_tests ;
+build_foa load_factor_tests ;
+build_foa rehash_tests ;
+build_foa equality_tests ;
+build_foa swap_tests ;
+run unordered/scoped_allocator.cpp : : : $(CPP11) <toolset>msvc-14.0:<build>no <define>BOOST_UNORDERED_FOA_TESTS : foa_scoped_allocator ;
+build_foa transparent_tests ;
+build_foa reserve_tests ;
+build_foa contains_tests ;
+build_foa erase_if ;
+build_foa scary_tests ;
+build_foa init_type_insert_tests ;
+
+run exception/constructor_exception_tests.cpp : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_constructor_exception_tests ;
+run exception/copy_exception_tests.cpp        : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_copy_exception_tests ;
+run exception/assign_exception_tests.cpp      : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_assign_exception_tests ;
+run exception/move_assign_exception_tests.cpp : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_move_assign_exception_tests ;
+run exception/insert_exception_tests.cpp      : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_insert_exception_tests ;
+run exception/erase_exception_tests.cpp       : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_erase_exception_tests ;
+run exception/rehash_exception_tests.cpp      : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_rehash_exception_tests ;
+run exception/swap_exception_tests.cpp        : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_swap_exception_tests ;
+run exception/merge_exception_tests.cpp       : : : $(CPP11) <define>BOOST_UNORDERED_FOA_TESTS : foa_merge_exception_tests ;

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/containers.hpp

@@ -1,17 +1,33 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_map.hpp>
-#include <boost/unordered_set.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../objects/exception.hpp"
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+typedef boost::unordered_flat_set<test::exception::object,
+  test::exception::hash, test::exception::equal_to,
+  test::exception::allocator<test::exception::object> >
+  test_set;
+
+typedef boost::unordered_flat_map<test::exception::object,
+  test::exception::object, test::exception::hash, test::exception::equal_to,
+  test::exception::allocator2<test::exception::object> >
+  test_map;
+
+typedef boost::unordered_flat_set<
+  std::pair<test::exception::object, test::exception::object>,
+  test::exception::hash, test::exception::equal_to,
+  test::exception::allocator<test::exception::object> >
+  test_pair_set;
+
+#define CONTAINER_SEQ (test_set)(test_map)
+#define CONTAINER_PAIR_SEQ (test_pair_set)(test_map)
+#else
 typedef boost::unordered_set<test::exception::object, test::exception::hash,
   test::exception::equal_to,
   test::exception::allocator<test::exception::object> >
@@ -42,3 +58,5 @@ typedef boost::unordered_multiset<
 #define CONTAINER_SEQ (test_set)(test_multiset)(test_map)(test_multimap)
 #define CONTAINER_PAIR_SEQ                                                     \
   (test_pair_set)(test_pair_multiset)(test_map)(test_multimap)
+
+#endif

test/exception/insert_exception_tests.cpp

@@ -1,5 +1,6 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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 "./containers.hpp"
@@ -95,7 +96,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);
@@ -221,16 +222,41 @@ struct emplace_lvalue_pos_type
 } emplace_lvalue_pos;
 
 // Run the exception tests in various combinations.
+using test::default_generator;
+using test::limited_range;
+using test::generate_collisions;
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+test_set* test_set_;
+test_map* test_map_;
+
+// clang-format off
+UNORDERED_TEST(insert_exception_test,
+    ((test_set_)(test_map_))
+    ((insert_lvalue)(insert_lvalue_begin)(insert_lvalue_end)
+     (insert_lvalue_pos)(insert_single_item_range)
+     (emplace_lvalue)(emplace_lvalue_begin)(emplace_lvalue_end)
+     (emplace_lvalue_pos)
+    )
+    ((default_generator)(limited_range)(generate_collisions))
+)
+
+UNORDERED_TEST(insert_rehash_exception_test,
+    ((test_set_)(test_map_))
+    ((insert_lvalue)(insert_lvalue_begin)(insert_lvalue_end)
+     (insert_lvalue_pos)(insert_single_item_range)
+     (emplace_lvalue)(emplace_lvalue_begin)(emplace_lvalue_end)
+     (emplace_lvalue_pos)
+    )
+    ((default_generator)(limited_range)(generate_collisions))
+)
+// clang-format on
+#else
 test_set* test_set_;
 test_multiset* test_multiset_;
 test_map* test_map_;
 test_multimap* test_multimap_;
 
-using test::default_generator;
-using test::limited_range;
-using test::generate_collisions;
-
 // clang-format off
 UNORDERED_TEST(insert_exception_test,
     ((test_set_)(test_multiset_)(test_map_)(test_multimap_))
@@ -252,6 +278,7 @@ UNORDERED_TEST(insert_rehash_exception_test,
     ((default_generator)(limited_range)(generate_collisions))
 )
 // clang-format on
+#endif
 
 // Repeat insert tests with pairs
 
@@ -259,8 +286,13 @@ struct pair_emplace_type : inserter_base
 {
   template <typename T, typename Iterator> void operator()(T& x, Iterator it)
   {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    x.emplace(std::piecewise_construct, std::make_tuple(it->first),
+      std::make_tuple(it->second));
+#else
     x.emplace(boost::unordered::piecewise_construct,
       boost::make_tuple(it->first), boost::make_tuple(it->second));
+#endif
   }
 } pair_emplace;
 
@@ -268,12 +300,34 @@ struct pair_emplace2_type : inserter_base
 {
   template <typename T, typename Iterator> void operator()(T& x, Iterator it)
   {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    x.emplace_hint(x.begin(), std::piecewise_construct,
+      std::make_tuple(it->first),
+      std::make_tuple(it->second.tag1_, it->second.tag2_));
+#else
     x.emplace_hint(x.begin(), boost::unordered::piecewise_construct,
       boost::make_tuple(it->first),
       boost::make_tuple(it->second.tag1_, it->second.tag2_));
+#endif
   }
 } pair_emplace2;
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+test_pair_set* test_pair_set_;
+
+// clang-format off
+UNORDERED_TEST(insert_exception_test,
+    ((test_pair_set_)(test_map_))
+    ((pair_emplace)(pair_emplace2))
+    ((default_generator)(limited_range)(generate_collisions))
+)
+UNORDERED_TEST(insert_rehash_exception_test,
+    ((test_pair_set_)(test_map_))
+    ((pair_emplace)(pair_emplace2))
+    ((default_generator)(limited_range)(generate_collisions))
+)
+// clang-format on
+#else
 test_pair_set* test_pair_set_;
 test_pair_multiset* test_pair_multiset_;
 
@@ -289,6 +343,7 @@ UNORDERED_TEST(insert_rehash_exception_test,
     ((default_generator)(limited_range)(generate_collisions))
 )
 // clang-format on
+#endif
 
 // Test inserting using operator[]
 
@@ -393,7 +448,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);
@@ -401,6 +456,19 @@ void insert_range_rehash_exception_test(T*, test::random_generator gen)
   }
 }
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+// clang-format off
+UNORDERED_TEST(insert_range_exception_test,
+    ((test_set_)(test_map_))
+    ((default_generator)(limited_range)(generate_collisions))
+)
+
+UNORDERED_TEST(insert_range_rehash_exception_test,
+    ((test_set_)(test_map_))
+    ((default_generator)(limited_range)(generate_collisions))
+)
+// clang-format on
+#else
 // clang-format off
 UNORDERED_TEST(insert_range_exception_test,
     ((test_set_)(test_multiset_)(test_map_)(test_multimap_))
@@ -412,5 +480,6 @@ UNORDERED_TEST(insert_range_rehash_exception_test,
     ((default_generator)(limited_range)(generate_collisions))
 )
 // clang-format on
+#endif
 
 RUN_TESTS()

test/exception/merge_exception_tests.cpp

@@ -1,5 +1,6 @@
 
 // Copyright 2017-2018 Daniel James.
+// 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)
 
@@ -52,6 +53,53 @@ void merge_exception_test(T1 const*, T2 const*, std::size_t count12, int tag12,
   EXCEPTION_LOOP(merge_exception_test(x, y))
 }
 
+using test::default_generator;
+using test::generate_collisions;
+using test::limited_range;
+
+#ifdef BOOST_UNORDERED_FOA_TESTS
+boost::unordered_flat_set<test::exception::object, test::exception::hash,
+  test::exception::equal_to,
+  test::exception::allocator<test::exception::object> >* test_set_;
+boost::unordered_flat_map<test::exception::object, test::exception::object,
+  test::exception::hash, test::exception::equal_to,
+  test::exception::allocator2<test::exception::object> >* test_map_;
+
+// clang-format off
+UNORDERED_MULTI_TEST(set_merge, merge_exception_test,
+    ((test_set_))
+    ((test_set_))
+    ((0x0000)(0x6400)(0x0064)(0x0a64)(0x3232))
+    ((0x0000)(0x0001)(0x0102))
+    ((default_generator)(limited_range))
+    ((default_generator)(limited_range))
+)
+UNORDERED_MULTI_TEST(map_merge, merge_exception_test,
+    ((test_map_))
+    ((test_map_))
+    ((0x0000)(0x6400)(0x0064)(0x0a64)(0x3232))
+    ((0x0101)(0x0200)(0x0201))
+    ((default_generator)(limited_range))
+    ((default_generator)(limited_range))
+)
+// Run fewer generate_collisions tests, as they're slow.
+UNORDERED_MULTI_TEST(set_merge_collisions, merge_exception_test,
+    ((test_set_))
+    ((test_set_))
+    ((0x0a0a))
+    ((0x0202)(0x0100)(0x0201))
+    ((generate_collisions))
+    ((generate_collisions))
+)
+UNORDERED_MULTI_TEST(map_merge_collisions, merge_exception_test,
+    ((test_map_))
+    ((test_map_))
+    ((0x0a0a))
+    ((0x0000)(0x0002)(0x0102))
+    ((generate_collisions))
+    ((generate_collisions))
+)
+#else
 boost::unordered_set<test::exception::object, test::exception::hash,
   test::exception::equal_to,
   test::exception::allocator<test::exception::object> >* test_set_;
@@ -65,10 +113,6 @@ boost::unordered_multimap<test::exception::object, test::exception::object,
   test::exception::hash, test::exception::equal_to,
   test::exception::allocator2<test::exception::object> >* test_multimap_;
 
-using test::default_generator;
-using test::generate_collisions;
-using test::limited_range;
-
 // clang-format off
 UNORDERED_MULTI_TEST(set_merge, merge_exception_test,
     ((test_set_)(test_multiset_))
@@ -104,5 +148,6 @@ UNORDERED_MULTI_TEST(map_merge_collisions, merge_exception_test,
     ((generate_collisions))
 )
 // clang-format on
+#endif
 
 RUN_TESTS_QUIET()

test/exception/swap_exception_tests.cpp

@@ -1,10 +1,15 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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 "./containers.hpp"
 
+#if defined(BOOST_UNORDERED_FOA_TESTS)
+#define BOOST_UNORDERED_FOA_WEAK_GUARANTEE_SWAP_EXCEPTIONS_TESTS
+#endif
+
 #include "../helpers/invariants.hpp"
 #include "../helpers/random_values.hpp"
 #include "../helpers/tracker.hpp"

test/helpers/invariants.hpp

@@ -1,5 +1,6 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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)
 
@@ -53,11 +54,22 @@ namespace test {
       if (test::has_unique_keys<X>::value && count != 1)
         BOOST_ERROR("Non-unique key.");
 
+#if !defined(BOOST_UNORDERED_FOA_WEAK_GUARANTEE_SWAP_EXCEPTIONS_TESTS)
+      // we conditionally compile this check because our FOA implementation only
+      // exhibits the weak guarantee when swapping throws
+      //
+      // in this case, the hasher may be changed before the predicate and the
+      // arrays are swapped in which case, we can can find an element by
+      // iteration but unfortunately, it's in the wrong slot according to the
+      // new hash function so count(key) can wind up returning nothing when
+      // there really is something
       if (x1.count(key) != count) {
         BOOST_ERROR("Incorrect output of count.");
         std::cerr << x1.count(key) << "," << count << "\n";
       }
+#endif
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
       // Check that the keys are in the correct bucket and are
       // adjacent in the bucket.
       typename X::size_type bucket = x1.bucket(key);
@@ -86,6 +98,7 @@ namespace test {
           }
         }
       }
+#endif
     };
 
     // Check that size matches up.
@@ -104,6 +117,7 @@ namespace test {
     if (fabs(x1.load_factor() - load_factor) > x1.load_factor() / 64)
       BOOST_ERROR("x1.load_factor() doesn't match actual load_factor.");
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
     // Check that size in the buckets matches up.
 
     typename X::size_type bucket_size = 0;
@@ -120,6 +134,7 @@ namespace test {
       BOOST_ERROR("x1.size() doesn't match bucket size.");
       std::cout << x1.size() << "/" << bucket_size << std::endl;
     }
+#endif
   }
 }
 

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/helpers/unordered.hpp

@@ -0,0 +1,22 @@
+
+// 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)
+
+#if !defined(BOOST_UNORDERED_TEST_HELPERS_UNORDERED_HEADER)
+#define BOOST_UNORDERED_TEST_HELPERS_UNORDERED_HEADER
+
+// clang-format off
+#include "prefix.hpp"
+#ifdef BOOST_UNORDERED_FOA_TESTS
+#include <boost/unordered/unordered_flat_set.hpp>
+#include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/unordered/detail/implementation.hpp>
+#else
+#include <boost/unordered_set.hpp>
+#include <boost/unordered_map.hpp>
+#endif
+#include "postfix.hpp"
+// clang-format on
+
+#endif

test/objects/minimal.hpp

@@ -11,6 +11,7 @@
 #if !defined(BOOST_UNORDERED_OBJECTS_MINIMAL_HEADER)
 #define BOOST_UNORDERED_OBJECTS_MINIMAL_HEADER
 
+#include <boost/core/addressof.hpp>
 #include <boost/core/lightweight_test.hpp>
 #include <boost/core/pointer_traits.hpp>
 #include <boost/move/move.hpp>
@@ -320,7 +321,7 @@ namespace test {
       bool operator!() const { return !ptr_; }
 
       static ptr pointer_to(T& p) {
-        return ptr(&p);
+        return ptr(boost::addressof(p));
       }
 
       // I'm not using the safe bool idiom because the containers should be

test/unordered/assign_tests.cpp

@@ -1,14 +1,10 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../helpers/test.hpp"
 #include "../objects/test.hpp"
@@ -45,6 +41,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 +91,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);
     }
 
@@ -199,6 +197,54 @@ namespace assign_tests {
     }
   }
 
+  using test::default_generator;
+  using test::generate_collisions;
+  using test::limited_range;
+
+  template <typename T> bool is_propagate(T*)
+  {
+    return T::allocator_type::is_propagate_on_assign;
+  }
+
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_map<test::object, test::object, test::hash,
+    test::equal_to, std::allocator<test::object> >* test_map_std_alloc;
+
+  boost::unordered_flat_set<test::object, test::hash, test::equal_to,
+    test::allocator1<test::object> >* test_set;
+  boost::unordered_flat_map<test::object, test::object, test::hash,
+    test::equal_to, test::allocator2<test::object> >* test_map;
+
+  boost::unordered_flat_set<test::object, test::hash, test::equal_to,
+    test::cxx11_allocator<test::object, test::propagate_assign> >*
+    test_set_prop_assign;
+  boost::unordered_flat_map<test::object, test::object, test::hash,
+    test::equal_to,
+    test::cxx11_allocator<test::object, test::propagate_assign> >*
+    test_map_prop_assign;
+
+  boost::unordered_flat_set<test::object, test::hash, test::equal_to,
+    test::cxx11_allocator<test::object, test::no_propagate_assign> >*
+    test_set_no_prop_assign;
+  boost::unordered_flat_map<test::object, test::object, test::hash,
+    test::equal_to,
+    test::cxx11_allocator<test::object, test::no_propagate_assign> >*
+    test_map_no_prop_assign;
+
+  UNORDERED_AUTO_TEST (check_traits) {
+    BOOST_TEST(!is_propagate(test_set));
+    BOOST_TEST(is_propagate(test_set_prop_assign));
+    BOOST_TEST(!is_propagate(test_set_no_prop_assign));
+  }
+
+  UNORDERED_TEST(assign_tests1,
+    ((test_map_std_alloc)(test_set)(test_map)(test_set_prop_assign)(test_map_prop_assign)(test_set_no_prop_assign)(test_map_no_prop_assign))(
+      (default_generator)(generate_collisions)(limited_range)))
+
+  UNORDERED_TEST(assign_tests2,
+    ((test_set)(test_map)(test_set_prop_assign)(test_map_prop_assign)(test_set_no_prop_assign)(test_map_no_prop_assign))(
+      (default_generator)(generate_collisions)(limited_range)))
+#else
   boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
     std::allocator<test::object> >* test_map_std_alloc;
 
@@ -239,15 +285,6 @@ namespace assign_tests {
     test::cxx11_allocator<test::object, test::no_propagate_assign> >*
     test_multimap_no_prop_assign;
 
-  using test::default_generator;
-  using test::generate_collisions;
-  using test::limited_range;
-
-  template <typename T> bool is_propagate(T*)
-  {
-    return T::allocator_type::is_propagate_on_assign;
-  }
-
   UNORDERED_AUTO_TEST (check_traits) {
     BOOST_TEST(!is_propagate(test_set));
     BOOST_TEST(is_propagate(test_set_prop_assign));
@@ -269,13 +306,18 @@ namespace assign_tests {
                      test_set_no_prop_assign)(test_multiset_no_prop_assign)(
                      test_map_no_prop_assign)(test_multimap_no_prop_assign))(
                      (default_generator)(generate_collisions)(limited_range)))
+#endif
 
 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 
   UNORDERED_AUTO_TEST (assign_default_initializer_list) {
     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Initializer List Tests\n";
     std::initializer_list<std::pair<int const, int> > init;
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    boost::unordered_flat_map<int, int> x1;
+#else
     boost::unordered_map<int, int> x1;
+#endif
     x1[25] = 3;
     x1[16] = 10;
     BOOST_TEST(!x1.empty());
@@ -289,7 +331,11 @@ namespace assign_tests {
   UNORDERED_AUTO_TEST (assign_initializer_list) {
     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Initializer List Tests\n";
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    boost::unordered_flat_set<int> x;
+#else
     boost::unordered_set<int> x;
+#endif
     x.insert(10);
     x.insert(20);
     x = {1, 2, -10};

test/unordered/at_tests.cpp

@@ -1,13 +1,10 @@
 
 // Copyright 2007-2009 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../helpers/test.hpp"
 #include <string>
@@ -17,8 +14,13 @@ namespace at_tests {
   UNORDERED_AUTO_TEST (at_tests) {
     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Create Map" << std::endl;
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    boost::unordered_flat_map<std::string, int> x;
+    boost::unordered_flat_map<std::string, int> const& x_const(x);
+#else
     boost::unordered_map<std::string, int> x;
     boost::unordered_map<std::string, int> const& x_const(x);
+#endif
 
     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Check empty container" << std::endl;
 

test/unordered/compile_map.cpp

@@ -1,23 +1,41 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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)
 
 // This test creates the containers with members that meet their minimum
 // requirements. Makes sure everything compiles and is defined correctly.
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../helpers/test.hpp"
 #include "../objects/minimal.hpp"
 #include "./compile_tests.hpp"
 
 // Explicit instantiation to catch compile-time errors
+#ifdef BOOST_UNORDERED_FOA_TESTS
 
+// emulates what was already done for previous tests but without leaking to
+// the detail namespace
+//
+template <typename K, typename T, typename H, typename P, typename A>
+class instantiate_flat_map
+{
+  typedef boost::unordered_flat_map<K, T, H, P, A> container;
+  container x;
+};
+
+template class instantiate_flat_map<int, int, boost::hash<int>,
+  std::equal_to<int>, test::minimal::allocator<int> >;
+
+template class instantiate_flat_map<test::minimal::assignable const,
+  test::minimal::default_assignable const,
+  test::minimal::hash<test::minimal::assignable>,
+  test::minimal::equal_to<test::minimal::assignable>,
+  test::minimal::allocator<int> >;
+
+#else
 #define INSTANTIATE(type)                                                      \
   template class boost::unordered::detail::instantiate_##type
 
@@ -35,6 +53,7 @@ INSTANTIATE(multimap)<test::minimal::assignable, test::minimal::assignable,
   test::minimal::hash<test::minimal::assignable>,
   test::minimal::equal_to<test::minimal::assignable>,
   test::minimal::allocator<int> >;
+#endif
 
 UNORDERED_AUTO_TEST (test0) {
   test::minimal::constructor_param x;
@@ -45,6 +64,19 @@ UNORDERED_AUTO_TEST (test0) {
 
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_map.\n";
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_map<int, int> int_map;
+
+  boost::unordered_flat_map<int, int, boost::hash<int>, std::equal_to<int>,
+    test::minimal::cxx11_allocator<std::pair<int const, int> > >
+    int_map2;
+
+  boost::unordered_flat_map<test::minimal::assignable,
+    test::minimal::assignable, test::minimal::hash<test::minimal::assignable>,
+    test::minimal::equal_to<test::minimal::assignable>,
+    test::minimal::allocator<value_type> >
+    map;
+#else
   boost::unordered_map<int, int> int_map;
 
   boost::unordered_map<int, int, boost::hash<int>, std::equal_to<int>,
@@ -56,11 +88,13 @@ UNORDERED_AUTO_TEST (test0) {
     test::minimal::equal_to<test::minimal::assignable>,
     test::minimal::allocator<value_type> >
     map;
+#endif
 
   container_test(int_map, std::pair<int const, int>(0, 0));
   container_test(int_map2, std::pair<int const, int>(0, 0));
   container_test(map, value);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_multimap.\n";
 
   boost::unordered_multimap<int, int> int_multimap;
@@ -78,6 +112,7 @@ UNORDERED_AUTO_TEST (test0) {
   container_test(int_multimap, std::pair<int const, int>(0, 0));
   container_test(int_multimap2, std::pair<int const, int>(0, 0));
   container_test(multimap, value);
+#endif
 }
 
 UNORDERED_AUTO_TEST (equality_tests) {
@@ -85,6 +120,22 @@ UNORDERED_AUTO_TEST (equality_tests) {
     test::minimal::copy_constructible_equality_comparable>
     value_type;
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_map<int, int> int_map;
+
+  boost::unordered_flat_map<int, int, boost::hash<int>, std::equal_to<int>,
+    test::minimal::cxx11_allocator<std::pair<int const, int> > >
+    int_map2;
+
+  boost::unordered_flat_map<
+    test::minimal::copy_constructible_equality_comparable,
+    test::minimal::copy_constructible_equality_comparable,
+    test::minimal::hash<test::minimal::copy_constructible_equality_comparable>,
+    test::minimal::equal_to<
+      test::minimal::copy_constructible_equality_comparable>,
+    test::minimal::allocator<value_type> >
+    map;
+#else
   boost::unordered_map<int, int> int_map;
 
   boost::unordered_map<int, int, boost::hash<int>, std::equal_to<int>,
@@ -98,11 +149,13 @@ UNORDERED_AUTO_TEST (equality_tests) {
       test::minimal::copy_constructible_equality_comparable>,
     test::minimal::allocator<value_type> >
     map;
+#endif
 
   equality_test(int_map);
   equality_test(int_map2);
   equality_test(map);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   boost::unordered_multimap<int, int> int_multimap;
 
   boost::unordered_multimap<int, int, boost::hash<int>, std::equal_to<int>,
@@ -121,6 +174,7 @@ UNORDERED_AUTO_TEST (equality_tests) {
   equality_test(int_multimap);
   equality_test(int_multimap2);
   equality_test(multimap);
+#endif
 }
 
 UNORDERED_AUTO_TEST (test1) {
@@ -131,11 +185,19 @@ UNORDERED_AUTO_TEST (test1) {
 
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_map.\n";
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_map<int, int> map;
+
+  boost::unordered_flat_map<int, int, boost::hash<int>, std::equal_to<int>,
+    test::minimal::cxx11_allocator<std::pair<int const, int> > >
+    map2;
+#else
   boost::unordered_map<int, int> map;
 
   boost::unordered_map<int, int, boost::hash<int>, std::equal_to<int>,
     test::minimal::cxx11_allocator<std::pair<int const, int> > >
     map2;
+#endif
 
   unordered_unique_test(map, map_value);
   unordered_map_test(map, value, value);
@@ -147,6 +209,7 @@ UNORDERED_AUTO_TEST (test1) {
   unordered_copyable_test(map2, value, map_value, hash, equal_to);
   unordered_map_functions(map2, value, value);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_multimap.\n";
 
   boost::unordered_multimap<int, int> multimap;
@@ -162,6 +225,7 @@ UNORDERED_AUTO_TEST (test1) {
   unordered_equivalent_test(multimap2, map_value);
   unordered_map_test(multimap2, value, value);
   unordered_copyable_test(multimap2, value, map_value, hash, equal_to);
+#endif
 }
 
 UNORDERED_AUTO_TEST (test2) {
@@ -178,28 +242,46 @@ UNORDERED_AUTO_TEST (test2) {
 
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_map.\n";
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_map<test::minimal::assignable,
+    test::minimal::assignable, test::minimal::hash<test::minimal::assignable>,
+    test::minimal::equal_to<test::minimal::assignable>,
+    test::minimal::allocator<map_value_type> >
+    map;
+#else
   boost::unordered_map<test::minimal::assignable, test::minimal::assignable,
     test::minimal::hash<test::minimal::assignable>,
     test::minimal::equal_to<test::minimal::assignable>,
     test::minimal::allocator<map_value_type> >
     map;
+#endif
 
   unordered_unique_test(map, map_value);
   unordered_map_test(map, assignable, assignable);
   unordered_copyable_test(map, assignable, map_value, hash, equal_to);
   unordered_map_member_test(map, map_value);
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_map<test::minimal::assignable,
+    test::minimal::default_assignable,
+    test::minimal::hash<test::minimal::assignable>,
+    test::minimal::equal_to<test::minimal::assignable>,
+    test::minimal::allocator<map_value_type> >
+    map2;
+#else
   boost::unordered_map<test::minimal::assignable,
     test::minimal::default_assignable,
     test::minimal::hash<test::minimal::assignable>,
     test::minimal::equal_to<test::minimal::assignable>,
     test::minimal::allocator<map_value_type> >
     map2;
+#endif
 
   test::minimal::default_assignable default_assignable;
 
   unordered_map_functions(map2, assignable, default_assignable);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_multimap.\n";
 
   boost::unordered_multimap<test::minimal::assignable,
@@ -212,6 +294,7 @@ UNORDERED_AUTO_TEST (test2) {
   unordered_map_test(multimap, assignable, assignable);
   unordered_copyable_test(multimap, assignable, map_value, hash, equal_to);
   unordered_map_member_test(multimap, map_value);
+#endif
 }
 
 // Test for ambiguity when using key convertible from iterator
@@ -232,6 +315,11 @@ std::size_t hash_value(lwg2059_key x)
 bool operator==(lwg2059_key x, lwg2059_key y) { return x.value == y.value; }
 
 UNORDERED_AUTO_TEST (lwg2059) {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_map<lwg2059_key, int> x;
+  x.emplace(lwg2059_key(10), 5);
+  x.erase(x.begin());
+#else
   {
     boost::unordered_map<lwg2059_key, int> x;
     x.emplace(lwg2059_key(10), 5);
@@ -243,6 +331,7 @@ UNORDERED_AUTO_TEST (lwg2059) {
     x.emplace(lwg2059_key(10), 5);
     x.erase(x.begin());
   }
+#endif
 }
 
 RUN_TESTS()

test/unordered/compile_set.cpp

@@ -1,16 +1,13 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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)
 
 // This test creates the containers with members that meet their minimum
 // requirements. Makes sure everything compiles and is defined correctly.
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../helpers/test.hpp"
 #include "../objects/minimal.hpp"
@@ -18,6 +15,28 @@
 
 // Explicit instantiation to catch compile-time errors
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+
+// emulates what was already done for previous tests but without leaking to
+// the detail namespace
+//
+template <typename T, typename H, typename P, typename A>
+class instantiate_flat_set
+{
+  typedef boost::unordered_flat_set<T, H, P, A> container;
+  container x;
+};
+
+template class instantiate_flat_set<int, boost::hash<int>, std::equal_to<int>,
+  test::minimal::allocator<int> >;
+
+template class instantiate_flat_set<test::minimal::assignable const,
+  test::minimal::hash<test::minimal::assignable>,
+  test::minimal::equal_to<test::minimal::assignable>,
+  test::minimal::allocator<int> >;
+
+#else
+
 #define INSTANTIATE(type)                                                      \
   template class boost::unordered::detail::instantiate_##type
 
@@ -35,6 +54,21 @@ INSTANTIATE(multiset)<test::minimal::assignable,
   test::minimal::equal_to<test::minimal::assignable>,
   test::minimal::allocator<int> >;
 
+#endif
+
+UNORDERED_AUTO_TEST (type_traits) {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  typedef boost::unordered_flat_set<int> set_type;
+#else
+  typedef boost::unordered_set<int> set_type;
+#endif
+
+  typedef set_type::iterator iterator;
+
+  BOOST_STATIC_ASSERT(boost::is_same<int const&,
+    std::iterator_traits<iterator>::reference>::value);
+}
+
 UNORDERED_AUTO_TEST (test0) {
   test::minimal::constructor_param x;
 
@@ -42,6 +76,19 @@ UNORDERED_AUTO_TEST (test0) {
 
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_set.\n";
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<int> int_set;
+
+  boost::unordered_flat_set<int, boost::hash<int>, std::equal_to<int>,
+    test::minimal::cxx11_allocator<int> >
+    int_set2;
+
+  boost::unordered_flat_set<test::minimal::assignable,
+    test::minimal::hash<test::minimal::assignable>,
+    test::minimal::equal_to<test::minimal::assignable>,
+    test::minimal::allocator<test::minimal::assignable> >
+    set;
+#else
   boost::unordered_set<int> int_set;
 
   boost::unordered_set<int, boost::hash<int>, std::equal_to<int>,
@@ -53,11 +100,13 @@ UNORDERED_AUTO_TEST (test0) {
     test::minimal::equal_to<test::minimal::assignable>,
     test::minimal::allocator<test::minimal::assignable> >
     set;
+#endif
 
   container_test(int_set, 0);
   container_test(int_set2, 0);
   container_test(set, assignable);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_multiset.\n";
 
   boost::unordered_multiset<int> int_multiset;
@@ -75,11 +124,27 @@ UNORDERED_AUTO_TEST (test0) {
   container_test(int_multiset, 0);
   container_test(int_multiset2, 0);
   container_test(multiset, assignable);
+#endif
 }
 
 UNORDERED_AUTO_TEST (equality_tests) {
   typedef test::minimal::copy_constructible_equality_comparable value_type;
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<int> int_set;
+
+  boost::unordered_flat_set<int, boost::hash<int>, std::equal_to<int>,
+    test::minimal::cxx11_allocator<int> >
+    int_set2;
+
+  boost::unordered_flat_set<
+    test::minimal::copy_constructible_equality_comparable,
+    test::minimal::hash<test::minimal::copy_constructible_equality_comparable>,
+    test::minimal::equal_to<
+      test::minimal::copy_constructible_equality_comparable>,
+    test::minimal::allocator<value_type> >
+    set;
+#else
   boost::unordered_set<int> int_set;
 
   boost::unordered_set<int, boost::hash<int>, std::equal_to<int>,
@@ -92,11 +157,13 @@ UNORDERED_AUTO_TEST (equality_tests) {
       test::minimal::copy_constructible_equality_comparable>,
     test::minimal::allocator<value_type> >
     set;
+#endif
 
   equality_test(int_set);
   equality_test(int_set2);
   equality_test(set);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   boost::unordered_multiset<int> int_multiset;
 
   boost::unordered_multiset<int, boost::hash<int>, std::equal_to<int>,
@@ -114,6 +181,7 @@ UNORDERED_AUTO_TEST (equality_tests) {
   equality_test(int_multiset);
   equality_test(int_multiset2);
   equality_test(multiset);
+#endif
 }
 
 UNORDERED_AUTO_TEST (test1) {
@@ -122,12 +190,19 @@ UNORDERED_AUTO_TEST (test1) {
   int value = 0;
 
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_set." << std::endl;
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<int> set;
 
+  boost::unordered_flat_set<int, boost::hash<int>, std::equal_to<int>,
+    test::minimal::cxx11_allocator<int> >
+    set2;
+#else
   boost::unordered_set<int> set;
 
   boost::unordered_set<int, boost::hash<int>, std::equal_to<int>,
     test::minimal::cxx11_allocator<int> >
     set2;
+#endif
 
   unordered_unique_test(set, value);
   unordered_set_test(set, value);
@@ -137,6 +212,7 @@ UNORDERED_AUTO_TEST (test1) {
   unordered_set_test(set2, value);
   unordered_copyable_test(set2, value, value, hash, equal_to);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_multiset." << std::endl;
 
   boost::unordered_multiset<int> multiset;
@@ -152,6 +228,7 @@ UNORDERED_AUTO_TEST (test1) {
   unordered_equivalent_test(multiset2, value);
   unordered_set_test(multiset2, value);
   unordered_copyable_test(multiset2, value, value, hash, equal_to);
+#endif
 }
 
 UNORDERED_AUTO_TEST (test2) {
@@ -163,18 +240,26 @@ UNORDERED_AUTO_TEST (test2) {
   test::minimal::equal_to<test::minimal::assignable> equal_to(x);
 
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_set.\n";
-
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<test::minimal::assignable,
+    test::minimal::hash<test::minimal::assignable>,
+    test::minimal::equal_to<test::minimal::assignable>,
+    test::minimal::allocator<test::minimal::assignable> >
+    set;
+#else
   boost::unordered_set<test::minimal::assignable,
     test::minimal::hash<test::minimal::assignable>,
     test::minimal::equal_to<test::minimal::assignable>,
     test::minimal::allocator<test::minimal::assignable> >
     set;
+#endif
 
   unordered_unique_test(set, assignable);
   unordered_set_test(set, assignable);
   unordered_copyable_test(set, assignable, assignable, hash, equal_to);
   unordered_set_member_test(set, assignable);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_multiset.\n";
 
   boost::unordered_multiset<test::minimal::assignable,
@@ -187,6 +272,7 @@ UNORDERED_AUTO_TEST (test2) {
   unordered_set_test(multiset, assignable);
   unordered_copyable_test(multiset, assignable, assignable, hash, equal_to);
   unordered_set_member_test(multiset, assignable);
+#endif
 }
 
 UNORDERED_AUTO_TEST (movable1_tests) {
@@ -197,17 +283,25 @@ UNORDERED_AUTO_TEST (movable1_tests) {
   test::minimal::equal_to<test::minimal::movable1> equal_to(x);
 
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_set.\n";
-
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<test::minimal::movable1,
+    test::minimal::hash<test::minimal::movable1>,
+    test::minimal::equal_to<test::minimal::movable1>,
+    test::minimal::allocator<test::minimal::movable1> >
+    set;
+#else
   boost::unordered_set<test::minimal::movable1,
     test::minimal::hash<test::minimal::movable1>,
     test::minimal::equal_to<test::minimal::movable1>,
     test::minimal::allocator<test::minimal::movable1> >
     set;
+#endif
 
   // unordered_unique_test(set, movable1);
   unordered_set_test(set, movable1);
   unordered_movable_test(set, movable1, movable1, hash, equal_to);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_multiset.\n";
 
   boost::unordered_multiset<test::minimal::movable1,
@@ -219,6 +313,7 @@ UNORDERED_AUTO_TEST (movable1_tests) {
   // unordered_equivalent_test(multiset, movable1);
   unordered_set_test(multiset, movable1);
   unordered_movable_test(multiset, movable1, movable1, hash, equal_to);
+#endif
 }
 
 UNORDERED_AUTO_TEST (movable2_tests) {
@@ -229,17 +324,25 @@ UNORDERED_AUTO_TEST (movable2_tests) {
   test::minimal::equal_to<test::minimal::movable2> equal_to(x);
 
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_set.\n";
-
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<test::minimal::movable2,
+    test::minimal::hash<test::minimal::movable2>,
+    test::minimal::equal_to<test::minimal::movable2>,
+    test::minimal::allocator<test::minimal::movable2> >
+    set;
+#else
   boost::unordered_set<test::minimal::movable2,
     test::minimal::hash<test::minimal::movable2>,
     test::minimal::equal_to<test::minimal::movable2>,
     test::minimal::allocator<test::minimal::movable2> >
     set;
+#endif
 
   // unordered_unique_test(set, movable2);
   unordered_set_test(set, movable2);
   unordered_movable_test(set, movable2, movable2, hash, equal_to);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_multiset.\n";
 
   boost::unordered_multiset<test::minimal::movable2,
@@ -251,6 +354,7 @@ UNORDERED_AUTO_TEST (movable2_tests) {
   // unordered_equivalent_test(multiset, movable2);
   unordered_set_test(multiset, movable2);
   unordered_movable_test(multiset, movable2, movable2, hash, equal_to);
+#endif
 }
 
 UNORDERED_AUTO_TEST (destructible_tests) {
@@ -261,14 +365,21 @@ UNORDERED_AUTO_TEST (destructible_tests) {
   test::minimal::equal_to<test::minimal::destructible> equal_to(x);
 
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_set.\n";
-
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<test::minimal::destructible,
+    test::minimal::hash<test::minimal::destructible>,
+    test::minimal::equal_to<test::minimal::destructible> >
+    set;
+#else
   boost::unordered_set<test::minimal::destructible,
     test::minimal::hash<test::minimal::destructible>,
     test::minimal::equal_to<test::minimal::destructible> >
     set;
+#endif
 
   unordered_destructible_test(set);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Test unordered_multiset.\n";
 
   boost::unordered_multiset<test::minimal::destructible,
@@ -277,6 +388,7 @@ UNORDERED_AUTO_TEST (destructible_tests) {
     multiset;
 
   unordered_destructible_test(multiset);
+#endif
 }
 
 // Test for ambiguity when using key convertible from iterator
@@ -297,6 +409,11 @@ std::size_t hash_value(lwg2059_key x)
 bool operator==(lwg2059_key x, lwg2059_key y) { return x.value == y.value; }
 
 UNORDERED_AUTO_TEST (lwg2059) {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<lwg2059_key> x;
+  x.emplace(lwg2059_key(10));
+  x.erase(x.begin());
+#else
   {
     boost::unordered_set<lwg2059_key> x;
     x.emplace(lwg2059_key(10));
@@ -308,6 +425,7 @@ UNORDERED_AUTO_TEST (lwg2059) {
     x.emplace(lwg2059_key(10));
     x.erase(x.begin());
   }
+#endif
 }
 
 RUN_TESTS()

test/unordered/compile_tests.hpp

@@ -1,5 +1,6 @@
 
 // Copyright 2005-2009 Daniel James.
+// 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)
 
@@ -70,9 +71,19 @@ template <class X, class T> void container_test(X& r, T const&)
   typedef typename X::reference reference;
   typedef typename X::const_reference const_reference;
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   typedef typename X::node_type node_type;
+#endif
 
   typedef typename X::allocator_type allocator_type;
+  typedef typename X::pointer pointer;
+  typedef typename X::const_pointer const_pointer;
+
+  BOOST_STATIC_ASSERT((boost::is_same<pointer,
+    typename boost::allocator_pointer<allocator_type>::type>::value));
+
+  BOOST_STATIC_ASSERT((boost::is_same<const_pointer,
+    typename boost::allocator_const_pointer<allocator_type>::type>::value));
 
   // value_type
 
@@ -97,8 +108,10 @@ template <class X, class T> void container_test(X& r, T const&)
 
   // node_type
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_STATIC_ASSERT((
     boost::is_same<allocator_type, typename node_type::allocator_type>::value));
+#endif
 
   // difference_type
 
@@ -167,6 +180,7 @@ template <class X, class T> void container_test(X& r, T const&)
   sink(X(rvalue(a_const), m));
   X c3(rvalue(a_const), m);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   // node_type
 
   implicit_construct<node_type const>();
@@ -193,6 +207,7 @@ template <class X, class T> void container_test(X& r, T const&)
   test::check_return_type<bool>::equals(n_const.empty());
   TEST_NOEXCEPT_EXPR(!n_const);
   TEST_NOEXCEPT_EXPR(n_const.empty());
+#endif
 
   // Avoid unused variable warnings:
 
@@ -262,24 +277,30 @@ template <class X, class Key> void unordered_set_test(X& r, Key const&)
 
   typedef typename X::iterator iterator;
   typedef typename X::const_iterator const_iterator;
+#ifndef BOOST_UNORDERED_FOA_TESTS
   typedef typename X::local_iterator local_iterator;
   typedef typename X::const_local_iterator const_local_iterator;
+#endif
   typedef typename std::iterator_traits<iterator>::pointer iterator_pointer;
   typedef typename std::iterator_traits<const_iterator>::pointer
     const_iterator_pointer;
+#ifndef BOOST_UNORDERED_FOA_TESTS
   typedef typename std::iterator_traits<local_iterator>::pointer
     local_iterator_pointer;
   typedef typename std::iterator_traits<const_local_iterator>::pointer
     const_local_iterator_pointer;
+#endif
 
   BOOST_STATIC_ASSERT(
     (boost::is_same<value_type const*, iterator_pointer>::value));
   BOOST_STATIC_ASSERT(
     (boost::is_same<value_type const*, const_iterator_pointer>::value));
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_STATIC_ASSERT(
     (boost::is_same<value_type const*, local_iterator_pointer>::value));
   BOOST_STATIC_ASSERT(
     (boost::is_same<value_type const*, const_local_iterator_pointer>::value));
+#endif
 
   // pointer_traits<iterator>
 
@@ -299,6 +320,8 @@ template <class X, class Key> void unordered_set_test(X& r, Key const&)
   BOOST_STATIC_ASSERT((boost::is_same<std::ptrdiff_t,
     typename boost::pointer_traits<const_iterator>::difference_type>::value));
 
+  (void) r;
+#ifndef BOOST_UNORDERED_FOA_TESTS
   // pointer_traits<local_iterator>
 
   BOOST_STATIC_ASSERT((boost::is_same<local_iterator,
@@ -330,6 +353,7 @@ template <class X, class Key> void unordered_set_test(X& r, Key const&)
   r.emplace(boost::move(k_lvalue));
   node_type n1 = r.extract(r.begin());
   test::check_return_type<value_type>::equals_ref(n1.value());
+#endif
 }
 
 template <class X, class Key, class T>
@@ -345,23 +369,29 @@ void unordered_map_test(X& r, Key const& k, T const& v)
 
   typedef typename X::iterator iterator;
   typedef typename X::const_iterator const_iterator;
+#ifndef BOOST_UNORDERED_FOA_TESTS
   typedef typename X::local_iterator local_iterator;
   typedef typename X::const_local_iterator const_local_iterator;
+#endif
   typedef typename std::iterator_traits<iterator>::pointer iterator_pointer;
   typedef typename std::iterator_traits<const_iterator>::pointer
     const_iterator_pointer;
+#ifndef BOOST_UNORDERED_FOA_TESTS
   typedef typename std::iterator_traits<local_iterator>::pointer
     local_iterator_pointer;
   typedef typename std::iterator_traits<const_local_iterator>::pointer
     const_local_iterator_pointer;
+#endif
 
   BOOST_STATIC_ASSERT((boost::is_same<value_type*, iterator_pointer>::value));
   BOOST_STATIC_ASSERT(
     (boost::is_same<value_type const*, const_iterator_pointer>::value));
+#ifndef BOOST_UNORDERED_FOA_TESTS
   BOOST_STATIC_ASSERT(
     (boost::is_same<value_type*, local_iterator_pointer>::value));
   BOOST_STATIC_ASSERT(
     (boost::is_same<value_type const*, const_local_iterator_pointer>::value));
+#endif
 
   // pointer_traits<iterator>
 
@@ -381,6 +411,7 @@ void unordered_map_test(X& r, Key const& k, T const& v)
   BOOST_STATIC_ASSERT((boost::is_same<std::ptrdiff_t,
     typename boost::pointer_traits<const_iterator>::difference_type>::value));
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   // pointer_traits<local_iterator>
 
   BOOST_STATIC_ASSERT((boost::is_same<local_iterator,
@@ -409,6 +440,7 @@ void unordered_map_test(X& r, Key const& k, T const& v)
   BOOST_STATIC_ASSERT((boost::is_same<T, node_mapped_type>::value));
   // Superfluous,but just to make sure.
   BOOST_STATIC_ASSERT((!boost::is_const<node_key_type>::value));
+#endif
 
   // Calling functions
 
@@ -427,8 +459,12 @@ void unordered_map_test(X& r, Key const& k, T const& v)
   r.emplace(k_lvalue, v_lvalue);
   r.emplace(rvalue(k), rvalue(v));
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  r.emplace(std::piecewise_construct, std::make_tuple(k), std::make_tuple(v));
+#else
   r.emplace(boost::unordered::piecewise_construct, boost::make_tuple(k),
     boost::make_tuple(v));
+#endif
 
   // Emplace with hint
 
@@ -436,9 +472,15 @@ void unordered_map_test(X& r, Key const& k, T const& v)
   r.emplace_hint(r.begin(), k_lvalue, v_lvalue);
   r.emplace_hint(r.begin(), rvalue(k), rvalue(v));
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  r.emplace_hint(r.begin(), std::piecewise_construct, std::make_tuple(k),
+    std::make_tuple(v));
+#else
   r.emplace_hint(r.begin(), boost::unordered::piecewise_construct,
     boost::make_tuple(k), boost::make_tuple(v));
+#endif
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   // Extract
 
   test::check_return_type<node_type>::equals(r.extract(r.begin()));
@@ -461,6 +503,7 @@ void unordered_map_test(X& r, Key const& k, T const& v)
   node_type n = r.extract(r.begin());
   test::check_return_type<node_key_type>::equals_ref(n.key());
   test::check_return_type<node_mapped_type>::equals_ref(n.mapped());
+#endif
 }
 
 template <class X> void equality_test(X& r)
@@ -479,6 +522,7 @@ template <class X, class T> void unordered_unique_test(X& r, T const& t)
   test::check_return_type<std::pair<iterator, bool> >::equals(r.insert(t));
   test::check_return_type<std::pair<iterator, bool> >::equals(r.emplace(t));
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   typedef typename X::node_type node_type;
   typedef typename X::insert_return_type insert_return_type;
 
@@ -503,6 +547,7 @@ template <class X, class T> void unordered_unique_test(X& r, T const& t)
   test::check_return_type<iterator>::equals(insert_return.position);
   test::check_return_type<node_type>::equals_ref(insert_return.node);
   boost::swap(insert_return, insert_return2);
+#endif
 }
 
 template <class X, class T> void unordered_equivalent_test(X& r, T const& t)
@@ -554,6 +599,7 @@ void unordered_test(X& x, Key& k, Hash& hf, Pred& eq)
 
   typedef typename X::iterator iterator;
   typedef typename X::const_iterator const_iterator;
+#ifndef BOOST_UNORDERED_FOA_TESTS
   typedef typename X::local_iterator local_iterator;
   typedef typename X::const_local_iterator const_local_iterator;
 
@@ -590,6 +636,7 @@ void unordered_test(X& x, Key& k, Hash& hf, Pred& eq)
     const_local_iterator_pointer;
   typedef typename std::iterator_traits<const_local_iterator>::reference
     const_local_iterator_reference;
+#endif
   typedef typename X::allocator_type allocator_type;
 
   BOOST_STATIC_ASSERT((boost::is_same<Key, key_type>::value));
@@ -602,6 +649,7 @@ void unordered_test(X& x, Key& k, Hash& hf, Pred& eq)
   BOOST_STATIC_ASSERT((boost::is_same<Pred, key_equal>::value));
   test::check_return_type<bool>::convertible(eq(k, k));
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   boost::function_requires<boost::InputIteratorConcept<local_iterator> >();
   BOOST_STATIC_ASSERT(
     (boost::is_same<local_iterator_category, iterator_category>::value));
@@ -622,6 +670,7 @@ void unordered_test(X& x, Key& k, Hash& hf, Pred& eq)
     const_iterator_pointer>::value));
   BOOST_STATIC_ASSERT((boost::is_same<const_local_iterator_reference,
     const_iterator_reference>::value));
+#endif
 
   X a;
   allocator_type m = a.get_allocator();
@@ -667,6 +716,7 @@ void unordered_test(X& x, Key& k, Hash& hf, Pred& eq)
   test::check_return_type<std::pair<const_iterator, const_iterator> >::equals(
     b.equal_range(k));
   test::check_return_type<size_type>::equals(b.bucket_count());
+#ifndef BOOST_UNORDERED_FOA_TESTS
   test::check_return_type<size_type>::equals(b.max_bucket_count());
   test::check_return_type<size_type>::equals(b.bucket(k));
   test::check_return_type<size_type>::equals(b.bucket_size(0));
@@ -680,6 +730,7 @@ void unordered_test(X& x, Key& k, Hash& hf, Pred& eq)
   test::check_return_type<const_local_iterator>::equals(b.cbegin(0));
   test::check_return_type<const_local_iterator>::equals(a.cend(0));
   test::check_return_type<const_local_iterator>::equals(b.cend(0));
+#endif
 
   test::check_return_type<float>::equals(b.load_factor());
   test::check_return_type<float>::equals(b.max_load_factor());
@@ -792,7 +843,11 @@ void unordered_copyable_test(X& x, Key& k, T& t, Hash& hf, Pred& eq)
   X a10;
   a10.insert(t);
   q = a10.cbegin();
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  BOOST_STATIC_ASSERT(std::is_same<void, decltype(a10.erase(q))>::value);
+#else
   test::check_return_type<iterator>::equals(a10.erase(q));
+#endif
 
   // Avoid unused variable warnings:
 
@@ -807,10 +862,12 @@ void unordered_copyable_test(X& x, Key& k, T& t, Hash& hf, Pred& eq)
   sink(a7a);
   sink(a9a);
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   typedef typename X::node_type node_type;
   typedef typename X::allocator_type allocator_type;
   node_type const n_const = a.extract(a.begin());
   test::check_return_type<allocator_type>::equals(n_const.get_allocator());
+#endif
 }
 
 template <class X, class Key, class T, class Hash, class Pred>
@@ -879,7 +936,11 @@ void unordered_movable_test(X& x, Key& k, T& /* t */, Hash& hf, Pred& eq)
   T v5(v);
   a10.insert(boost::move(v5));
   q = a10.cbegin();
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  BOOST_STATIC_ASSERT(std::is_same<void, decltype(a10.erase(q))>::value);
+#else
   test::check_return_type<iterator>::equals(a10.erase(q));
+#endif
 
   // Avoid unused variable warnings:
 

test/unordered/constructor_tests.cpp

@@ -1,14 +1,10 @@
 
 // Copyright 2006-2010 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../helpers/test.hpp"
 #include "../objects/test.hpp"
@@ -35,6 +31,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 +70,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 +138,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 +165,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 +325,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 +381,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)
   {
@@ -394,6 +493,35 @@ namespace constructor_tests {
     test::check_equivalent_keys(x);
   }
 
+  using test::default_generator;
+  using test::generate_collisions;
+  using test::limited_range;
+
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_map<test::object, test::object, test::hash,
+    test::equal_to, std::allocator<test::object> >* test_map_std_alloc;
+
+  boost::unordered_flat_set<test::object, test::hash, test::equal_to,
+    test::allocator1<test::object> >* test_set;
+  boost::unordered_flat_map<test::object, test::object, test::hash,
+    test::equal_to, test::allocator2<test::object> >* test_map;
+
+  UNORDERED_TEST(constructor_tests1,
+    ((test_map_std_alloc)(test_set)(test_map))(
+      (default_generator)(generate_collisions)(limited_range)))
+
+  UNORDERED_TEST(constructor_tests2,
+    ((test_set)(test_map))(
+      (default_generator)(generate_collisions)(limited_range)))
+
+  UNORDERED_TEST(map_constructor_test,
+    ((test_map_std_alloc)(test_map))(
+      (default_generator)(generate_collisions)(limited_range)))
+
+  UNORDERED_TEST(no_alloc_default_construct_test,
+    ((test_set)(test_map))(
+      (default_generator)(generate_collisions)(limited_range)))
+#else
   boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
     std::allocator<test::object> >* test_map_std_alloc;
 
@@ -406,10 +534,6 @@ namespace constructor_tests {
   boost::unordered_multimap<test::object, test::object, test::hash,
     test::equal_to, test::allocator1<test::object> >* test_multimap;
 
-  using test::default_generator;
-  using test::generate_collisions;
-  using test::limited_range;
-
   UNORDERED_TEST(constructor_tests1,
     ((test_map_std_alloc)(test_set)(test_multiset)(test_map)(test_multimap))(
       (default_generator)(generate_collisions)(limited_range)))
@@ -422,11 +546,20 @@ 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)))
+#endif
+
 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 
   UNORDERED_AUTO_TEST (test_default_initializer_list) {
     std::initializer_list<int> init;
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    boost::unordered_flat_set<int> x1 = init;
+#else
     boost::unordered_set<int> x1 = init;
+#endif
     BOOST_TEST(x1.empty());
   }
 
@@ -435,7 +568,12 @@ namespace constructor_tests {
 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 
   UNORDERED_AUTO_TEST (test_initializer_list) {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    boost::unordered_flat_set<int> x1 = {2, 10, 45, -5};
+#else
     boost::unordered_set<int> x1 = {2, 10, 45, -5};
+#endif
+
     BOOST_TEST(x1.find(10) != x1.end());
     BOOST_TEST(x1.find(46) == x1.end());
   }

test/unordered/contains_tests.cpp

@@ -1,13 +1,8 @@
-// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../helpers/test.hpp"
 
@@ -129,6 +124,20 @@ template <class UnorderedMap> void test_map_non_transparent_contains()
 
 void test_map()
 {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  typedef boost::unordered_flat_map<key, int, transparent_hasher,
+    transparent_key_equal>
+    transparent_map;
+
+  typedef boost::unordered_flat_map<key, int, transparent_hasher, key_equal>
+    non_transparent_map1;
+
+  typedef boost::unordered_flat_map<key, int, hasher, transparent_key_equal>
+    non_transparent_map2;
+
+  typedef boost::unordered_flat_map<key, int, hasher, key_equal>
+    non_transparent_map3;
+#else
   typedef boost::unordered_map<key, int, transparent_hasher,
     transparent_key_equal>
     transparent_map;
@@ -141,6 +150,7 @@ void test_map()
 
   typedef boost::unordered_map<key, int, hasher, key_equal>
     non_transparent_map3;
+#endif
 
   test_map_transparent_contains<transparent_map>();
   test_map_non_transparent_contains<non_transparent_map1>();
@@ -148,6 +158,7 @@ void test_map()
   test_map_non_transparent_contains<non_transparent_map3>();
 }
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
 void test_multimap()
 {
   typedef boost::unordered_multimap<key, int, transparent_hasher,
@@ -168,6 +179,7 @@ void test_multimap()
   test_map_non_transparent_contains<non_transparent_multimap2>();
   test_map_non_transparent_contains<non_transparent_multimap3>();
 }
+#endif
 
 template <class UnorderedSet> void test_set_transparent_contains()
 {
@@ -231,6 +243,18 @@ template <class UnorderedSet> void test_set_non_transparent_contains()
 
 void test_set()
 {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  typedef boost::unordered_flat_set<key, transparent_hasher,
+    transparent_key_equal>
+    transparent_set;
+
+  typedef boost::unordered_flat_set<key, transparent_hasher, key_equal>
+    non_transparent_set1;
+  typedef boost::unordered_flat_set<key, hasher, transparent_key_equal>
+    non_transparent_set2;
+  typedef boost::unordered_flat_set<key, hasher, key_equal>
+    non_transparent_set3;
+#else
   typedef boost::unordered_set<key, transparent_hasher, transparent_key_equal>
     transparent_set;
 
@@ -239,6 +263,7 @@ void test_set()
   typedef boost::unordered_set<key, hasher, transparent_key_equal>
     non_transparent_set2;
   typedef boost::unordered_set<key, hasher, key_equal> non_transparent_set3;
+#endif
 
   test_set_transparent_contains<transparent_set>();
   test_set_non_transparent_contains<non_transparent_set1>();
@@ -246,6 +271,7 @@ void test_set()
   test_set_non_transparent_contains<non_transparent_set3>();
 }
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
 void test_multiset()
 {
   typedef boost::unordered_multiset<key, transparent_hasher,
@@ -264,11 +290,15 @@ void test_multiset()
   test_set_non_transparent_contains<non_transparent_multiset2>();
   test_set_non_transparent_contains<non_transparent_multiset3>();
 }
+#endif
 
 UNORDERED_AUTO_TEST (contains_) { // avoid -Wshadow warning with `bool contains`
   test_map();
-  test_multimap();
   test_set();
+#ifndef BOOST_UNORDERED_FOA_TESTS
+  test_multimap();
+  test_multiset();
+#endif
 }
 
 RUN_TESTS()

test/unordered/copy_tests.cpp

@@ -1,14 +1,10 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../helpers/test.hpp"
 #include "../objects/test.hpp"
@@ -43,6 +39,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 +104,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 +135,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 +164,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 +195,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_;
 
@@ -150,6 +225,38 @@ namespace copy_tests {
     }
   }
 
+  using test::default_generator;
+  using test::generate_collisions;
+  using test::limited_range;
+
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<test::object, test::hash, test::equal_to,
+    test::allocator1<test::object> >* test_set;
+  boost::unordered_flat_map<test::object, test::object, test::hash,
+    test::equal_to, test::allocator1<test::object> >* test_map;
+
+  boost::unordered_flat_set<test::object, test::hash, test::equal_to,
+    test::cxx11_allocator<test::object, test::select_copy> >*
+    test_set_select_copy;
+  boost::unordered_flat_map<test::object, test::object, test::hash,
+    test::equal_to, test::cxx11_allocator<test::object, test::select_copy> >*
+    test_map_select_copy;
+
+  boost::unordered_flat_set<test::object, test::hash, test::equal_to,
+    test::cxx11_allocator<test::object, test::no_select_copy> >*
+    test_set_no_select_copy;
+  boost::unordered_flat_map<test::object, test::object, test::hash,
+    test::equal_to, test::cxx11_allocator<test::object, test::no_select_copy> >*
+    test_map_no_select_copy;
+
+  UNORDERED_TEST(copy_construct_tests1,
+    ((test_set)(test_map)(test_set_select_copy)(test_map_select_copy)(test_set_no_select_copy)(test_map_no_select_copy))(
+      (default_generator)(generate_collisions)(limited_range)))
+
+  UNORDERED_TEST(copy_construct_tests2,
+    ((test_set)(test_map)(test_set_select_copy)(test_map_select_copy)(test_set_no_select_copy)(test_map_no_select_copy))(
+      (default_generator)(generate_collisions)(limited_range)))
+#else
   boost::unordered_set<test::object, test::hash, test::equal_to,
     test::allocator1<test::object> >* test_set;
   boost::unordered_multiset<test::object, test::hash, test::equal_to,
@@ -185,25 +292,14 @@ namespace copy_tests {
     test::equal_to, test::cxx11_allocator<test::object, test::no_select_copy> >*
     test_multimap_no_select_copy;
 
-  using test::default_generator;
-  using test::generate_collisions;
-  using test::limited_range;
-
   UNORDERED_TEST(copy_construct_tests1,
-    ((test_set)(test_multiset)(test_map)(test_multimap)(test_set_select_copy)(
-      test_multiset_select_copy)(test_map_select_copy)(
-      test_multimap_select_copy)(test_set_no_select_copy)(
-      test_multiset_no_select_copy)(test_map_no_select_copy)(
-      test_multimap_no_select_copy))(
+    ((test_set)(test_multiset)(test_map)(test_multimap)(test_set_select_copy)(test_multiset_select_copy)(test_map_select_copy)(test_multimap_select_copy)(test_set_no_select_copy)(test_multiset_no_select_copy)(test_map_no_select_copy)(test_multimap_no_select_copy))(
       (default_generator)(generate_collisions)(limited_range)))
 
   UNORDERED_TEST(copy_construct_tests2,
-    ((test_set)(test_multiset)(test_map)(test_multimap)(test_set_select_copy)(
-      test_multiset_select_copy)(test_map_select_copy)(
-      test_multimap_select_copy)(test_set_no_select_copy)(
-      test_multiset_no_select_copy)(test_map_no_select_copy)(
-      test_multimap_no_select_copy))(
+    ((test_set)(test_multiset)(test_map)(test_multimap)(test_set_select_copy)(test_multiset_select_copy)(test_map_select_copy)(test_multimap_select_copy)(test_set_no_select_copy)(test_multiset_no_select_copy)(test_map_no_select_copy)(test_multimap_no_select_copy))(
       (default_generator)(generate_collisions)(limited_range)))
-}
+#endif
+} // namespace copy_tests
 
 RUN_TESTS()

test/unordered/emplace_tests.cpp

@@ -1,14 +1,10 @@
 //
 // Copyright 2016 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include <boost/functional/hash/hash.hpp>
 #include "../helpers/test.hpp"
@@ -46,47 +42,56 @@ namespace emplace_tests {
     A8 a8;
     A9 a9;
 
-    emplace_value(A0 const& b0, A1 const& b1) : arg_count(2), a0(b0), a1(b1) {}
+    emplace_value(A0 const& b0, A1 const& b1)
+        : arg_count(2), a0(b0), a1(b1), a2('\0'), a3(-1), a4(-1), a5(-1),
+          a6(-1), a7(-1), a8(-1), a9(-1)
+    {
+    }
 
     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2)
-        : arg_count(3), a0(b0), a1(b1), a2(b2)
+        : arg_count(3), a0(b0), a1(b1), a2(b2), a3(-1), a4(-1), a5(-1), a6(-1),
+          a7(-1), a8(-1), a9(-1)
     {
     }
 
     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3)
-        : arg_count(4), a0(b0), a1(b1), a2(b2), a3(b3)
+        : arg_count(4), a0(b0), a1(b1), a2(b2), a3(b3), a4(-1), a5(-1), a6(-1),
+          a7(-1), a8(-1), a9(-1)
     {
     }
 
     emplace_value(
       A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3, A4 const& b4)
-        : arg_count(5), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4)
+        : arg_count(5), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(-1), a6(-1),
+          a7(-1), a8(-1), a9(-1)
     {
     }
 
     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3,
       A4 const& b4, A5 const& b5)
-        : arg_count(6), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5)
+        : arg_count(6), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(-1),
+          a7(-1), a8(-1), a9(-1)
     {
     }
 
     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3,
       A4 const& b4, A5 const& b5, A6 const& b6)
-        : arg_count(7), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6)
+        : arg_count(7), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6),
+          a7(-1), a8(-1), a9(-1)
     {
     }
 
     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3,
       A4 const& b4, A5 const& b5, A6 const& b6, A7 const& b7)
         : arg_count(8), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6),
-          a7(b7)
+          a7(b7), a8(-1), a9(-1)
     {
     }
 
     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3,
       A4 const& b4, A5 const& b5, A6 const& b6, A7 const& b7, A8 const& b8)
         : arg_count(9), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6),
-          a7(b7), a8(b8)
+          a7(b7), a8(b8), a9(-1)
     {
     }
 
@@ -162,16 +167,29 @@ namespace emplace_tests {
       return true;
     }
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    emplace_value() = delete;
+    emplace_value(emplace_value const&) = default;
+    emplace_value(emplace_value&&) = default;
+#else
   private:
     emplace_value();
     emplace_value(emplace_value const&);
+#endif
+
   };
 
   UNORDERED_AUTO_TEST (emplace_set) {
     test::check_instances check_;
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    typedef boost::unordered_flat_set<emplace_value,
+      boost::hash<emplace_value> >
+      container;
+#else
     typedef boost::unordered_set<emplace_value, boost::hash<emplace_value> >
       container;
+#endif
     typedef container::iterator iterator;
     typedef std::pair<iterator, bool> return_type;
     container x(10);
@@ -187,7 +205,15 @@ namespace emplace_tests {
     BOOST_TEST(*r1.first == v1);
     BOOST_TEST(r1.first == x.find(v1));
     BOOST_TEST_EQ(check_.instances(), 2);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    // 1 from v1
+    // 1 from constructing the value_type() so we can pluck the key
+    // 1 from move-constructing which invokes the counted_object base
+    // constructor
+    BOOST_TEST_EQ(check_.constructions(), 3);
+#else
     BOOST_TEST_EQ(check_.constructions(), 2);
+#endif
 
     // 3 args
 
@@ -198,7 +224,11 @@ namespace emplace_tests {
     BOOST_TEST(*r1.first == v2);
     BOOST_TEST(r1.first == x.find(v2));
     BOOST_TEST_EQ(check_.instances(), 4);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  BOOST_TEST_EQ(check_.constructions(), 6);
+#else
     BOOST_TEST_EQ(check_.constructions(), 4);
+#endif
 
     // 7 args with hint + duplicate
 
@@ -208,7 +238,11 @@ namespace emplace_tests {
     BOOST_TEST(*i1 == v3);
     BOOST_TEST(i1 == x.find(v3));
     BOOST_TEST_EQ(check_.instances(), 6);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    BOOST_TEST_EQ(check_.constructions(), 9);
+#else
     BOOST_TEST_EQ(check_.constructions(), 6);
+#endif
 
     r2 = x.emplace(25, "something", 'z', 4, 5, 6, 7);
     BOOST_TEST_EQ(x.size(), 3u);
@@ -218,7 +252,11 @@ namespace emplace_tests {
     // whether it can emplace, so there's an extra construction
     // here.
     BOOST_TEST_EQ(check_.instances(), 6);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    BOOST_TEST_EQ(check_.constructions(), 10);
+#else
     BOOST_TEST_EQ(check_.constructions(), 7);
+#endif
 
     // 10 args + hint duplicate
 
@@ -230,7 +268,11 @@ namespace emplace_tests {
     BOOST_TEST(*r1.first == v4);
     BOOST_TEST(r1.first == x.find(v4));
     BOOST_TEST_EQ(check_.instances(), 8);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    BOOST_TEST_EQ(check_.constructions(), 13);
+#else
     BOOST_TEST_EQ(check_.constructions(), 9);
+#endif
 
     BOOST_TEST(
       r1.first == x.emplace_hint(r1.first, 10, "", 'a', 4, 5, 6, 7, 8, 9, 10));
@@ -239,7 +281,11 @@ namespace emplace_tests {
     BOOST_TEST(
       r1.first == x.emplace_hint(x.end(), 10, "", 'a', 4, 5, 6, 7, 8, 9, 10));
     BOOST_TEST_EQ(check_.instances(), 8);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    BOOST_TEST_EQ(check_.constructions(), 16);
+#else
     BOOST_TEST_EQ(check_.constructions(), 12);
+#endif
 
     BOOST_TEST_EQ(x.size(), 4u);
     BOOST_TEST(x.count(v1) == 1);
@@ -248,6 +294,7 @@ namespace emplace_tests {
     BOOST_TEST(x.count(v4) == 1);
   }
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   UNORDERED_AUTO_TEST (emplace_multiset) {
     test::check_instances check_;
 
@@ -325,20 +372,79 @@ namespace emplace_tests {
     BOOST_TEST_EQ(x.count(v2), 2u);
     BOOST_TEST_EQ(x.count(v3), 2u);
   }
+#endif
 
   UNORDERED_AUTO_TEST (emplace_map) {
     test::check_instances check_;
-
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    typedef boost::unordered_flat_map<emplace_value, emplace_value,
+      boost::hash<emplace_value> >
+      container;
+#else
     typedef boost::unordered_map<emplace_value, emplace_value,
       boost::hash<emplace_value> >
       container;
+#endif
     typedef container::iterator iterator;
     typedef std::pair<iterator, bool> return_type;
     container x(10);
     return_type r1, r2;
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
     // 5/8 args + duplicate
+    emplace_value k1(5, "", 'b', 4, 5);
+    emplace_value m1(8, "xxx", 'z', 4, 5, 6, 7, 8);
+    r1 = x.emplace(std::piecewise_construct, std::make_tuple(5, "", 'b', 4, 5),
+      std::make_tuple(8, "xxx", 'z', 4, 5, 6, 7, 8));
+    BOOST_TEST_EQ(x.size(), 1u);
+    BOOST_TEST(r1.second);
+    BOOST_TEST(x.find(k1) == r1.first);
+    BOOST_TEST(x.find(k1)->second == m1);
+    BOOST_TEST_EQ(check_.instances(), 4);
+    BOOST_TEST_EQ(check_.constructions(), 6);
 
+    r2 = x.emplace(std::piecewise_construct, std::make_tuple(5, "", 'b', 4, 5),
+      std::make_tuple(8, "xxx", 'z', 4, 5, 6, 7, 8));
+    BOOST_TEST_EQ(x.size(), 1u);
+    BOOST_TEST(!r2.second);
+    BOOST_TEST(r1.first == r2.first);
+    BOOST_TEST(x.find(k1)->second == m1);
+    BOOST_TEST_EQ(check_.instances(), 4);
+    // constructions could possibly be 5 if the implementation only
+    // constructed the key.
+    BOOST_TEST_EQ(check_.constructions(), 8);
+
+    // 9/3 args + duplicates with hints, different mapped value.
+
+    emplace_value k2(9, "", 'b', 4, 5, 6, 7, 8, 9);
+    emplace_value m2(3, "aaa", 'm');
+    r1 = x.emplace(std::piecewise_construct,
+      std::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
+      std::make_tuple(3, "aaa", 'm'));
+    BOOST_TEST_EQ(x.size(), 2u);
+    BOOST_TEST(r1.second);
+    BOOST_TEST(r1.first->first.arg_count == 9);
+    BOOST_TEST(r1.first->second.arg_count == 3);
+    BOOST_TEST(x.find(k2) == r1.first);
+    BOOST_TEST(x.find(k2)->second == m2);
+    BOOST_TEST_EQ(check_.instances(), 8);
+    BOOST_TEST_EQ(check_.constructions(), 14);
+
+    BOOST_TEST(r1.first == x.emplace_hint(r1.first, std::piecewise_construct,
+                             std::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
+                             std::make_tuple(15, "jkjk")));
+    BOOST_TEST(r1.first == x.emplace_hint(r2.first, std::piecewise_construct,
+                             std::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
+                             std::make_tuple(275, "xxx", 'm', 6)));
+    BOOST_TEST(r1.first == x.emplace_hint(x.end(), std::piecewise_construct,
+                             std::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
+                             std::make_tuple(-10, "blah blah", '\0')));
+    BOOST_TEST_EQ(x.size(), 2u);
+    BOOST_TEST(x.find(k2)->second == m2);
+    BOOST_TEST_EQ(check_.instances(), 8);
+    BOOST_TEST_EQ(check_.constructions(), 20);
+#else
+    // 5/8 args + duplicate
     emplace_value k1(5, "", 'b', 4, 5);
     emplace_value m1(8, "xxx", 'z', 4, 5, 6, 7, 8);
     r1 = x.emplace(boost::unordered::piecewise_construct,
@@ -395,8 +501,10 @@ namespace emplace_tests {
     BOOST_TEST(x.find(k2)->second == m2);
     BOOST_TEST_EQ(check_.instances(), 8);
     BOOST_TEST_EQ(check_.constructions(), 16);
+#endif
   }
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
   UNORDERED_AUTO_TEST (emplace_multimap) {
     test::check_instances check_;
 
@@ -461,11 +569,15 @@ namespace emplace_tests {
     BOOST_TEST_EQ(check_.instances(), 20);
     BOOST_TEST_EQ(check_.constructions(), 20);
   }
+#endif
 
   UNORDERED_AUTO_TEST (try_emplace) {
     test::check_instances check_;
-
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    typedef boost::unordered_flat_map<int, emplace_value> container;
+#else
     typedef boost::unordered_map<int, emplace_value> container;
+#endif
     typedef container::iterator iterator;
     typedef std::pair<iterator, bool> return_type;
     container x(10);

test/unordered/equality_tests.cpp

@@ -1,14 +1,10 @@
 
 // Copyright 2008-2009 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include <boost/preprocessor/seq.hpp>
 #include <list>
@@ -30,14 +26,27 @@ namespace equality_tests {
     }
   };
 
-#define UNORDERED_EQUALITY_SET_TEST(seq1, op, seq2)                            \
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  using boost_unordered_set =
+    boost::unordered_flat_set<int, mod_compare, mod_compare>;
+
+  using boost_unordered_map =
+    boost::unordered_flat_map<int, int, mod_compare, mod_compare>;
+
+#define UNORDERED_EQUALITY_MULTISET_TEST(seq1, op, seq2)                       \
   {                                                                            \
-    boost::unordered_set<int, mod_compare, mod_compare> set1, set2;            \
-    BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set1, seq1)                    \
-    BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set2, seq2)                    \
-    BOOST_TEST(set1 op set2);                                                  \
   }
 
+#define UNORDERED_EQUALITY_MULTIMAP_TEST(seq1, op, seq2)                       \
+  {                                                                            \
+  }
+#else
+  typedef boost::unordered_set<int, mod_compare, mod_compare>
+    boost_unordered_set;
+
+  typedef boost::unordered_map<int, int, mod_compare, mod_compare>
+    boost_unordered_map;
+
 #define UNORDERED_EQUALITY_MULTISET_TEST(seq1, op, seq2)                       \
   {                                                                            \
     boost::unordered_multiset<int, mod_compare, mod_compare> set1, set2;       \
@@ -46,17 +55,26 @@ namespace equality_tests {
     BOOST_TEST(set1 op set2);                                                  \
   }
 
-#define UNORDERED_EQUALITY_MAP_TEST(seq1, op, seq2)                            \
+#define UNORDERED_EQUALITY_MULTIMAP_TEST(seq1, op, seq2)                       \
   {                                                                            \
-    boost::unordered_map<int, int, mod_compare, mod_compare> map1, map2;       \
+    boost::unordered_multimap<int, int, mod_compare, mod_compare> map1, map2;  \
     BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map1, seq1)                    \
     BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map2, seq2)                    \
     BOOST_TEST(map1 op map2);                                                  \
   }
+#endif
 
-#define UNORDERED_EQUALITY_MULTIMAP_TEST(seq1, op, seq2)                       \
+#define UNORDERED_EQUALITY_SET_TEST(seq1, op, seq2)                            \
   {                                                                            \
-    boost::unordered_multimap<int, int, mod_compare, mod_compare> map1, map2;  \
+    boost_unordered_set set1, set2;            \
+    BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set1, seq1)                    \
+    BOOST_PP_SEQ_FOR_EACH(UNORDERED_SET_INSERT, set2, seq2)                    \
+    BOOST_TEST(set1 op set2);                                                  \
+  }
+
+#define UNORDERED_EQUALITY_MAP_TEST(seq1, op, seq2)                            \
+  {                                                                            \
+    boost_unordered_map map1, map2;                                            \
     BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map1, seq1)                    \
     BOOST_PP_SEQ_FOR_EACH(UNORDERED_MAP_INSERT, map2, seq2)                    \
     BOOST_TEST(map1 op map2);                                                  \
@@ -67,7 +85,11 @@ namespace equality_tests {
   map.insert(std::pair<int const, int> BOOST_PP_SEQ_TO_TUPLE(item));
 
   UNORDERED_AUTO_TEST (equality_size_tests) {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    boost::unordered_flat_set<int> x1, x2;
+#else
     boost::unordered_set<int> x1, x2;
+#endif
     BOOST_TEST(x1 == x2);
     BOOST_TEST(!(x1 != x2));
 
@@ -134,7 +156,7 @@ namespace equality_tests {
   // different hash functions but the same equality predicate.
 
   UNORDERED_AUTO_TEST (equality_different_hash_test) {
-    typedef boost::unordered_set<int, mod_compare, mod_compare> set;
+    typedef boost_unordered_set set;
     set set1(0, mod_compare(false), mod_compare(false));
     set set2(0, mod_compare(true), mod_compare(true));
     BOOST_TEST(set1 == set2);

test/unordered/equivalent_keys_tests.cpp

@@ -1,14 +1,10 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../helpers/test.hpp"
 #include <algorithm>
@@ -38,8 +34,11 @@ void test_equal_insertion(Iterator begin, Iterator end)
 UNORDERED_AUTO_TEST (set_tests) {
   int values[][5] = {{1}, {54, 23}, {-13, 65}, {77, 77}, {986, 25, 986}};
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  typedef boost::unordered_flat_set<int> set;
+#else
   typedef boost::unordered_set<int> set;
-  typedef boost::unordered_multiset<int> multiset;
+#endif
 
   test_equal_insertion<set>(values[0], values[0] + 1);
   test_equal_insertion<set>(values[1], values[1] + 2);
@@ -47,6 +46,7 @@ UNORDERED_AUTO_TEST (set_tests) {
   test_equal_insertion<set>(values[3], values[3] + 2);
   test_equal_insertion<set>(values[4], values[4] + 3);
 
+  typedef boost::unordered_multiset<int> multiset;
   test_equal_insertion<multiset>(values[0], values[0] + 1);
   test_equal_insertion<multiset>(values[1], values[1] + 2);
   test_equal_insertion<multiset>(values[2], values[2] + 2);
@@ -66,12 +66,17 @@ UNORDERED_AUTO_TEST (map_tests) {
   v[2].push_back(std::pair<int const, int>(432, 24));
 
   for (int i = 0; i < 5; ++i)
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    test_equal_insertion<boost::unordered_flat_map<int, int> >(
+      v[i].begin(), v[i].end());
+#else
     test_equal_insertion<boost::unordered_map<int, int> >(
       v[i].begin(), v[i].end());
 
   for (int i2 = 0; i2 < 5; ++i2)
     test_equal_insertion<boost::unordered_multimap<int, int> >(
       v[i2].begin(), v[i2].end());
+#endif
 }
 
 RUN_TESTS()

test/unordered/erase_if.cpp

@@ -1,19 +1,15 @@
-// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #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
@@ -22,36 +18,13 @@
 namespace test {
   struct is_even
   {
-    is_even() {}
-
-#if BOOST_CXX_VERSION >= 201703L
-    // immovable for C++17
-    is_even(is_even const&) = delete;
-    is_even(is_even&&) = delete;
-
-    is_even& operator=(is_even const&) = delete;
-    is_even& operator=(is_even&&) = delete;
-#elif BOOST_CXX_VERSION >= 201103L
-    // move-only for C++11
-    is_even(is_even const&) = delete;
-    is_even(is_even&&) = default;
-
-    is_even& operator=(is_even const&) = delete;
-    is_even& operator=(is_even&&) = default;
-#else
-    // copyable otherwise
-    is_even(is_even const&) {}
-    is_even& operator=(is_even const&) { return *this; }
-#endif
-
-    bool operator()(
-      std::pair<std::string const, int>& key_value) UNORDERED_LVALUE_QUAL
+    bool operator()(std::pair<std::string const, int>& key_value)
     {
       int const v = key_value.second;
       return (v % 2 == 0);
     }
 
-    bool operator()(int const& value) UNORDERED_LVALUE_QUAL
+    bool operator()(int const& value)
     {
       int const v = value;
       return (v % 2 == 0);
@@ -60,37 +33,13 @@ namespace test {
 
   struct is_too_large
   {
-    is_too_large() {}
-
-#if BOOST_CXX_VERSION >= 201703L
-    // immovable for C++17
-    is_too_large(is_too_large const&) = delete;
-    is_too_large(is_too_large&&) = delete;
-
-    is_too_large& operator=(is_too_large const&) = delete;
-    is_too_large& operator=(is_too_large&&) = delete;
-#elif BOOST_CXX_VERSION >= 201103L
-    // move-only for C++11
-    is_too_large(is_too_large const&) = delete;
-    is_too_large(is_too_large&&) = default;
-
-    is_too_large& operator=(is_too_large const&) = delete;
-    is_too_large& operator=(is_too_large&&) = default;
-#else
-    // copyable otherwise
-    is_too_large(is_too_large const&) {}
-
-    is_too_large& operator=(is_too_large const&) { return *this; }
-#endif
-
-    bool operator()(
-      std::pair<std::string const, int>& key_value) UNORDERED_LVALUE_QUAL
+    bool operator()(std::pair<std::string const, int>& key_value)
     {
       int const v = key_value.second;
       return v >= 1000;
     }
 
-    bool operator()(int const& value) UNORDERED_LVALUE_QUAL
+    bool operator()(int const& value)
     {
       int const v = value;
       return v >= 1000;
@@ -158,11 +107,16 @@ template <class UnorderedSet> void test_set_erase_if()
 }
 
 UNORDERED_AUTO_TEST (unordered_erase_if) {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  test_map_erase_if<boost::unordered_flat_map<std::string, int> >();
+  test_set_erase_if<boost::unordered_flat_set<int> >();
+#else
   test_map_erase_if<boost::unordered_map<std::string, int> >();
   test_map_erase_if<boost::unordered_multimap<std::string, int> >();
 
   test_set_erase_if<boost::unordered_set<int> >();
   test_set_erase_if<boost::unordered_multiset<int> >();
+#endif
 }
 
 RUN_TESTS()

test/unordered/erase_tests.cpp

@@ -1,14 +1,10 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../helpers/test.hpp"
 #include "../objects/test.hpp"
@@ -27,7 +23,9 @@ namespace erase_tests {
   template <class Container>
   void erase_tests1(Container*, test::random_generator generator)
   {
+#ifndef BOOST_UNORDERED_FOA_TESTS
     typedef typename Container::iterator iterator;
+#endif
     typedef typename Container::const_iterator c_iterator;
 
     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Erase by key.\n";
@@ -61,9 +59,13 @@ namespace erase_tests {
       while (size > 0 && !x.empty()) {
         typename Container::key_type key = test::get_key<Container>(*x.begin());
         std::size_t count = x.count(key);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+        x.erase(x.begin());
+#else
         iterator pos = x.erase(x.begin());
-        --size;
         BOOST_TEST(pos == x.begin());
+#endif
+        --size;
         BOOST_TEST(x.count(key) == count - 1);
         BOOST_TEST(x.size() == size);
         if (++iterations % 20 == 0)
@@ -93,10 +95,15 @@ namespace erase_tests {
         typename Container::key_type key = test::get_key<Container>(*pos);
         std::size_t count = x.count(key);
         BOOST_TEST(count > 0);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+        x.erase(pos);
+        --size;
+#else
         BOOST_TEST(next == x.erase(pos));
         --size;
         if (size > 0)
           BOOST_TEST(index == 0 ? next == x.begin() : next == test::next(prev));
+#endif
         BOOST_TEST(x.count(key) == count - 1);
         if (x.count(key) != count - 1) {
           BOOST_LIGHTWEIGHT_TEST_OSTREAM << count << " => " << x.count(key)
@@ -185,7 +192,11 @@ namespace erase_tests {
       while (size > 0 && !x.empty()) {
         typename Container::key_type key = test::get_key<Container>(*x.begin());
         std::size_t count = x.count(key);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+        x.erase(x.begin());
+#else
         x.quick_erase(x.begin());
+#endif
         --size;
         BOOST_TEST(x.count(key) == count - 1);
         BOOST_TEST(x.size() == size);
@@ -216,7 +227,11 @@ namespace erase_tests {
         typename Container::key_type key = test::get_key<Container>(*pos);
         std::size_t count = x.count(key);
         BOOST_TEST(count > 0);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+        x.erase(pos);
+#else
         x.quick_erase(pos);
+#endif
         --size;
         if (size > 0)
           BOOST_TEST(index == 0 ? next == x.begin() : next == test::next(prev));
@@ -246,6 +261,20 @@ namespace erase_tests {
     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n";
   }
 
+  using test::default_generator;
+  using test::generate_collisions;
+  using test::limited_range;
+
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<test::object, test::hash, test::equal_to,
+    test::allocator1<test::object> >* test_set;
+  boost::unordered_flat_map<test::object, test::object, test::hash,
+    test::equal_to, test::allocator1<test::object> >* test_map;
+
+  UNORDERED_TEST(
+    erase_tests1, ((test_set)(test_map))(
+                    (default_generator)(generate_collisions)(limited_range)))
+#else
   boost::unordered_set<test::object, test::hash, test::equal_to,
     test::allocator1<test::object> >* test_set;
   boost::unordered_multiset<test::object, test::hash, test::equal_to,
@@ -255,13 +284,11 @@ namespace erase_tests {
   boost::unordered_multimap<test::object, test::object, test::hash,
     test::equal_to, test::allocator2<test::object> >* test_multimap;
 
-  using test::default_generator;
-  using test::generate_collisions;
-  using test::limited_range;
 
   UNORDERED_TEST(
     erase_tests1, ((test_set)(test_multiset)(test_map)(test_multimap))(
                     (default_generator)(generate_collisions)(limited_range)))
+#endif
 }
 
 RUN_TESTS()

test/unordered/find_tests.cpp

@@ -1,14 +1,10 @@
 
 // Copyright 2006-2009 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_set.hpp>
-#include <boost/unordered_map.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include "../helpers/test.hpp"
 #include "../objects/test.hpp"
@@ -133,6 +129,20 @@ namespace find_tests {
     }
   }
 
+  using test::default_generator;
+  using test::generate_collisions;
+  using test::limited_range;
+
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  boost::unordered_flat_set<test::object, test::hash, test::equal_to,
+    test::allocator2<test::object> >* test_set;
+  boost::unordered_flat_map<test::object, test::object, test::hash, test::equal_to,
+    test::allocator2<test::object> >* test_map;
+
+  UNORDERED_TEST(
+    find_tests1, ((test_set)(test_map))(
+                   (default_generator)(generate_collisions)(limited_range)))
+#else
   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,
@@ -142,16 +152,13 @@ namespace find_tests {
   boost::unordered_multimap<test::object, test::object, test::hash,
     test::equal_to, test::allocator1<test::object> >* test_multimap;
 
-  using test::default_generator;
-  using test::generate_collisions;
-  using test::limited_range;
-
   UNORDERED_TEST(
     find_tests1, ((test_set)(test_multiset)(test_map)(test_multimap))(
                    (default_generator)(generate_collisions)(limited_range)))
   UNORDERED_TEST(find_compatible_keys_test,
     ((test_set)(test_multiset)(test_map)(test_multimap))(
       (default_generator)(generate_collisions)(limited_range)))
+#endif
 }
 
 RUN_TESTS()

test/unordered/fwd_map_test.cpp

@@ -1,14 +1,44 @@
 
 // Copyright 2008-2009 Daniel James.
+// 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)
 
 // clang-format off
 #include "../helpers/prefix.hpp"
+#ifdef BOOST_UNORDERED_FOA_TESTS
+#include <boost/unordered/unordered_flat_map_fwd.hpp>
+#include <boost/unordered/detail/implementation.hpp>
+#else
 #include <boost/unordered/unordered_map_fwd.hpp>
+#endif
 #include "../helpers/postfix.hpp"
 // clang-format on
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+template <typename T>
+void call_swap(
+  boost::unordered_flat_map<T, T>& x, boost::unordered_flat_map<T, T>& y)
+{
+  swap(x, y);
+}
+
+template <typename T>
+bool call_equals(
+  boost::unordered_flat_map<T, T>& x, boost::unordered_flat_map<T, T>& y)
+{
+  return x == y;
+}
+
+template <typename T>
+bool call_not_equals(
+  boost::unordered_flat_map<T, T>& x, boost::unordered_flat_map<T, T>& y)
+{
+  return x != y;
+}
+
+#include <boost/unordered/unordered_flat_map.hpp>
+#else
 template <typename T>
 void call_swap(boost::unordered_map<T, T>& x, boost::unordered_map<T, T>& y)
 {
@@ -50,10 +80,15 @@ bool call_not_equals(
 }
 
 #include <boost/unordered_map.hpp>
+#endif
 #include "../helpers/test.hpp"
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+typedef boost::unordered_flat_map<int, int> int_map;
+#else
 typedef boost::unordered_map<int, int> int_map;
 typedef boost::unordered_multimap<int, int> int_multimap;
+#endif
 
 UNORDERED_AUTO_TEST (use_map_fwd_declared_function) {
   int_map x, y;
@@ -71,11 +106,13 @@ UNORDERED_AUTO_TEST (use_map_fwd_declared_function) {
   BOOST_TEST(call_not_equals(x, y));
 }
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
 UNORDERED_AUTO_TEST (use_multimap_fwd_declared_function) {
   int_multimap x, y;
   call_swap(x, y);
   BOOST_TEST(call_equals(x, y));
   BOOST_TEST(!call_not_equals(x, y));
 }
+#endif
 
 RUN_TESTS()

test/unordered/fwd_set_test.cpp

@@ -1,11 +1,17 @@
 
 // Copyright 2008-2009 Daniel James.
+// 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)
 
 // clang-format off
 #include "../helpers/prefix.hpp"
+#ifdef BOOST_UNORDERED_FOA_TESTS
+#include <boost/unordered/unordered_flat_set_fwd.hpp>
+#include <boost/unordered/detail/implementation.hpp>
+#else
 #include <boost/unordered/unordered_set_fwd.hpp>
+#endif
 #include "../helpers/postfix.hpp"
 // clang-format on
 
@@ -20,6 +26,31 @@ struct false_type
 
 false_type is_unordered_set_impl(void*);
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+template <class Value, class Hash, class Pred, class Alloc>
+true_type is_unordered_set_impl(
+  boost::unordered_flat_set<Value, Hash, Pred, Alloc>*);
+
+template <typename T>
+void call_swap(boost::unordered_flat_set<T>& x, boost::unordered_flat_set<T>& y)
+{
+  swap(x, y);
+}
+
+template <typename T>
+bool call_equals(
+  boost::unordered_flat_set<T>& x, boost::unordered_flat_set<T>& y)
+{
+  return x == y;
+}
+
+template <typename T>
+bool call_not_equals(
+  boost::unordered_flat_set<T>& x, boost::unordered_flat_set<T>& y)
+{
+  return x != y;
+}
+#else
 template <class Value, class Hash, class Pred, class Alloc>
 true_type is_unordered_set_impl(
   boost::unordered_set<Value, Hash, Pred, Alloc>*);
@@ -41,7 +72,9 @@ bool call_not_equals(boost::unordered_set<T>& x, boost::unordered_set<T>& y)
 {
   return x != y;
 }
+#endif
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
 template <typename T>
 void call_swap(boost::unordered_multiset<T>& x, boost::unordered_multiset<T>& y)
 {
@@ -61,20 +94,29 @@ bool call_not_equals(
 {
   return x != y;
 }
+#endif
 
 #include "../helpers/test.hpp"
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+typedef boost::unordered_flat_set<int> int_set;
+#else
 typedef boost::unordered_set<int> int_set;
 typedef boost::unordered_multiset<int> int_multiset;
+#endif
 
 UNORDERED_AUTO_TEST (use_fwd_declared_trait_without_definition) {
   BOOST_TEST(sizeof(is_unordered_set_impl((int_set*)0)) == sizeof(true_type));
 }
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+#include <boost/unordered/unordered_flat_set.hpp>
+#else
 #include <boost/unordered_set.hpp>
+#endif
 
 UNORDERED_AUTO_TEST (use_fwd_declared_trait) {
-  boost::unordered_set<int> x;
+  int_set x;
   BOOST_TEST(sizeof(is_unordered_set_impl(&x)) == sizeof(true_type));
 
   BOOST_TEST(sizeof(is_unordered_set_impl((int*)0)) == sizeof(false_type));
@@ -96,11 +138,13 @@ UNORDERED_AUTO_TEST (use_set_fwd_declared_function) {
   BOOST_TEST(call_not_equals(x, y));
 }
 
+#ifndef BOOST_UNORDERED_FOA_TESTS
 UNORDERED_AUTO_TEST (use_multiset_fwd_declared_function) {
   int_multiset x, y;
   call_swap(x, y);
   BOOST_TEST(call_equals(x, y));
   BOOST_TEST(!call_not_equals(x, y));
 }
+#endif
 
 RUN_TESTS()

test/unordered/incomplete_test.cpp

@@ -1,21 +1,21 @@
 
 // Copyright 2009 Daniel James.
+// 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)
 
-// clang-format off
-#include "../helpers/prefix.hpp"
-#include <boost/unordered_map.hpp>
-#include <boost/unordered_set.hpp>
-#include "../helpers/postfix.hpp"
-// clang-format on
+#include "../helpers/unordered.hpp"
 
 #include <utility>
 
 namespace x {
   struct D
   {
+#ifdef BOOST_UNORDERED_FOA_TESTS
+    boost::unordered_flat_map<D, D> x;
+#else
     boost::unordered_map<D, D> x;
+#endif
   };
 }
 
@@ -29,6 +29,17 @@ namespace incomplete_test {
 
   // Declare some instances
 
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  typedef boost::unordered_flat_map<value, value, hash, equals,
+    allocator<std::pair<value const, value> > >
+    map;
+  typedef boost::unordered_flat_map<value, value, hash, equals,
+    allocator<std::pair<value const, value> > >
+    multimap;
+  typedef boost::unordered_flat_set<value, hash, equals, allocator<value> > set;
+  typedef boost::unordered_flat_set<value, hash, equals, allocator<value> >
+    multiset;
+#else
   typedef boost::unordered_map<value, value, hash, equals,
     allocator<std::pair<value const, value> > >
     map;
@@ -38,6 +49,7 @@ namespace incomplete_test {
   typedef boost::unordered_set<value, hash, equals, allocator<value> > set;
   typedef boost::unordered_multiset<value, hash, equals, allocator<value> >
     multiset;
+#endif
 
   // Now define the types which are stored as members, as they are needed for
   // declaring struct members.
@@ -76,7 +88,28 @@ namespace incomplete_test {
   //
   // Incomplete hash, equals and allocator aren't here supported at the
   // moment.
-
+#ifdef BOOST_UNORDERED_FOA_TESTS
+  struct struct1
+  {
+    boost::unordered_flat_map<struct1, struct1, hash, equals,
+      allocator<std::pair<struct1 const, struct1> > >
+      x;
+  };
+  struct struct2
+  {
+    boost::unordered_flat_map<struct2, struct2, hash, equals,
+      allocator<std::pair<struct2 const, struct2> > >
+      x;
+  };
+  struct struct3
+  {
+    boost::unordered_flat_set<struct3, hash, equals, allocator<struct3> > x;
+  };
+  struct struct4
+  {
+    boost::unordered_flat_set<struct4, hash, equals, allocator<struct4> > x;
+  };
+#else
   struct struct1
   {
     boost::unordered_map<struct1, struct1, hash, equals,
@@ -97,7 +130,7 @@ namespace incomplete_test {
   {
     boost::unordered_multiset<struct4, hash, equals, allocator<struct4> > x;
   };
-
+#endif
   // Now define the value type.
 
   struct value