Make typedef private and rename it so older versions of msvc don't erroneously treat the typedef like it's in scope when doing template instantiation

Manually implement node_handle_base's default constructor instead of defaulting it which can delete it on older toolchains
Add foa-based node containers to extract tests in transparent_tests
2023-02-13 09:10:21 -08:00 · 2023-02-10 15:16:59 -08:00 · 2023-02-10 14:19:20 -08:00 · 2023-02-10 14:19:01 -08:00 · 2023-02-09 15:59:23 -08:00 · 2023-02-08 15:08:51 -08:00
161 changed files with 1655 additions and 17550 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,18 +352,8 @@ 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(
@@ -483,12 +362,6 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
        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",
-    ),
-
    windows_pipeline(
        "Windows VS2015 msvc-14.0",
        "cppalliance/dronevs2015",
@@ -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,17 @@ 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' }

-    timeout-minutes: 180
+    timeout-minutes: 120
    runs-on: ${{matrix.os}}
    container: ${{matrix.container}}
    env: {B2_USE_CCACHE: 1}
@@ -193,8 +184,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 +197,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
@@ -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,5 +1,4 @@
 // 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

@@ -7,7 +6,6 @@
 #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/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
@@ -274,9 +272,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>>;

@@ -350,9 +345,6 @@ 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>>;

@@ -381,7 +373,6 @@ 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
@@ -399,7 +390,6 @@ int main()

    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
@@ -1,5 +1,4 @@
 // 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

@@ -7,7 +6,6 @@
 #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/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
@@ -275,9 +273,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>>;

@@ -351,9 +346,6 @@ 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>>;

@@ -382,7 +374,6 @@ 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
@@ -400,7 +391,6 @@ int main()

    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
@@ -1,5 +1,4 @@
 // 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

@@ -7,7 +6,6 @@
 #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/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
@@ -291,9 +289,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>>;

@@ -320,7 +315,6 @@ 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
@@ -1,5 +1,4 @@
 // 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

@@ -7,7 +6,6 @@
 #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/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
@@ -291,9 +289,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>>;

@@ -330,7 +325,6 @@ int main()
 #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
@@ -1,5 +1,4 @@
 // 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

@@ -7,7 +6,6 @@
 #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/endian/conversion.hpp>
 #include <boost/core/detail/splitmix64.hpp>
@@ -342,9 +340,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>>;

@@ -371,7 +366,6 @@ 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
@@ -1,5 +1,4 @@
 // 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

@@ -7,7 +6,6 @@
 #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
@@ -229,9 +227,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>>;

@@ -305,9 +300,6 @@ 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>>;

@@ -336,7 +328,6 @@ 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
@@ -354,7 +345,6 @@ int main()

    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
@@ -1,5 +1,4 @@
 // 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

@@ -7,7 +6,6 @@
 #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
@@ -183,9 +181,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>>;

@@ -212,7 +207,6 @@ 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
@@ -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,163 @@ 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.
+
+A more detailed description of Boost.Unordered's closed-addressing implementation is
+given in an
+https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html[external article].
+For more information on implementation rationale, read the
+xref:#rationale_boostunordered_multiset_and_boostunordered_multimap[corresponding section].
+
+== Open Addressing Implementation
+
+The diagram shows the basic internal layout of `boost::unordered_flat_map` and
+`boost:unordered_flat_set`.
+
+
+[#img-foa-layout]
+.Open-addressing layout used by Boost.Unordered.
+image::foa.png[align=center]
+
+As with all open-addressing containers, elements are stored directly in the bucket array.
+This array is logically divided into 2^_n_^ _groups_ of 15 elements each.
+In addition to the bucket array, there is an associated _metadata array_ with 2^_n_^
+16-byte words.
+
+[#img-foa-metadata]
+.Breakdown of a metadata word.
+image::foa-metadata.png[align=center]
+
+A metadata word is divided into 15 _h_~_i_~ bytes (one for each associated
+bucket), and an _overflow byte_ (_ofw_ in the diagram). The value of _h_~_i_~ is:
+
+  - 0 if the corresponding bucket is empty.
+  - 1 to encode a special empty bucket called a _sentinel_, which is used internally to
+  stop iteration when the container has been fully traversed.
+  - If the bucket is occupied, a _reduced hash value_ obtained from the hash value of
+  the element.
+
+When looking for an element with hash value _h_, SIMD technologies such as
+https://en.wikipedia.org/wiki/SSE2[SSE2] and
+https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] allow us
+to very quickly inspect the full metadata word and look for the reduced value of _h_ among all the
+15 buckets with just a handful of CPU instructions: non-matching buckets can be
+readily discarded, and those whose reduced hash value matches need be inspected via full
+comparison with the corresponding element. If the looked-for element is not present,
+the overflow byte is inspected:
+
+- If the bit in the position _h_ mod 8 is zero, lookup terminates (and the
+element is not present).
+- If the bit is set to 1 (the group has been _overflowed_), further groups are
+checked using https://en.wikipedia.org/wiki/Quadratic_probing[_quadratic probing_], and
+the process is repeated.
+
+Insertion is algorithmically similar: empty buckets are located using SIMD,
+and when going past a full group its corresponding overflow bit is set to 1.
+
+In architectures without SIMD support, the logical layout stays the same, but the metadata
+word is codified using a technique we call _bit interleaving_: this layout allows us
+to emulate SIMD with reasonably good performance using only standard arithmetic and
+logical operations.
+
+[#img-foa-metadata-interleaving]
+.Bit-interleaved metadata word.
+image::foa-metadata-interleaving.png[align=center]
+
+A more detailed description of Boost.Unordered's open-addressing implementation is
+given in an
+https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[external article].
+For more information on implementation rationale, read the
+xref:#rationale_boostunordered_flat_set_and_boostunordered_flat_map[corresponding section].
@@ -6,24 +6,10 @@
 :github-pr-url: https://github.com/boostorg/unordered/pull
 :cpp: C++

-== Release 1.83.0 - Major update
+== Release 1.82.0

-* 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.
+  https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2363r3.html[P2363].

 == Release 1.81.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[]
@@ -1,179 +0,0 @@
-[#structures]
-= Data Structures
-
-:idprefix: structures_
-
-== Closed-addressing Containers
-
-++++
-<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.
-
-A more detailed description of Boost.Unordered's closed-addressing implementation is
-given in an
-https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html[external article].
-For more information on implementation rationale, read the
-xref:#rationale_closed_addressing_containers[corresponding section].
-
-== Open-addressing Containers
-
-The diagram shows the basic internal layout of `boost::unordered_flat_map`/`unordered_node_map` and
-`boost:unordered_flat_set`/`unordered_node_set`.
-
-
-[#img-foa-layout]
-.Open-addressing layout used by Boost.Unordered.
-image::foa.png[align=center]
-
-As with all open-addressing containers, elements (or pointers to the element nodes in the case of
-`boost::unordered_node_map` and `boost::unordered_node_set`) are stored directly in the bucket array.
-This array is logically divided into 2^_n_^ _groups_ of 15 elements each.
-In addition to the bucket array, there is an associated _metadata array_ with 2^_n_^
-16-byte words.
-
-[#img-foa-metadata]
-.Breakdown of a metadata word.
-image::foa-metadata.png[align=center]
-
-A metadata word is divided into 15 _h_~_i_~ bytes (one for each associated
-bucket), and an _overflow byte_ (_ofw_ in the diagram). The value of _h_~_i_~ is:
-
-  - 0 if the corresponding bucket is empty.
-  - 1 to encode a special empty bucket called a _sentinel_, which is used internally to
-  stop iteration when the container has been fully traversed.
-  - If the bucket is occupied, a _reduced hash value_ obtained from the hash value of
-  the element.
-
-When looking for an element with hash value _h_, SIMD technologies such as
-https://en.wikipedia.org/wiki/SSE2[SSE2] and
-https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] allow us
-to very quickly inspect the full metadata word and look for the reduced value of _h_ among all the
-15 buckets with just a handful of CPU instructions: non-matching buckets can be
-readily discarded, and those whose reduced hash value matches need be inspected via full
-comparison with the corresponding element. If the looked-for element is not present,
-the overflow byte is inspected:
-
- If the bit in the position _h_ mod 8 is zero, lookup terminates (and the
-element is not present).
- If the bit is set to 1 (the group has been _overflowed_), further groups are
-checked using https://en.wikipedia.org/wiki/Quadratic_probing[_quadratic probing_], and
-the process is repeated.
-
-Insertion is algorithmically similar: empty buckets are located using SIMD,
-and when going past a full group its corresponding overflow bit is set to 1.
-
-In architectures without SIMD support, the logical layout stays the same, but the metadata
-word is codified using a technique we call _bit interleaving_: this layout allows us
-to emulate SIMD with reasonably good performance using only standard arithmetic and
-logical operations.
-
-[#img-foa-metadata-interleaving]
-.Bit-interleaved metadata word.
-image::foa-metadata-interleaving.png[align=center]
-
-A more detailed description of Boost.Unordered's open-addressing implementation is
-given in an
-https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[external article].
-For more information on implementation rationale, read the
-xref:#rationale_open_addresing_containers[corresponding section].
-
-== Concurrent Containers
-
-`boost::concurrent_flat_map` uses the basic
-xref:#structures_open_addressing_containers[open-addressing layout] described above
-augmented with synchronization mechanisms.
-
-
-[#img-cfoa-layout]
-.Concurrent open-addressing layout used by Boost.Unordered.
-image::cfoa.png[align=center]
-
-Two levels of synchronization are used:
-
-* Container level: A read-write mutex is used to control access from any operation
-to the container. Typically, such access is in read mode (that is, concurrent) even
-for modifying operations, so for most practical purposes there is no thread
-contention at this level. Access is only in write mode (blocking) when rehashing or
-performing container-wide operations such as swapping or assignment.
-* Group level: Each 15-slot group is equipped with an 8-byte word containing:
-  ** A read-write spinlock for synchronized access to any element in the group.
-  ** An atomic _insertion counter_ used for optimistic insertion as described
-  below.
-
-By using atomic operations to access the group metadata, lookup is (group-level)
-lock-free up to the point where an actual comparison needs to be done with an element
-that has been previously SIMD-matched: only then it's the group's spinlock used.
-
-Insertion uses the following _optimistic algorithm_:
-
-* The value of the insertion counter for the initial group in the probe
-sequence is locally recorded (let's call this value `c0`).
-* Lookup is as described above. If lookup finds no equivalent element,
-search for an available slot for insertion successively locks/unlocks
-each group in the probing sequence.
-* When an available slot is located, it is preemptively occupied (its
-reduced hash value is set) and the insertion counter is atomically
-incremented: if no other thread has incremented the counter during the
-whole operation (which is checked by comparing with `c0`), then we're
-good to go and complete the insertion, otherwise we roll back and start
-over.
-
-This algorithm has very low contention both at the lookup and actual
-insertion phases in exchange for the possibility that computations have
-to be started over if some other thread interferes in the process by
-performing a succesful insertion beginning at the same group. In
-practice, the start-over frequency is extremely small, measured in the range
-of parts per million for some of our benchmarks.
-
-For more information on implementation rationale, read the
-xref:#rationale_concurrent_containers[corresponding section].
@@ -1,5 +1,5 @@
 [#unordered_flat_map]
-== Class Template unordered_flat_map
+== Class template unordered_flat_map

 :idprefix: unordered_flat_map_

@@ -280,7 +280,6 @@ namespace boost {
              unordered_flat_map<Key, T, Hash, Pred, Alloc>& y)
      noexcept(noexcept(x.swap(y)));

-  // Erasure
  template<class K, class T, class H, class P, class A, class Predicate>
    typename unordered_flat_map<K, T, H, P, A>::size_type
       xref:#unordered_flat_map_erase_if[erase_if](unordered_flat_map<K, T, H, P, A>& c, Predicate pred);
@@ -860,7 +859,7 @@ void insert(std::initializer_list<value_type>);
 Inserts a range of elements into the container. Elements are inserted if and only if there is no element in the container with an equivalent key.

 [horizontal]
-Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^] into the container.
+Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[EmplaceConstructible^] into the container from `*first`.
 Throws:;; When inserting a single element, if an exception is thrown by an operation other than a call to `hasher` the function has no effect.
 Notes:;; Can invalidate iterators, pointers and references, but only if the insert causes the load to be greater than the maximum load.

@@ -876,7 +875,7 @@ template<class K, class... Args>
  std::pair<iterator, bool> try_emplace(K&& k, Args&&... args);
 ```

-Inserts a new element into the container if there is no existing element with key `k` contained within it.
+Inserts a new node into the container if there is no existing element with key `k` contained within it.

 If there is an existing element with key `k` this function does nothing.

@@ -905,7 +904,7 @@ unlike xref:#unordered_flat_map_emplace[emplace], which simply forwards all argu

 Can invalidate iterators pointers and references, but only if the insert causes the load to be greater than the maximum load.

-The `template<class K, class\... Args>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs and neither `iterator` nor `const_iterator` are implicitly convertible from `K`. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+The `template <class K, class... Args>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs and neither `iterator` nor `const_iterator` are implicitly convertible from `K`. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 --

@@ -921,7 +920,7 @@ template<class K, class... Args>
  iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
 ```

-Inserts a new element into the container if there is no existing element with key `k` contained within it.
+Inserts a new node into the container if there is no existing element with key `k` contained within it.

 If there is an existing element with key `k` this function does nothing.

@@ -950,7 +949,7 @@ unlike xref:#unordered_flat_map_emplace_hint[emplace_hint], which simply forward

 Can invalidate iterators pointers and references, but only if the insert causes the load to be greater than the maximum load.

-The `template<class K, class\... Args>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs and neither `iterator` nor `const_iterator` are implicitly convertible from `K`. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+The `template <class K, class... Args>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs and neither `iterator` nor `const_iterator` are implicitly convertible from `K`. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 --

@@ -1161,7 +1160,7 @@ template<class K>

 [horizontal]
 Returns:;; An iterator pointing to an element with key equivalent to `k`, or `end()` if no such element exists.
-Notes:;; The `template<class K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1174,7 +1173,7 @@ template<class K>

 [horizontal]
 Returns:;; The number of elements with key equivalent to `k`.
-Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1187,7 +1186,7 @@ template<class K>

 [horizontal]
 Returns:;; A boolean indicating whether or not there is an element with key equal to `key` in the container
-Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1203,7 +1202,7 @@ template<class K>

 [horizontal]
 Returns:;; A range containing all elements with key equivalent to `k`. If the container doesn't contain any such elements, returns `std::make_pair(b.end(), b.end())`.
-Notes:;; The `template<class K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1,5 +1,5 @@
 [#unordered_flat_set]
-== Class Template unordered_flat_set
+== Class template unordered_flat_set

 :idprefix: unordered_flat_set_

@@ -234,7 +234,6 @@ namespace boost {
              unordered_flat_set<Key, T, Hash, Pred, Alloc>& y)
      noexcept(noexcept(x.swap(y)));

-  // Erasure
  template<class K, class T, class H, class P, class A, class Predicate>
    typename unordered_flat_set<K, T, H, P, A>::size_type
       xref:#unordered_flat_set_erase_if[erase_if](unordered_flat_set<K, T, H, P, A>& c, Predicate pred);
@@ -838,7 +837,7 @@ void insert(std::initializer_list<value_type>);
 Inserts a range of elements into the container. Elements are inserted if and only if there is no element in the container with an equivalent key.

 [horizontal]
-Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^] into the container.
+Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[EmplaceConstructible^] into the container from `*first`.
 Throws:;; When inserting a single element, if an exception is thrown by an operation other than a call to `hasher` the function has no effect.
 Notes:;; Can invalidate iterators, pointers and references, but only if the insert causes the load to be greater than the maximum load.

@@ -972,7 +971,7 @@ template<class K>

 [horizontal]
 Returns:;; An iterator pointing to an element with key equivalent to `k`, or `end()` if no such element exists.
-Notes:;; The `template<class K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -985,7 +984,7 @@ template<class K>

 [horizontal]
 Returns:;; The number of elements with key equivalent to `k`.
-Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -998,7 +997,7 @@ template<class K>

 [horizontal]
 Returns:;; A boolean indicating whether or not there is an element with key equal to `key` in the container
-Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1014,7 +1013,7 @@ template<class K>

 [horizontal]
 Returns:;; A range containing all elements with key equivalent to `k`. If the container doesn't contain any such elements, returns `std::make_pair(b.end(), b.end())`.
-Notes:;; The `template<class K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1,5 +1,5 @@
 [#unordered_map]
-== Class Template unordered_map
+== Class template unordered_map

 :idprefix: unordered_map_

@@ -286,7 +286,6 @@ namespace boost {
              unordered_map<Key, T, Hash, Pred, Alloc>& y)
      noexcept(noexcept(x.swap(y)));

-  // Erasure
  template<class K, class T, class H, class P, class A, class Predicate>
    typename unordered_map<K, T, H, P, A>::size_type
       xref:#unordered_map_erase_if[erase_if](unordered_map<K, T, H, P, A>& c, Predicate pred);
@@ -996,7 +995,7 @@ void insert(std::initializer_list<value_type>);
 Inserts a range of elements into the container. Elements are inserted if and only if there is no element in the container with an equivalent key.

 [horizontal]
-Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^] into the container.
+Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[EmplaceConstructible^] into `X` from `*first`.
 Throws:;; When inserting a single element, if an exception is thrown by an operation other than a call to `hasher` the function has no effect.
 Notes:;; Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor. +
 +
@@ -1010,11 +1009,11 @@ template<class... Args>
  std::pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
 template<class... Args>
  std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
-template<class K, class... Args>
+template <class K, class... Args>
  std::pair<iterator, bool> try_emplace(K&& k, Args&&... args)
 ```

-Inserts a new element into the container if there is no existing element with key `k` contained within it.
+Inserts a new node into the container if there is no existing element with key `k` contained within it.

 If there is an existing element with key `k` this function does nothing.

@@ -1044,7 +1043,7 @@ Can invalidate iterators, but only if the insert causes the load factor to be gr

 Pointers and references to elements are never invalidated.

-The `template<class K, class\... Args>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs and neither `iterator` nor `const_iterator` are implicitly convertible from `K`. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+The `template <class K, class... Args>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs and neither `iterator` nor `const_iterator` are implicitly convertible from `K`. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 If the compiler doesn't support variadic template arguments or rvalue references, this is emulated for up to `10` arguments, with no support for rvalue references or move semantics.

@@ -1063,7 +1062,7 @@ template<class K, class... Args>
  iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
 ```

-Inserts a new element into the container if there is no existing element with key `k` contained within it.
+Inserts a new node into the container if there is no existing element with key `k` contained within it.

 If there is an existing element with key `k` this function does nothing.

@@ -1095,7 +1094,7 @@ Can invalidate iterators, but only if the insert causes the load factor to be gr

 Pointers and references to elements are never invalidated.

-The `template<class K, class\... Args>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs and neither `iterator` nor `const_iterator` are implicitly convertible from `K`. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+The `template <class K, class... Args>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs and neither `iterator` nor `const_iterator` are implicitly convertible from `K`. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 If the compiler doesn't support variadic template arguments or rvalue references, this is emulated for up to `10` arguments, with no support for rvalue references or move semantics.

@@ -1467,7 +1466,7 @@ template<typename CompatibleKey, typename CompatibleHash, typename CompatiblePre
 Returns:;; An iterator pointing to an element with key equivalent to `k`, or `b.end()` if no such element exists.
 Notes:;; The templated overloads containing `CompatibleKey`, `CompatibleHash` and `CompatiblePredicate` are non-standard extensions which allow you to use a compatible hash function and equality predicate for a key of a different type in order to avoid an expensive type cast. In general, its use is not encouraged and instead the `K` member function templates should be used. +
 +
-The `template<class K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+The `template <typename K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1480,7 +1479,7 @@ template<class K>

 [horizontal]
 Returns:;; The number of elements with key equivalent to `k`.
-Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1493,7 +1492,7 @@ template<class K>

 [horizontal]
 Returns:;; A boolean indicating whether or not there is an element with key equal to `key` in the container
-Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1509,7 +1508,7 @@ template<class K>

 [horizontal]
 Returns:;; A range containing all elements with key equivalent to `k`. If the container doesn't contain any such elements, returns `std::make_pair(b.end(), b.end())`.
-Notes:;; The `template<class K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1,5 +1,5 @@
 [#unordered_multimap]
-== Class Template unordered_multimap
+== Class template unordered_multimap

 :idprefix: unordered_multimap_

@@ -253,7 +253,6 @@ namespace boost {
              unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
      noexcept(noexcept(x.swap(y)));

-  // Erasure
  template<class K, class T, class H, class P, class A, class Predicate>
    typename unordered_multimap<K, T, H, P, A>::size_type
      xref:#unordered_multimap_erase_if[erase_if](unordered_multimap<K, T, H, P, A>& c, Predicate pred);
@@ -942,7 +941,7 @@ void insert(std::initializer_list<value_type> il);
 Inserts a range of elements into the container.

 [horizontal]
-Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^] into the container.
+Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[EmplaceConstructible^] into `X` from `*first`.
 Throws:;; When inserting a single element, if an exception is thrown by an operation other than a call to `hasher` the function has no effect.
 Notes:;; Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor. +
 +
@@ -1224,7 +1223,7 @@ template<typename CompatibleKey, typename CompatibleHash, typename CompatiblePre
 Returns:;; An iterator pointing to an element with key equivalent to `k`, or `b.end()` if no such element exists.
 Notes:;; The templated overloads containing `CompatibleKey`, `CompatibleHash` and `CompatiblePredicate` are non-standard extensions which allow you to use a compatible hash function and equality predicate for a key of a different type in order to avoid an expensive type cast. In general, its use is not encouraged and instead the `K` member function templates should be used. +
 +
-The `template<class K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+The `template <typename K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1237,7 +1236,7 @@ template<class K>

 [horizontal]
 Returns:;; The number of elements with key equivalent to `k`.
-Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1250,7 +1249,7 @@ template<class K>

 [horizontal]
 Returns:;; A boolean indicating whether or not there is an element with key equal to `key` in the container
-Notes:;; The `template<class K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overload only participates in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

@@ -1266,7 +1265,7 @@ template<class K>

 [horizontal]
 Returns:;; A range containing all elements with key equivalent to `k`. If the container doesn't contain any such elements, returns `std::make_pair(b.end(), b.end())`.
-Notes:;; The `template<class K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.
+Notes:;; The `template <typename K>` overloads only participate in overload resolution if `Hash::is_transparent` and `Pred::is_transparent` are valid member typedefs. The library assumes that `Hash` is callable with both `K` and `Key` and that `Pred` is transparent. This enables heterogeneous lookup which avoids the cost of instantiating an instance of the `Key` type.

 ---

--- a/Show More
+++ b/Show More
Author	SHA1	Message	Date
Christian Mazakas	0c93fbc330	Make typedef private and rename it so older versions of msvc don't erroneously treat the typedef like it's in scope when doing template instantiation	2023-02-13 09:10:21 -08:00
Christian Mazakas	b8ff76f4ab	Manually implement node_handle_base's default constructor instead of defaulting it which can delete it on older toolchains	2023-02-10 15:16:59 -08:00
Christian Mazakas	5df80086ed	Add foa-based node containers to extract tests in transparent_tests	2023-02-10 14:19:20 -08:00
Christian Mazakas	f9c32e7f8c	Clean up impl of node_handle	2023-02-10 14:19:01 -08:00
Christian Mazakas	21e673c697	Begin cleanup of node_handle implementation	2023-02-09 15:59:23 -08:00
Christian Mazakas	b96dd2184f	Add foa-based node containers to node_handle_tests	2023-02-08 15:08:51 -08:00
Christian Mazakas	9636875596	Fix incorrect placement new of allocator type by reifying ad hoc node handle implementations into a base class	2023-02-08 10:36:19 -08:00
Christian Mazakas	bd6829220c	Add extract/insert semantics to foa-based node set, add more tests	2023-02-07 15:17:25 -08:00
Christian Mazakas	71bf336c9d	Add missing empty_ initialization to move constructor of node_type	2023-02-07 10:08:58 -08:00
Christian Mazakas	b7c1e6a184	Remove print statements	2023-02-07 10:08:34 -08:00
Christian Mazakas	77edd24b4e	Interim checkin of attempt at extract/insert node handles	2023-02-06 15:56:55 -08:00
Christian Mazakas	b7032baaf4	fixup osx fix	2023-02-03 10:02:49 -08:00
Christian Mazakas	6580dc8d80	Add regression test for test::exception::less	2023-02-03 10:02:28 -08:00
Christian Mazakas	5384edd568	Attempt osx ci fix by fixing logic buf in less_impl for test::exception::less	2023-02-02 13:32:08 -08:00
Christian Mazakas	2a7a8f55e1	Revert OSX CI experiment as it breaks emplace_tests	2023-02-01 10:49:20 -08:00
Christian Mazakas	18a664c4a6	Experiment for failing OSX CI	2023-02-01 10:25:50 -08:00
Christian Mazakas	e1b394d5b2	Disable immovable test for libstdc++ versions below 6.0 as their std::pair implementation doesn't support immovable types	2023-02-01 09:02:05 -08:00
Christian Mazakas	dc548a1a9e	Update compare_range() to skip size check and use direct comparison function	2023-01-31 15:59:29 -08:00
Christian Mazakas	2787717d78	Update compare_range to use BOOST_TEST_ALL_WITH in lieu of homegrown implementation	2023-01-31 13:55:06 -08:00
Christian Mazakas	d6ba04ca4b	Remove use of unevaluated function in init_type_insert_tests for older versions of gcc	2023-01-31 13:45:29 -08:00
Christian Mazakas	43add11970	Add macos-12 to GHA	2023-01-31 13:45:10 -08:00
Christian Mazakas	8e45197d4d	Add -Wunused-template only to clang-14 builds	2023-01-31 13:44:57 -08:00
Christian Mazakas	a46220986f	Replace usage of rote try-catch with corresponding Boost versions	2023-01-31 10:32:06 -08:00
Christian Mazakas	16099478db	Clean up implementation of emplace_dispatch(false_type)	2023-01-31 10:31:52 -08:00
Christian Mazakas	e5320df017	Fix msvc warnings	2023-01-31 09:03:25 -08:00
Christian Mazakas	b9fcfeb24e	Update foa table to support immovable types in the case of the node-based maps	2023-01-30 13:55:50 -08:00
Christian Mazakas	f1aeb3b099	Update init_type_insert_tests for node-based foa containers	2023-01-30 13:55:50 -08:00
Christian Mazakas	5b706bb7b5	Update node-based foa containers to default their element_type default constructor and delete the copy constructor to get the appropriate type-based optimizations	2023-01-30 13:55:50 -08:00
Christian Mazakas	fd7d888832	Add missing test back in for non-foa runs	2023-01-30 13:55:50 -08:00
Christian Mazakas	827c69eb1a	Conditionally exclude node_map from non-foa test runs	2023-01-30 13:55:50 -08:00
Christian Mazakas	9973b3f8a8	Comment tests back in	2023-01-30 13:55:50 -08:00
joaquintides	e6f911e815	provide erase_on_exit ctor	2023-01-30 13:55:50 -08:00
joaquintides	53e4531295	fixed bug with dangling moved element on throwing rehash during merge	2023-01-30 13:55:50 -08:00
Christian Mazakas	8da44f4f46	Check in interim tests for easy debugging between team members	2023-01-30 13:55:50 -08:00
Christian Mazakas	dddfbf8aa8	Add node-based foa containers to swap_exception_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	a66eedef58	Add node-based foa containers to insert_exception_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	202049ddc0	Add node-based foa containers to merge_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	000833d647	fixup insert_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	d84e6f7be2	fixup assign_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	8acfccdf6e	fixup constructor_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	c85dd289f9	Add node-based foa containers to simple_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	8ac6019d30	Add node-based foa containers to incomplete_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	9602799710	Add node-based foa containers to link tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	217a171b33	Add node-based foa containers to noexcept_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	b372ab6641	Add node-based foa containers to compile_map	2023-01-30 13:55:50 -08:00
Christian Mazakas	140cb56e2b	Add node-based foa containers to compile_set	2023-01-30 13:55:50 -08:00
Christian Mazakas	8b842c4640	fixup fwd_set_test	2023-01-30 13:55:50 -08:00
Christian Mazakas	9b2ecd6ec5	Add node-based foa containers to fwd_map_test	2023-01-30 13:55:50 -08:00
Christian Mazakas	351e5ae41a	Add node-based foa containers to fwd_set_test	2023-01-30 13:55:50 -08:00
Christian Mazakas	1c5733ed15	Add node-based foa containers to exception tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	cd44e0ba08	Add node-based foa containers to max_load_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	3363261ad8	Add node-based foa containers to scary_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	58b8b00233	Add node-based foa containers to reserve_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	6474f3c8d3	Add node-based foa containers to transparent_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	63269d2115	Add node-based foa container to scoped_allocator tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	0925a99d98	Add node-based foa containers to swap_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	1b23d08941	Add node-based foa containers to equality_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	28142b6251	Add node-based foa container to at_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	b60f2ce22c	Add rehash tests proving that elements are not relocated for node-based containers	2023-01-30 13:55:50 -08:00
Christian Mazakas	473ed9b88b	Update check used to determine when to move during rehashing to accomodate node-based containers	2023-01-30 13:55:50 -08:00
Christian Mazakas	c554c5b1c9	Add node-based foa containers to rehash_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	e244b35d23	fixup load_factor_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	f7bfb85d84	Add node-based foa containers to load_factor_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	5e0257cb08	Add node-based foa containers to erase_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	64721fa1ef	Clean up insert tests to use more idiomatic UNORDERED_TEST macros	2023-01-30 13:55:50 -08:00
Christian Mazakas	5bfc77c3e4	Add node-based foa containers to emplace_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	aaf0e40247	Update unordered_node_map to be a proper copy of unordered_flat_map	2023-01-30 13:55:50 -08:00
Christian Mazakas	8e86a263fc	Add node-based foa containers to insert_hint_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	a5a5b75dcc	Add node-based foa containers to post_move_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	b57b51b036	Remove moved_value_from() in favor of overloading move() in container type traits	2023-01-30 13:55:50 -08:00
Christian Mazakas	91b3863c77	Add node-based foa containers to erase_if tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	b4a23a875c	fixup copy_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	f0afa5aaef	Add node-based foa containers to equivalent_keys_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	7ce7ef5050	Add moved_value_from() to container policies, enabling proper move semantics for node-based containers in the case of unequal allocators	2023-01-30 13:55:50 -08:00
Christian Mazakas	a3d4a078de	Add node-based foa containers to move_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	1e61423eac	Prove relevance of strong typedef for node-based foa containers	2023-01-30 13:55:50 -08:00
Christian Mazakas	904e806b1e	Update node containers to no longer memcpy their pointer arrays	2023-01-30 13:55:50 -08:00
Christian Mazakas	3201a014c4	Add node-based foa containers to copy_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	1a87580c58	Add node-based foa containers to contains_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	ab58b613c9	Remove multiset from set_tests2_impl call	2023-01-30 13:55:50 -08:00
Christian Mazakas	bb57d91675	Update insert_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	7d1e64a3c6	Update node set to conditionally use strong vs weak typedef	2023-01-30 13:55:50 -08:00
Christian Mazakas	ff956ad080	Update flat_set to eschew strong typedef	2023-01-30 13:55:50 -08:00
Christian Mazakas	d9bf1e435c	Revert perfect forwarding when hashing for transparent ops	2023-01-30 13:55:50 -08:00
Christian Mazakas	eb6d0d1f66	remove print statements	2023-01-30 13:55:50 -08:00
Christian Mazakas	bce898165c	Add transparent insert, show we don't need a strong typedef	2023-01-30 13:55:50 -08:00
Christian Mazakas	e3c66a5e82	Remove print statements	2023-01-30 13:55:50 -08:00
Christian Mazakas	b167ab7d84	Update code to use strong typedefs	2023-01-30 13:55:50 -08:00
Christian Mazakas	71fd0c07ed	Add new failing test case	2023-01-30 13:55:50 -08:00
Christian Mazakas	130b483123	Add node-based foa containers to assign_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	03ee5d135b	Add node-based foa containers to constructor_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	72841102f6	Add node-based foa containers to find_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	cc6748e2b1	Flesh out insert_tests for node-based foa set	2023-01-30 13:55:50 -08:00
Christian Mazakas	f99decc0ca	Add unordered_node_set to the insert_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	ae10a1e0df	Add unordered_node_set	2023-01-30 13:55:50 -08:00
Christian Mazakas	b1e497cd1d	Get test suite passing	2023-01-30 13:55:50 -08:00
Christian Mazakas	cbe19722a3	interim commit	2023-01-30 13:55:50 -08:00
Christian Mazakas	dcff2ac5b5	Pull type policies into detail namespace	2023-01-30 13:55:50 -08:00
Christian Mazakas	cb4e636d78	Implement new type policy requirements for flat containers	2023-01-30 13:55:50 -08:00
Christian Mazakas	6e41418744	Reinstate insert_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	1d8d065113	Update interim prototype to eschew allocator wrapper and instead use extended map_types	2023-01-30 13:55:50 -08:00
Christian Mazakas	a858517c49	Update clang to warn on unused static function templates	2023-01-30 13:55:50 -08:00
Christian Mazakas	2cdcbd24f5	Catch remaining places where value_type was used instead of storage_type	2023-01-30 13:55:50 -08:00
Christian Mazakas	721d8713cd	Extend insert_tests to test unordered_node_map wherever unordered_flat_map is also tested	2023-01-30 13:55:50 -08:00
Christian Mazakas	62e1d3eafb	Remove bad static_assert() from insert_tests	2023-01-30 13:55:50 -08:00
Christian Mazakas	3744bafa55	Update implementation to use storage_type when allocating arrays and constructing/destroying elements	2023-01-30 13:55:50 -08:00
Christian Mazakas	f034e43b74	Get simple prototype of insert_tests working for unordered_node_map	2023-01-30 13:55:50 -08:00