There may be to many individual test binaries which slow down the build/CI. See e.g. https://github.com/boostorg/unordered/runs/6779803837?check_suite_focus=true

For b2 -j3 libs/%LIBRARY%/test toolset=msvc-14.3 cxxstd=14,17,20,latest address-model=32,64 variant=debug,release embed-manifest-via=linker it already yields (at least) 422=16 variants of each test.

In the test Jamfile we have 54 run-tests and 4 compile-tests yielding at least 928 compilations. That job already takes over an hour on GHA. With coverage collection it is even over 3h and counting.

And it seems the calculation is still to low: ...updated 7154 targets... O.o

Is it possible to trim that down? E.g. combine more tests into single compilation units as especially on Windows firing up the compiler/linker is very expensive (in terms of time).

Also I'm not sure where the additional factor of 7 (in the targets) is coming from. Maybe that could also be trimmed down somehow.

These seem at odds with what's in the STL found here: https://en.cppreference.com/w/cpp/container/unordered_map/find

and http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0919r2.html as well.

Looking at the benchmarks at the beta docs, it looks like the two Erasure With Duplicate elements cases against Visual Studio 2019 + Dinkumware were slower. It would be great if this could be addressed for the v1.80 final release.

Thanks!

Avoid the cost of hashing by directly linearly searching the table.

E.g. here

Since the call to boost::throw_exception generates a fair bit of code and is typically "cold", we want this extracted into a separate BOOST_NOINLINE function so that the rest of at can be inlined.

In addition, we also typically want to either pass BOOST_CURRENT_LOCATION to boost::throw_exception, or switch to boost::throw_with_location (again with supplying a location to it).

As a further refinement, it's possible to add a default source_location argument to at so that the location in the exception ends up being the point of calling at, instead of the point inside of at. This however changes the signature of at, so it should be a separate change, should we decide to do it.

More info found here.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2077r3.html

This proposal updates wording and adds extra overload for transparent conversions.

This will be the super issue for all the related issues:

• #49
• #48
• #47
• #46
• #44
• #43

Seems like we don't have (InputIterator,InputIterator,Allocator) and (std::initializer_list,Allocator) deduction guides for set types as mandated by the resolution of LWG2713.

In the standard, empty() is defined as:

    // capacity
    [[nodiscard]] bool empty() const noexcept;
    size_type size() const noexcept;
    size_type max_size() const noexcept;

This simply just requires adding BOOST_ATTRIBUTE_NODISCARD to the member functions.

API described here.

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

Compiling the test suite using, for example:

./b2 -a libs/unordered/test cxxstd=20 toolset=clang-12

on Ubuntu 20.04 will generate many such warnings:

In file included from libs/unordered/test/unordered/assign_tests.cpp:15:
libs/unordered/test/unordered/../objects/cxx11_allocator.hpp:265:5: warning: definition of implicit copy assignment operator for 'cxx11_allocator<boost::unordered::detail::ptr_node<std::pair<const test::object, test::object>>, test::propagate_assign>' is deprecated because it has a user-declared copy constructor [-Wdeprecated-copy]
    cxx11_allocator(cxx11_allocator const& x) : cxx11_allocator_base<T>(x) {}
    ^
./boost/unordered/detail/implementation.hpp:452:20: note: in implicit copy assignment operator for 'test::cxx11_allocator<boost::unordered::detail::ptr_node<std::pair<const test::object, test::object>>, test::propagate_assign>' first required here
          second() = x.second();
                   ^
./boost/unordered/detail/implementation.hpp:3462:25: note: in instantiation of member function 'boost::unordered::detail::compressed<test::cxx11_allocator<boost::unordered::detail::ptr_bucket, test::propagate_assign>, test::cxx11_allocator<boost::unordered::detail::ptr_node<std::pair<const test::object, test::object>>, test::propagate_assign>>::assign' requested here
            allocators_.assign(x.allocators_);
                        ^
./boost/unordered/detail/implementation.hpp:3425:13: note: in instantiation of function template specialization 'boost::unordered::detail::table<boost::unordered::detail::map<test::cxx11_allocator<test::object, test::propagate_assign>, test::object, test::object, test::hash, test::equal_to>>::assign<std::integral_constant<bool, true>>' requested here
            assign(x, is_unique,
            ^
./boost/unordered/unordered_map.hpp:166:16: note: in instantiation of function template specialization 'boost::unordered::detail::table<boost::unordered::detail::map<test::cxx11_allocator<test::object, test::propagate_assign>, test::object, test::object, test::hash, test::equal_to>>::assign<std::integral_constant<bool, true>>' requested here
        table_.assign(x.table_, boost::unordered::detail::true_type());
               ^
libs/unordered/test/unordered/assign_tests.cpp:38:9: note: in instantiation of member function 'boost::unordered::unordered_map<test::object, test::object, test::hash, test::equal_to, test::cxx11_allocator<test::object, test::propagate_assign>>::operator=' requested here
      x = x;
        ^
libs/unordered/test/unordered/assign_tests.cpp:251:18: note: in instantiation of function template specialization 'assign_tests::assign_tests1<boost::unordered::unordered_map<test::object, test::object, test::hash, test::equal_to, test::cxx11_allocator<test::object, test::propagate_assign>>>' requested here
  UNORDERED_TEST(assign_tests1,
                 ^

This also shows up in the CI:
https://github.com/boostorg/unordered/runs/4216196265?check_suite_focus=true#step:6:847

Outlined here by cppref.

unordered_map is missing documentation for the try_emplace series of member functions

Users have noted that certain warnings will trigger for the SFINAE used in the main implementation.hpp file as noted here #8

Due to the busy lives of contributors, this issue can be directly tackled by a separate PR which refactors the SFINAE into the return type thus fixing the error and also updating the code to be more in line with current style recommendations.

Running:

exbigboss@DESKTOP-I99BGOL:~/cpp/boost-root$ ./b2 -a libs/unordered/test cxxstd=20 toolset=clang-12

generates several warnings of the form:

In file included from libs/unordered/test/unordered/assign_tests.cpp:8:
In file included from ./boost/unordered_set.hpp:17:
In file included from ./boost/unordered/unordered_set.hpp:20:
In file included from ./boost/unordered/detail/set.hpp:6:
./boost/unordered/detail/implementation.hpp:4344:17: warning: ISO C++20 considers use of overloaded operator '==' (with operand types 'test::test_detail::list_iterator<test::object>' and 'test::test_detail::list_iterator<test::object>') to be ambiguous despite there being a unique best viable function [-Wambiguous-reversed-operator]
          if (i == j)
              ~ ^  ~
./boost/unordered/unordered_set.hpp:1714:14: note: in instantiation of function template specialization 'boost::unordered::detail::table<boost::unordered::detail::set<test::cxx11_allocator<test::object, test::propagate_assign>, test::object, test::hash, test::equal_to>>::insert_range_equiv<test::test_detail::list_iterator<test::object>>' requested here
      table_.insert_range_equiv(first, last);
             ^
./boost/unordered/unordered_set.hpp:1559:13: note: in instantiation of function template specialization 'boost::unordered::unordered_multiset<test::object, test::hash, test::equal_to, test::cxx11_allocator<test::object, test::propagate_assign>>::insert<test::test_detail::list_iterator<test::object>>' requested here
      this->insert(f, l);
            ^
libs/unordered/test/unordered/assign_tests.cpp:49:9: note: in instantiation of function template specialization 'boost::unordered::unordered_multiset<test::object, test::hash, test::equal_to, test::cxx11_allocator<test::object, test::propagate_assign>>::unordered_multiset<test::test_detail::list_iterator<test::object>>' requested here
      T x(v.begin(), v.end());
        ^
libs/unordered/test/unordered/assign_tests.cpp:251:18: note: in instantiation of function template specialization 'assign_tests::assign_tests1<boost::unordered::unordered_multiset<test::object, test::hash, test::equal_to, test::cxx11_allocator<test::object, test::propagate_assign>>>' requested here
  UNORDERED_TEST(assign_tests1,
                 ^
libs/unordered/test/unordered/../helpers/./list.hpp:116:12: note: ambiguity is between a regular call to this operator and a call with the argument order reversed
      bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
           ^

You can see similar issues raised in the CI here:
https://github.com/boostorg/unordered/runs/4216196265?check_suite_focus=true#step:6:5429

Inserting in "hash order" can dramatically degrade the performance of insertion. This can be easily triggered by:

unordered_flat_map<int, int> map1(...);
unordered_flat_map<int, int> map2;
for (auto const& kv: map1) { map2.insert(kv); }

For users, this can be circumvented easily by either using the copy constructor or by calling reserve() prior to insertion.

Described here.

https://en.cppreference.com/w/cpp/container/unordered_map/insert

The unordered_map implementation is missing insert overloads:

insert_return_type insert(node_type&& nh);
iterator insert(const_iterator hint, node_type&& nh);

// lookup

const_iterator find(const key_type&) const;

template <class Key>
typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
  const_iterator>::type
find(const Key& k) const;

template <class CompatibleKey, class CompatibleHash,
  class CompatiblePredicate>
const_iterator find(CompatibleKey const&, CompatibleHash const&,
  CompatiblePredicate const&) const;

Why aren't there any non-const lookup methods for unordered_set?
unordered_map has them, Boost and repo docs also state that they should be a part of the unordered_set interface. Not to mention that they are present in std::unordered_set.

Am I missing something?

I have discovered that if I have an empty hash table and call reserve(size), the hash table, instead of allocating a big enough bucket table to insert size * load items, deletes whatever table it has, and then waits until I am in my critical path to allocate the bucket table.

This bug was installed in fe3d612f on 2009-10-04 10:37:36.

In order to work around this bug, I have to insert a dummy element, call reserve(size), and then erase the dummy element.

This behavior violates the entire purpose of reserve(), which is to front-load allocations so that they will not stall time-critical operations.

Gnu libstdc++ and Clang libc++ std::unordered_set both implement reserve(size) correctly.

#include <boost/unordered_set.hpp>
#include <new>
#include <functional>
#include <iostream>
#include <cstdlib>

int total_allocation = 0;

struct B {
  B() : i(++count) {}
  static int count;
  int i;
  bool operator==(B const& b) { return i == b.i; };
  bool operator!=(B const& b) { return i != b.i; };
};

int B::count = 0;

template<typename T> struct A : B {
  using value_type = T;

  A() = default;
  template <class U> A(const A<U>&) noexcept {}

  T* allocate(std::size_t n) {
    std::cout << "  " << i <<  " allocated " << n << " x " << sizeof(T) << '\n';
    total_allocation += n * sizeof(T);
    return (T*) std::calloc(n, sizeof(T));
  }

  void deallocate(T* p, std::size_t n) noexcept {
    std::cout << "  " << i <<  " deallocated " << n << " x " << sizeof(T) << '\n';
    total_allocation -= n * sizeof(T);
    std::free(p);
  }
};

int main() {
  boost::unordered_set<int, std::hash<int>, std::equal_to<int>, A<int>> s(1000'000);
  std::cout << "Bucket table allocation = " << total_allocation
    << ", expected at least " << sizeof(int*) * 1000'000 << '\n';

  s.insert(0);
  s.reserve(2000'000);
  s.erase(0);
  std::cout << "Bucket table allocation = " << total_allocation
    << ", expect at least " << sizeof(int*) * 2000'000 << '\n';

  s.reserve(3000'000);
  std::cout << "Bucket table allocation = " << total_allocation
    << ", expected at least " << sizeof(int*) * 3000'000 << '\n';

  return total_allocation == 0;
}

Output is

Bucket table allocation = 0, expected at least 8000000
  2 allocated 1 x 24
  3 allocated 1572870 x 8
  3 allocated 3145740 x 8
  3 deallocated 1572870 x 8
  2 deallocated 1 x 24
Bucket table allocation = 25165920, expect at least 16000000
  3 deallocated 3145740 x 8
Bucket table allocation = 0, expected at least 24000000

This is a super issue for all compiler-generated warnings for the Unordered test suite.

In test/helpers/metafunctions.hpp the following code generates error: ‘this’ pointer is null [-Werror=nonnull] with GCC 11:

template <class Container> struct has_unique_keys
{
  static char flip(typename Container::iterator const&);
  static long flip(std::pair<typename Container::iterator, bool> const&);
  BOOST_STATIC_CONSTANT(bool,
    value = sizeof(long) ==
            sizeof(flip(
              ((Container*)0)->insert(*(typename Container::value_type*)0))));
};

Potential solutions include:

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wnonnull"
    BOOST_STATIC_CONSTANT(bool,
      value = sizeof(long) ==
              sizeof(flip(
                ((Container*)0)->insert(*(typename Container::value_type*)0))));
#pragma GCC diagnostic pop

and:

value = sizeof(long) == sizeof(flip(unordered_declval<Container&>().insert(unordered_declval<typename Container::value_type>())))

for when unordered_declval exists.

Stack overflow linked question

Following code compile (MSVC C++ latest) using std::unordered_map but not with the new boost:unordered_flat_map:

#include "boost/unordered/unordered_flat_map.hpp"
#include <unordered_map>
    class Foo
    {
    public:
        Foo() = default;
        explicit Foo(int x) : m_x_(x) {};
    private:
        int m_x_;
        std::mutex mtx;
        
    };
    
    int main(int argc, char** argv)
    {
        boost::unordered_flat_map<int,Foo> map_test; //compile with std::unordered_map
        map_test.try_emplace(1,1);
        return 0;
    }

I dont expect it to work with flat_map as with std::map , guessing as the map need reordering, elements need to be able to move/copy. But I dont get why its working with std::unordered_map and not boost:unordered_flat_map.

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2363r3.html

I have a user-defined type which is allocator aware:
https://github.com/kleunen/tilemaker/blob/win_ci_build/include/osm_store.h#L108-L122

This user-defined type I would like to store in an unordered_map, which is allocated in an mmap file using boost interprocess:
https://github.com/kleunen/tilemaker/blob/win_ci_build/include/osm_store.h#L331-L337

Finally I use emplace to store an entry in this map:
https://github.com/kleunen/tilemaker/blob/win_ci_build/include/osm_store.h#L375-L380

On MSVC and linux/g++ this works fine. However, if I compile on MacOS, with g++ and probably libc++ as STL, the unordered_map construct seems to default initialize the VarIntVector and not pass the scoped allocator. Which fails, because the interprocess allocator is not default constructable, it needs a reference to a segment manager.

2021-03-20T07:14:56.5388750Z /usr/local/share/vcpkg/installed/x64-osx/include/boost/container/scoped_allocator.hpp:443:32: error: constructor for 'boost::container::dtl::scoped_allocator_adaptor_base<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64>>' must explicitly initialize the base class 'boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64>' which does not have a default constructor
2021-03-20T07:14:56.5391710Z    BOOST_CONTAINER_FORCEINLINE scoped_allocator_adaptor_base()
2021-03-20T07:14:56.5392270Z                                ^
2021-03-20T07:14:56.5395420Z /usr/local/share/vcpkg/installed/x64-osx/include/boost/container/scoped_allocator.hpp:644:32: note: in instantiation of member function 'boost::container::dtl::scoped_allocator_adaptor_base<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64>>::scoped_allocator_adaptor_base' requested here
2021-03-20T07:14:56.5397550Z    BOOST_CONTAINER_FORCEINLINE scoped_allocator_adaptor()
2021-03-20T07:14:56.5398080Z                                ^
2021-03-20T07:14:56.5400950Z /Users/runner/work/tilemaker/tilemaker/include/osm_store.h:120:25: note: in instantiation of member function 'boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >::scoped_allocator_adaptor' requested here
2021-03-20T07:14:56.5402840Z         VarIntVector(A alloc = A())
2021-03-20T07:14:56.5403260Z                                ^
2021-03-20T07:14:56.5413170Z /usr/local/share/vcpkg/installed/x64-osx/include/boost/unordered/detail/implementation.hpp:2040:11: note: in instantiation of function template specialization 'boost::unordered::detail::func::construct_from_args<boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<boost::unordered::detail::node<boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >, std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >, std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > >, const std::__1::piecewise_construct_t &, std::__1::tuple<unsigned long long &>, std::__1::tuple<> >' requested here
2021-03-20T07:14:56.5420390Z           construct_from_args(
2021-03-20T07:14:56.5420750Z           ^
2021-03-20T07:14:56.5428320Z /usr/local/share/vcpkg/installed/x64-osx/include/boost/unordered/detail/implementation.hpp:3774:54: note: in instantiation of function template specialization 'boost::unordered::detail::func::construct_node_from_args<boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<boost::unordered::detail::node<boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >, std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >, const std::__1::piecewise_construct_t &, std::__1::tuple<unsigned long long &>, std::__1::tuple<> >' requested here
2021-03-20T07:14:56.5434010Z           node_tmp b(boost::unordered::detail::func::construct_node_from_args(
2021-03-20T07:14:56.5434560Z                                                      ^
2021-03-20T07:14:56.5441480Z /usr/local/share/vcpkg/installed/x64-osx/include/boost/unordered/unordered_map.hpp:226:23: note: in instantiation of function template specialization 'boost::unordered::detail::table<boost::unordered::detail::map<boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >, const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > >, std::__1::hash<unsigned long long>, std::__1::equal_to<unsigned long long> > >::emplace_unique<const std::__1::piecewise_construct_t &, std::__1::tuple<unsigned long long &>, std::__1::tuple<> >' requested here
2021-03-20T07:14:56.5446600Z         return table_.emplace_unique(
2021-03-20T07:14:56.5447020Z                       ^
2021-03-20T07:14:56.5453500Z /Users/runner/work/tilemaker/tilemaker/include/osm_store.h:377:30: note: in instantiation of function template specialization 'boost::unordered::unordered_map<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > >, std::__1::hash<unsigned long long>, std::__1::equal_to<unsigned long long>, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > >::emplace<const std::__1::piecewise_construct_t &, std::__1::tuple<unsigned long long &>, std::__1::tuple<> >' requested here

https://pipelines.actions.githubusercontent.com/ya42YO45OlA9LAnHTfxsjT6uj2KbvrHrStfya2AgUYklRTQFd7/_apis/pipelines/1/runs/255/signedlogcontent/8?urlExpires=2021-03-20T07%3A21%3A48.5176130Z&urlSigningMethod=HMACV1&urlSignature=mLfAstpJX4HmQ9g2S%2FnGVYNFIkD9E6hB399%2B2xhuwDs%3D
https://github.com/kleunen/tilemaker/runs/2154401042?check_suite_focus=true

The containers can use one of two policies: a "prime_policy" (

Generally, the mix64_policy is selected when size_t is 64 bit, and prime_policy is used otherwise (

However, when the key is integral (int and above), prime_policy is selected as a special case (

The comment claims that the prime policy is a lot faster for consecutive integral keys, but since it performs a modulo operation, which is an expensive div instruction, on benchmark/uint64.cpp mix64_policy is slightly faster for me (~23 seconds against ~24 seconds under msvc-14.2 64 bit release).

Therefore, we should consider removing this special case, and use mix64_policy for integral keys, too.

mix64_policy contains code that scrambles the hash value (

// Multiplier taken from https://arxiv.org/pdf/2001.05304.pdf
// Computationally Easy, Spectrally Good Multipliers for Congruential Pseudorandom Number Generators
// Guy Steele, Sebastiano Vigna, September 28, 2021

key *= 0xf1357aea2e62a9c5;
key ^= key >> 32;

which for me is about 20% faster and should have good enough scrambling properties. So we should consider this alternative.

We probably want a mix32_policy, too, for the 32 bit case.

Dear All

Can you implement template equal_range like std library?

template< class K >
std::pair<iterator,iterator> equal_range( const K& x );

can read more in:
https://en.cppreference.com/w/cpp/container/unordered_multimap/equal_range

I'm not familiar with boost codebase multi-lib structure so apologies if this is in wrong sub-repo, but I get lots of these errors after upgrading to latest WinSDK 10.0.19041.0 version (I have no idea why 10.0.18xx didn't raise it):

include\boost\unordered\detail\implementation.hpp(1452,7): error C4996: 'std::allocator::is_always_equal': warning STL4010: Various members of std::allocator are deprecated in C++17. Use std::allocator_traits instead of accessing these members directly. You can define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING or _SILENCE_ALL_CXX17_DEPRECATION_WARNINGS to acknowledge that you have received this warning.

I saw boostorg/regex#67 - is this something which is not consistent across different boost libs? I've fixed it in my project but was surprised to come across it.

This code segfaults in 1.80.0 but not 1.79.0 (nor using std::unordered_set):

    boost::unordered_set<std::string> a;
    boost::unordered_set<std::string> b = std::move(a);
    boost::unordered_set<std::string> c = std::move(a);
    c.clear(); // <-- segfault

Based on the standard, the first move should leave a in a "valid but unspecified state"; since a should still be valid, moving from it a second time presumably should not corrupt c (even if the contents of c are technically unspecified afterward).

Note: it appears that unordered_map also exhibits the same behavior.

Currently all the tests are broken. To be clear: it's not the the library code that's broken, but the tests itself. There are multiples issues:

• somehow the downloaded boost-snapshot doesn't get unpacked (python complains that the downloaded file is not a bz2 file)
• appveyor tries to invoke msvc 10 and 11, which seem to be no longer present ('cl' is not a recognized command)
• travis fails when trying to install 'cpp-coveralls' with pip

While testing boost::unordered_flat_set, I noticed my code is reliably running over 10% faster if I __forceinline all the function calls that the boost::unordered_flat_set makes in my hot path. My hot path is only doing .contains(), so anything called by .contains(), including the .contains itself, is where I added __forceinline. So that in my own code where I call .contains(), looking at the disassembly there is no call anywhere any more, it's fully inlined. I think I had to add __forceinline to 6 functions inside boost code.

It is a bit inconvenient to manually add __forceinline to all those functions though - it's definitely worth the 10% performance gain, but I am quite sure that the next time I update boost in a few years, I'll forget to apply these changes again, and then my performance will be worse.

Assuming you don't want to add __forceinline to those functions by default, could there maybe some define like BOOST_FORCEINLINE_UNORDERED_SET that automatically enables forceinlining all the important functions?

I am already compiling with maximum optimization level of MSVC, so by default it doesn't want to inline it, MSVC often needs to be forced to inline stuff.

This repo currently has 55 branches

All branches which are merged to develop (have a "0" in the 2nd number of the table above, i.e. "0 commits ahead of develop") can be safely deleted.
Also there are branches with no activity in 13-15 years. Some don't have any commits with content (check the "Compare" button), e.g. https://github.com/boostorg/unordered/compare/svn-branches/cpp0x

Others may be so outdated it might make sense to just remove them.
That makes working with the repo harder and clones/checkouts larger, so a cleanup is due

unordered_flat_map<string,string> m;
string_view key;
m[key] = "";  // does not work
m.insert_or_assign( key, "" );  // does not work

I'd like to replace our usage of absl::flat_hash_map with boost::unordered_flat_map.
But this missing functions cannot be simulated without performance losses.

Consider a new group14 structure with uses 14 bytes for reduced hashes and 2 bytes for marking overflow.

Compare performance against current group15 implementation.

P1690R1 added a transparent overload of count() that avoids creating an intermediate object when getting the count.

See: https://en.cppreference.com/w/cpp/container/unordered_map/count

In the documentation of the CGAL library we have links to unordered map and set. As this has changed we have broken links (see our issue).
Wouldn't it make sense that you add redirections in the .htacess file at https://github.com/boostorg/website/?

Consider this program:

#include <boost/unordered_set.hpp>
#include <iostream>

static bool log_allocate=false;

template<class T> struct allocator
{
  using value_type=T;
  allocator()=default;
  template<class U> allocator(allocator<U> const &)noexcept{}
  template<class U> bool operator==(allocator<U> const &)const noexcept{return true;}
  template<class U> bool operator!=(allocator<U> const&)const noexcept{return false;}
  T* allocate(std::size_t n)const  
  {
    if(log_allocate)std::cout<<"allocate: "<<n<<"\n";
    return std::allocator<T>().allocate(n);
  }
  void deallocate(T* p,std::size_t n)const noexcept{std::allocator<T>().deallocate(p,n);}
};

int main()
{
  boost::unordered_set<int,boost::hash<int>,std::equal_to<int>,::allocator<int>> s(100);
  for(int i=0;i<s.bucket_count()-1;++i)s.insert(i);
  std::cout<<"bucket count: "<<s.bucket_count()<<"\n";
  std::cout<<"about to rehash\n";
  log_allocate=true;
  s.rehash(0);
  std::cout<<"bucket count: "<<s.bucket_count()<<"\n";
 }

The output against develop is

bucket count: 193
about to rehash
allocate: 194
allocate: 4
bucket count: 193

where it can be seen that, even though bucket_count remains the same after rehashing, reallocation has indeed happened. The problem lies in table::rehash:

template <typename Types>
inline void table<Types>::rehash(std::size_t num_buckets)
{
  num_buckets = (std::max)(
    min_buckets(size_, mlf_), buckets_.bucket_count_for(num_buckets));

  if (num_buckets != this->bucket_count()) {
    this->rehash_impl(num_buckets);
  }
}

Unnecessary reallocation happens because, in the example, num_buckets != this->bucket_count() but buckets_.bucket_count_for(num_buckets) == this->bucket_count(). A simple fix is to rewrite as:

template <typename Types>
inline void table<Types>::rehash(std::size_t num_buckets)
{
  num_buckets = buckets_.bucket_count_for(
    (std::max)(min_buckets(size_, mlf_), num_buckets));

  if (num_buckets != this->bucket_count()) {
    this->rehash_impl(num_buckets);
  }
}

See: https://cplusplus.github.io/LWG/issue2713

This is a blocker for the deduction guides mentioned in #149

If I'm reading it right, it looks like the internal table is not storing the calculated hashes of the node keys. Instead, the hash is calculated on insertion to determine the bucket, and then thrown away. After that, only key-equality is used for things like find(), erasure, equality, etc.

That's fine when the key is something small, like an int, but is slow when the key is not small. Even for string type keys, if the container happens to have a lot of keys of the same string lengths, then equality checking is not cheap. And of course people use custom types for keys too, with potentially non-trivial equality comparisons.

On the other hand, if you stored the full calculated hash in the nodes, you could skip past entries in the same bucket that don't have a matching full-hash, thereby improving performance. (at the expense of memory, obviously)

Another example is rehashing when the load-factor is exceeded. Right now it looks like it has to re-calc the hash of every single node, whereas if it had stored the full-hash it wouldn't need to.

LLVM/clang's libc++ unordered containers store the full-hash, and gcc's libstdc++ does as well in specific cases (e.g., for string-ish types, or if the user specifies the hashing is slow).

So I'm wondering if you've considered doing that, or believe the memory tradeoff isn't worth it?

When using bcp in version 1.69.0 to move boost to a different designated namespace, file boost/unordered/detail/implementation.hpp does not get changed and requires manual fixing.

Near line 1603 of the aforementioned file, the several uses of macro BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE keep on using the original namespace.

Situation
We are storing a unordered_map, unordered_multi_map and unordered_set in a Boost Interprocess Shared Memory that is accessed by a 32bit process and a 64bit process. The 32bit process or the 64bit process can be the creator of the object.

Symptoms
If a 64bit process creates these containers, the 32bit process will crash trying to retrieve it and vice-versa.
If a 64bit process inserts object into one of the containers, the 32bit process will fail to retrieve them by hashing and vice-versa.

Solution
I had to modify some headers so that the sizeof of the unordered's implementation is exactly the same in 32 and 64bits.
In my own code, I force the hashing to be on 32bit instead of size_t. There is some issues internally around the policy. It will fall on a different logic and yield different result if on 32bit or 64bit.

See patch attached.
boost-1.68.0-fix-interoperability-32-64-unordered.patch.zip

See related issue for Boost Multi-Index boostorg/multi_index#17

Unordered could use some sprucing up by replacing its own homespun allocator traits with the utilities in Core:
https://www.boost.org/doc/libs/develop/libs/core/doc/html/core/allocator_access.html

Implement small proof-of-concept of an unordered flat map that stores elements in nodes, granting them reference stability.

This would (most likely) enable a full compliant implementation of the unordered_flat_map.

Attempt to wrap unordered_flat_map<unique_ptr<K, T>> and begin development from there.

The memory_tracker is a helper used by the allocators in the test suite to make sure that allocate + construct calls are matched up properly with destruct + deallocation calls. The memory_tracker also keeps track of how many allocators are alive and referencing it.

Unfortunately, the destructor's usage of BOOST_TEST does not work as was intended by the original author.

The destructor is defined here:

~memory_tracker() { BOOST_TEST(count_allocators == 0); }

and the memory tracker is included in the unit tests as an object in namespace scope:

namespace detail {
  // This won't be a problem as I'm only using a single compile unit
  // in each test (this is actually required by the minimal test
  // framework).
  //
  // boostinspect:nounnamed
  namespace {
    test::detail::memory_tracker tracker;
  }
}

Unfortunately, this destructor does not have the desired effect when running the test suite. Namely, tests in Unordered are run via this macro:

#define RUN_TESTS()                                                            \
  int main(int, char**)                                                        \
  {                                                                            \
    BOOST_UNORDERED_TEST_COMPILER_INFO()                                       \
    ::test::get_state().run_tests();                                           \
    return boost::report_errors();                                             \
  }

The tracker's lifetime is static which means that its destructor is run after main has already ended so all errors are ignored by the test runner. To this end, a developer can erroneously refactor the cxx11_allocator and mess up the reference counting without even knowing.

gdb pretty-printers will probably also be needed.

Docs in the reference appear to be missing for:

    unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a);
    unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
                  const allocator_type& a)

These weren't part of the original documentation and will require new text.

The rest of the containers will need to be audited as well.

detail\prime_fmod.hpp:120 triggers a runtime check failure #1 on msvc (Run-Time Check Failure #1 - A cast to a smaller data type has caused a loss of data.)

Looks intentional due to the cast of boost::uint32_t(hash).

It could be guarded somehow to not trigger this runtime failure when using msvc compiler.
Microsoft suggests the following:

Run-Time Check Failure #1 - A cast to a smaller data type has caused a loss of data. If this was intentional, you should mask the source of the cast with the appropriate bitmask. For example:
char c = (i & 0xFF);