included missing header

* re-enabled gc
* optimized mco calculation
* added heuristic to *reduce* mco at insertion time
* fixed signedness bug at update_size_ctrl

.appveyor.yml

@@ -31,168 +31,123 @@ environment:
     B2_VARIANT: debug,release
 
   matrix:
-    - FLAVOR: VS2015 (32 bit)
+    - FLAVOR: Visual Studio 2015
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2015
       B2_TOOLSET: msvc-14.0
-      B2_ADDRESS_MODEL: 32
 
-    - FLAVOR: VS2015 (64 bit)
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2015
-      B2_TOOLSET: msvc-14.0
-      B2_ADDRESS_MODEL: 64
-
-    - FLAVOR: VS2017 (32 bit, C++14, Debug)
+    - FLAVOR: Visual Studio 2017, C++14
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
       B2_CXXSTD: 14
       B2_TOOLSET: msvc-14.1
-      B2_ADDRESS_MODEL: 32
-      B2_VARIANT: debug
 
-    - FLAVOR: VS2017 (32 bit, C++17, Release)
+    - FLAVOR: Visual Studio 2017, C++17
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
       B2_CXXSTD: 17
       B2_TOOLSET: msvc-14.1
-      B2_ADDRESS_MODEL: 32
-      B2_VARIANT: release
 
-    - FLAVOR: VS2017 (32 bit, C++latest, Debug)
+    - FLAVOR: Visual Studio 2017, C++latest
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
       B2_CXXSTD: latest
       B2_TOOLSET: msvc-14.1
-      B2_ADDRESS_MODEL: 32
-      B2_VARIANT: debug
 
-    - FLAVOR: VS2017 (64 bit, C++14, Release)
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
-      B2_CXXSTD: 14
-      B2_TOOLSET: msvc-14.1
-      B2_ADDRESS_MODEL: 64
-      B2_VARIANT: release
-
-    - FLAVOR: VS2017 (64 bit, C++17, Debug)
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
-      B2_CXXSTD: 17
-      B2_TOOLSET: msvc-14.1
-      B2_ADDRESS_MODEL: 64
-      B2_VARIANT: debug
-
-    - FLAVOR: VS2017 (64 bit, C++latest, Release)
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
-      B2_CXXSTD: latest
-      B2_TOOLSET: msvc-14.1
-      B2_ADDRESS_MODEL: 64
-      B2_VARIANT: release
-
-    - FLAVOR: Cygwin (32 bit, C++11, Release)
+    - FLAVOR: cygwin (32-bit, C++11)
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
       ADDPATH: C:\cygwin\bin;
       B2_ADDRESS_MODEL: 32
       B2_CXXSTD: 11
       B2_TOOLSET: gcc
-      B2_VARIANT: release
 
-    - FLAVOR: Cygwin (32 bit, C++14, Debug)
+    - FLAVOR: cygwin (32-bit, C++14)
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
       ADDPATH: C:\cygwin\bin;
       B2_ADDRESS_MODEL: 32
       B2_CXXSTD: 14
       B2_TOOLSET: gcc
-      B2_VARIANT: debug
 
-    - FLAVOR: Cygwin (32 bit, C++1z, Release)
+    - FLAVOR: cygwin (32-bit, C++1z)
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
       ADDPATH: C:\cygwin\bin;
       B2_ADDRESS_MODEL: 32
       B2_CXXSTD: 1z
       B2_TOOLSET: gcc
+
+    - FLAVOR: cygwin (64-bit, latest, C++11)
+      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
+      ADDPATH: C:\cygwin64\bin;
+      B2_ADDRESS_MODEL: 64
+      B2_CXXSTD: 11
+      B2_TOOLSET: gcc
+      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
       B2_VARIANT: release
 
-    - FLAVOR: Cygwin (64 bit, C++11, Debug)
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
-      ADDPATH: C:\cygwin64\bin;
-      B2_ADDRESS_MODEL: 64
-      B2_CXXSTD: 11
-      B2_TOOLSET: gcc
-      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
-      B2_VARIANT: debug
-
-    - FLAVOR: Cygwin (64 bit, C++14, Debug)
+    - FLAVOR: cygwin (64-bit, latest, C++14)
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
       ADDPATH: C:\cygwin64\bin;
       B2_ADDRESS_MODEL: 64
       B2_CXXSTD: 14
       B2_TOOLSET: gcc
       B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
-      B2_VARIANT: debug
+      B2_VARIANT: release
 
-    - FLAVOR: Cygwin (64 bit, C++17, Debug)
+    - FLAVOR: cygwin (64-bit, latest, C++1z)
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
       ADDPATH: C:\cygwin64\bin;
       B2_ADDRESS_MODEL: 64
-      B2_CXXSTD: 17
+      B2_CXXSTD: 1z
       B2_TOOLSET: gcc
       B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
-      B2_VARIANT: debug
+      B2_VARIANT: release
 
-    - FLAVOR: Cygwin (64 bit, C++2a, Debug)
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
-      ADDPATH: C:\cygwin64\bin;
-      B2_ADDRESS_MODEL: 64
-      B2_CXXSTD: 2a
-      B2_TOOLSET: gcc
-      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
-      B2_VARIANT: debug
-
-    - FLAVOR: MinGW-w64 (32 bit, C++11)
+    - FLAVOR: mingw-w64, 32 bit, C++11
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
       ADDPATH: C:\mingw-w64\i686-8.1.0-posix-dwarf-rt_v6-rev0\mingw32\bin;
       B2_CXXSTD: 11
       B2_TOOLSET: gcc
       B2_ADDRESS_MODEL: 32
 
-    - FLAVOR: MinGW-w64 (32 bit, C++14)
+    - FLAVOR: mingw-w64, 32 bit, C++14
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
       ADDPATH: C:\mingw-w64\i686-8.1.0-posix-dwarf-rt_v6-rev0\mingw32\bin;
       B2_CXXSTD: 14
       B2_TOOLSET: gcc
       B2_ADDRESS_MODEL: 32
 
-    - FLAVOR: MinGW-w64 (32 bit, C++17)
+    - FLAVOR: mingw-w64, 32 bit, C++17
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
       ADDPATH: C:\mingw-w64\i686-8.1.0-posix-dwarf-rt_v6-rev0\mingw32\bin;
       B2_CXXSTD: 17
       B2_TOOLSET: gcc
       B2_ADDRESS_MODEL: 32
 
-    - FLAVOR: MinGW-w64 (32 bit, C++2a)
+    - FLAVOR: mingw-w64, 32 bit, C++2a
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
       ADDPATH: C:\mingw-w64\i686-8.1.0-posix-dwarf-rt_v6-rev0\mingw32\bin;
       B2_CXXSTD: 2a
       B2_TOOLSET: gcc
       B2_ADDRESS_MODEL: 32
 
-    - FLAVOR: MinGW-w64 (64 bit, C++11)
+    - FLAVOR: mingw-w64, 64 bit, C++11
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
       ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
       B2_CXXSTD: 11
       B2_TOOLSET: gcc
       B2_ADDRESS_MODEL: 64
 
-    - FLAVOR: MinGW-w64 (64 bit, C++14)
+    - FLAVOR: mingw-w64, 64 bit, C++14
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
       ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
       B2_CXXSTD: 14
       B2_TOOLSET: gcc
       B2_ADDRESS_MODEL: 64
 
-    - FLAVOR: MinGW-w64 (64 bit, C++17)
+    - FLAVOR: mingw-w64, 64 bit, C++17
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
       ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
       B2_CXXSTD: 17
       B2_TOOLSET: gcc
       B2_ADDRESS_MODEL: 64
 
-    - FLAVOR: MinGW-w64 (64 bit, C++2a)
+    - FLAVOR: mingw-w64, 64 bit, C++2a
       APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
       ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
       B2_CXXSTD: 2a

.drone.jsonnet

@@ -30,7 +30,6 @@ local linux_pipeline(name, image, environment, packages = "", sources = [], arch
             name: "everything",
             image: image,
             environment: environment,
-            privileged: true,
             commands:
             [
                 'set -e',
@@ -103,16 +102,16 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
 [
     linux_pipeline(
         "Linux 14.04 GCC 4.8* 32/64",
-        "cppalliance/droneubuntu1604:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-4.8', CXXSTD: '11', ADDRMD: '32,64' },
-        "g++-4.8-multilib",
+        "cppalliance/droneubuntu1404:1",
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '11', ADDRMD: '32,64' },
     ),
 
     linux_pipeline(
         "Linux 14.04 GCC 4.9 32/64",
-        "cppalliance/droneubuntu1604:1",
+        "cppalliance/droneubuntu1404:1",
         { TOOLSET: 'gcc', COMPILER: 'g++-4.9', CXXSTD: '11', ADDRMD: '32,64' },
         "g++-4.9-multilib",
+        [ "ppa:ubuntu-toolchain-r/test" ],
     ),
 
     linux_pipeline(
@@ -469,7 +468,7 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
     windows_pipeline(
         "Windows VS2015 msvc-14.0",
         "cppalliance/dronevs2015",
-        { TOOLSET: 'msvc-14.0', CXXSTD: '14,latest', 'B2_DONT_EMBED_MANIFEST': 1 },
+        { TOOLSET: 'msvc-14.0', CXXSTD: '14,latest' },
     ),
 
     windows_pipeline(
@@ -478,33 +477,15 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
         { TOOLSET: 'msvc-14.1', CXXSTD: '14,17,latest' },
     ),
 
-    windows_pipeline(
-        "Windows VS2017 msvc-14.1 permissive-",
-        "cppalliance/dronevs2017",
-        { TOOLSET: 'msvc-14.1', CXXSTD: '14,17', CXXFLAGS: '/permissive-' },
-    ),
-
     windows_pipeline(
         "Windows VS2019 msvc-14.2",
         "cppalliance/dronevs2019",
         { TOOLSET: 'msvc-14.2', CXXSTD: '14,17,20,latest' },
     ),
 
-    windows_pipeline(
-        "Windows VS2019 msvc-14.2 permissive-",
-        "cppalliance/dronevs2019",
-        { TOOLSET: 'msvc-14.2', CXXSTD: '14,17', CXXFLAGS: '/permissive-' },
-    ),
-
     windows_pipeline(
         "Windows VS2022 msvc-14.3",
         "cppalliance/dronevs2022:1",
         { TOOLSET: 'msvc-14.3', CXXSTD: '14,17,20,latest' },
     ),
-
-    windows_pipeline(
-        "Windows VS2022 msvc-14.3 permissive-",
-        "cppalliance/dronevs2022:1",
-        { TOOLSET: 'msvc-14.3', CXXSTD: '14,17', CXXFLAGS: '/permissive-' },
-    ),
 ]

.drone/drone.bat

@@ -20,5 +20,4 @@ b2 -d0 headers
 
 if not "%CXXSTD%" == "" set CXXSTD=cxxstd=%CXXSTD%
 if not "%ADDRMD%" == "" set ADDRMD=address-model=%ADDRMD%
-if not "%CXXFLAGS%" == "" set CXXFLAGS=cxxflags=%CXXFLAGS%
-b2 --abbreviate-paths -j3 libs/%LIBRARY%/test toolset=%TOOLSET% %CXXSTD% %ADDRMD% %CXXFLAGS% variant=debug,release embed-manifest-via=linker
+b2 --abbreviate-paths -j3 libs/%LIBRARY%/test toolset=%TOOLSET% %CXXSTD% %ADDRMD% variant=debug,release embed-manifest-via=linker

.drone/drone.sh

@@ -14,11 +14,6 @@ DRONE_BUILD_DIR=$(pwd)
 BOOST_BRANCH=develop
 if [ "$DRONE_BRANCH" = "master" ]; then BOOST_BRANCH=master; fi
 
-if [[ $(uname) == "Linux" && ( "$TSAN" == 1 || "$ASAN" == 1 ) ]]; then
-    echo 0 | sudo tee /proc/sys/kernel/randomize_va_space
-    sudo sysctl vm.mmap_rnd_bits=28
-fi
-
 cd ..
 git clone -b $BOOST_BRANCH --depth 1 https://github.com/boostorg/boost.git boost-root
 cd boost-root

.github/workflows/ci.yml

@@ -107,10 +107,10 @@ jobs:
           - { compiler: 'clang-15', cxxstd: '17,20,2b', os: 'ubuntu-22.04', stdlib: libc++, install: 'clang-15 libc++-15-dev libc++abi-15-dev' }
 
           # OSX, clang
+          - { compiler: clang, cxxstd: '11,14,17,2a',    os: 'macos-11' }
           - { compiler: clang, cxxstd: '11,14,17,2a',    os: 'macos-12', sanitize: yes, ccache_key: "san1" }
           - { compiler: clang, cxxstd: '11,14,17,2a',    os: 'macos-12', thread-sanitize: yes, targets: 'libs/unordered/test//cfoa_tests', ccache_key: "tsan" }
           - { compiler: clang, cxxstd: '11,14,17,20,2b', os: 'macos-13' }
-          - { compiler: clang, cxxstd: '11,14,17,20,2b', os: 'macos-14' }
 
     timeout-minutes: 360
     # posix (gcc-12 w/ sanitizers is taking longer than 210 minutes
@@ -244,8 +244,6 @@ jobs:
       - name: Upload coverage
         if: matrix.coverage
         run: ci/codecov.sh "upload"
-        env:
-          CODECOV_TOKEN: ${{ secrets.CODECOV_TOKEN }}
 
       - name: Run coverity
         if: matrix.coverity && github.event_name == 'push' && (github.ref_name == 'develop' || github.ref_name == 'master')
@@ -267,7 +265,6 @@ jobs:
           - { toolset: msvc-14.3, cxxstd: '14,17,20,latest', addrmd: '32,64', os: 'windows-2022', variant: 'debug,release' }
           - { toolset: msvc-14.3, cxxstd: '14',              addrmd: '64',    os: 'windows-2022', variant: 'debug', defines: '_ALLOW_RTCc_IN_STL', cxxflags: '/RTCc'              }
           - { toolset: msvc-14.3, cxxstd: '14',              addrmd: '32',    os: 'windows-2022', variant: 'debug', defines: '_ALLOW_RTCc_IN_STL', cxxflags: '"/RTCc /arch:IA32"' }
-          - { toolset: msvc-14.3, cxxstd: '14,17',           addrmd: '32,64', os: 'windows-2022', variant: 'debug,release', cxxflags: '/permissive-' }
           - { toolset: clang-win, cxxstd: '14,17,latest',    addrmd: '32,64', os: 'windows-2022', variant: 'debug,release' }
           - { toolset: gcc,       cxxstd: '11,14,17,2a',     addrmd: '64',    os: 'windows-2019', variant: 'debug,release' }
 

CMakeLists.txt

@@ -23,15 +23,6 @@ target_link_libraries(boost_unordered
     Boost::throw_exception
 )
 
-if(CMAKE_VERSION VERSION_GREATER 3.18 AND CMAKE_GENERATOR MATCHES "Visual Studio")
-
-  file(GLOB_RECURSE boost_unordered_IDEFILES CONFIGURE_DEPENDS include/*.hpp)
-  source_group(TREE ${PROJECT_SOURCE_DIR}/include FILES ${boost_unordered_IDEFILES} PREFIX "Header Files")
-  list(APPEND boost_unordered_IDEFILES extra/boost_unordered.natvis)
-  target_sources(boost_unordered PRIVATE ${boost_unordered_IDEFILES})
-
-endif()
-
 target_compile_features(boost_unordered INTERFACE cxx_std_11)
 
 if(BUILD_TESTING AND EXISTS "${CMAKE_CURRENT_SOURCE_DIR}/test/CMakeLists.txt")

README.md

@@ -25,10 +25,6 @@ deviate from the standard in exchange for top performance.</ul>
 
 <ul>High performance for multithreaded scenarios. Introducing a new non-standard, iterator-free API.</ul>
 
-**`boost::concurrent_node_set` `boost::concurrent_node_map`**
-
-<ul>Variations of <code>boost::concurrent_flat_(set|map)</code> providing pointer stability.</ul>
-
 ## Learn about Boost.Unordered
 
 * [Online documentation](https://boost.org/libs/unordered)
@@ -38,18 +34,16 @@ deviate from the standard in exchange for top performance.</ul>
   * [Inside `boost::unordered_flat_map`](https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html)
   * [Inside `boost::concurrent_flat_map`](https://bannalia.blogspot.com/2023/07/inside-boostconcurrentflatmap.html)
   * [Bulk visitation in `boost::concurrent_flat_map`](https://bannalia.blogspot.com/2023/10/bulk-visitation-in-boostconcurrentflatm.html)
-* Debugging visualizers for Boost.Unordered:
-  * [Natvis for boost::unordered_map, and how to use &lt;Intrinsic&gt; elements](https://blog.ganets.ky/NatvisForUnordered/)
-  * [Natvis for boost::concurrent_flat_map, and why fancy pointers are hard](https://blog.ganets.ky/NatvisForUnordered2/)
-  * [Visualizing boost::unordered_map in GDB, with pretty-printer customization points](https://blog.ganets.ky/PrettyPrinter/)
+
+## Get the library
 
 Boost.Unordered can be installed in a number of ways:
 
 * [Download Boost](https://www.boost.org/users/download/) and you're ready to go (this is a header-only library requiring no building).
-* Using Conan 2: In case you don't have it yet, add an entry for Boost in your `conanfile.txt` (the example requires at least Boost 1.86):
+* Using Conan 2: In case you don't have it yet, add an entry for Boost in your `conanfile.txt` (the example requires at least Boost 1.83):
 ```
 [requires]
-boost/[>=1.86.0]
+boost/[>=1.83.0]
 ```
 <ul>If you're not using any compiled Boost library, the following will skip building altogether:</ul>
 

benchmark/string.cpp

@@ -1,5 +1,5 @@
 // Copyright 2021 Peter Dimov.
-// Copyright 2023-2024 Joaquin M Lopez Munoz.
+// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt
 
@@ -25,7 +25,6 @@
 #include <iostream>
 #include <iomanip>
 #include <chrono>
-#include <type_traits>
 
 using namespace std::chrono_literals;
 
@@ -342,7 +341,7 @@ template<> struct fnv1a_hash_impl<64>
 
 struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
 {
-    using is_avalanching = std::true_type;
+    using is_avalanching = void;
 };
 
 template<class K, class V> using std_unordered_map_fnv1a =

benchmark/string_stats.cpp

@@ -1,343 +0,0 @@
-// Copyright 2021 Peter Dimov.
-// Copyright 2023-2024 Joaquin M Lopez Munoz.
-// Distributed under the Boost Software License, Version 1.0.
-// https://www.boost.org/LICENSE_1_0.txt
-
-#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
-#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
-
-#define BOOST_UNORDERED_ENABLE_STATS
-
-#include <boost/unordered/unordered_flat_map.hpp>
-#include <boost/core/detail/splitmix64.hpp>
-#include <boost/config.hpp>
-#include <unordered_map>
-#include <vector>
-#include <memory>
-#include <cstdint>
-#include <iostream>
-#include <iomanip>
-#include <chrono>
-#include <type_traits>
-
-using namespace std::chrono_literals;
-
-static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::uint32_t s, std::size_t size )
-{
-    auto t2 = std::chrono::steady_clock::now();
-
-    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
-
-    t1 = t2;
-}
-
-constexpr unsigned N = 50'000;
-constexpr int K = 10;
-
-static std::vector<std::string> indices1, indices2;
-
-static std::string make_index( unsigned x )
-{
-    char buffer[ 64 ];
-    std::snprintf( buffer, sizeof(buffer), "pfx_%u_sfx", x );
-
-    return buffer;
-}
-
-static std::string make_random_index( unsigned x )
-{
-    char buffer[ 64 ];
-    std::snprintf( buffer, sizeof(buffer), "pfx_%0*d_%u_sfx", x % 8 + 1, 0, x );
-
-    return buffer;
-}
-
-static void init_indices()
-{
-    indices1.reserve( N*2+1 );
-    indices1.push_back( make_index( 0 ) );
-
-    for( unsigned i = 1; i <= N*2; ++i )
-    {
-        indices1.push_back( make_index( i ) );
-    }
-
-    indices2.reserve( N*2+1 );
-    indices2.push_back( make_index( 0 ) );
-
-    {
-        boost::detail::splitmix64 rng;
-
-        for( unsigned i = 1; i <= N*2; ++i )
-        {
-            indices2.push_back( make_random_index( static_cast<std::uint32_t>( rng() ) ) );
-        }
-    }
-}
-
-template<class Map> BOOST_NOINLINE void test_insert( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    for( unsigned i = 1; i <= N; ++i )
-    {
-        map.insert( { indices1[ i ], i } );
-    }
-
-    print_time( t1, "Consecutive insert",  0, map.size() );
-
-    for( unsigned i = 1; i <= N; ++i )
-    {
-        map.insert( { indices2[ i ], i } );
-    }
-
-    print_time( t1, "Random insert",  0, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_lookup( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    std::uint32_t s;
-    
-    s = 0;
-
-    for( int j = 0; j < K; ++j )
-    {
-        for( unsigned i = 1; i <= N * 2; ++i )
-        {
-            auto it = map.find( indices1[ i ] );
-            if( it != map.end() ) s += it->second;
-        }
-    }
-
-    print_time( t1, "Consecutive lookup",  s, map.size() );
-
-    s = 0;
-
-    for( int j = 0; j < K; ++j )
-    {
-        for( unsigned i = 1; i <= N * 2; ++i )
-        {
-            auto it = map.find( indices2[ i ] );
-            if( it != map.end() ) s += it->second;
-        }
-    }
-
-    print_time( t1, "Random lookup",  s, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    auto it = map.begin();
-
-    while( it != map.end() )
-    {
-        if( it->second & 1 )
-        {
-            if constexpr( std::is_void_v< decltype( map.erase( it ) ) > )
-            {
-                map.erase( it++ );
-            }
-            else
-            {
-                it = map.erase( it );
-            }
-        }
-        else
-        {
-            ++it;
-        }
-    }
-
-    print_time( t1, "Iterate and erase odd elements",  0, map.size() );
-
-    std::cout << std::endl;
-}
-
-template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::steady_clock::time_point & t1 )
-{
-    for( unsigned i = 1; i <= N; ++i )
-    {
-        map.erase( indices1[ i ] );
-    }
-
-    print_time( t1, "Consecutive erase",  0, map.size() );
-
-    for( unsigned i = 1; i <= N; ++i )
-    {
-        map.erase( indices2[ i ] );
-    }
-
-    print_time( t1, "Random erase",  0, map.size() );
-
-    std::cout << std::endl;
-}
-
-//
-
-// All Unordered container use the same struct
-using stats = boost::unordered_flat_map<int, int>::stats; 
-
-struct record
-{
-    std::string label_;
-    long long time_;
-    stats stats_;
-};
-
-static std::vector<record> records;
-
-template<template<class...> class Map> BOOST_NOINLINE void test( char const* label )
-{
-    std::cout << label << ":\n\n";
-
-    Map<std::string, std::uint32_t> map;
-
-    auto t0 = std::chrono::steady_clock::now();
-    auto t1 = t0;
-
-    test_insert( map, t1 );
-
-    record rec = { label, 0 };
-
-    test_lookup( map, t1 );
-    test_iteration( map, t1 );
-    test_lookup( map, t1 );
-    test_erase( map, t1 );
-
-    auto tN = std::chrono::steady_clock::now();
-    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
-
-    rec.time_ = ( tN - t0 ) / 1ms;
-    rec.stats_ = map.get_stats();
-    records.push_back( rec );
-}
-
-//
-
-template<class K, class V> using boost_unordered_flat_map =
-    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>>;
-
-// fnv1a_hash
-
-template<int Bits> struct fnv1a_hash_impl;
-
-template<> struct fnv1a_hash_impl<32>
-{
-    std::size_t operator()( std::string const& s ) const
-    {
-        std::size_t h = 0x811C9DC5u;
-
-        char const * first = s.data();
-        char const * last = first + s.size();
-
-        for( ; first != last; ++first )
-        {
-            h ^= static_cast<unsigned char>( *first );
-            h *= 0x01000193ul;
-        }
-
-        return h;
-    }
-};
-
-template<> struct fnv1a_hash_impl<64>
-{
-    std::size_t operator()( std::string const& s ) const
-    {
-        std::size_t h = 0xCBF29CE484222325ull;
-
-        char const * first = s.data();
-        char const * last = first + s.size();
-
-        for( ; first != last; ++first )
-        {
-            h ^= static_cast<unsigned char>( *first );
-            h *= 0x00000100000001B3ull;
-        }
-
-        return h;
-    }
-};
-
-struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
-{
-    using is_avalanching = std::true_type;
-};
-
-template<class K, class V> using boost_unordered_flat_map_fnv1a =
-    boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>>;
-
-// slightly bad hash
-
-struct slightly_bad_hash
-{
-    using is_avalanching = std::true_type;
-
-    std::size_t operator()( std::string const& s ) const
-    {
-       std::size_t h = s.size();
-
-       for( auto ch: s )
-       {
-         h *= 0x811C9DC4u; // multiplicative factor is even!
-         h += static_cast<std::size_t>( ch );
-       }
-
-       return h;
-    }
-};
-
-template<class K, class V> using boost_unordered_flat_map_slightly_bad_hash =
-    boost::unordered_flat_map<K, V, slightly_bad_hash, std::equal_to<K>>;
-
-// bad hash
-
-struct bad_hash
-{
-    using is_avalanching = std::true_type;
-
-    std::size_t operator()( std::string const& s ) const
-    {
-       std::size_t h = s.size();
-
-       for( auto ch: s )
-       {
-         h *= 31;
-         h += static_cast<std::size_t>( ch );
-       }
-
-       return h;
-    }
-};
-
-template<class K, class V> using boost_unordered_flat_map_bad_hash =
-    boost::unordered_flat_map<K, V, bad_hash, std::equal_to<K>>;
-
-//
-
-int main()
-{
-    init_indices();
-
-    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
-    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
-    test<boost_unordered_flat_map_slightly_bad_hash>( "boost::unordered_flat_map, slightly_bad_hash" );
-    test<boost_unordered_flat_map_bad_hash>( "boost::unordered_flat_map, bad_hash" );
-
-    std::cout << "---\n\n";
-
-    for( auto const& x: records )
-    {
-        std::cout << std::setw( 46 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms\n"
-                  << std::setw( 46 ) << "insertion: "
-                      << "probe length " << x.stats_.insertion.probe_length.average << "\n"
-                  << std::setw( 46 ) << "successful lookup: "
-                      << "probe length " << x.stats_.successful_lookup.probe_length.average 
-                      << ", num comparisons " << x.stats_.successful_lookup.num_comparisons.average << "\n"
-                  << std::setw( 46 ) << "unsuccessful lookup: "
-                      << "probe length " << x.stats_.unsuccessful_lookup.probe_length.average 
-                      << ", num comparisons " << x.stats_.unsuccessful_lookup.num_comparisons.average << "\n\n";
-    }
-}

benchmark/string_view.cpp

@@ -1,5 +1,5 @@
 // Copyright 2021 Peter Dimov.
-// Copyright 2023-2024 Joaquin M Lopez Munoz.
+// Copyright 2023 Joaquin M Lopez Munoz.
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt
 
@@ -26,7 +26,6 @@
 #include <iostream>
 #include <iomanip>
 #include <chrono>
-#include <type_traits>
 
 using namespace std::chrono_literals;
 
@@ -343,7 +342,7 @@ template<> struct fnv1a_hash_impl<64>
 
 struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
 {
-    using is_avalanching = std::true_type;
+    using is_avalanching = void;
 };
 
 template<class K, class V> using std_unordered_map_fnv1a =

build.jam

@@ -1,26 +0,0 @@
-# Copyright 2023-2024 René Ferdinand Rivera Morell
-# Copyright 2024 Peter Dimov
-# Distributed under the Boost Software License, Version 1.0.
-# https://www.boost.org/LICENSE_1_0.txt
-
-require-b2 5.2 ;
-
-constant boost_dependencies :
-    /boost/assert//boost_assert
-    /boost/config//boost_config
-    /boost/container_hash//boost_container_hash
-    /boost/core//boost_core
-    /boost/mp11//boost_mp11
-    /boost/predef//boost_predef
-    /boost/throw_exception//boost_throw_exception
-    ;
-
-project /boost/unordered ;
-
-explicit
-    [ alias boost_unordered : : : : <include>include <library>$(boost_dependencies) ]
-    [ alias all : boost_unordered test ]
-    ;
-
-call-if : boost-library unordered
-    ;