fourth attempt

micro-optimized previous
third attempt
2026-08-09 23:21:17 +02:00 · 2022-11-28 17:58:15 +01:00 · 2022-11-28 12:13:04 +01:00 · 2022-11-27 20:54:26 +01:00 · 2022-11-24 20:12:48 +01:00 · 2022-11-24 20:00:04 +01:00
214 changed files with 3014 additions and 24854 deletions
@@ -6,12 +6,11 @@ local library = "unordered";

 local triggers =
 {
-    branch: [ "master", "develop", "bugfix/*", "fix/*", "pr/*" ]
+    branch: [ "master", "develop", "feature/*", "bugfix/*" ]
 };

 local ubsan = { UBSAN: '1', UBSAN_OPTIONS: 'print_stacktrace=1' };
 local asan = { ASAN: '1' };
-local tsan = { TSAN: '1' };

 local linux_pipeline(name, image, environment, packages = "", sources = [], arch = "amd64") =
 {
@@ -158,29 +157,16 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    linux_pipeline(
-        "Linux 18.04 GCC 8 32/64 (03,11)",
+        "Linux 18.04 GCC 8 32/64",
        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-8', CXXSTD: '03,11', ADDRMD: '32,64' },
+        { TOOLSET: 'gcc', COMPILER: 'g++-8', CXXSTD: '03,11,14,17', ADDRMD: '32,64' },
        "g++-8-multilib",
    ),

    linux_pipeline(
-        "Linux 18.04 GCC 8 32/64 (14,17)",
-        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-8', CXXSTD: '14,17', ADDRMD: '32,64' },
-        "g++-8-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 GCC 9* 32/64 (03,11,14)",
+        "Linux 20.04 GCC 9* 32/64",
        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14', ADDRMD: '32,64' },
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 GCC 9* 32/64 (17,2a)",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '17,2a', ADDRMD: '32,64' },
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32,64' },
    ),

    linux_pipeline(
@@ -191,77 +177,36 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    linux_pipeline(
-        "Linux 20.04 GCC 9* S390x (03,11,14)",
+        "Linux 20.04 GCC 9* S390x",
        "cppalliance/droneubuntu2004:multiarch",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14' },
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a' },
        arch="s390x",
    ),

    linux_pipeline(
-        "Linux 20.04 GCC 9* S390x (17,2a)",
-        "cppalliance/droneubuntu2004:multiarch",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '17,2a' },
-        arch="s390x",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 GCC 10 32/64 (03,11,14)",
+        "Linux 20.04 GCC 10 32/64",
        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-10', CXXSTD: '03,11,14', ADDRMD: '32,64' },
+        { TOOLSET: 'gcc', COMPILER: 'g++-10', CXXSTD: '03,11,14,17,20', ADDRMD: '32,64' },
        "g++-10-multilib",
    ),

    linux_pipeline(
-        "Linux 20.04 GCC 10 32/64 (17,20)",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-10', CXXSTD: '17,20', ADDRMD: '32,64' },
-        "g++-10-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 11* 32/64 (03,11,14)",
+        "Linux 22.04 GCC 11* 32/64",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14', ADDRMD: '32,64' },
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 11* 32/64 (17,2a)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '17,2a', ADDRMD: '32,64' },
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32,64' },
    ),

    linux_pipeline(
        "Linux 22.04 GCC 12 32 ASAN (03,11,14)",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '03,11', ADDRMD: '32' } + asan,
+        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '03,11,14', ADDRMD: '32' } + asan,
        "g++-12-multilib",
    ),

    linux_pipeline(
-        "Linux 22.04 GCC 12 32 ASAN (14)",
+        "Linux 22.04 GCC 12 32 ASAN (17,20,2b)",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '14', ADDRMD: '32' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 32 ASAN (17)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17', ADDRMD: '32' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 32 ASAN (20)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '20', ADDRMD: '32' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 32 ASAN (2b)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '2b', ADDRMD: '32' } + asan,
+        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17,20,2b', ADDRMD: '32' } + asan,
        "g++-12-multilib",
    ),

@@ -273,47 +218,12 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    linux_pipeline(
-        "Linux 22.04 GCC 12 64 ASAN (17)",
+        "Linux 22.04 GCC 12 64 ASAN (17,20,2b)",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17', ADDRMD: '64' } + asan,
+        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17,20,2b', ADDRMD: '64' } + asan,
        "g++-12-multilib",
    ),

-    linux_pipeline(
-        "Linux 22.04 GCC 12 64 ASAN (20)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '20', ADDRMD: '64' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 64 ASAN (2b)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '2b', ADDRMD: '64' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 64 TSAN (11,14,17,20,2b)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '11,14,17,20,2b', ADDRMD: '64', TARGET: 'libs/unordered/test//cfoa_tests' } + tsan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 23.04 GCC 13 32/64 (03,11,14)",
-        "cppalliance/droneubuntu2304:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-13', CXXSTD: '03,11,14', ADDRMD: '32,64' },
-        "g++-13 g++-13-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 23.04 GCC 13 32/64 (17,20,2b)",
-        "cppalliance/droneubuntu2304:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-13', CXXSTD: '17,20,2b', ADDRMD: '32,64' },
-        "g++-13 g++-13-multilib",
-    ),
-
    linux_pipeline(
        "Linux 16.04 Clang 3.5",
        "cppalliance/droneubuntu1604:1",
@@ -420,40 +330,19 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    linux_pipeline(
-        "Linux 22.04 Clang 14 UBSAN (03,11,14)",
+        "Linux 22.04 Clang 14 UBSAN",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14' } + ubsan,
+        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14,17,20' } + ubsan,
        "clang-14",
    ),

    linux_pipeline(
-        "Linux 22.04 Clang 14 UBSAN (17,20)",
+        "Linux 22.04 Clang 14 ASAN",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '17,20' } + ubsan,
+        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14,17,20' } + asan,
        "clang-14",
    ),

-    linux_pipeline(
-        "Linux 22.04 Clang 14 ASAN (03,11,14)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14' } + asan,
-        "clang-14",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 Clang 14 ASAN (17,20)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '17,20' } + asan,
-        "clang-14",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 Clang 14 libc++ 64 TSAN",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', ADDRMD: '64', TARGET: 'libs/unordered/test//cfoa_tests', CXXSTD: '11,14,17,20', STDLIB: 'libc++' } + tsan,
-        "clang-14 libc++-14-dev libc++abi-14-dev",
-    ),
-
    linux_pipeline(
        "Linux 22.04 Clang 15",
        "cppalliance/droneubuntu2204:1",
@@ -463,30 +352,14 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    macos_pipeline(
-        "MacOS 10.15 Xcode 12.2 UBSAN (03,11)",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11' } + ubsan,
-    ),
-
-    macos_pipeline(
-        "MacOS 10.15 Xcode 12.2 UBSAN (14)",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '14' } + ubsan,
-    ),
-
-    macos_pipeline(
-        "MacOS 10.15 Xcode 12.2 UBSAN (1z)",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '1z' } + ubsan,
+        "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", arch = "arm64",
-    ),
-
-    macos_pipeline(
-        "MacOS 12.4 Xcode 13.4.1 TSAN",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '11,14,1z', TARGET: 'libs/unordered/test//cfoa_tests' } + tsan,
-        xcode_version = "13.4.1", osx_version = "monterey", arch = "arm64",
+        xcode_version = "13.4.1", osx_version = "monterey",
    ),

    windows_pipeline(
@@ -7,8 +7,6 @@
 set -ex
 export PATH=~/.local/bin:/usr/local/bin:$PATH

-: ${TARGET:="libs/$LIBRARY/test"}
-
 DRONE_BUILD_DIR=$(pwd)

 BOOST_BRANCH=develop
@@ -24,4 +22,4 @@ python tools/boostdep/depinst/depinst.py $LIBRARY
 ./b2 -d0 headers

 echo "using $TOOLSET : : $COMPILER ;" > ~/user-config.jam
-./b2 -j3 $TARGET toolset=$TOOLSET cxxstd=$CXXSTD variant=debug,release ${ADDRMD:+address-model=$ADDRMD} ${STDLIB:+stdlib=$STDLIB} ${UBSAN:+undefined-sanitizer=norecover debug-symbols=on} ${ASAN:+address-sanitizer=norecover debug-symbols=on} ${TSAN:+thread-sanitizer=norecover debug-symbols=on} ${LINKFLAGS:+linkflags=$LINKFLAGS}
+./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}
@@ -15,9 +15,9 @@ on:
      - master
      - develop
      - bugfix/**
+      - feature/**
      - fix/**
      - pr/**
-      - feature/cfoa-size-padding

 concurrency:
  group: ${{format('{0}:{1}', github.repository, github.ref)}}
@@ -52,10 +52,7 @@ jobs:
          - { name: "gcc-12 w/ sanitizers (17,20,2b)", sanitize: yes,
              compiler: gcc-12,    cxxstd: '17,20,2b',       os: ubuntu-22.04, ccache_key: "san2" }
          - { name: Collect coverage, coverage: yes,
-              compiler: gcc-12,     cxxstd: '03,20',          os: ubuntu-22.04, install: 'g++-12-multilib', address-model: '32,64', ccache_key: "cov" }
-
-          - { name: "cfoa tsan (gcc)", cxxstd: '11,14,17,20,2b', os: ubuntu-22.04, compiler: gcc-12,
-              targets: 'libs/unordered/test//cfoa_tests', thread-sanitize: yes }
+              compiler: gcc-8,     cxxstd: '03,11',          os: ubuntu-20.04, install: 'g++-8-multilib', address-model: '32,64', ccache_key: "cov" }

          # Linux, clang, libc++
          - { compiler: clang-7,   cxxstd: '03,11,14,17',       os: ubuntu-20.04, stdlib: libc++, install: 'clang-7 libc++-7-dev libc++abi-7-dev' }
@@ -68,23 +65,16 @@ jobs:
              compiler: clang-12,  cxxstd: '17,20,2b',          os: ubuntu-20.04, stdlib: libc++, install: 'clang-12 libc++-12-dev libc++abi-12-dev', ccache_key: "san2" }
          - { compiler: clang-13,  cxxstd: '03,11,14,17,20,2b', os: ubuntu-22.04, stdlib: libc++, install: 'clang-13 libc++-13-dev libc++abi-13-dev' }
          - { compiler: clang-14,  cxxstd: '03,11,14,17,20,2b', os: ubuntu-22.04, stdlib: libc++, install: 'clang-14 libc++-14-dev libc++abi-14-dev' }
-
          # not using libc++ because of https://github.com/llvm/llvm-project/issues/52771
          - { name: "clang-14 w/ sanitizers (03,11,14)", sanitize: yes,
              compiler: clang-14,  cxxstd: '03,11,14',          os: ubuntu-22.04, ccache_key: "san1" }
          - { name: "clang-14 w/ sanitizers (17,20,2b)", sanitize: yes,
              compiler: clang-14,  cxxstd: '17,20,2b',          os: ubuntu-22.04, ccache_key: "san2" }

-          - { name: "cfoa tsan (clang)", cxxstd: '11,14,17,20,2b', os: ubuntu-22.04, compiler: clang-14,
-              targets: 'libs/unordered/test//cfoa_tests', thread-sanitize: yes, 
-              stdlib: libc++, install: 'clang-14 libc++-14-dev libc++abi-14-dev' }
-
          # OSX, clang
-          - { compiler: clang,     cxxstd: '03,11,14,17,2a',    os: macos-11, }
-          - { compiler: clang,     cxxstd: '03,11,14,17,2a',    os: macos-12, sanitize: yes }
-          - { compiler: clang,     cxxstd: '11,14,17,2a',       os: macos-12, thread-sanitize: yes, targets: 'libs/unordered/test//cfoa_tests' }
+          - { compiler: clang,     cxxstd: '03,11,14,17,2a',    os: macos-11, sanitize: yes }

-    timeout-minutes: 180
+    timeout-minutes: 120
    runs-on: ${{matrix.os}}
    container: ${{matrix.container}}
    env: {B2_USE_CCACHE: 1}
@@ -193,8 +183,6 @@ jobs:
          B2_COMPILER: ${{matrix.compiler}}
          B2_CXXSTD: ${{matrix.cxxstd}}
          B2_SANITIZE: ${{matrix.sanitize}}
-          B2_TSAN: ${{matrix.thread-sanitize}}
-          B2_TARGETS: ${{matrix.targets}}
          B2_STDLIB: ${{matrix.stdlib}}
          # More entries can be added in the same way, see the B2_ARGS assignment in ci/enforce.sh for the possible keys.
          # B2_DEFINES: ${{matrix.defines}}
@@ -208,7 +196,7 @@ jobs:

      - name: Run tests
        if: '!matrix.coverity'
-        run: B2_TARGETS=${{matrix.targets}} ci/build.sh
+        run: ci/build.sh

      - name: Upload coverage
        if: matrix.coverage
@@ -229,13 +217,11 @@ jobs:
      fail-fast: false
      matrix:
        include:
-          - { toolset: msvc-14.0, cxxstd: '14,latest',       addrmd: '32,64', os: windows-2019, variant: 'debug,release' }
-          - { toolset: msvc-14.2, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2019, variant: 'debug,release' }
-          - { toolset: msvc-14.3, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2022, variant: 'debug,release' }
-          - { toolset: msvc-14.3, cxxstd: '14',              addrmd: '64',    os: windows-2022, variant: 'debug', defines: '_ALLOW_RTCc_IN_STL', cxxflags: '/RTCc'              }
-          - { toolset: msvc-14.3, cxxstd: '14',              addrmd: '32',    os: windows-2022, variant: 'debug', defines: '_ALLOW_RTCc_IN_STL', cxxflags: '"/RTCc /arch:IA32"' }
-          - { toolset: clang-win, cxxstd: '14,17,latest',    addrmd: '32,64', os: windows-2022, variant: 'debug,release' }
-          - { toolset: gcc,       cxxstd: '03,11,14,17,2a',  addrmd: '64',    os: windows-2019, variant: 'debug,release' }
+          - { 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}}

@@ -264,9 +250,6 @@ jobs:
          B2_TOOLSET: ${{matrix.toolset}}
          B2_CXXSTD: ${{matrix.cxxstd}}
          B2_ADDRESS_MODEL: ${{matrix.addrmd}}
-          B2_DEFINES: ${{matrix.defines}}
-          B2_VARIANT: ${{matrix.variant}}
-          B2_CXXFLAGS: ${{matrix.cxxflags}}

      - name: Collect coverage
        shell: powershell
@@ -1,2 +1 @@
 /doc/html/
-/doc/pdf/
@@ -22,7 +22,6 @@ target_link_libraries(boost_unordered
    Boost::mp11
    Boost::predef
    Boost::preprocessor
-    Boost::static_assert
    Boost::throw_exception
    Boost::tuple
    Boost::type_traits
@@ -1,3 +0,0 @@
-enwik8
-enwik9
-*.exe
@@ -1,22 +1,25 @@
 // Copyright 2021 Peter Dimov.
-// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt

 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING

 #include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.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_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#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>
@@ -264,6 +267,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
    times.push_back( rec );
 }

+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator

 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -274,9 +295,6 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;

-template<class K, class V> using boost_unordered_node_map =
-    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
 template<class K, class V> using boost_unordered_flat_map =
    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;

@@ -290,10 +308,23 @@ template<class K, class V> using absl_flat_hash_map =

 #endif

-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH

-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+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

@@ -350,12 +381,17 @@ std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 template<class K, class V> using boost_unordered_map_fnv1a =
    boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;

-template<class K, class V> using boost_unordered_node_map_fnv1a =
-    boost::unordered_node_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
 template<class K, class V> using boost_unordered_flat_map_fnv1a =
    boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;

+template<class K, class V> using multi_index_map_fnv1a = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first>, fnv1a_hash >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 #ifdef HAVE_ABSEIL

 template<class K, class V> using absl_node_hash_map_fnv1a =
@@ -366,10 +402,23 @@ template<class K, class V> using absl_flat_hash_map_fnv1a =

 #endif

-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH

-template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
-    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+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

@@ -379,16 +428,12 @@ int main()
 {
    init_indices();

+#if 1
+
    test<std_unordered_map>( "std::unordered_map" );
    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_node_map>( "boost::unordered_node_map" );
    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );

 #ifdef HAVE_ABSEIL

@@ -397,29 +442,53 @@ int main()

 #endif

-    test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
-    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
-    test<boost_unordered_node_map_fnv1a>( "boost::unordered_node_map, FNV-1a" );
-    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
+#ifdef HAVE_TSL_HOPSCOTCH

-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
+    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" );
+    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
+    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
+    test<multi_index_map_fnv1a>( "multi_index_map, FNV-1a" );
+
 #ifdef HAVE_ABSEIL

    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( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 35 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
    }
 }

@@ -1,22 +1,25 @@
 // Copyright 2021 Peter Dimov.
-// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt

 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING

 #include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.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_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#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>
@@ -265,6 +268,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
    times.push_back( rec );
 }

+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator

 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -275,9 +296,6 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;

-template<class K, class V> using boost_unordered_node_map =
-    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
 template<class K, class V> using boost_unordered_flat_map =
    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;

@@ -291,10 +309,23 @@ template<class K, class V> using absl_flat_hash_map =

 #endif

-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH

-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+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

@@ -351,12 +382,17 @@ std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 template<class K, class V> using boost_unordered_map_fnv1a =
    boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;

-template<class K, class V> using boost_unordered_node_map_fnv1a =
-    boost::unordered_node_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
 template<class K, class V> using boost_unordered_flat_map_fnv1a =
    boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;

+template<class K, class V> using multi_index_map_fnv1a = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first>, fnv1a_hash >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 #ifdef HAVE_ABSEIL

 template<class K, class V> using absl_node_hash_map_fnv1a =
@@ -367,10 +403,23 @@ template<class K, class V> using absl_flat_hash_map_fnv1a =

 #endif

-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH

-template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
-    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+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

@@ -380,16 +429,12 @@ int main()
 {
    init_indices();

+#if 1
+
    test<std_unordered_map>( "std::unordered_map" );
    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_node_map>( "boost::unordered_node_map" );
    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );

 #ifdef HAVE_ABSEIL

@@ -398,29 +443,53 @@ int main()

 #endif

-    test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
-    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
-    test<boost_unordered_node_map_fnv1a>( "boost::unordered_node_map, FNV-1a" );
-    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
+#ifdef HAVE_TSL_HOPSCOTCH

-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
+    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" );
+    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
+    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
+    test<multi_index_map_fnv1a>( "multi_index_map, FNV-1a" );
+
 #ifdef HAVE_ABSEIL

    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( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 35 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
    }
 }

@@ -1,14 +1,14 @@
 // Copyright 2021 Peter Dimov.
-// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt

 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING

 #include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/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>
@@ -16,8 +16,11 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#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>
@@ -281,6 +284,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
    times.push_back( rec );
 }

+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator

 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -291,9 +312,6 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;

-template<class K, class V> using boost_unordered_node_map =
-    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
 template<class K, class V> using boost_unordered_flat_map =
    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;

@@ -307,10 +325,23 @@ template<class K, class V> using absl_flat_hash_map =

 #endif

-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH

-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+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

@@ -320,27 +351,35 @@ int main()

    test<std_unordered_map>( "std::unordered_map" );
    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_node_map>( "boost::unordered_node_map" );
    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );

 #ifdef HAVE_ABSEIL

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

    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( 27 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
    }
 }

@@ -1,14 +1,14 @@
 // Copyright 2021 Peter Dimov.
-// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt

 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING

 #include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/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>
@@ -16,8 +16,11 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
+#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>
@@ -281,6 +284,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
    times.push_back( rec );
 }

+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator

 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -291,9 +312,6 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;

-template<class K, class V> using boost_unordered_node_map =
-    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
 template<class K, class V> using boost_unordered_flat_map =
    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;

@@ -307,10 +325,23 @@ template<class K, class V> using absl_flat_hash_map =

 #endif

-#ifdef HAVE_ANKERL_UNORDERED_DENSE
+#ifdef HAVE_TSL_HOPSCOTCH

-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+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

@@ -318,39 +349,37 @@ int main()
 {
    init_indices();

-#if defined(BOOST_LIBSTDCXX_VERSION) && __SIZE_WIDTH__ == 32
-
-    // Pathological behavior:
-    // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104945
-
-#else
-
    test<std_unordered_map>( "std::unordered_map" );
-
-#endif
-
    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_node_map>( "boost::unordered_node_map" );
    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );

 #ifdef HAVE_ABSEIL

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

    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( 27 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
    }
 }

@@ -1,14 +1,14 @@
 // Copyright 2021, 2022 Peter Dimov.
-// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt

 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING

 #include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/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/container_hash/hash.hpp>
@@ -17,9 +17,6 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
-#endif
 #include <unordered_map>
 #include <vector>
 #include <memory>
@@ -332,6 +329,24 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
    times.push_back( rec );
 }

+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
 // aliases using the counting allocator

 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
@@ -342,9 +357,6 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;

-template<class K, class V> using boost_unordered_node_map =
-    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
 template<class K, class V> using boost_unordered_flat_map =
    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;

@@ -358,27 +370,14 @@ template<class K, class V> using absl_flat_hash_map =

 #endif

-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
 int main()
 {
    init_indices();

    test<std_unordered_map>( "std::unordered_map" );
    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_node_map>( "boost::unordered_node_map" );
    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
+    test<multi_index_map>( "multi_index_map" );

 #ifdef HAVE_ABSEIL

@@ -391,7 +390,7 @@ int main()

    for( auto const& x: times )
    {
-        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 27 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
    }
 }

@@ -1,386 +0,0 @@
-// Copyright 2021, 2022 Peter Dimov.
-// Copyright 2023 Joaquin M Lopez Munoz.
-// Distributed under the Boost Software License, Version 1.0.
-// https://www.boost.org/LICENSE_1_0.txt
-
-#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
-
-#include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_node_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
-#include <boost/regex.hpp>
-#ifdef HAVE_ABSEIL
-# include "absl/container/node_hash_map.h"
-# include "absl/container/flat_hash_map.h"
-#endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
-#endif
-#include <unordered_map>
-#include <vector>
-#include <memory>
-#include <cstdint>
-#include <iostream>
-#include <iomanip>
-#include <chrono>
-#include <fstream>
-#include <string_view>
-#include <string>
-
-using namespace std::chrono_literals;
-
-static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::size_t s, std::size_t size )
-{
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
-
-    t1 = t2;
-}
-
-static std::vector<std::string> words;
-
-static void init_words()
-{
-#if SIZE_MAX > UINT32_MAX
-
-    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
-
-#else
-
-    char const* fn = "enwik8"; // ditto
-
-#endif
-
-    auto t1 = std::chrono::steady_clock::now();
-
-    std::ifstream is( fn );
-    std::string in( std::istreambuf_iterator<char>( is ), std::istreambuf_iterator<char>{} );
-
-    boost::regex re( "[a-zA-Z]+");
-    boost::sregex_token_iterator it( in.begin(), in.end(), re, 0 ), end;
-
-    words.assign( it, end );
-
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << fn << ": " << words.size() << " words, " << ( t2 - t1 ) / 1ms << " ms\n\n";
-}
-
-template<class Map> BOOST_NOINLINE void test_word_count( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& word: words )
-    {
-        ++map[ word ];
-        ++s;
-    }
-
-    print_time( t1, "Word count", s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_contains( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& word: words )
-    {
-        std::string_view w2( word );
-        w2.remove_prefix( 1 );
-
-        s += map.contains( w2 );
-    }
-
-    print_time( t1, "Contains", s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_count( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& word: words )
-    {
-        std::string_view w2( word );
-        w2.remove_prefix( 1 );
-
-        s += map.count( w2 );
-    }
-
-    print_time( t1, "Count", s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t max = 0;
-    std::string_view word;
-
-    for( auto const& x: map )
-    {
-        if( x.second > max )
-        {
-            word = x.first;
-            max = x.second;
-        }
-    }
-
-    print_time( t1, "Iterate and find max element",  max, map.size() );
-
-    std::cout << std::endl;
-}
-
-// counting allocator
-
-static std::size_t s_alloc_bytes = 0;
-static std::size_t s_alloc_count = 0;
-
-template<class T> struct allocator
-{
-    using value_type = T;
-
-    allocator() = default;
-
-    template<class U> allocator( allocator<U> const & ) noexcept
-    {
-    }
-
-    template<class U> bool operator==( allocator<U> const & ) const noexcept
-    {
-        return true;
-    }
-
-    template<class U> bool operator!=( allocator<U> const& ) const noexcept
-    {
-        return false;
-    }
-
-    T* allocate( std::size_t n ) const
-    {
-        s_alloc_bytes += n * sizeof(T);
-        s_alloc_count++;
-
-        return std::allocator<T>().allocate( n );
-    }
-
-    void deallocate( T* p, std::size_t n ) const noexcept
-    {
-        s_alloc_bytes -= n * sizeof(T);
-        s_alloc_count--;
-
-        std::allocator<T>().deallocate( p, n );
-    }
-};
-
-//
-
-struct record
-{
-    std::string label_;
-    long long time_;
-    std::size_t bytes_;
-    std::size_t count_;
-};
-
-static std::vector<record> times;
-
-template<template<class...> class Map> BOOST_NOINLINE void test( char const* label )
-{
-    std::cout << label << ":\n\n";
-
-    s_alloc_bytes = 0;
-    s_alloc_count = 0;
-
-    Map<std::string_view, std::size_t> map;
-
-    auto t0 = std::chrono::steady_clock::now();
-    auto t1 = t0;
-
-    test_word_count( map, t1 );
-
-    std::cout << "Memory: " << s_alloc_bytes << " bytes in " << s_alloc_count << " allocations\n\n";
-
-    record rec = { label, 0, s_alloc_bytes, s_alloc_count };
-
-    test_contains( map, t1 );
-    test_count( map, t1 );
-    test_iteration( map, t1 );
-
-    auto tN = std::chrono::steady_clock::now();
-    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
-
-    rec.time_ = ( tN - t0 ) / 1ms;
-    times.push_back( rec );
-}
-
-// aliases using the counting allocator
-
-template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
-
-template<class K, class V> using std_unordered_map =
-    std::unordered_map<K, V, std::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_map =
-    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_node_map =
-    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-#ifdef HAVE_ABSEIL
-
-template<class K, class V> using absl_node_hash_map =
-    absl::node_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-template<class K, class V> using absl_flat_hash_map =
-    absl::flat_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-#endif
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-// fnv1a_hash
-
-template<int Bits> struct fnv1a_hash_impl;
-
-template<> struct fnv1a_hash_impl<32>
-{
-    std::size_t operator()( std::string_view const& s ) const
-    {
-        std::size_t h = 0x811C9DC5u;
-
-        char const * first = s.data();
-        char const * last = first + s.size();
-
-        for( ; first != last; ++first )
-        {
-            h ^= static_cast<unsigned char>( *first );
-            h *= 0x01000193ul;
-        }
-
-        return h;
-    }
-};
-
-template<> struct fnv1a_hash_impl<64>
-{
-    std::size_t operator()( std::string_view const& s ) const
-    {
-        std::size_t h = 0xCBF29CE484222325ull;
-
-        char const * first = s.data();
-        char const * last = first + s.size();
-
-        for( ; first != last; ++first )
-        {
-            h ^= static_cast<unsigned char>( *first );
-            h *= 0x00000100000001B3ull;
-        }
-
-        return h;
-    }
-};
-
-struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
-{
-    using is_avalanching = void;
-};
-
-template<class K, class V> using std_unordered_map_fnv1a =
-std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_map_fnv1a =
-    boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_node_map_fnv1a =
-    boost::unordered_node_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_flat_map_fnv1a =
-    boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
-
-#ifdef HAVE_ABSEIL
-
-template<class K, class V> using absl_node_hash_map_fnv1a =
-    absl::node_hash_map<K, V, fnv1a_hash, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-template<class K, class V> using absl_flat_hash_map_fnv1a =
-    absl::flat_hash_map<K, V, fnv1a_hash, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-#endif
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
-    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-//
-
-int main()
-{
-    init_words();
-
-    test<std_unordered_map>( "std::unordered_map" );
-    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_node_map>( "boost::unordered_node_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
-
-#ifdef HAVE_ABSEIL
-
-    test<absl_node_hash_map>( "absl::node_hash_map" );
-    test<absl_flat_hash_map>( "absl::flat_hash_map" );
-
-#endif
-
-    test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
-    test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
-    test<boost_unordered_node_map_fnv1a>( "boost::unordered_node_map, FNV-1a" );
-    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
-
-#endif
-
-#ifdef HAVE_ABSEIL
-
-    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
-
-    std::cout << "---\n\n";
-
-    for( auto const& x: times )
-    {
-        std::cout << std::setw( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
-    }
-}
-
-#ifdef HAVE_ABSEIL
-# include "absl/container/internal/raw_hash_set.cc"
-# include "absl/hash/internal/hash.cc"
-# include "absl/hash/internal/low_level_hash.cc"
-# include "absl/hash/internal/city.cc"
-#endif
@@ -1,244 +0,0 @@
-// Copyright 2021, 2022 Peter Dimov.
-// Copyright 2023 Joaquin M Lopez Munoz.
-// Distributed under the Boost Software License, Version 1.0.
-// https://www.boost.org/LICENSE_1_0.txt
-
-#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
-
-#include <boost/unordered_map.hpp>
-#include <boost/unordered/unordered_node_map.hpp>
-#include <boost/unordered/unordered_flat_map.hpp>
-#include <boost/regex.hpp>
-#ifdef HAVE_ABSEIL
-# include "absl/container/node_hash_map.h"
-# include "absl/container/flat_hash_map.h"
-#endif
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-# include "ankerl/unordered_dense.h"
-#endif
-#include <unordered_map>
-#include <vector>
-#include <memory>
-#include <cstdint>
-#include <iostream>
-#include <iomanip>
-#include <chrono>
-#include <fstream>
-
-using namespace std::chrono_literals;
-
-static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::size_t s, std::size_t size )
-{
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
-
-    t1 = t2;
-}
-
-static std::vector<std::string> words;
-
-static void init_words()
-{
-#if SIZE_MAX > UINT32_MAX
-
-    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
-
-#else
-
-    char const* fn = "enwik8"; // ditto
-
-#endif
-
-    auto t1 = std::chrono::steady_clock::now();
-
-    std::ifstream is( fn );
-    std::string in( std::istreambuf_iterator<char>( is ), std::istreambuf_iterator<char>{} );
-
-    boost::regex re( "[a-zA-Z]+");
-    boost::sregex_token_iterator it( in.begin(), in.end(), re, 0 ), end;
-
-    words.assign( it, end );
-
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << fn << ": " << words.size() << " words, " << ( t2 - t1 ) / 1ms << " ms\n\n";
-}
-
-template<class Map> BOOST_NOINLINE void test_word_size( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    for( auto const& word: words )
-    {
-        ++map[ word.size() ];
-    }
-
-    print_time( t1, "Word size count",  0, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::size_t s = 0;
-
-    for( auto const& x: map )
-    {
-        s += x.second;
-    }
-
-    print_time( t1, "Iterate and sum counts",  s, map.size() );
-
-    std::cout << std::endl;
-}
-
-// counting allocator
-
-static std::size_t s_alloc_bytes = 0;
-static std::size_t s_alloc_count = 0;
-
-template<class T> struct allocator
-{
-    using value_type = T;
-
-    allocator() = default;
-
-    template<class U> allocator( allocator<U> const & ) noexcept
-    {
-    }
-
-    template<class U> bool operator==( allocator<U> const & ) const noexcept
-    {
-        return true;
-    }
-
-    template<class U> bool operator!=( allocator<U> const& ) const noexcept
-    {
-        return false;
-    }
-
-    T* allocate( std::size_t n ) const
-    {
-        s_alloc_bytes += n * sizeof(T);
-        s_alloc_count++;
-
-        return std::allocator<T>().allocate( n );
-    }
-
-    void deallocate( T* p, std::size_t n ) const noexcept
-    {
-        s_alloc_bytes -= n * sizeof(T);
-        s_alloc_count--;
-
-        std::allocator<T>().deallocate( p, n );
-    }
-};
-
-//
-
-struct record
-{
-    std::string label_;
-    long long time_;
-    std::size_t bytes_;
-    std::size_t count_;
-};
-
-static std::vector<record> times;
-
-template<template<class...> class Map> BOOST_NOINLINE void test( char const* label )
-{
-    std::cout << label << ":\n\n";
-
-    s_alloc_bytes = 0;
-    s_alloc_count = 0;
-
-    Map<std::size_t, std::size_t> map;
-
-    auto t0 = std::chrono::steady_clock::now();
-    auto t1 = t0;
-
-    test_word_size( map, t1 );
-
-    std::cout << "Memory: " << s_alloc_bytes << " bytes in " << s_alloc_count << " allocations\n\n";
-
-    record rec = { label, 0, s_alloc_bytes, s_alloc_count };
-
-    test_iteration( map, t1 );
-
-    auto tN = std::chrono::steady_clock::now();
-    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
-
-    rec.time_ = ( tN - t0 ) / 1ms;
-    times.push_back( rec );
-}
-
-// aliases using the counting allocator
-
-template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
-
-template<class K, class V> using std_unordered_map =
-    std::unordered_map<K, V, std::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_map =
-    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_node_map =
-    boost::unordered_node_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
-
-#ifdef HAVE_ABSEIL
-
-template<class K, class V> using absl_node_hash_map =
-    absl::node_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-template<class K, class V> using absl_flat_hash_map =
-    absl::flat_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
-
-#endif
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-template<class K, class V> using ankerl_unordered_dense_map =
-    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-int main()
-{
-    init_words();
-
-    test<std_unordered_map>( "std::unordered_map" );
-    test<boost_unordered_map>( "boost::unordered_map" );
-    test<boost_unordered_node_map>( "boost::unordered_node_map" );
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-
-#ifdef HAVE_ANKERL_UNORDERED_DENSE
-
-    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
-
-#endif
-
-#ifdef HAVE_ABSEIL
-
-    test<absl_node_hash_map>( "absl::node_hash_map" );
-    test<absl_flat_hash_map>( "absl::flat_hash_map" );
-
-#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";
-    }
-}
-
-#ifdef HAVE_ABSEIL
-# include "absl/container/internal/raw_hash_set.cc"
-# include "absl/hash/internal/hash.cc"
-# include "absl/hash/internal/low_level_hash.cc"
-# include "absl/hash/internal/city.cc"
-#endif
@@ -13,10 +13,8 @@
 include::unordered/intro.adoc[]
 include::unordered/buckets.adoc[]
 include::unordered/hash_equality.adoc[]
-include::unordered/regular.adoc[]
-include::unordered/concurrent.adoc[]
+include::unordered/comparison.adoc[]
 include::unordered/compliance.adoc[]
-include::unordered/structures.adoc[]
 include::unordered/benchmarks.adoc[]
 include::unordered/rationale.adoc[]
 include::unordered/ref.adoc[]
@@ -278,14 +278,13 @@ max load factor 5

 |===

-== boost::unordered_(flat|node)_map
+== boost::unordered_flat_map

 All benchmarks were created using:

 * `https://abseil.io/docs/cpp/guides/container[absl::flat_hash_map^]<uint64_t, uint64_t>`
-* `boost::unordered_map<uint64_t, uint64_t>`
 * `boost::unordered_flat_map<uint64_t, uint64_t>`
-* `boost::unordered_node_map<uint64_t, uint64_t>`
+* `boost::unordered_map<uint64_t, uint64_t>`

 The source code can be https://github.com/boostorg/boost_unordered_benchmarks/tree/boost_unordered_flat_map[found here^].

@@ -431,263 +430,3 @@ h|unsuccessful lookup

 |===

-== boost::concurrent_flat_map
-
-All benchmarks were created using:
-
-* `https://spec.oneapi.io/versions/latest/elements/oneTBB/source/containers/concurrent_hash_map_cls.html[oneapi::tbb::concurrent_hash_map^]<int, int>`
-* `https://github.com/greg7mdp/gtl/blob/main/docs/phmap.md[gtl::parallel_flat_hash_map^]<int, int>` with 64 submaps
-* `boost::concurrent_flat_map<int, int>`
-
-The source code can be https://github.com/boostorg/boost_unordered_benchmarks/tree/boost_concurrent_flat_map[found here^].
-
-The benchmarks exercise a number of threads _T_ (between 1 and 16) concurrently performing operations
-randomly chosen among **update**, **successful lookup** and **unsuccessful lookup**. The keys used in the
-operations follow a https://en.wikipedia.org/wiki/Zipf%27s_law#Formal_definition[Zipf distribution^]
-with different _skew_ parameters: the higher the skew, the more concentrated are the keys in the lower values
-of the covered range.
-
-=== GCC 12, x64
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== Clang 15, x64
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== Visual Studio 2022, x64
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== Clang 12, ARM64
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== GCC 12, x86
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== Clang 15, x86
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== Visual Studio 2022, x86
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
@@ -2,9 +2,9 @@
 :idprefix: buckets_
 :imagesdir: ../diagrams

-= Basics of Hash Tables
+= The Data Structure

-The containers are made up of a number of _buckets_, each of which can contain
+The containers are made up of a number of 'buckets', each of which can contain
 any number of elements. For example, the following diagram shows a <<unordered_set,`boost::unordered_set`>> with 7 buckets containing 5 elements, `A`,
 `B`, `C`, `D` and `E` (this is just for illustration, containers will typically
 have more buckets).
@@ -12,7 +12,8 @@ have more buckets).
 image::buckets.png[]

 In order to decide which bucket to place an element in, the container applies
-the hash function, `Hash`, to the element's key (for sets the key is the whole element, but is referred to as the key
+the hash function, `Hash`, to the element's key (for `unordered_set` and
+`unordered_multiset` the key is the whole element, but is referred to as the key
 so that the same terminology can be used for sets and maps). This returns a
 value of type `std::size_t`. `std::size_t` has a much greater range of values
 then the number of buckets, so the container applies another transformation to
@@ -52,7 +53,8 @@ h|*Method* h|*Description*
 |`size_type bucket_count() const` 
 |The number of buckets.

-2+^h| *Closed-addressing containers only*
+2+^h| *Closed-addressing containers only* +
+`boost::unordered_[multi]set`, `boost::unordered_[multi]map` 
 h|*Method* h|*Description*

 |`size_type max_bucket_count() const` 
@@ -78,7 +80,7 @@ h|*Method* h|*Description*

 |===

-== Controlling the Number of Buckets
+== Controlling the number of buckets

 As more elements are added to an unordered associative container, the number
 of collisions will increase causing performance to degrade.
@@ -88,8 +90,8 @@ calling `rehash`.

 The standard leaves a lot of freedom to the implementer to decide how the
 number of buckets is chosen, but it does make some requirements based on the
-container's _load factor_, the number of elements divided by the number of buckets.
-Containers also have a _maximum load factor_ which they should try to keep the
+container's 'load factor', the number of elements divided by the number of buckets.
+Containers also have a 'maximum load factor' which they should try to keep the
 load factor below.

 You can't control the bucket count directly but there are two ways to
@@ -131,7 +133,8 @@ h|*Method* h|*Description*
 |`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.

-2+^h| *Open-addressing and concurrent containers only*
+2+^h| *Open-addressing containers only* +
+`boost::unordered_flat_set`, `boost::unordered_flat_map` 
 h|*Method* h|*Description*

 |`size_type max_load() const`
@@ -139,7 +142,7 @@ h|*Method* h|*Description*

 |===

-A note on `max_load` for open-addressing and concurrent containers: the maximum load will be 
+A note on `max_load` for open-addressing containers: the maximum load will be 
 (`max_load_factor() * bucket_count()`) right after `rehash` or on container creation, but may
 slightly decrease when erasing elements in high-load situations. For instance, if we
 have a <<unordered_flat_map,`boost::unordered_flat_map`>> with `size()` almost
@@ -147,4 +150,98 @@ at `max_load()` level and then erase 1,000 elements, `max_load()` may decrease b
 few dozen elements. This is done internally by Boost.Unordered in order
 to keep its performance stable, and must be taken into account when planning for rehash-free insertions.

+== Iterator Invalidation

+It is not specified how member functions other than `rehash` and `reserve` affect
+the bucket count, although `insert` can only invalidate iterators
+when the insertion causes the container's load to be greater than the maximum allowed.
+For most implementations this means that `insert` will only
+change the number of buckets when this happens. Iterators can be
+invalidated by calls to `insert`, `rehash` and `reserve`.
+
+As for pointers and references,
+they are never invalidated for closed-addressing containers (`boost::unordered_[multi]set`, `boost::unordered_[multi]map`),
+but they will when rehashing occurs for open-addressing
+`boost::unordered_flat_set` and `boost::unordered_flat_map`: this is because
+these containers store elements directly into their holding buckets, so
+when allocating a new bucket array the elements must be transferred by means of move construction.
+
+In a similar manner to using `reserve` for ``vector``s, it can be a good idea
+to call `reserve` before inserting a large number of elements. This will get
+the expensive rehashing out of the way and let you store iterators, safe in
+the knowledge that they won't be invalidated. If you are inserting `n`
+elements into container `x`, you could first call:
+
+```
+x.reserve(n);
+```
+
+Note:: `reserve(n)` reserves space for at least `n` elements, allocating enough buckets
+so as to not exceed the maximum load factor.
+
+Because the maximum load factor is defined as the number of elements divided by the total
+number of available buckets, this function is logically equivalent to:
+
+```
+x.rehash(std::ceil(n / x.max_load_factor()))
+```
+
+See the <<unordered_map_rehash,reference for more details>> on the `rehash` function.
+
+== Fast Closed Addressing Implementation
+
++++
+<style>
+  .imageblock > .title {
+    text-align: inherit;
+  }
+</style>
++++
+
+Boost.Unordered sports one of the fastest implementations of closed addressing, also commonly known as https://en.wikipedia.org/wiki/Hash_table#Separate_chaining[separate chaining]. An example figure representing the data structure is below:
+
+[#img-bucket-groups,.text-center]
+.A simple bucket group approach
+image::bucket-groups.png[align=center]
+
+An array of "buckets" is allocated and each bucket in turn points to its own individual linked list. This makes meeting the standard requirements of bucket iteration straight-forward. Unfortunately, iteration of the entire container is often times slow using this layout as each bucket must be examined for occupancy, yielding a time complexity of `O(bucket_count() + size())` when the standard requires complexity to be `O(size())`.
+
+Canonical standard implementations will wind up looking like the diagram below:
+
+[.text-center]
+.The canonical standard approach
+image::singly-linked.png[align=center,link=../diagrams/singly-linked.png,window=_blank]
+
+It's worth noting that this approach is only used by pass:[libc++] and pass:[libstdc++]; the MSVC Dinkumware implementation uses a different one. A more detailed analysis of the standard containers can be found http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html[here].
+
+This unusually laid out data structure is chosen to make iteration of the entire container efficient by inter-connecting all of the nodes into a singly-linked list. One might also notice that buckets point to the node _before_ the start of the bucket's elements. This is done so that removing elements from the list can be done efficiently without introducing the need for a doubly-linked list. Unfortunately, this data structure introduces a guaranteed extra indirection. For example, to access the first element of a bucket, something like this must be done:
+
+```c++
+auto const idx = get_bucket_idx(hash_function(key));
+node* p = buckets[idx]; // first load
+node* n = p->next; // second load
+if (n && is_in_bucket(n, idx)) {
+  value_type const& v = *n; // third load
+  // ...
+}
+```
+
+With a simple bucket group layout, this is all that must be done:
+```c++
+auto const idx = get_bucket_idx(hash_function(key));
+node* n = buckets[idx]; // first load
+if (n) {
+  value_type const& v = *n; // second load
+  // ...
+}
+```
+
+In practice, the extra indirection can have a dramatic performance impact to common operations such as `insert`, `find` and `erase`. But to keep iteration of the container fast, Boost.Unordered introduces a novel data structure, a "bucket group". A bucket group is a fixed-width view of a subsection of the buckets array. It contains a bitmask (a `std::size_t`) which it uses to track occupancy of buckets and contains two pointers so that it can form a doubly-linked list with non-empty groups. An example diagram is below:
+
+[#img-fca-layout]
+.The new layout used by Boost
+image::fca.png[align=center]
+
+Thus container-wide iteration is turned into traversing the non-empty bucket groups (an operation with constant time complexity) which reduces the time complexity back to `O(size())`. In total, a bucket group is only 4 words in size and it views `sizeof(std::size_t) * CHAR_BIT` buckets meaning that for all common implementations, there's only 4 bits of space overhead per bucket introduced by the bucket groups.
+
+For more information on implementation rationale, read the <<Implementation Rationale, corresponding section>>.
@@ -6,31 +6,10 @@
 :github-pr-url: https://github.com/boostorg/unordered/pull
 :cpp: C++

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

 * Added fast containers `boost::unordered_flat_map` and `boost::unordered_flat_set`
  based on open addressing.
-* Added CTAD deduction guides for all containers.
-* Added missing constructors as specified in https://cplusplus.github.io/LWG/issue2713[LWG issue 2713].

 == Release 1.80.0 - Major update

@@ -1,99 +1,8 @@
-[#regular]
-= Regular Containers
-
-:idprefix: regular_
-
-Boost.Unordered closed-addressing containers (`boost::unordered_set`, `boost::unordered_map`,
-`boost::unordered_multiset` and `boost::unordered_multimap`) are fully conformant with the
-C++ specification for unordered associative containers, so for those who know how to use 
-`std::unordered_set`, `std::unordered_map`, etc., their homonyms in Boost.Unordered are
-drop-in replacements. The interface of open-addressing containers (`boost::unordered_node_set`, 
-`boost::unordered_node_map`, `boost::unordered_flat_set` and `boost::unordered_flat_map`)
-is very similar, but they present some minor differences listed in the dedicated
-xref:#compliance_open_addressing_containers[standard compliance section].
-
-
-For readers without previous experience with hash containers but familiar
-with normal associative containers (`std::set`, `std::map`,
-`std::multiset` and `std::multimap`), Boost.Unordered containers are used in a similar manner:
-
-[source,cpp]
----
-typedef boost::unordered_map<std::string, int> map;
-map x;
-x["one"] = 1;
-x["two"] = 2;
-x["three"] = 3;
-
-assert(x.at("one") == 1);
-assert(x.find("missing") == x.end());
----
-
-But since the elements aren't ordered, the output of:
-
-[source,c++]
----
-for(const map::value_type& i: x) {
-    std::cout<<i.first<<","<<i.second<<"\n";
-}
----
-
-can be in any order. For example, it might be:
-
-[source]
----
-two,2
-one,1
-three,3
----
-
-There are other differences, which are listed in the
-<<comparison,Comparison with Associative Containers>> section.
-
-== Iterator Invalidation
-
-It is not specified how member functions other than `rehash` and `reserve` affect
-the bucket count, although `insert` can only invalidate iterators
-when the insertion causes the container's load to be greater than the maximum allowed.
-For most implementations this means that `insert` will only
-change the number of buckets when this happens. Iterators can be
-invalidated by calls to `insert`, `rehash` and `reserve`.
-
-As for pointers and references,
-they are never invalidated for node-based containers 
-(`boost::unordered_[multi]set`, `boost::unordered_[multi]map`, `boost::unordered_node_set`, `boost::unordered_node_map`),
-but they will be when rehashing occurs for
-`boost::unordered_flat_set` and `boost::unordered_flat_map`: this is because
-these containers store elements directly into their holding buckets, so
-when allocating a new bucket array the elements must be transferred by means of move construction.
-
-In a similar manner to using `reserve` for ``vector``s, it can be a good idea
-to call `reserve` before inserting a large number of elements. This will get
-the expensive rehashing out of the way and let you store iterators, safe in
-the knowledge that they won't be invalidated. If you are inserting `n`
-elements into container `x`, you could first call:
-
-```
-x.reserve(n);
-```
-
-Note:: `reserve(n)` reserves space for at least `n` elements, allocating enough buckets
-so as to not exceed the maximum load factor.
-+
-Because the maximum load factor is defined as the number of elements divided by the total
-number of available buckets, this function is logically equivalent to:
-+
-```
-x.rehash(std::ceil(n / x.max_load_factor()))
-```
-+
-See the <<unordered_map_rehash,reference for more details>> on the `rehash` function.
-
 [#comparison]

 :idprefix: comparison_

-== Comparison with Associative Containers
+= Comparison with Associative Containers

 [caption=, title='Table {counter:table-counter} Interface differences']
 [cols="1,1", frame=all, grid=rows]
@@ -123,9 +32,9 @@ See the <<unordered_map_rehash,reference for more details>> on the `rehash` func
 |`iterator`, `const_iterator` are of at least the forward category.

 |Iterators, pointers and references to the container's elements are never invalidated.
-|<<regular_iterator_invalidation,Iterators can be invalidated by calls to insert or rehash>>. +
-**Node-based containers:** Pointers and references to the container's elements are never invalidated. +
-**Flat containers:** Pointers and references to the container's elements are invalidated when rehashing occurs.
+|<<buckets_iterator_invalidation,Iterators can be invalidated by calls to insert or rehash>>. +
+**Closed-addressing containers:** Pointers and references to the container's elements are never invalidated. +
+**Open-addressing containers:** Pointers and references to the container's elements are invalidated when rehashing occurs.

 |Iterators iterate through the container in the order defined by the comparison object.
 |Iterators iterate through the container in an arbitrary order, that can change as elements are inserted, although equivalent elements are always adjacent.
@@ -5,15 +5,15 @@

 :cpp: C++

-== Closed-addressing Containers
+== Closed-addressing containers: unordered_[multi]set, unordered_[multi]map

-`unordered_[multi]set` and `unordered_[multi]map` are intended to provide a conformant
+The intent of Boost.Unordered is to provide a conformant
 implementation of the {cpp}20 standard that will work with {cpp}98 upwards.
 This wide compatibility does mean some compromises have to be made.
 With a compiler and library that fully support {cpp}11, the differences should
 be minor.

-=== Move Emulation
+=== Move emulation

 Support for move semantics is implemented using Boost.Move. If rvalue
 references are available it will use them, but if not it uses a close,
@@ -25,7 +25,7 @@ but imperfect emulation. On such compilers:
 * The containers themselves are not movable.
 * Argument forwarding is not perfect.

-=== Use of Allocators
+=== Use of allocators

 {cpp}11 introduced a new allocator system. It's backwards compatible due to
 the lax requirements for allocators in the old standard, but might need
@@ -58,7 +58,7 @@ Due to imperfect move emulation, some assignments might check
 `propagate_on_container_copy_assignment` on some compilers and
 `propagate_on_container_move_assignment` on others.

-=== Construction/Destruction Using Allocators
+=== Construction/Destruction using allocators

 The following support is required for full use of {cpp}11 style
 construction/destruction:
@@ -117,88 +117,27 @@ Variadic constructor arguments for `emplace` are only used when both
 rvalue references and variadic template parameters are available.
 Otherwise `emplace` can only take up to 10 constructors arguments.

-== Open-addressing Containers
+== Open-addressing containers: unordered_flat_set, unordered_flat_map

 The C++ standard does not currently provide any open-addressing container
-specification to adhere to, so `boost::unordered_flat_set`/`unordered_node_set` and
-`boost::unordered_flat_map`/`unordered_node_map` take inspiration from `std::unordered_set` and
+specification to adhere to, so `boost::unordered_flat_set` and
+`boost::unordered_flat_map` take inspiration from `std::unordered_set` and
 `std::unordered_map`, respectively, and depart from their interface where
 convenient or as dictated by their internal data structure, which is
-radically different from that imposed by the standard (closed addressing).
+radically different from that imposed by the standard (closed addressing, node based).

-Open-addressing containers provided by Boost.Unordered only work with reasonably
+`unordered_flat_set` and `unordered_flat_map` only work with reasonably
 compliant C++11 (or later) compilers. Language-level features such as move semantics
 and variadic template parameters are then not emulated. 
-The containers are fully https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^].
+`unordered_flat_set` and `unordered_flat_map` are fully https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^].

 The main differences with C++ unordered associative containers are:

-* In general:
-  ** `begin()` is not constant-time.
-  ** `erase(iterator)` returns `void` instead of an iterator to the following element.
-  ** There is no API for bucket handling (except `bucket_count`).
-  ** The maximum load factor of the container is managed internally and can't be set by the user. The maximum load,
-     exposed through the public function `max_load`, may decrease on erasure under high-load conditions.
-* Flat containers (`boost::unordered_flat_set` and `boost::unordered_flat_map`):
-  ** `value_type` must be move-constructible.
-  ** Pointer stability is not kept under rehashing.
-  ** There is no API for node extraction/insertion.
+* `value_type` must be move-constructible.
+* Pointer stability is not kept under rehashing.
+* `begin()` is not constant-time.
+* `erase(iterator)` returns `void` instead of an iterator to the following element.
+* There is no API for bucket handling (except `bucket_count`) or node extraction/insertion.
+* The maximum load factor of the container is managed internally and can't be set by the user. The maximum load,
+exposed through the public function `max_load`, may decrease on erasure under high-load conditions.

-== Concurrent Containers
-
-There is currently no specification in the C++ standard for this or any other concurrent
-data structure. `boost::concurrent_flat_map` takes the same template parameters as `std::unordered_map`
-and all the maps provided by Boost.Unordered, and its API is modelled after that of
-`boost::unordered_flat_map` with the crucial difference that iterators are not provided
-due to their inherent problems in concurrent scenarios (high contention, prone to deadlocking):
-so, `boost::concurrent_flat_map` is technically not a
-https://en.cppreference.com/w/cpp/named_req/Container[Container^], although
-it meets all the requirements of https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^]
-containers except those implying iterators.
-
-In a non-concurrent unordered container, iterators serve two main purposes:
-
-* Access to an element previously located via lookup. 
-* Container traversal.
-
-In place of iterators, `boost::concurrent_flat_map` uses _internal visitation_
-facilities as a thread-safe substitute. Classical operations returning an iterator to an
-element already existing in the container, like for instance:
-
-[source,c++]
----
-iterator find(const key_type& k);
-std::pair<iterator, bool> insert(const value_type& obj);
----
-
-are transformed to accept a _visitation function_ that is passed such element:
-
-[source,c++]
----
-template<class F> size_t visit(const key_type& k, F f);
-template<class F> bool insert_or_visit(const value_type& obj, F f);
----
-
-(In the second case `f` is only invoked if there's an equivalent element
-to `obj` in the table, not if insertion is successful). Container traversal
-is served by:
-
-[source,c++]
----
-template<class F> size_t visit_all(F f);
----
-
-of which there are parallelized versions in C++17 compilers with parallel
-algorithm support. In general, the interface of `boost::concurrent_flat_map`
-is derived from that of `boost::unordered_flat_map` by a fairly straightforward
-process of replacing iterators with visitation where applicable. If
-`iterator` and `const_iterator` provide mutable and const access to elements,
-respectively, here visitation is granted mutable or const access depending on
-the constness of the member function used (there are also `*cvisit` overloads for
-explicit const visitation).
-
-The one notable operation not provided is `operator[]`/`at`, which can be
-replaced, if in a more convoluted manner, by
-xref:#concurrent_flat_map_try_emplace_or_cvisit[`try_emplace_or_visit`].
-
-//-
@@ -1,182 +0,0 @@
-[#concurrent]
-= Concurrent Containers
-
-:idprefix: concurrent_
-
-Boost.Unordered currently provides just one concurrent container named `boost::concurrent_flat_map`.
-`boost::concurrent_flat_map` is a hash table that allows concurrent write/read access from
-different threads without having to implement any synchronzation mechanism on the user's side.
-
-[source,c++]
----
-std::vector<int>                    input;
-boost::concurrent_flat_map<int,int> m;
-
-...
-
-// process input in parallel
-const int                 num_threads = 8;
-std::vector<std::jthread> threads;
-std::size_t               chunk = input.size() / num_threads; // how many elements per thread
-
-for (int i = 0; i < num_threads; ++i) {
-  threads.emplace_back([&,i] {
-    // calculate the portion of input this thread takes care of
-    std::size_t start = i * chunk;
-    std::size_t end = (i == num_threads - 1)? input.size(): (i + 1) * chunk;
-
-    for (std::size_t n = start; n < end; ++n) {
-      m.emplace(input[n], calculation(input[n]));
-    }
-  });
-}
----
-
-In the example above, threads access `m` without synchronization, just as we'd do in a
-single-threaded scenario. In an ideal setting, if a given workload is distributed among
-_N_ threads, execution is _N_ times faster than with one thread —this limit is
-never attained in practice due to synchronization overheads and _contention_ (one thread
-waiting for another to leave a locked portion of the map), but `boost::concurrent_flat_map`
-is designed to perform with very little overhead and typically achieves _linear scaling_
-(that is, performance is proportional to the number of threads up to the number of
-logical cores in the CPU).
-
-== Visitation-based API
-
-The first thing a new user of `boost::concurrent_flat_map` will notice is that this
-class _does not provide iterators_ (which makes it technically
-not a https://en.cppreference.com/w/cpp/named_req/Container[Container^]
-in the C++ standard sense). The reason for this is that iterators are inherently
-thread-unsafe. Consider this hypothetical code:
-
-[source,c++]
----
-auto it = m.find(k);  // A: get an iterator pointing to the element with key k
-if (it != m.end() ) {
-  some_function(*it); // B: use the value of the element
-}
----
-
-In a multithreaded scenario, the iterator `it` may be invalid at point B if some other
-thread issues an `m.erase(k)` operation between A and B. There are designs that
-can remedy this by making iterators lock the element they point to, but this
-approach lends itself to high contention and can easily produce deadlocks in a program.
-`operator[]` has similar concurrency issues, and is not provided by
-`boost::concurrent_flat_map` either. Instead, element access is done through
-so-called _visitation functions_:
-
-[source,c++]
----
-m.visit(k, [](const auto& x) { // x is the element with key k (if it exists)
-  some_function(x);            // use it
-});
----
-
-The visitation function passed by the user (in this case, a lambda function)
-is executed internally by `boost::concurrent_flat_map` in
-a thread-safe manner, so it can access the element without worrying about other
-threads interfering in the process.
-
-On the other hand, a visitation function can _not_ access the container itself:
-
-[source,c++]
----
-m.visit(k, [&](const auto& x) { 
-  some_function(x, m.size()); // forbidden: m can't be accessed inside visitation
-});
----
-
-Access to a different container is allowed, though:
-
-[source,c++]
----
-m.visit(k, [&](const auto& x) {
-  if (some_function(x)) {
-    m2.insert(x); // OK, m2 is a different boost::concurrent_flat_map
-  }
-});
----
-
-But, in general, visitation functions should be as lightweight as possible to
-reduce contention and increase parallelization. In some cases, moving heavy work
-outside of visitation may be beneficial:
-
-[source,c++]
----
-std::optional<value_type> o;
-bool found = m.visit(k, [&](const auto& x) { 
-  o = x;
-});
-if (found) {
-  some_heavy_duty_function(*o);
-}
----
-
-Visitation is prominent in the API provided by `boost::concurrent_flat_map`, and
-many classical operations have visitation-enabled variations:
-
-[source,c++]
----
-m.insert_or_visit(x, [](auto& y) { 
-  // if insertion failed because of an equivalent element y,
-  // do something with it, for instance:
-  ++y.second; // increment the mapped part of the element
-});
----
-
-Note that in this last example the visitation function could actually _modify_
-the element: as a general rule, operations on a `boost::concurrent_flat_map` `m`
-will grant visitation functions const/non-const access to  the element depending on whether
-`m` is const/non-const. Const access can be always be explicitly requested
-by using `cvisit` overloads (for instance, `insert_or_cvisit`) and may result
-in higher parallelization. Consult the xref:#concurrent_flat_map[reference]
-for a complete list of available operations.
-
-== Whole-table Visitation
-
-In the absence of iterators, `boost::concurrent_flat_map` provides `visit_all`
-as an alternative way to process all the elements in the map:
-
-[source,c++]
----
-m.visit_all([](auto& x) {
-  x.second = 0; // reset the mapped part of the element
-});
----
-
-In C++17 compilers implementing standard parallel algorithms, whole-table
-visitation can be parallelized:
-
-[source,c++]
----
-m.visit_all(std::execution::par, [](auto& x) { // run in parallel
-  x.second = 0; // reset the mapped part of the element
-});
----
-
-There is another whole-table visitation operation, `erase_if`:
-
-[source,c++]
----
-m.erase_if([](auto& x) {
-  return x.second == 0; // erase the elements whose mapped value is zero
-});
----
-
-`erase_if` can also be parallelized. Note that, in order to increase efficiency,
-these operations do not block the table during execution: this implies that elements
-may be inserted, modified or erased by other threads during visitation. It is
-advisable not to assume too much about the exact global state of a `boost::concurrent_flat_map`
-at any point in your program.
-
-== Blocking Operations
-
-``boost::concurrent_flat_map``s can be copied, assigned, cleared and merged just like any
-Boost.Unordered container. Unlike most other operations, these are _blocking_,
-that is, all other threads are prevented from accesing the tables involved while a copy, assignment,
-clear or merge operation is in progress. Blocking is taken care of automatically by the library
-and the user need not take any special precaution, but overall performance may be affected.
-
-Another blocking operation is _rehashing_, which happens explicitly via `rehash`/`reserve`
-or during insertion when the table's load hits `max_load()`. As with non-concurrent containers,
-reserving space in advance of bulk insertions will generally speed up the process.
@@ -9,10 +9,10 @@ Copyright (C) 2003, 2004 Jeremy B. Maitin-Shepard

 Copyright (C) 2005-2008 Daniel James

-Copyright (C) 2022-2023 Christian Mazakas
+Copyright (C) 2022 Christian Mazakas

-Copyright (C) 2022-2023 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz
+Copyright (C) 2022 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz

-Copyright (C) 2022-2023 Peter Dimov
+Copyright (C) 2022 Peter Dimov

 Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
@@ -20,14 +20,14 @@ class unordered_map;

 The hash function comes first as you might want to change the hash function
 but not the equality predicate. For example, if you wanted to use the
-https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1a_hash[FNV-1a hash^] you could write:
+http://www.isthe.com/chongo/tech/comp/fnv/[FNV-1 hash^] you could write:

 ```
-boost::unordered_map<std::string, int, hash::fnv_1a>
+boost::unordered_map<std::string, int, hash::fnv_1>
    dictionary;
 ```

-There is an link:../../examples/fnv1.hpp[implementation of FNV-1a^] in the examples directory.
+There is an link:../../examples/fnv1.hpp[implementation of FNV-1^] in the examples directory.

 If you wish to use a different equality function, you will also need to use a matching hash function. For example, to implement a case insensitive dictionary you need to define a case insensitive equality predicate and hash function:

@@ -4,65 +4,26 @@
 :idprefix: intro_
 :cpp: C++

-link:https://en.wikipedia.org/wiki/Hash_table[Hash tables^] are extremely popular
-computer data structures and can be found under one form or another in virtually any programming
-language. Whereas other associative structures such as rb-trees (used in {cpp} by `std::set` and `std::map`)
-have logarithmic-time complexity for insertion and lookup, hash tables, if configured properly,
-perform these operations in constant time on average, and are generally much faster.
+For accessing data based on key lookup, the {cpp} standard library offers `std::set`,
+`std::map`, `std::multiset` and `std::multimap`. These are generally
+implemented using balanced binary trees so that lookup time has
+logarithmic complexity. That is generally okay, but in many cases a
+link:https://en.wikipedia.org/wiki/Hash_table[hash table^] can perform better, as accessing data has constant complexity,
+on average. The worst case complexity is linear, but that occurs rarely and
+with some care, can be avoided.

-{cpp} introduced __unordered associative containers__ `std::unordered_set`, `std::unordered_map`,
-`std::unordered_multiset` and `std::unordered_multimap` in {cpp}11, but research on hash tables
-hasn't stopped since: advances in CPU architectures such as
-more powerful caches, link:https://en.wikipedia.org/wiki/Single_instruction,_multiple_data[SIMD] operations
-and increasingly available link:https://en.wikipedia.org/wiki/Multi-core_processor[multicore processors]
-open up possibilities for improved hash-based data structures and new use cases that
-are simply beyond reach of unordered associative containers as specified in 2011.
+Also, the existing containers require a 'less than' comparison object
+to order their elements. For some data types this is impossible to implement
+or isn't practical. In contrast, a hash table only needs an equality function
+and a hash function for the key.

-Boost.Unordered offers a catalog of hash containers with different standards compliance levels,
-performances and intented usage scenarios:
-
-[caption=, title='Table {counter:table-counter}. Boost.Unordered containers']
-[cols="1,1,.^1", frame=all, grid=all]
-|===
-^h|
-^h|*Node-based*
-^h|*Flat*
-
-^.^h|*Closed addressing*
-^m|
-boost::unordered_set +
-boost::unordered_map +
-boost::unordered_multiset +
-boost::unordered_multimap
-^| N/A
-
-^.^h|*Open addressing*
-^m| boost::unordered_node_set + 
-boost::unordered_node_map
-^m| boost::unordered_flat_set +
-boost::unordered_flat_map
-
-^.^h|*Concurrent*
-^|
-^| `boost::concurrent_flat_map`
-
-|===
-
-* **Closed-addressing containers** are fully compliant with the C++ specification
-for unordered associative containers and feature one of the fastest implementations
-in the market within the technical constraints imposed by the required standard interface.
-* **Open-addressing containers** rely on much faster data structures and algorithms
-(more than 2 times faster in typical scenarios) while slightly diverging from the standard
-interface to accommodate the implementation.
-There are two variants: **flat** (the fastest) and **node-based**, which 
-provide pointer stability under rehashing at the expense of being slower.
-* Finally, `boost::concurrent_flat_map` (the only **concurrent container** provided
-at present) is a hashmap designed and implemented to be used in high-performance
-multithreaded scenarios. Its interface is radically different from that of regular C++ containers.
-
-All sets and maps in Boost.Unordered are instantiatied similarly as
-`std::unordered_set` and `std::unordered_map`, respectively:
+With this in mind, unordered associative containers were added to the {cpp}
+standard. Boost.Unordered provides an implementation of the containers described in {cpp}11,
+with some <<compliance,deviations from the standard>> in
+order to work with non-{cpp}11 compilers and libraries.

+`unordered_set` and `unordered_multiset` are defined in the header
+`<boost/unordered/unordered_set.hpp>`
 [source,c++]
 ----  
 namespace boost {
@@ -71,20 +32,116 @@ namespace boost {
        class Hash = boost::hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<Key> >
-    class unordered_set; 
-    // same for unordered_multiset, unordered_flat_set, unordered_node_set
+    class unordered_set;

+    template<
+        class Key,
+        class Hash = boost::hash<Key>, 
+        class Pred = std::equal_to<Key>, 
+        class Alloc = std::allocator<Key> > 
+    class unordered_multiset;
+}
+----
+
+`unordered_map` and `unordered_multimap` are defined in the header
+`<boost/unordered/unordered_map.hpp>`
+
+[source,c++]
+----
+namespace boost {
    template <
        class Key, class Mapped,
        class Hash = boost::hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<std::pair<Key const, Mapped> > >
    class unordered_map;
-    // same for unordered_multimap, unordered_flat_map, unordered_node_map
-    // and concurrent_flat_map
+
+    template<
+        class Key, class Mapped,
+        class Hash = boost::hash<Key>,
+        class Pred = std::equal_to<Key>,
+        class Alloc = std::allocator<std::pair<Key const, Mapped> > >
+    class unordered_multimap;
 }
 ----

+These containers, and all other implementations of standard unordered associative
+containers, use an approach to its internal data structure design called
+*closed addressing*. Starting in Boost 1.81, Boost.Unordered also provides containers
+`boost::unordered_flat_set` and `boost::unordered_flat_map`, which use a
+different data structure strategy commonly known as *open addressing* and depart in
+a small number of ways from the standard so as to offer much better performance
+in exchange (more than 2 times faster in typical scenarios):
+
+
+[source,c++]
+----
+// #include <boost/unordered/unordered_flat_set.hpp>
+//
+// Note: no multiset version
+
+namespace boost {
+    template <
+        class Key,
+        class Hash = boost::hash<Key>,
+        class Pred = std::equal_to<Key>,
+        class Alloc = std::allocator<Key> >
+    class unordered_flat_set;
+}
+----
+
+[source,c++]
+----
+// #include <boost/unordered/unordered_flat_map.hpp>
+//
+// Note: no multimap version
+
+namespace boost {
+    template <
+        class Key, class Mapped,
+        class Hash = boost::hash<Key>,
+        class Pred = std::equal_to<Key>,
+        class Alloc = std::allocator<std::pair<Key const, Mapped> > >
+    class unordered_flat_map;
+}
+----
+
+`boost::unordered_flat_set` and `boost::unordered_flat_map` require a
+reasonably compliant C++11 compiler.
+
+Boost.Unordered containers are used in a similar manner to the normal associative
+containers:
+
+[source,cpp]
+----
+typedef boost::unordered_map<std::string, int> map;
+map x;
+x["one"] = 1;
+x["two"] = 2;
+x["three"] = 3;
+
+assert(x.at("one") == 1);
+assert(x.find("missing") == x.end());
+----
+
+But since the elements aren't ordered, the output of:
+
+[source,c++]
+----
+for(const map::value_type& i: x) {
+    std::cout<<i.first<<","<<i.second<<"\n";
+}
+----
+
+can be in any order. For example, it might be:
+
+[source]
+----
+two,2
+one,1
+three,3
+----
+
 To store an object in an unordered associative container requires both a
 key equality function and a hash function. The default function objects in
 the standard containers support a few basic types including integer types,
@@ -95,3 +152,6 @@ you have to extend Boost.Hash to support the type or use
 your own custom equality predicates and hash functions. See the
 <<hash_equality,Equality Predicates and Hash Functions>> section
 for more details.
+
+There are other differences, which are listed in the
+<<comparison,Comparison with Associative Containers>> section.
@@ -4,10 +4,9 @@

 = Implementation Rationale

-== Closed-addressing Containers
+== boost::unordered_[multi]set and boost::unordered_[multi]map

-`boost::unordered_[multi]set` and `boost::unordered_[multi]map`
-adhere to the standard requirements for unordered associative
+These containers adhere to the standard requirements for unordered associative
 containers, so the interface was fixed. But there are
 still some implementation decisions to make. The priorities are
 conformance to the standard and portability.
@@ -65,8 +64,8 @@ of bits in the hash value, so it was only used when `size_t` was 64 bit.

 Since release 1.79.0, https://en.wikipedia.org/wiki/Hash_function#Fibonacci_hashing[Fibonacci hashing]
 is used instead. With this implementation, the bucket number is determined
-by using `(h * m) >> (w - k)`, where `h` is the hash value, `m` is `2^w` divided
-by the golden ratio, `w` is the word size (32 or 64), and `2^k` is the
+by using `(h * m) >> (w - k)`, where `h` is the hash value, `m` is the golden
+ratio multiplied by `2^w`, `w` is the word size (32 or 64), and `2^k` is the
 number of buckets. This provides a good compromise between speed and
 distribution.

@@ -74,7 +73,7 @@ Since release 1.80.0, prime numbers are chosen for the number of buckets in
 tandem with sophisticated modulo arithmetic. This removes the need for "mixing"
 the result of the user's hash function as was used for release 1.79.0.

-== Open-addresing Containers 
+== boost::unordered_flat_set and boost::unordered_flat_map

 The C++ standard specification of unordered associative containers impose
 severe limitations on permissible implementations, the most important being
@@ -82,33 +81,30 @@ that closed addressing is implicitly assumed. Slightly relaxing this specificati
 opens up the possibility of providing container variations taking full
 advantage of open-addressing techniques.

-The design of `boost::unordered_flat_set`/`unordered_node_set` and `boost::unordered_flat_map`/`unordered_node_map` has been
+The design of `boost::unordered_flat_set` and `boost::unordered_flat_map` has been
 guided by Peter Dimov's https://pdimov.github.io/articles/unordered_dev_plan.html[Development Plan for Boost.Unordered^].
 We discuss here the most relevant principles.

-=== Hash Function
+=== Hash function

 Given its rich functionality and cross-platform interoperability,
-`boost::hash` remains the default hash function of open-addressing containers.
+`boost::hash` remains the default hash function of `boost::unordered_flat_set` and `boost::unordered_flat_map`.
 As it happens, `boost::hash` for integral and other basic types does not possess
 the statistical properties required by open addressing; to cope with this,
 we implement a post-mixing stage:

-{nbsp}{nbsp}{nbsp}{nbsp} _a_ <- _h_ *mulx* _C_, +
-{nbsp}{nbsp}{nbsp}{nbsp} _h_ <- *high*(_a_) *xor* *low*(_a_),
-
-where *mulx* is an _extended multiplication_ (128 bits in 64-bit architectures, 64 bits in 32-bit environments),
-and *high* and *low* are the upper and lower halves of an extended word, respectively.
-In 64-bit architectures, _C_ is the integer part of 2^64^&#8725;https://en.wikipedia.org/wiki/Golden_ratio[_&phi;_],
-whereas in 32 bits _C_ = 0xE817FB2Du has been obtained from https://arxiv.org/abs/2001.05304[Steele and Vigna (2021)^].
+*  64-bit architectures: we use the `xmx` function defined in
+Jon Maiga's http://jonkagstrom.com/bit-mixer-construction/index.html[The construct of a bit mixer^].
+*  32-bit architectures: the mixer used was selected from a set generated with https://github.com/skeeto/hash-prospector[Hash Function Prospector^]
+as the best overall performer in our internal benchmarks. Score assigned by Hash Prospector is 333.7934929677524.

 When using a hash function directly suitable for open addressing, post-mixing can be opted out by via a dedicated <<hash_traits_hash_is_avalanching,`hash_is_avalanching`>>trait.
 `boost::hash` specializations for string types are marked as avalanching.

-=== Platform Interoperability
+=== Platform interoperability

-The observable behavior of `boost::unordered_flat_set`/`unordered_node_set` and `boost::unordered_flat_map`/`unordered_node_map` is deterministically
-identical across different compilers as long as their ``std::size_t``s are the same size and the user-provided
+The observable behavior of `boost::unordered_flat_set` and `boost::unordered_flat_map` is deterministically
+identical across different compilers as long as their ``std::size_type``s are the same size and the user-provided
 hash function and equality predicate are also interoperable
 &#8212;this includes elements being ordered in exactly the same way for the same sequence of
 operations.
@@ -117,25 +113,3 @@ Although the implementation internally uses SIMD technologies, such as https://e
 and https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(NEON)[Neon^], when available,
 this does not affect interoperatility. For instance, the behavior is the same
 for Visual Studio on an x64-mode Intel CPU with SSE2 and for GCC on an IBM s390x without any supported SIMD technology.
-
-== Concurrent Containers
-
-The same data structure used by Boost.Unordered open-addressing containers has been chosen
-also as the foundation of `boost::concurrent_flat_map`:
-
-* Open-addressing is faster than closed-addressing alternatives, both in non-concurrent and
-concurrent scenarios.
-* Open-addressing layouts are eminently suitable for concurrent access and modification
-with minimal locking. In particular, the metadata array can be used for implementations of
-lookup that are lock-free up to the last step of actual element comparison.
-* Layout compatibility with Boost.Unordered flat containers allows for fast transfer
-of all elements between `boost::concurrent_flat_map` and `boost::unordered_flat_map`.
-(This feature has not been implemented yet.)
-
-=== Hash Function and Platform Interoperability
-
-`boost::concurrent_flat_map` makes the same decisions and provides the same guarantees
-as Boost.Unordered open-addressing containers with regards to 
-xref:#rationale_hash_function[hash function defaults] and
-xref:#rationale_platform_interoperability[platform interoperability].
-
@@ -8,6 +8,3 @@ include::unordered_multiset.adoc[]
 include::hash_traits.adoc[]
 include::unordered_flat_map.adoc[]
 include::unordered_flat_set.adoc[]
-include::unordered_node_map.adoc[]
-include::unordered_node_set.adoc[]
-include::concurrent_flat_map.adoc[]
--- a/Show More
+++ b/Show More
Author	SHA1	Message	Date
joaquintides	1e57c08686	fourth attempt	2022-11-28 17:58:15 +01:00
joaquintides	3a34b8dae9	micro-optimized previous	2022-11-28 12:13:04 +01:00
joaquintides	0a91421fb8	third attempt	2022-11-27 20:54:26 +01:00
joaquintides	602488abc1	reverted `c463cf13fd` (wrong branch)	2022-11-24 20:12:48 +01:00
joaquintides	c463cf13fd	added "Open Addressing Implementation" section	2022-11-24 20:00:04 +01:00
joaquintides	09171776f7	second attempt	2022-11-24 13:01:09 +01:00
joaquintides	cf2a0ef303	added first draft of new pow2_size_policy	2022-11-22 20:06:29 +01:00