boostorg/container_hash

Generic hash function for STL style unordered containers

Boost.ContainerHash

The Boost.ContainerHash library, part of Boost C++ Libraries, provides boost::hash, an enhanced implementation of the hash function object specified by C++11 as std::hash, and several support facilities (hash_combine, hash_range, hash_unordered_range).

boost::hash supports most standard types and some user-defined types out of the box, and is extensible; it's possible for a user-defined type X to make iself hashable via boost::hash<X> by defining an appropriate overload of the function hash_value.

See the documentation of the library for more information.

License

Distributed under the Boost Software License, Version 1.0.

container_hash's Issues

Nonexistent Boost config macro BOOST_NO_CXX11_HDR_MEMORY

An automated search for erroneous macro usage picked this up here and in Wave. There is no such macro because <memory> predates C++11, so the test in extensions.hpp is always true.

Plans to release development version

I'm getting this error in Boost 1.80.0 with Clang/Libc++-15

/boost/boost/container_hash/hash.hpp:132:33: error: no template named 'unary_function' in namespace 'std'; did you mean '__unary_function'?
        struct hash_base : std::unary_function<T, std::size_t> {};

It looks like this is already fixed here and has been since 2019, 5048576 and the current version doesn't even have any std::unary_function code, even with a guard. Is there a timeline for the version of container_hash in this repo to merged into the released version of Boost?

Modular Boost C++ Libraries Request

We are in the process of making B2 build changes to all of the B2 build files
to support "modular" consumption of the Boost Libraries by users. See this list
post for some details: https://lists.boost.org/Archives/boost/2024/01/255704.php

The process requires making a variety of changes to make each Boost library
independent of the super-project structure. But the changes do not remove the
super-project structure or the comprehensive Boost release. The changes make
solely make it possible, optionally, for users, like package manages, to easily
consume libraries individually.

Generally the changes include:

• Adding a libroot/build.jam.
• Porting any functionality from libroot/jamfile to libroot/build.jam.
• Moving boost-install declaration from libroot/build/jamfile is applicable.
• Adjusting other B2 build files in the library, like test/jamfile, as needed.
• Possible changes to C++ source files to remove includes relative to the
  super-project boostroot location.

Some examples of such changes:

• boostorg/interval#38
• boostorg/ublas#189
• boostorg/local_function#10
• boostorg/preprocessor#57
• boostorg/callable_traits#194
• boostorg/compatibility#4
• boostorg/hof#228
• boostorg/preprocessor#56

We are asking how you would like us to handle the changes. We would prefer if
you allow the owners of the Boost.org GitHub project to make changes to B2
build files, as needed, to accomplish the changes. But understand
that you may want to manage the proposed changes yourself.

We previously sent emails to all known maintainers to fill out a form with their
preference. We are contacting you in this issue as we have not gotten a response
to that email. You can see the ongoing responses for that form and the responses
to these issues here https://github.com/users/grafikrobot/projects/1/views/6

We are now asking if you can reply directly to this issue to indicate your
preference of handling the changes. Please supply a response to this question
and close the issue (so that we can verify you are a maintainer).

How would you like the build changes to be processed?

1. Pull request, reviewed and merged by a BOOSTORG OWNER.
2. Pull request, reviewed and merged by YOU.
3. Other. (please specify details in the reply)

Also please indicate any special instructions you want us to consider. Or other
information you want us to be aware of.

Thanks you, René

unary_function has been removed from libc++

#22 talks about a similar issue with gcc warning about a deprecated use. Trunk libc++ has removed this function for the 15.0 release in C++17 and newer, so now I am getting an error:

/usr/include/boost/container_hash/hash.hpp:132:33: error: no template named 'unary_function' in namespace 'std'; did you mean '__unary_function'?
        struct hash_base : std::unary_function<T, std::size_t> {};
                           ~~~~~^
/home/david/llvm/build/bin/../include/c++/v1/__functional/unary_function.h:46:1: note: '__unary_function' declared here
using __unary_function = __unary_function_keep_layout_base<_Arg, _Result>;
^

See https://github.com/llvm/llvm-project/blob/main/libcxx/docs/ReleaseNotes.rst

Different hash_combine() output on OSX vs Linux/Windows 64-bit

On macOS, size_t and uint64_t are different types. Thus, different hash_combine_impl() methods get called on 64-bit Linux/Windows vs macOS, which result in different outputs.

#include <boost/container_hash/hash.hpp>
#include <iostream>

int main()
{
    std::size_t x = 0, y = 0;
    boost::hash_combine(x, y);
    std::cout << std::hex << x << "\n";
    // Linux/Windows: e6546b64
    // macOS: 9e3779b9
    return 0;
}

header include cycle problematic for modules

There is a cycle between container_hash/hash.hpp and container_hash/extensions.hpp. This is problematic for modules (both clang and C++ header units). This cycle is made acceptable by removing extensions.hpp's idempotency and have it pre-include hash.hpp if that's not already been included. Then, should hash.hpp include extensions.hpp the later conditional will nullify the (second) tokenization of extensions.hpp's body. This preserves the existing textual-header behaviour of the two files. But, it also makes them buildable as clang-headers, because the cycality remaining in the graph is unproblematic.

An alternative would be to move the body of extensions.hpp to extensions-impl.hpp, and have hash.hpp conditionally include that. Then turn extensions.hpp into a stub that include hash.hpp with BOOST_HASH_NO_EXTENSIONS undefined so it includes extensions-impl. that way extensions-impl.hpp and extensions.hpp can be idempotent (but hash.hpp has to remain not)

+++ boost/container_hash/extensions.hpp
@@ -10,15 +10,22 @@
 // This implements the extensions to the standard.
 // It's undocumented, so you shouldn't use it....
 
+#if !defined(BOOST_FUNCTIONAL_HASH_HASH_HPP)
+// container_hash/hash.hpp and container_hash/extensions.hpp
+// (conditionally) include each other. This causes problems for clang
+// modules (and c++ header units). So, we include
+// container_hash/hash.hpp *outside our header protection* if it's not
+// already included. That in turn might reinclude us, in which case
+// when we get back to here, our header protection will kick in. When
+// building as a module, the cycle is unproblematic.
+#include <boost/container_hash/hash.hpp>
+#endif
+
 #if !defined(BOOST_FUNCTIONAL_HASH_EXTENSIONS_HPP)
 #define BOOST_FUNCTIONAL_HASH_EXTENSIONS_HPP
 
 #include <boost/config.hpp>
-#if defined(BOOST_HAS_PRAGMA_ONCE)
-#pragma once
-#endif
 
-#include <boost/container_hash/hash.hpp>
 #include <boost/detail/container_fwd.hpp>
 #include <boost/core/enable_if.hpp>
 #include <boost/static_assert.hpp>

boost::hash needs c++20 to compile with clang 15 and gcc 10

I have a blob type with begin/end member functions that return const void* and when I try to use that with boost::unordered_map I get a compilation error with gcc 10 and clang 15 unless I compile with -std=c++20 (funny enough it works with gcc 11+ and msvc)

Am I doing something strange or are the ADL changes in c++20 relevant for this case? I attached a small repro as well as the output from compiling with gcc-10 -std=c++17 and clang-15 -std=c++17

Either way it feels like boost shouldn't require c++20 to compile this example where I provide my own hash_value function, right? I'm really confused whether this is a bug in boost or a bug somewhere in gcc/clang or if my code is doing something wrong.

hash_repro.tar.gz

Still not keen on `container_hash`

Making people #include <boost/container_hash/hash.hpp> would be a bit ridiculous if you ask me. :-)

Convention is module has <boost/module.hpp> and <boost/module/things.hpp>.

Please include CMakeLists.txt in next Boost release

There are a couple of libraries referencing the Boost::container_hash CMake target, but CMakeLists.txt is not included in the released Boost 1.71.0 tarball

[MSVC] Boost\libs\container_hash failed to build

Issue description:
Boost\libs\container_hash failed to build due to warning C4996 on MSVC, regress by microsoft/STL#2759. Could you please take a look?

Build step:

1. git clone -c core.autocrlf=true --recursive ​https://github.com/boostorg/boost.git F:\gitP\boostorg\boost
2. open a VS2022 x86 command prompt and browse to F:\gitP\boostorg\boost
3. .\bootstrap
4. .\b2 headers variant=release --build-dir=out\x86rel address-model=32
5. .\b2 variant=release --build-dir=out\x86rel address-model=32
6. .\b2 -j16 variant=release --build-dir=..\out\x86rel libs\container_hash\test

Error info:
hash_complex_test.cpp
libs\container_hash\test\hash_complex_test.cpp(83): error C2220: the following warning is treated as an error
libs\container_hash\test\hash_complex_test.cpp(83): warning C4996: 'std::complex::complex': warning STL4037: The effect of instantiating the template std::complex for any type other than float, double, or long double is unspecified. You can define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING to acknowledge that you have received this warning.
with
[
Integer=int
]
libs\container_hash\test\hash_complex_test.cpp(101): note: see reference to function template instantiation 'void complex_integral_tests(Integer *)' being compiled
with
[
Integer=int
]
libs\container_hash\test\hash_complex_test.cpp(84): warning C4996: 'std::complex::complex': warning STL4037: The effect of instantiating the template std::complex for any type other than float, double, or long double is unspecified. You can define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING to acknowledge that you have received this warning.
with
[
Integer=int
]
libs\container_hash\test\hash_complex_test.cpp(85): warning C4996: 'std::complex::complex': warning STL4037: The effect of instantiating the template std::complex for any type other than float, double, or long double is unspecified. You can define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING to acknowledge that you have received this warning.
with
[
Integer=int
]
libs\container_hash\test\hash_complex_test.cpp(86): warning C4996: 'std::complex::complex': warning STL4037: The effect of instantiating the template std::complex for any type other than float, double, or long double is unspecified. You can define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING to acknowledge that you have received this warning.
with
[
Integer=int
]
libs\container_hash\test\hash_complex_test.cpp(87): warning C4996: 'std::complex::complex': warning STL4037: The effect of instantiating the template std::complex for any type other than float, double, or long double is unspecified. You can define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING to acknowledge that you have received this warning.
with
[
Integer=int
]
libs\container_hash\test\hash_complex_test.cpp(88): warning C4996: 'std::complex::complex': warning STL4037: The effect of instantiating the template std::complex for any type other than float, double, or long double is unspecified. You can define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING to acknowledge that you have received this warning.
with
[
Integer=int
]
libs\container_hash\test\hash_complex_test.cpp(83): warning C4996: 'std::complex::complex': warning STL4037: The effect of instantiating the template std::complex for any type other than float, double, or long double is unspecified. You can define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING to acknowledge that you have received this warning.
with
[
Integer=long
]
libs\container_hash\test\hash_complex_test.cpp(102): note: see reference to function template instantiation 'void complex_integral_tests(Integer *)' being compiled
with
[
Integer=long

boost/container_hash: Breaking change of boost::hash_value in 1.81.0?

In yuzu, we are using boost::hash_value to compute the hash of a macro program (represented by a std::vector<u32>):
https://github.com/yuzu-emu/yuzu/blob/09da9da6fb4428e8f305e967c9102dcf4030c5e9/src/video_core/macro/macro.cpp#L90-L108

These values, in turn, are used to determine the macro programs to emulate at a high level for performance reasons:
https://github.com/yuzu-emu/yuzu/blob/09da9da6fb4428e8f305e967c9102dcf4030c5e9/src/video_core/macro/macro_hle.cpp#L467-L549

Upon updating boost to 1.81.0, we have discovered boost::hash_value produces completely different values to 1.79.0.

As a result, we have 2 questions:
Is the value returned by boost::hash_value meant to be different on 1.81.0 compared to previous releases?
If this is the case, why was this not documented as a potentially breaking change in the changelog?

Missing hash_value overloads for C++11 and later containers

Hello.

In Boost.ContainerHash library there are no hash_value overloads for all containers with PMR allocator. Also overloads for unordered_(multi)set/map are missing.

Do you plan to add it later?

Add hash_value for tuple-like types

One example is boost::json::key_value_pair, which is tuple-like, but does not work out of the box.

hash_combine, hash_range, and hash_value can be constexpr

https://github.com/boostorg/container_hash/blob/develop/include/boost/container_hash/hash.hpp

Since most part of internal calculations are based on integer arithmetic and bitwise operations, I believe those three functions and all their variants can be marked constexpr today. Can someone please enlighten me, why the standard std::hash<T>::operator() and proposed std::hash_combine() in P0814R2 is not constexpr? (backward-compatibility, or other reasons?)

If we are to provide constexpr-ness, there are two cases of implementations:

• When user is using standard later or equal to C++20
  • In this case, non-constexpr intrinsic like _rotl (defined for BOOST_FUNCTIONAL_HASH_ROTL32) can be replaced with std::rotl
• When user is using C++14 to C++17 and one prefers constexpr
  • The library can fallback to bitwise implementation (which is always constexpr)
  • Currently Boost.ContainerHash provides no option for this case. I think new macro like BOOST_FUNCTIONAL_HASH_USE_CONSTEXPR is needed.

refs: cplusplus/papers#253

Internal compiler error with msvc-14.0 in test_uuid.cpp

As reported in boostorg/uuid#138.

Compatibility with std::hash

boost::hash_combine is very useful, however, it does require to implement a hash function twice in order to be used. std::hash and boost::hash_value.

On stackoverflow, several 'workarounds' exist for making this easier, all assume you are able to encapsulate the includes to hash.hpp in your own wrapping header.

Would it be possible to allow hash_combine ... to fall back to std::hash when no hash_value is available?

https://stackoverflow.com/a/51915825/2466431

Unsupported types should be poisoned similarly to the stdlib

Consider https://godbolt.org/z/5W1x94aTh

We see that:

static_assert(std::is_invocable_v<std::hash<rawr>, rawr>);

correctly fails until

template<>
struct std::hash<rawr> {
  std::size_t operator()(rawr const&) const noexcept { return 0; }
};

is defined.

This would enable downstream consumers to write simple is_hashable trait checks.

Warning about conversion to unsigned int from int

GCC 4.6 complains that:

../boost/container_hash/hash.hpp: In function 'std::size_t boost::hash_detail::hash_value_signed(T)':
../boost/container_hash/hash.hpp:273:81: error: conversion to 'unsigned int' from 'int' may change the sign of the result [-Werror=sign-conversion]
../boost/container_hash/hash.hpp: In function 'std::size_t boost::hash_detail::hash_value_unsigned(T)':
../boost/container_hash/hash.hpp:294:81: error: conversion to 'unsigned int' from 'int' may change the sign of the result [-Werror=sign-conversion]

I've taken a look at the develop branch and saw no trace of a hash_value_signed function, so I wonder if the branch was meant to be merged to master before 1.80 (probably too late now).

hash_value for std::nullptr_t is missing

This is needed for

std::size_t boost::json::hash_value( value const& jv ) noexcept
{
    std::size_t seed = 0;

    boost::hash_combine( seed, jv.kind() == kind::int64? kind::uint64: jv.kind() );
    boost::json::visit( [&]( auto const& v ){ boost::hash_combine( seed, v ); }, jv );

    return seed;
}

Cannot compile using Boost 1.77, gcc 11.1.0, and C++ 17

I'm trying to upgrade a project that used to use Boost 1.63 and gcc 6.5 to Boost 1.77 and gcc 11.1.0
I am able to compile using flags for c++ 11 and c++ 14 but not c++ 17

This is the error I get from the container hash library and I'm not sure what's wrong here:

In file included from /home/dev/boost/include/boost/container_hash/hash.hpp:761,
                 from /home/dev/boost/include/boost/functional/hash.hpp:6,
                 from /home/dev/boost/include/boost/unordered/unordered_map.hpp:18,
                 from /home/dev/boost/include/boost/unordered_map.hpp:17,
                 from /home/dev/gcc_stapl/stapl/tools/boost/serialization/unordered_map.hpp:27,
                 from /home/dev/gcc_stapl/stapl/tools/libstdc++/stl_define_types.h:250,
                 from /home/dev/gcc_stapl/stapl/./tools/libstdc++/11.1.0/bits/stl_vector.h:1994,
                 from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /home/dev/boost/include/boost/container_hash/hash.hpp:20,
                 from /home/dev/boost/include/boost/functional/hash.hpp:6,
                 from /home/dev/gcc_stapl/stapl/stapl/utility/hash_fwd.hpp:41,
                 from p_object_registry.cc:29:
/home/dev/boost/include/boost/container_hash/extensions.hpp:300:40: error: expected template-name before ‘<’ token
  300 |         : boost::hash_detail::hash_base<T>
      |                                        ^
/home/dev/boost/include/boost/container_hash/extensions.hpp:300:40: error: expected ‘{’ before ‘<’ token
In file included from /home/dev/boost/include/boost/functional/hash.hpp:6,
                 from /home/dev/gcc_stapl/stapl/stapl/utility/hash_fwd.hpp:41,
                 from p_object_registry.cc:29:
/home/dev/boost/include/boost/container_hash/hash.hpp: In instantiation of ‘void boost::hash_combine(std::size_t&, const T&) [with T = stapl::runtime::full_location; std::size_t = long unsigned int]’:
/home/dev/gcc_stapl/stapl/stapl/runtime/context_id.hpp:159:24:   required from here
/home/dev/boost/include/boost/container_hash/hash.hpp:415:24: error: ‘boost::hash<stapl::runtime::full_location> hasher’ has incomplete type
  415 |         boost::hash<T> hasher;
      |                        ^~~~~~
/home/dev/boost/include/boost/container_hash/hash.hpp: In instantiation of ‘void boost::hash_combine(std::size_t&, const T&) [with T = stapl::runtime::object_virtual_address::address_type; std::size_t = long unsigned int]’:
/home/dev/gcc_stapl/stapl/stapl/runtime/rmi_handle_fwd.hpp:158:24:   required from here
/home/dev/boost/include/boost/container_hash/hash.hpp:415:24: error: ‘boost::hash<stapl::runtime::object_virtual_address::address_type> hasher’ has incomplete type

Regression in boost::hash with version 1.81.0

We are noticing regression with boost::hash when used with std::u16string in boost 1.81.0 version and compared to 1.78.0. As per the 1.81.0 documentation, it seems there are major changes in boost::hash and the performance with string should be improved. Any thoughts on this regression?

Sample program -

#include <boost/functional/hash.hpp>
#include <iostream>
#include <chrono>

int main()
{
    // Start the timer
    auto start = std::chrono::high_resolution_clock::now();

    for(int i = 0; i < 10; i++)
    {
        boost::hash<std::u16string>()(u"hello");
    }

    // End the timer
    auto end = std::chrono::high_resolution_clock::now();

    // Calculate the duration
    std::chrono::duration<double> duration = end - start;

    // Print the duration in seconds
    std::cout << "Execution time: " << (duration.count())/10 << " seconds." << std::endl;

    return 0;
}

Link 1.78.0 - https://godbolt.org/z/ManWPoK8j
Link 1.81.0 - https://godbolt.org/z/hejbsfhc6

`std::unary_function` deprecation warning with GCC 12

Starting in GCC 12, the compiler emits a warning when std::unary_function/std::binary_function is used (they haven't gone as far as removing these for C++ standard versions beyond 14 as mandated). This affects boost::hash as it conditionally uses std::unary_function based on BOOST_NO_CXX98_FUNCTION_BASE, which, correctly, is still undefined for GCC 12.

There are various alternatives to deal with this:

• Stop using std::unary_function altogether (unlikely, it may break C++03 user code).
• Stop using it based on a combination of BOOST_NO_CXX98_FUNCTION_BASE and __cplusplus.
• Wrap in warning-stopping pragma.

Thank you,

Please merge the 'develop' branch change into 'master' for the Boost 1.75 release

The fix in the 'develop' branch is for the Embarcadero C++ clang-based compilers.