Merge pull request #238 from boostorg/fix/gh-237

Fixed bug in the `const` version of `unordered_multimap::find(k, hash, eq)`

.drone.jsonnet

@@ -102,16 +102,16 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
 [
     linux_pipeline(
         "Linux 14.04 GCC 4.8* 32/64",
-        "cppalliance/droneubuntu1404:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '11', ADDRMD: '32,64' },
+        "cppalliance/droneubuntu1604:1",
+        { TOOLSET: 'gcc', COMPILER: 'g++-4.8', CXXSTD: '11', ADDRMD: '32,64' },
+        "g++-4.8-multilib",
     ),
 
     linux_pipeline(
         "Linux 14.04 GCC 4.9 32/64",
-        "cppalliance/droneubuntu1404:1",
+        "cppalliance/droneubuntu1604:1",
         { TOOLSET: 'gcc', COMPILER: 'g++-4.9', CXXSTD: '11', ADDRMD: '32,64' },
         "g++-4.9-multilib",
-        [ "ppa:ubuntu-toolchain-r/test" ],
     ),
 
     linux_pipeline(
@@ -468,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' },
+        { TOOLSET: 'msvc-14.0', CXXSTD: '14,latest', 'B2_DONT_EMBED_MANIFEST': 1 },
     ),
 
     windows_pipeline(
@@ -477,15 +477,33 @@ 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,4 +20,5 @@ b2 -d0 headers
 
 if not "%CXXSTD%" == "" set CXXSTD=cxxstd=%CXXSTD%
 if not "%ADDRMD%" == "" set ADDRMD=address-model=%ADDRMD%
-b2 --abbreviate-paths -j3 libs/%LIBRARY%/test toolset=%TOOLSET% %CXXSTD% %ADDRMD% variant=debug,release embed-manifest-via=linker
+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

.github/workflows/ci.yml

@@ -95,12 +95,12 @@ jobs:
           - { name: "clang-14 w/ sanitizers (17)", sanitize: yes,
               compiler: clang-14,  cxxstd: '17',    os: 'ubuntu-22.04', ccache_key: "san2" }
           - { name: "clang-14 w/ sanitizers (20)", sanitize: yes,
-              compiler: clang-14,  cxxstd: '20',    os: 'ubuntu-22.04', ccache_key: "san2" }
+              compiler: clang-14,  cxxstd: '20',   container: 'ubuntu:22.04',  os: 'ubuntu-latest', ccache_key: "san2" }
           - { name: "clang-14 w/ sanitizers (2b)", sanitize: yes,
-              compiler: clang-14,  cxxstd: '2b',    os: 'ubuntu-22.04', ccache_key: "san2" }
+              compiler: clang-14,  cxxstd: '2b',   container: 'ubuntu:22.04',  os: 'ubuntu-latest', ccache_key: "san2" }
 
           - { name: "cfoa tsan (clang-14)", cxxstd: '11,14,17,20,2b', os: 'ubuntu-22.04', compiler: clang-14,
-              targets: 'libs/unordered/test//cfoa_tests', thread-sanitize: yes, 
+              targets: 'libs/unordered/test//cfoa_tests', thread-sanitize: yes,
               stdlib: libc++, install: 'clang-14 libc++-14-dev libc++abi-14-dev', ccache_key: "tsan" }
 
           - { compiler: 'clang-15', cxxstd: '11,14',    os: 'ubuntu-22.04', stdlib: libc++, install: 'clang-15 libc++-15-dev libc++abi-15-dev' }
@@ -134,7 +134,7 @@ jobs:
                 apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys E1DD270288B4E6030699E45FA1715D88E1DF1F24
                 for i in {1..${NET_RETRY_COUNT:-3}}; do sudo -E add-apt-repository -y ppa:git-core/ppa && break || sleep 10; done
                 apt-get -o Acquire::Retries=$NET_RETRY_COUNT update
-                apt-get -o Acquire::Retries=$NET_RETRY_COUNT install -y g++ python libpython-dev git
+                apt-get -o Acquire::Retries=$NET_RETRY_COUNT install -y g++ python-is-python3 git
             fi
             # For jobs not compatible with ccache, use "ccache: no" in the matrix
             if [[ "${{ matrix.ccache }}" == "no" ]]; then
@@ -265,6 +265,7 @@ 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

@@ -3,7 +3,7 @@
 # Distributed under the Boost Software License, Version 1.0.
 # https://www.boost.org/LICENSE_1_0.txt
 
-cmake_minimum_required(VERSION 3.5...3.20)
+cmake_minimum_required(VERSION 3.8...3.20)
 
 project(boost_unordered VERSION "${BOOST_SUPERPROJECT_VERSION}" LANGUAGES CXX)
 
@@ -18,16 +18,13 @@ target_link_libraries(boost_unordered
     Boost::config
     Boost::container_hash
     Boost::core
-    Boost::move
     Boost::mp11
     Boost::predef
-    Boost::preprocessor
-    Boost::static_assert
     Boost::throw_exception
-    Boost::tuple
-    Boost::type_traits
 )
 
+target_compile_features(boost_unordered INTERFACE cxx_std_11)
+
 if(BUILD_TESTING AND EXISTS "${CMAKE_CURRENT_SOURCE_DIR}/test/CMakeLists.txt")
 
   add_subdirectory(test)

README.md

@@ -1,49 +1,73 @@
 # Boost.Unordered
 
-Part of collection of the [Boost C++ Libraries](http://github.com/boostorg).
+[![Branch](https://img.shields.io/badge/branch-master-brightgreen.svg)](https://github.com/boostorg/unordered/tree/master) [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=master)](https://github.com/boostorg/unordered/actions/workflows/ci.yml) [![Drone status](https://img.shields.io/drone/build/boostorg/unordered/master?server=https%3A%2F%2Fdrone.cpp.al&logo=drone&logoColor=%23CCCCCC&label=CI)](https://drone.cpp.al/boostorg/unordered) [![Build status](https://img.shields.io/appveyor/build/cppalliance/unordered/master?logo=appveyor&label=CI)](https://ci.appveyor.com/project/cppalliance/unordered/branch/master)  [![codecov](https://codecov.io/gh/boostorg/unordered/branch/master/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/master)  [![Deps](https://img.shields.io/badge/deps-master-brightgreen.svg)](https://pdimov.github.io/boostdep-report/master/unordered.html)  [![Documentation](https://img.shields.io/badge/docs-master-brightgreen.svg)](https://www.boost.org/doc/libs/master/libs/unordered/doc/html/unordered.html)  [![Enter the Matrix](https://img.shields.io/badge/matrix-master-brightgreen.svg)](http://www.boost.org/development/tests/master/developer/unordered.html)<br/>
+[![Branch](https://img.shields.io/badge/branch-develop-brightgreen.svg)](https://github.com/boostorg/unordered/tree/develop) [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=develop)](https://github.com/boostorg/unordered/actions/workflows/ci.yml) [![Drone status](https://img.shields.io/drone/build/boostorg/unordered/develop?server=https%3A%2F%2Fdrone.cpp.al&logo=drone&logoColor=%23CCCCCC&label=CI)](https://drone.cpp.al/boostorg/unordered) [![Build status](https://img.shields.io/appveyor/build/cppalliance/unordered/master?logo=appveyor&label=CI)](https://ci.appveyor.com/project/cppalliance/unordered/branch/develop) [![codecov](https://codecov.io/gh/boostorg/unordered/branch/develop/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/develop) [![Deps](https://img.shields.io/badge/deps-develop-brightgreen.svg)](https://pdimov.github.io/boostdep-report/develop/unordered.html) [![Documentation](https://img.shields.io/badge/docs-develop-brightgreen.svg)](https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered.html) [![Enter the Matrix](https://img.shields.io/badge/matrix-develop-brightgreen.svg)](http://www.boost.org/development/tests/develop/developer/unordered.html)<br/>
+[![BSL 1.0](https://img.shields.io/badge/license-BSL_1.0-blue.svg)](https://www.boost.org/users/license.html) <img alt="C++11 required" src="https://img.shields.io/badge/standard-C%2b%2b11-blue.svg"> <img alt="Header-only library" src="https://img.shields.io/badge/build-header--only-blue.svg">
 
-For accessing data based on key lookup, the C++ 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 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.
+Boost.Unordered offers a catalog of hash containers with different standards compliance levels, performances and intented usage scenarios:
 
-Also, the existing containers require a 'less than' comparison object to order their elements.
-For some data types this is impossible to implement or isn’t practical.
-In contrast, a hash table only needs an equality function and a hash function for the key.
+**`boost::unordered_set` `boost::unordered_map` `boost::unordered_multiset` `boost::unordered_multimap`**
 
-With this in mind, unordered associative containers were added to the C++ standard.
-This is an implementation of the containers described in C++11, with some deviations from the standard in order to work with non-C++11 compilers and libraries.
+<ul>Fully conformant implementations of <code>std::unordered_[multi](set|map)</code>,
+but faster and up to the latest revisions of the standard even if you're working in an older version of C++ (heterogeneous lookup,
+<code>try_emplace</code>, <code>contains</code>, etc.)</ul>
 
+**`boost::unordered_flat_set` `boost::unordered_flat_map`**
 
-### License
+<ul>The fastest of the lot. Based on open addressing, these containers slightly
+deviate from the standard in exchange for top performance.</ul>
 
-Distributed under the [Boost Software License, Version 1.0](http://www.boost.org/LICENSE_1_0.txt).
+**`boost::unordered_node_set` `boost::unordered_node_map`**
 
-### Properties
+<ul>Variations of <code>boost::unordered_flat_(set|map)</code> providing pointer stability.</ul>
 
-* C++03
-* Header-Only
+**`boost::concurrent_flat_set` `boost::concurrent_flat_map`**
 
-### Build Status
+<ul>High performance for multithreaded scenarios. Introducing a new non-standard, iterator-free API.</ul>
 
-Branch          | GH Actions | Appveyor | codecov.io | Deps | Docs | Tests |
-:-------------: | ---------- | -------- | ---------- | ---- | ---- | ----- |
-[`master`](https://github.com/boostorg/unordered/tree/master)   | [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=master)](https://github.com/boostorg/unordered/actions/workflows/ci.yml)  | [![Build status](https://ci.appveyor.com/api/projects/status/github/boostorg/unordered?branch=master&svg=true)](https://ci.appveyor.com/project/danieljames/unordered-qtwe6/branch/master)   | [![codecov](https://codecov.io/gh/boostorg/unordered/branch/master/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/master)   | [![Deps](https://img.shields.io/badge/deps-master-brightgreen.svg)](https://pdimov.github.io/boostdep-report/master/unordered.html)   | [![Documentation](https://img.shields.io/badge/docs-master-brightgreen.svg)](https://www.boost.org/doc/libs/master/libs/unordered/doc/html/unordered.html)   | [![Enter the Matrix](https://img.shields.io/badge/matrix-master-brightgreen.svg)](http://www.boost.org/development/tests/master/developer/unordered.html)
-[`develop`](https://github.com/boostorg/unordered/tree/develop) | [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=develop)](https://github.com/boostorg/unordered/actions/workflows/ci.yml) | [![Build status](https://ci.appveyor.com/api/projects/status/github/boostorg/unordered?branch=develop&svg=true)](https://ci.appveyor.com/project/danieljames/unordered-qtwe6/branch/develop) | [![codecov](https://codecov.io/gh/boostorg/unordered/branch/develop/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/develop) | [![Deps](https://img.shields.io/badge/deps-develop-brightgreen.svg)](https://pdimov.github.io/boostdep-report/develop/unordered.html) | [![Documentation](https://img.shields.io/badge/docs-develop-brightgreen.svg)](https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered.html) | [![Enter the Matrix](https://img.shields.io/badge/matrix-develop-brightgreen.svg)](http://www.boost.org/development/tests/develop/developer/unordered.html)
+## Learn about Boost.Unordered
 
-### Directories
+* [Online documentation](https://boost.org/libs/unordered)
+* [Some benchmarks](https://github.com/boostorg/boost_unordered_benchmarks)
+* Technical articles on Boost.Unordered internal design:
+  * [Advancing the state of the art for `std::unordered_map` implementations](https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html)
+  * [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)
 
-| Name        | Purpose                        |
-| ----------- | ------------------------------ |
-| `doc`       | documentation                  |
-| `example`   | examples                       |
-| `include`   | headers                        |
-| `test`      | unit tests                     |
+## Get the library
 
-### More information
+Boost.Unordered can be installed in a number of ways:
 
-* [Ask questions](http://stackoverflow.com/questions/ask?tags=c%2B%2B,boost,boost-unordered)
-* [Report bugs](https://github.com/boostorg/unordered/issues): Be sure to mention Boost version, platform and compiler you're using. A small compilable code sample to reproduce the problem is always good as well.
-* Submit your patches as pull requests against **develop** branch. Note that by submitting patches you agree to license your modifications under the [Boost Software License, Version 1.0](http://www.boost.org/LICENSE_1_0.txt).
-* Discussions about the library are held on the [Boost developers mailing list](http://www.boost.org/community/groups.html#main). Be sure to read the [discussion policy](http://www.boost.org/community/policy.html) before posting and add the `[unordered]` tag at the beginning of the subject line.
+* [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.83):
+```
+[requires]
+boost/[>=1.83.0]
+```
+<ul>If you're not using any compiled Boost library, the following will skip building altogether:</ul>
 
+```
+[options]
+boost:header_only=True
+```
+* Using vcpkg: Execute the command
+```
+vcpkg install boost-unordered
+```
+* Using CMake: [Boost CMake support infrastructure](https://github.com/boostorg/cmake)
+allows you to use CMake directly to download, build and consume all of Boost or
+some specific libraries.
+
+## Support
+
+* Join the **#boost-unordered** discussion group at [cpplang.slack.com](https://cpplang.slack.com/)
+([ask for an invite](https://cppalliance.org/slack/) if you’re not a member of this workspace yet)
+* Ask in the [Boost Users mailing list](https://lists.boost.org/mailman/listinfo.cgi/boost-users)
+(add the `[unordered]` tag at the beginning of the subject line)
+* [File an issue](https://github.com/boostorg/unordered/issues)
+
+## Contribute
+
+* [Pull requests](https://github.com/boostorg/unordered/pulls) against **develop** branch are most welcome.
+Note that by submitting patches you agree to license your modifications under the [Boost Software License, Version 1.0](http://www.boost.org/LICENSE_1_0.txt).

doc/unordered/benchmarks.adoc

@@ -10,7 +10,7 @@ All benchmarks were created using `unordered_set<unsigned int>` (non-duplicate)
 
 The insertion benchmarks insert `n` random values, where `n` is between 10,000 and 3 million. For the duplicated benchmarks, the same random values are repeated an average of 5 times.
 
-The erasure benchmarks erase all `n` elements randomly until the container is empty.
+The erasure benchmarks erase all `n` elements randomly until the container is empty. Erasure by key uses `erase(const key_type&)` to remove entire groups of equivalent elements in each operation.
 
 The successful lookup benchmarks are done by looking up all `n` values, in their original insertion order.
 
@@ -30,7 +30,7 @@ The unsuccessful lookup benchmarks use `n` randomly generated integers but using
 
 h|non-duplicate elements 
 h|duplicate elements 
-h|duplicate elements +
+h|duplicate elements, +
 max load factor 5
 |===
 
@@ -64,8 +64,18 @@ prior `reserve`
 
 h|non-duplicate elements 
 h|duplicate elements 
-h|duplicate elements +
+h|duplicate elements, +
 max load factor 5
+
+|
+|image::benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique.png[width=250,link=../diagrams/benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique.png,window=_blank]
+|image::benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png[width=250,link=../diagrams/benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png,window=_blank]
+
+|
+h|by key, duplicate elements 
+h|by key, duplicate elements, +
+max load factor 5
+
 |===
 
 ==== Successful Lookup
@@ -154,6 +164,15 @@ h|duplicate elements
 h|duplicate elements, +
 max load factor 5
 
+|
+|image::benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique.png[width=250,link=../diagrams/benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique.png,window=_blank]
+|image::benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png[width=250,link=../diagrams/benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png,window=_blank]
+
+|
+h|by key, duplicate elements 
+h|by key, duplicate elements, +
+max load factor 5
+
 |===
 
 ==== Successful lookup
@@ -242,6 +261,15 @@ h|duplicate elements
 h|duplicate elements, +
 max load factor 5
 
+|
+|image::benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique.png[width=250,link=../diagrams/benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique.png,window=_blank]
+|image::benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png[width=250,link=../diagrams/benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png,window=_blank]
+
+|
+h|by key, duplicate elements 
+h|by key, duplicate elements, +
+max load factor 5
+
 |===
 
 ==== Successful lookup

doc/unordered/changes.adoc

@@ -6,6 +6,13 @@
 :github-pr-url: https://github.com/boostorg/unordered/pull
 :cpp: C++
 
+== Release 1.85.0
+
+* Optimized `emplace()` for a `value_type` or `init_type` (if applicable) argument to bypass creating an intermediate object. The argument is already the same type as the would-be intermediate object.
+* Optimized `emplace()` for `k,v` arguments on map containers to delay constructing the object until it is certain that an element should be inserted. This optimization happens when the map's `key_type` is move constructible or when the `k` argument is a `key_type`.
+* Fixed support for allocators with `explicit` copy constructors ({github-pr-url}/234[PR#234^]).
+* Fixed bug in the `const` version of `unordered_multimap::find(k, hash, eq)` ({github-pr-url}/238[PR#238^]).
+
 == Release 1.84.0 - Major update
 
 * Added `boost::concurrent_flat_set`.
@@ -19,6 +26,9 @@ a concurrent container from user code.
 * Added Boost.Serialization support to all containers and their (non-local) iterator types.
 * Added support for fancy pointers to open-addressing and concurrent containers.
   This enables scenarios like the use of Boost.Interprocess allocators to construct containers in shared memory.
+* Fixed bug in member of pointer operator for local iterators of closed-addressing
+  containers ({github-pr-url}/221[PR#221^], credit goes to GitHub user vslashg for finding
+  and fixing this issue).
 * Starting with this release, `boost::unordered_[multi]set` and `boost::unordered_[multi]map`
   only work with C++11 onwards.
 
@@ -39,7 +49,7 @@ when the returned proxy is not used.
   `boost::unordered_node_map` and `boost::unordered_node_set`.
 * Extended heterogeneous lookup to more member functions as specified in
   https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2363r5.html[P2363].
-* Replaced the previous post-mixing process for open-addressing containers with 
+* 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
@@ -56,20 +66,20 @@ when the returned proxy is not used.
 
 * Refactor internal implementation to be dramatically faster
 * Allow `final` Hasher and KeyEqual objects
-* Update documentation, adding benchmark graphs and notes on the new internal 
+* Update documentation, adding benchmark graphs and notes on the new internal
   data structures
 
 == Release 1.79.0
 
 * Improved {cpp}20 support:
-  ** All containers have been updated to support 
+  ** All containers have been updated to support
     heterogeneous `count`, `equal_range` and `find`.
   ** All containers now implement the member function `contains`.
   ** `erase_if` has been implemented for all containers.
 * Improved {cpp}23 support:
   ** All containers have been updated to support
     heterogeneous `erase` and `extract`.
-* Changed behavior of `reserve` to eagerly 
+* Changed behavior of `reserve` to eagerly
   allocate ({github-pr-url}/59[PR#59^]).
 * Various warning fixes in the test suite.
 * Update code to internally use `boost::allocator_traits`.

doc/unordered/concurrent_flat_map.adoc

@@ -908,7 +908,9 @@ Inserts an object, constructed with the arguments `args`, in the table if and on
 Requires:;; `value_type` is constructible from `args`.
 Returns:;; `true` if an insert took place.
 Concurrency:;; Blocking on rehashing of `*this`.
-Notes:;; Invalidates pointers and references to elements if a rehashing is issued.
+Notes:;; Invalidates pointers and references to elements if a rehashing is issued. +
++
+If `args...` is of the form `k,v`, it delays constructing the whole object until it is certain that an element should be inserted, using only the `k` argument to check.
 
 ---
 

doc/unordered/copyright.adoc

@@ -11,8 +11,10 @@ Copyright (C) 2005-2008 Daniel James
 
 Copyright (C) 2022-2023 Christian Mazakas
 
-Copyright (C) 2022-2023 Joaquín M López Muñoz
+Copyright (C) 2022-2024 Joaquín M López Muñoz
 
 Copyright (C) 2022-2023 Peter Dimov
 
+Copyright (C) 2024 Braden Ganetsky
+
 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)

doc/unordered/hash_traits.adoc

@@ -38,7 +38,7 @@ Users can then declare a hash function `Hash` as avalanching either by embedding
 into the definition of `Hash`, or directly by specializing `hash_is_avalanching<Hash>` to a class with
 an embedded compile-time constant `value` set to `true`.
 
-xref:unordered_flat_set[`boost::unordered_flat_set`] and xref:unordered_flat_map[`boost::unordered_flat_map`]
+Open-addressing and concurrent containers
 use the provided hash function `Hash` as-is if `hash_is_avalanching<Hash>::value` is `true`; otherwise, they
 implement a bit-mixing post-processing stage to increase the quality of hashing at the expense of
 extra computational cost.

doc/unordered/structures.adoc

@@ -152,7 +152,7 @@ performing container-wide operations such as swapping or assignment.
 
 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.
+that has been previously SIMD-matched: only then is the group's spinlock used.
 
 Insertion uses the following _optimistic algorithm_:
 

doc/unordered/unordered_flat_map.adoc

@@ -750,6 +750,8 @@ Returns:;; The `bool` component of the return type is `true` if an insert took p
 If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent key.
 Throws:;; 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. +
++
+If `args...` is of the form `k,v`, it delays constructing the whole object until it is certain that an element should be inserted, using only the `k` argument to check.
 
 ---
 
@@ -769,6 +771,8 @@ Returns:;; The `bool` component of the return type is `true` if an insert took p
 If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent key.
 Throws:;; 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. +
++
+If `args...` is of the form `k,v`, it delays constructing the whole object until it is certain that an element should be inserted, using only the `k` argument to check.
 
 ---
 

doc/unordered/unordered_map.adoc

@@ -797,7 +797,9 @@ If an insert took place, then the iterator points to the newly inserted element.
 Throws:;; 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. +
 +
-Pointers and references to elements are never invalidated.
+Pointers and references to elements are never invalidated. +
++
+If `args...` is of the form `k,v`, it delays constructing the whole object until it is certain that an element should be inserted, using only the `k` argument to check. This optimization happens when the map's `key_type` is move constructible or when the `k` argument is a `key_type`.
 
 ---
 
@@ -818,7 +820,9 @@ Notes:;; The standard is fairly vague on the meaning of the hint. But the only p
 +
 Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor. +
 +
-Pointers and references to elements are never invalidated.
+Pointers and references to elements are never invalidated. +
++
+If `args...` is of the form `k,v`, it delays constructing the whole object until it is certain that an element should be inserted, using only the `k` argument to check. This optimization happens when the map's `key_type` is move constructible or when the `k` argument is a `key_type`.
 
 ---
 

doc/unordered/unordered_node_map.adoc

@@ -767,6 +767,8 @@ Returns:;; The `bool` component of the return type is `true` if an insert took p
 If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent key.
 Throws:;; 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 to be greater than the maximum load. +
++
+If `args...` is of the form `k,v`, it delays constructing the whole object until it is certain that an element should be inserted, using only the `k` argument to check. This optimization happens when `key_type` is move constructible or when the `k` argument is a `key_type`.
 
 ---
 
@@ -786,6 +788,8 @@ Returns:;; The `bool` component of the return type is `true` if an insert took p
 If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent key.
 Throws:;; 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 to be greater than the maximum load. +
++
+If `args...` is of the form `k,v`, it delays constructing the whole object until it is certain that an element should be inserted, using only the `k` argument to check. This optimization happens when `key_type` is move constructible or when the `k` argument is a `key_type`.
 
 ---
 
@@ -1216,6 +1220,12 @@ template<class H2, class P2>
 
 Transfers all the element nodes from `source` whose key is not already present in `*this`.
 
+[horizontal]
+Requires:;; `this\->get_allocator() == source.get_allocator()`.
+Notes:;; Invalidates iterators to the elements transferred.
+If the resulting size of `*this` is greater than its original maximum load,
+invalidates all iterators associated to `*this`.
+
 ---
 
 === Observers

doc/unordered/unordered_node_set.adoc

@@ -1030,6 +1030,12 @@ template<class H2, class P2>
 
 Transfers all the element nodes from `source` whose key is not already present in `*this`.
 
+[horizontal]
+Requires:;; `this\->get_allocator() == source.get_allocator()`.
+Notes:;; Invalidates iterators to the elements transferred.
+If the resulting size of `*this` is greater than its original maximum load,
+invalidates all iterators associated to `*this`.
+
 ---
 
 === Observers

include/boost/unordered/concurrent_flat_map.hpp

@@ -855,8 +855,6 @@ namespace boost {
 #endif
 
   } // namespace unordered
-
-  using unordered::concurrent_flat_map;
 } // namespace boost
 
 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_MAP_HPP

include/boost/unordered/concurrent_flat_map_fwd.hpp

@@ -46,9 +46,6 @@ namespace boost {
   } // namespace unordered
 
   using boost::unordered::concurrent_flat_map;
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost
 
 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_MAP_HPP

include/boost/unordered/concurrent_flat_set.hpp

@@ -711,8 +711,6 @@ namespace boost {
 #endif
 
   } // namespace unordered
-
-  using unordered::concurrent_flat_set;
 } // namespace boost
 
 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_SET_HPP

include/boost/unordered/concurrent_flat_set_fwd.hpp

@@ -47,9 +47,6 @@ namespace boost {
   } // namespace unordered
 
   using boost::unordered::concurrent_flat_set;
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost
 
 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_SET_FWD_HPP

include/boost/unordered/detail/allocator_constructed.hpp

@@ -0,0 +1,59 @@
+/* Copyright 2024 Braden Ganetsky.
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or copy at
+ * http://www.boost.org/LICENSE_1_0.txt)
+ *
+ * See https://www.boost.org/libs/unordered for library home page.
+ */
+
+#ifndef BOOST_UNORDERED_DETAIL_ALLOCATOR_CONSTRUCTED_HPP
+#define BOOST_UNORDERED_DETAIL_ALLOCATOR_CONSTRUCTED_HPP
+
+#include <boost/core/allocator_traits.hpp>
+#include <boost/unordered/detail/opt_storage.hpp>
+
+namespace boost {
+  namespace unordered {
+    namespace detail {
+
+      struct allocator_policy
+      {
+        template <class Allocator, class T, class... Args>
+        static void construct(Allocator& a, T* p, Args&&... args)
+        {
+          boost::allocator_construct(a, p, std::forward<Args>(args)...);
+        }
+
+        template <class Allocator, class T>
+        static void destroy(Allocator& a, T* p)
+        {
+          boost::allocator_destroy(a, p);
+        }
+      };
+
+      /* constructs a stack-based object with the given policy and allocator */
+      template <class Allocator, class T, class Policy = allocator_policy>
+      class allocator_constructed
+      {
+        opt_storage<T> storage;
+        Allocator alloc;
+
+      public:
+        template <class... Args>
+        allocator_constructed(Allocator const& alloc_, Args&&... args)
+            : alloc(alloc_)
+        {
+          Policy::construct(
+            alloc, storage.address(), std::forward<Args>(args)...);
+        }
+
+        ~allocator_constructed() { Policy::destroy(alloc, storage.address()); }
+
+        T& value() { return *storage.address(); }
+      };
+
+    } /* namespace detail */
+  }   /* namespace unordered */
+} /* namespace boost */
+
+#endif

include/boost/unordered/detail/fca.hpp

@@ -1,4 +1,4 @@
-// Copyright (C) 2022-2023 Joaquin M Lopez Munoz.
+// Copyright (C) 2022-2024 Joaquin M Lopez Munoz.
 // Copyright (C) 2022 Christian Mazakas
 //
 // Distributed under the Boost Software License, Version 1.0. (See accompanying
@@ -318,7 +318,10 @@ namespace boost {
 
         reference operator*() const noexcept { return dereference(); }
 
-        pointer operator->() const noexcept { return boost::to_address(p); }
+        pointer operator->() const noexcept
+        {
+          return std::addressof(dereference());
+        }
 
         grouped_local_bucket_iterator& operator++() noexcept
         {
@@ -386,7 +389,10 @@ namespace boost {
 
         reference operator*() const noexcept { return dereference(); }
 
-        pointer operator->() const noexcept { return boost::to_address(p); }
+        pointer operator->() const noexcept
+        {
+          return std::addressof(dereference());
+        }
 
         const_grouped_local_bucket_iterator& operator++() noexcept
         {
@@ -512,7 +518,8 @@ namespace boost {
         }
 
         grouped_bucket_array(size_type n, const Allocator& al)
-            : empty_value<node_allocator_type>(empty_init_t(), al),
+            : empty_value<node_allocator_type>(
+                empty_init_t(), node_allocator_type(al)),
               size_index_(0), size_(0), buckets(), groups()
         {
           if (n == 0) {
@@ -672,12 +679,17 @@ namespace boost {
 
         bucket_allocator_type get_bucket_allocator() const
         {
-          return this->get_node_allocator();
+          return bucket_allocator_type(this->get_node_allocator());
         }
 
         group_allocator_type get_group_allocator() const
         {
-          return this->get_node_allocator();
+          return group_allocator_type(this->get_node_allocator());
+        }
+
+        Allocator get_allocator() const
+        {
+          return Allocator(this->get_node_allocator());
         }
 
         size_type buckets_len() const noexcept { return size_ + 1; }