replaced our spinlock with tbb's

avoided old GCC/Clang hiccup with {} for aggregate copy construction
Merge branch 'feature/cfoa' of https://github.com/boostorg/unordered into feature/cfoa
2026-08-04 12:44:27 +02:00 · 2023-06-12 19:27:39 +02:00 · 2023-06-09 21:31:30 +02:00 · 2023-06-09 21:20:36 +02:00 · 2023-06-09 08:55:25 -07:00 · 2023-06-09 08:55:25 -07:00
161 changed files with 17550 additions and 1655 deletions
@@ -6,11 +6,12 @@ local library = "unordered";

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

 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") =
 {
@@ -157,16 +158,29 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

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

    linux_pipeline(
-        "Linux 20.04 GCC 9* 32/64",
+        "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)",
        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32,64' },
+        { 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' },
    ),

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

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

    linux_pipeline(
-        "Linux 20.04 GCC 10 32/64",
+        "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)",
        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-10', CXXSTD: '03,11,14,17,20', ADDRMD: '32,64' },
+        { TOOLSET: 'gcc', COMPILER: 'g++-10', CXXSTD: '03,11,14', ADDRMD: '32,64' },
        "g++-10-multilib",
    ),

    linux_pipeline(
-        "Linux 22.04 GCC 11* 32/64",
+        "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)",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32,64' },
+        { 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' },
    ),

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

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

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

    linux_pipeline(
-        "Linux 22.04 GCC 12 64 ASAN (17,20,2b)",
+        "Linux 22.04 GCC 12 64 ASAN (17)",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17,20,2b', ADDRMD: '64' } + asan,
+        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17', 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",
@@ -330,19 +420,40 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

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

    linux_pipeline(
-        "Linux 22.04 Clang 14 ASAN",
+        "Linux 22.04 Clang 14 UBSAN (17,20)",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14,17,20' } + asan,
+        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '17,20' } + ubsan,
        "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",
@@ -352,8 +463,18 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    macos_pipeline(
-        "MacOS 10.15 Xcode 12.2 UBSAN",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11,14,1z' } + ubsan,
+        "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_pipeline(
@@ -362,6 +483,12 @@ 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,6 +7,8 @@
 set -ex
 export PATH=~/.local/bin:/usr/local/bin:$PATH

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

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

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

@@ -52,7 +51,10 @@ 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-8,     cxxstd: '03,11',          os: ubuntu-20.04, install: 'g++-8-multilib', address-model: '32,64', ccache_key: "cov" }
+              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 }

          # 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' }
@@ -65,17 +67,23 @@ 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: 120
+    timeout-minutes: 180
    runs-on: ${{matrix.os}}
    container: ${{matrix.container}}
    env: {B2_USE_CCACHE: 1}
@@ -184,6 +192,8 @@ 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}}
@@ -197,7 +207,7 @@ jobs:

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

      - name: Upload coverage
        if: matrix.coverage
@@ -22,6 +22,7 @@ target_link_libraries(boost_unordered
    Boost::mp11
    Boost::predef
    Boost::preprocessor
+    Boost::static_assert
    Boost::throw_exception
    Boost::tuple
    Boost::type_traits
@@ -1,4 +1,5 @@
 // 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

@@ -6,6 +7,7 @@
 #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>
@@ -272,6 +274,9 @@ 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>>;

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

@@ -373,6 +381,7 @@ 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
@@ -390,6 +399,7 @@ 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,4 +1,5 @@
 // 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

@@ -6,6 +7,7 @@
 #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>
@@ -273,6 +275,9 @@ 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>>;

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

@@ -374,6 +382,7 @@ 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
@@ -391,6 +400,7 @@ 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,4 +1,5 @@
 // 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

@@ -6,6 +7,7 @@
 #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>
@@ -289,6 +291,9 @@ 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>>;

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

@@ -6,6 +7,7 @@
 #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>
@@ -289,6 +291,9 @@ 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>>;

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

@@ -6,6 +7,7 @@
 #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>
@@ -340,6 +342,9 @@ 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>>;

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

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

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

@@ -328,6 +336,7 @@ 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
@@ -345,6 +354,7 @@ 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,4 +1,5 @@
 // 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

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

@@ -207,6 +212,7 @@ 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,8 +13,10 @@
 include::unordered/intro.adoc[]
 include::unordered/buckets.adoc[]
 include::unordered/hash_equality.adoc[]
-include::unordered/comparison.adoc[]
+include::unordered/regular.adoc[]
+include::unordered/concurrent.adoc[]
 include::unordered/compliance.adoc[]
+include::unordered/structures.adoc[]
 include::unordered/benchmarks.adoc[]
 include::unordered/rationale.adoc[]
 include::unordered/ref.adoc[]
@@ -278,13 +278,14 @@ max load factor 5

 |===

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

 All benchmarks were created using:

 * `https://abseil.io/docs/cpp/guides/container[absl::flat_hash_map^]<uint64_t, uint64_t>`
-* `boost::unordered_flat_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>`

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

@@ -430,3 +431,263 @@ 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

-= The Data Structure
+= Basics of Hash Tables

-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,8 +12,7 @@ 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 `unordered_set` and
-`unordered_multiset` the key is the whole element, but is referred to as the key
+the hash function, `Hash`, to the element's key (for sets 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
@@ -53,8 +52,7 @@ h|*Method* h|*Description*
 |`size_type bucket_count() const` 
 |The number of buckets.

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

 |`size_type max_bucket_count() const` 
@@ -80,7 +78,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.
@@ -90,8 +88,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
@@ -133,8 +131,7 @@ 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 containers only* +
-`boost::unordered_flat_set`, `boost::unordered_flat_map` 
+2+^h| *Open-addressing and concurrent containers only*
 h|*Method* h|*Description*

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

 |===

-A note on `max_load` for open-addressing containers: the maximum load will be 
+A note on `max_load` for open-addressing and concurrent 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
@@ -150,163 +147,4 @@ 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,10 +6,24 @@
 :github-pr-url: https://github.com/boostorg/unordered/pull
 :cpp: C++

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

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

 == Release 1.81.0 - Major update

@@ -5,15 +5,15 @@

 :cpp: C++

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

-The intent of Boost.Unordered is to provide a conformant
+`unordered_[multi]set` and `unordered_[multi]map` are intended 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,27 +117,88 @@ 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: unordered_flat_set, unordered_flat_map
+== Open-addressing Containers

 The C++ standard does not currently provide any open-addressing container
-specification to adhere to, so `boost::unordered_flat_set` and
-`boost::unordered_flat_map` take inspiration from `std::unordered_set` and
+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
 `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, node based).
+radically different from that imposed by the standard (closed addressing).

-`unordered_flat_set` and `unordered_flat_map` only work with reasonably
+Open-addressing containers provided by Boost.Unordered 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. 
-`unordered_flat_set` and `unordered_flat_map` are fully https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^].
+The containers are fully https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^].

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

-* `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.
+* 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.

+== 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`].
+
+//-
@@ -0,0 +1,182 @@
+[#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 Christian Mazakas
+Copyright (C) 2022-2023 Christian Mazakas

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

-Copyright (C) 2022 Peter Dimov
+Copyright (C) 2022-2023 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
-http://www.isthe.com/chongo/tech/comp/fnv/[FNV-1 hash^] you could write:
+https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1a_hash[FNV-1a hash^] you could write:

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

-There is an link:../../examples/fnv1.hpp[implementation of FNV-1^] in the examples directory.
+There is an link:../../examples/fnv1.hpp[implementation of FNV-1a^] 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,26 +4,65 @@
 :idprefix: intro_
 :cpp: C++

-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.
+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.

-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.
+{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.

-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.
+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
+^|
+
+^.^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:

-`unordered_set` and `unordered_multiset` are defined in the header
-`<boost/unordered/unordered_set.hpp>`
 [source,c++]
 ----  
 namespace boost {
@@ -32,117 +71,21 @@ namespace boost {
        class Hash = boost::hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<Key> >
-    class unordered_set;
+    class unordered_set; 
+    // same for unordered_multiset, unordered_flat_set, unordered_node_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;
-
-    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;
+    // same for unordered_multimap, unordered_flat_map, unordered_node_map
+    // and concurrent_flat_map
 }
 ----

-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
+Storing 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,
 floating point types, pointer types, and the standard strings. Since
@@ -152,6 +95,3 @@ 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,9 +4,10 @@

 = Implementation Rationale

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

-These containers adhere to the standard requirements for unordered associative
+`boost::unordered_[multi]set` and `boost::unordered_[multi]map`
+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.
@@ -64,8 +65,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 the golden
-ratio multiplied by `2^w`, `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 `2^w` divided
+by the golden ratio, `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.

@@ -73,7 +74,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.

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

 The C++ standard specification of unordered associative containers impose
 severe limitations on permissible implementations, the most important being
@@ -81,30 +82,33 @@ 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` and `boost::unordered_flat_map` has been
+The design of `boost::unordered_flat_set`/`unordered_node_set` and `boost::unordered_flat_map`/`unordered_node_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 `boost::unordered_flat_set` and `boost::unordered_flat_map`.
+`boost::hash` remains the default hash function of open-addressing containers.
 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:

-*  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.
+{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)^].

 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` 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
+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
 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.
@@ -113,3 +117,25 @@ 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,3 +8,6 @@ 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,8 +1,99 @@
+[#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]
@@ -32,9 +123,9 @@
 |`iterator`, `const_iterator` are of at least the forward category.

 |Iterators, pointers and references to the container's elements are never invalidated.
-|<<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.
+|<<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.

 |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.
@@ -0,0 +1,179 @@
+[#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,6 +280,7 @@ 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);
@@ -859,7 +860,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/EmplaceConstructible[EmplaceConstructible^] into the container from `*first`.
+Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^] into the container.
 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.

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

-Inserts a new node into the container if there is no existing element with key `k` contained within it.
+Inserts a new element 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.

@@ -904,7 +905,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.

 --

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

-Inserts a new node into the container if there is no existing element with key `k` contained within it.
+Inserts a new element 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.

@@ -949,7 +950,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.

 --

@@ -1160,7 +1161,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 <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.
+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.

 ---

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

 [horizontal]
 Returns:;; The number of elements with key equivalent to `k`.
-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.
+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.

 ---

@@ -1186,7 +1187,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 <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.
+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.

 ---

@@ -1202,7 +1203,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 <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.
+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.

 ---

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

 :idprefix: unordered_flat_set_

@@ -234,6 +234,7 @@ 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);
@@ -837,7 +838,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/EmplaceConstructible[EmplaceConstructible^] into the container from `*first`.
+Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^] into the container.
 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.

@@ -971,7 +972,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 <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.
+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.

 ---

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

 [horizontal]
 Returns:;; The number of elements with key equivalent to `k`.
-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.
+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.

 ---

@@ -997,7 +998,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 <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.
+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.

 ---

@@ -1013,7 +1014,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 <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.
+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.

 ---

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

 :idprefix: unordered_map_

@@ -286,6 +286,7 @@ 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);
@@ -995,7 +996,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/EmplaceConstructible[EmplaceConstructible^] into `X` from `*first`.
+Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^] into the container.
 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. +
 +
@@ -1009,11 +1010,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 node into the container if there is no existing element with key `k` contained within it.
+Inserts a new element 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.

@@ -1043,7 +1044,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.

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

-Inserts a new node into the container if there is no existing element with key `k` contained within it.
+Inserts a new element 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.

@@ -1094,7 +1095,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.

@@ -1466,7 +1467,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 <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.
+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.

 ---

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

 [horizontal]
 Returns:;; The number of elements with key equivalent to `k`.
-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.
+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.

 ---

@@ -1492,7 +1493,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 <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.
+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.

 ---

@@ -1508,7 +1509,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 <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.
+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.

 ---

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

 :idprefix: unordered_multimap_

@@ -253,6 +253,7 @@ 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);
@@ -941,7 +942,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/EmplaceConstructible[EmplaceConstructible^] into `X` from `*first`.
+Requires:;; `value_type` is https://en.cppreference.com/w/cpp/named_req/CopyInsertable[CopyInsertable^] into the container.
 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. +
 +
@@ -1223,7 +1224,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 <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.
+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.

 ---

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

 [horizontal]
 Returns:;; The number of elements with key equivalent to `k`.
-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.
+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.

 ---

@@ -1249,7 +1250,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 <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.
+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.

 ---

@@ -1265,7 +1266,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 <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.
+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.

 ---

--- a/Show More
+++ b/Show More