boostorg / container Goto Github PK

STL-like containers from Boost

Home Page: http://www.boost.org/libs/container/

License: Boost Software License 1.0

C++ 91.65% C 8.24% HTML 0.01% CMake 0.04% Shell 0.03% Starlark 0.04%

container's Introduction

Boost.Container

Boost.Container, part of collection of the Boost C++ Libraries, implements several well-known containers, including STL containers. The aim of the library is to offer advanced features not present in standard containers, to offer the latest standard draft features for compilers that don't comply with the latest C++ standard and to offer useful non-STL containers.

License

Distributed under the Boost Software License, Version 1.0.

Properties

C++03
Mostly header-only, library compilation is required for few features.
Supports compiler modes without exceptions support (e.g. -fno-exceptions).

Build Status

Branch	Travis	Appveyor	Coverity Scan	codecov.io	Deps	Docs	Tests
`master`
`develop`

Directories

Name	Purpose
`doc`	documentation
`example`	examples
`include`	headers
`proj`	ide projects
`test`	unit tests

More information

Ask questions
Report bugs: 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.
Discussions about the library are held on the Boost developers mailing list. Be sure to read the discussion policy before posting and add the [container] tag at the beginning of the subject line.

container's People

Contributors

Stargazers

Watchers

Forkers

sanderbog gnzlbg benpope ibmsoe jzmaddock danieljames mikael-s-persson orexym awulkiew yuriks akumta erenon kariya-mitsuru limbolily mclow ya1gaurav crossbuild hpesoj gjasny scopeinfinity seancyw ahundt rishabhcs53 alfc autodesk-forks zamazan4ik elfofo danielae xltools mknejp zerotypos-found lexliy njlr tsnorri gupta2140 joker-eph bmwiedemann garyfurnish jakirkham ecatmur iamrameshkumar jwakely malterlib sarvex xwcs bazelboost quvalda sehe myestro devindusoft p8499 rmpowell77 larryk85 timmmm mike-devel luzpaz apiaryio tobiasludwig jeking3 buckaroo-pm prashantkn94 boostandroid breakthrough rolandd marcelraad stac47 romain-geissler-1a ccf19881030 lastique tobias-loew logan-5 guanqun robertleahy toruniina asdlei99 mucki-at mrpi f3rm4rf3r camolezi giomasce-throwaway abhishekkujur1307 samd2 xtrememapping sdarwin opensourceeda fieryswampshire longgang think-cell dsbabkov tristanfloch krishnaagarwal2001 ekra-ltd wthrowe orgads jingliang2005 0xfeedc0de64 strager fanquake isabella232 georgthegreat

container's Issues

Function definition in header file

Hello,

With the last fix/refactoring commit on adaptive pool (04b0791), I have an "already defined symbol" issue when building our software with boost 1.68.

Indeed, when including boost/container/adaptive_pool.hpp, it includes boost/container/detail/adaptive_node_pool.hpp which itself includes boost/container/detail/adaptive_node_pool_impl.hpp.

The issue in in this last file, where we are declaring AND defining the function boost::container::dtl::candidate_power_of_2_rt(). This triggers a nice linker error.

flat_set of flat_set has allocator type void

Click here for a minimal example on compiler explorer.
The snippet works with boost-1.69 but not with boost-1.70. That's the only difference between the two compiler windows (a click on 'output' reveals the error message).
This seems to be related to issue #120 ... so it may already be fixed. Can anyone confirm?

vector assignment not using memcpy

Hello,
when copy-assigning a boost::container::vector<long> to another one of the same size, I would expect the code to end up as a call to memcpy (or possibly memmove). However, in boost, we end up in a hand-written loop in assign:

      for ( ; first != last && cur != end_it; ++cur, ++first){
         *cur = *first;
      }

This makes the following crude benchmark 4-5 times slower than using std::vector from libstdc++ or libc++.

#include <vector>
#include <boost/container/vector.hpp>
int main(int argc,char**){
#if 1
  typedef boost::container::vector<long> V;
#else
  typedef std::vector<long> V;
#endif
  V m(1024),n(1024);
  for(int k=0;k<1000000;++k) {
    n=m;
    m=n;
  }
  return m[argc];
}

container::vector of interprocess::offset_ptrs to variants holding incomplete type.

Recently I was notified that code compiling some time ago and using container::vector stopped compiling at some point in the past (not sure when). The code I'm talking about is Geometry R-tree with Interprocess allocator.

The R-tree has internal and leaf nodes. Internal nodes contain (more or less) vector of pointers to variants containing either internal or leaf nodes. So when the vector type is defined the internal node type is incomplete but this is fine since pointers are stored.

At some point this code stopped compiling with Clang in gnu++98 and c++03 modes when the pointer is interprocess::offset_ptr taken from interprocess::allocator. It works with container::new_allocator though. I was able to limit the test case (see below). The original errors reported for Geometry can be found here. These are the tests rtree_interprocess_XXX_dyn, e.g. this one.

I didn't dig much but it seems that variant checks some type_traits after it's instantiated by vector's check of boost::move_detail::is_convertible:

static const bool value = sizeof(dispatch(trigger())) == sizeof(true_t);

and the instantiation is done at trigger(). The type passed to the type traits is expected to be complete. It seems all versions of Clang are affected. I was able to reproduce it with 3.8.

Do you have some idea about a workaround for this?

Below is the limited test case in case you wanted to play with it.

#include <boost/container/vector.hpp>
#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <boost/variant.hpp>

template <typename T>
struct wrapper
{
    T v;
};

template <typename Alloc>
struct internal_node
{
    typedef boost::variant<internal_node<Alloc> > node_type;

    typedef typename boost::container::allocator_traits
        <
            Alloc
        >::template rebind_alloc<node_type> node_alloc_type;

    typedef typename boost::container::allocator_traits
        <
            node_alloc_type
        >::pointer node_pointer_type;

    typedef wrapper
        <
            node_pointer_type
        > elem_type;

    typedef typename boost::container::allocator_traits
        <
            node_alloc_type
        >::template rebind_alloc<elem_type> elem_alloc_type;

    template <typename A>
    internal_node(A const& a) : elems(elem_alloc_type(a)) {}

    boost::container::vector<elem_type, elem_alloc_type> elems;
};

int main()
{
    {
        typedef boost::container::new_allocator<int> alloc;
        alloc al;

        internal_node<alloc> n(al);
    }

#ifndef DISABLE_ERROR
    {
        namespace bi = boost::interprocess;
        typedef bi::allocator
            <
                int, bi::managed_shared_memory::segment_manager
            > shmem_alloc;

        bi::managed_shared_memory segment(bi::create_only, "shmem", 65535);
        shmem_alloc sh_al(segment.get_segment_manager());

        internal_node<shmem_alloc> n(sh_al);
    }
#endif
}

Missing files breaks develop documentation build

The following two commits have broken the build of all develop documentation at https://www.boost.org/doc/libs/develop/:

They reference the following files which don't exist:

example/doc_custom_static_vector.cpp
example/doc_custom_small_vector.cpp

container.qbk:744: error: Unable to find file: ../example/doc_custom_static_vector.cpp
container.qbk:771: error: Unable to find file: ../example/doc_custom_small_vector.cpp
Error: Error count: 2.

flat_map doc misleading complexity

Hello,
the documentation of some flat_map operations has a misleading complexity guarantee. For instance, operator[] or insert_or_assign say "logarithmic", but while the number of comparisons is logarithmic, the number of move/copy can be linear. emplace kind of acknowledges this ("Logarithmic search time plus linear insertion to the elements with bigger keys than x"), although it is still wrong if the capacity is exceeded.

flat_map/flat_set with small_vector as container requires explicit allocator-type

The latest changes to the allocator handling in small_vector now requires that the allocator-type has to be specified explicitely when used with flat_map/set:

This line doesn't compile anymore:
boost::container::flat_map<int, double, std::less, boost::container::small_vector<std::pair<int, double>,17>> my_map;

But this one does:
boost::container::flat_map<int, double, std::less, boost::container::small_vector<std::pair<int, double>,17, boost::container::new_allocator<std::pair<int, double>>>> my_map;

The reason for this is that in container_rebind.hpp:60ff

//Needed for non-conforming compilers like GCC 4.3
template <template <class, std::size_t, class> class Cont, typename V, std::size_t N, typename A, class U>
struct container_rebind<Cont<V, N, A>, U>
{
typedef Cont<U, N, typename allocator_traits::template portable_rebind_alloc::type> type;
};

The template doesn't use the "real_allocator" template to figure out the allocator but uses the small_vector's allocator-default "void".

Tobias

Compile error on Green Hills: container_detail::flat_tree has no member "insert"

The following lines cause issue on GHS C++14 compiler (lines 1218 and 1225):

container/include/boost/container/detail/flat_tree.hpp

Lines 1215 to 1227 in 83bb62f

    
           template<class C2> 
        
           BOOST_CONTAINER_FORCEINLINE void merge_unique(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source) 
        
           { 
        
              this->insert( boost::make_move_iterator(source.begin()) 
        
                          , boost::make_move_iterator(source.end())); 
        
           } 
        
           template<class C2> 
        
           BOOST_CONTAINER_FORCEINLINE void merge_equal(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source) 
        
           { 
        
              this->insert( boost::make_move_iterator(source.begin()) 
        
                          , boost::make_move_iterator(source.end())); 
        
           }

Specifically, yields the following errors:

\boost_1_66_0\boost/container/detail/flat_tree.hpp", line 1131: error #135:
          class template "boost::container::container_detail::flat_tree<Value,
          KeyOfValue, Compare, AllocatorOrContainer>" has no member "insert"
        this->insert( boost::make_move_iterator(source.begin())
              ^

\boost_1_66_0\boost/container/detail/flat_tree.hpp", line 1138: error #135:
          class template "boost::container::container_detail::flat_tree<Value,
          KeyOfValue, Compare, AllocatorOrContainer>" has no member "insert"
        this->insert( boost::make_move_iterator(source.begin())
              ^

I'm not 100% sure on the solution, but think it might be replacing this->insert with this->insert_unique/insert_equal?

Thank you!

Syntax error in detail/flat_tree.hpp?

gcc.compile.c++ bin.v2/libs/container/test/scoped_allocator_usage_test.test/gcc-gnu-4.8/debug/cxxstd-11-iso/threadapi-pthread/scoped_allocator_usage_test.o
In file included from ./boost/container/flat_map.hpp:29:0,
                 from libs/container/test/scoped_allocator_usage_test.cpp:20:
./boost/container/detail/flat_tree.hpp:459:68: error: expected unqualified-id before ‘,’ token
       BOOST_INTRUSIVE_HAS_TYPE(boost::container::container_detail::, container_type, stored_allocator_type);
                                                                    ^

From https://travis-ci.org/boostorg/boost/jobs/295693904 and https://ci.appveyor.com/project/boostorg/boost/build/1.0.4464-master/job/mhcujct9n5lj4fdg.

I can't reproduce this locally, so it might have been caused by a temporarily broken Interprocess.

I'm enabling some minimal Travis here, to get some CI.

[Feature Request] Templated lookup methods in associative containers

C++14 added find/lower_bound/upper_bound/equal_range/count methods that accept a templated argument instead of a value of key_type. This is useful if the keys can be ordered against objects of different types (e.g. when the key is std::string and the argument is a std::string_view).

Please, add similar overloads to the associative containers in Boost.Container: flat_set, flat_multiset, flat_map, flat_multimap, set, multiset, map, multimap.

buffer overflow in boost::container::flat_map on FreeBSD

Hi everyone,

I found a bug in boost::container::flat_map on FreeBSD.

System: FreeBSD 12.0
Compiler: Clang 6.0.1 with libc++ (default compiler on FreeBSD)
Boost: master branch on Github

See the following example:

#include <cstdio>
#include <boost/container/flat_map.hpp>

int main() {
  boost::container::flat_map<std::pair<char, char>, char> map;
  map.emplace(std::make_pair(1, 2), 3);
  printf("%d, %d, %d\n",
    map.begin()->first.first,
    map.begin()->first.second,
    map.begin()->second);
  return 0;
}

Output: 2, 3, 0
Expected: 1, 2, 3

flat_map uses boost::container::dtl::pair internally and uses reinterpret_casts to expose a std::pair in the iterators, see flat_map.hpp#L66 and flat_map.hpp#L547

The problem is that std::pair and boost::container::dtl::pair have a different memory layout!

See the following example:

#include <cstdio>
#include <boost/container/flat_map.hpp>

int main() {
  std::pair< std::pair< char, char >, char > std_pair;
  boost::container::dtl::pair< std::pair< char, char >, char > boost_pair;
  printf("%lu %p %p\n", sizeof(std_pair), &std_pair, &std_pair.first);
  printf("%lu %p %p\n", sizeof(boost_pair), &boost_pair, &boost_pair.first);
  return 0;
}

Output:

4 0x7fffffffe738 0x7fffffffe739
3 0x7fffffffe730 0x7fffffffe730

std::pair has a weird padding of 1 byte at the beginning. I think this is related to this patch: https://reviews.llvm.org/D25389
I think there might be a problem with the base class __non_trivially_copyable_base. It looks like the EBO doesn't work properly.

I'm not sure what to do to fix this. I think the C++ standard doesn't enforce the layout of std::pair to be {first, second}, so maybe boost shouldn't assume this.

To reproduce this, I used the following virtual machine:
https://download.freebsd.org/ftp/releases/VM-IMAGES/12.0-RELEASE/amd64/Latest/
Upstream bug in IKOS: NASA-SW-VnV/ikos#22

triviality of pair

The following hack

namespace boost {
  namespace move_detail {
    template<class A, class B> struct is_trivially_copy_assignable<boost::container::dtl::pair<A,B>> {
      static const bool value = is_trivially_copy_assignable<A>::value && is_trivially_copy_assignable<B>::value;
    };
  }
}

changes the running time of this trivial benchmark from 3.4s to just 1.0s on my laptop with g++ -DNDEBUG -O3 -march=native. I think it would be good if you could make pair trivial when the elements are, or at least lie convincingly through traits so an efficient implementation of algorithms is used.

#include <boost/container/flat_map.hpp>
int main(int argc,char**){
  boost::container::flat_map<int,int> m;
  for(int n=100000;n>=0;--n)
    m[n]=n;
  return m[argc];
}

flat_set.hpp and set.hpp in pmr have the same header guard

The same header guard BOOST_CONTAINER_PMR_SET_HPP is used in both pmr/set.hpp and pmr/flat_set.hpp.

Non-unique inplace_set_difference used in in flat_tree_merge_unique and iterator invalidation in insert_unique

In "flat_tree_merge_unique" inplace_set_difference is used insted of inplace_set_unique_difference
Im "insert_unique", the operation "seq.erase(e, seq.cend());" can invalidate the iterator "it" in the corner case if "it == e", so "it" should not be used in "flat_tree_container_inplace_merge". This invalidation does not show in contiguous memory sequence containers like vector, but it is triggered when using stable_vector and other non-contiguous sequences.

unused parameter warning when compiling with assertions disabled

There are some functions here that would need to mask this warning

container/include/boost/container/throw_exception.hpp

Line 60 in 6a9e46e

BOOST_ASSERT_MSG(!"boost::container out_of_range thrown", str);

Please could you silent these warnings?

UBSAN failures detected in preflight CI PR

Setup:

  gcc-8:    &gcc-8    { apt: { packages: [ "g++-8"           ], sources: [ "ubuntu-toolchain-r-test"   ] } }

Command:

UBSAN_OPTIONS=print_stacktrace=1 /home/travis/build/jeking3/boost-root/b2 . toolset=gcc-8 cxxstd=03,11,14,17,2a cxxflags=-fno-omit-frame-pointer cxxflags=-fsanitize=undefined cxxflags=-fno-sanitize-recover=undefined define=BOOST_NO_STRESS_TEST=1 linkflags=-fsanitize=undefined linkflags=-fno-sanitize-recover=undefined linkflags=-fuse-ld=gold variant=debug -j3

Output (first 2 failures):

https://travis-ci.org/jeking3/container/jobs/454295437#L1090

gcc.compile.c++ ../../bin.v2/libs/container/test/tree_test.test/gcc-8/debug/cxxstd-14-iso/visibility-hidden/tree_test.o
gcc.link ../../bin.v2/libs/container/test/tree_test.test/gcc-8/debug/cxxstd-14-iso/visibility-hidden/tree_test
testing.capture-output ../../bin.v2/libs/container/test/tree_test.test/gcc-8/debug/cxxstd-14-iso/visibility-hidden/tree_test.run
====== BEGIN OUTPUT ======
../../boost/intrusive/detail/hook_traits.hpp:61:10: runtime error: reference binding to null pointer of type 'struct slist_base_hook'
    #0 0x47e9a5 in boost::intrusive::bhtraits_base<boost::intrusive::slist_base_hook<boost::intrusive::void_pointer<void*>, boost::intrusive::link_mode<(boost::intrusive::link_mode_type)0>, void>, boost::intrusive::slist_node<void*>*, boost::intrusive::dft_tag, 2u>::to_value_ptr(boost::intrusive::slist_node<void*>* const&) ../../boost/intrusive/detail/hook_traits.hpp:61
    #1 0x466c93 in boost::intrusive::slist_iterator<boost::intrusive::bhtraits<boost::intrusive::slist_base_hook<boost::intrusive::void_pointer<void*>, boost::intrusive::link_mode<(boost::intrusive::link_mode_type)0>, void>, boost::intrusive::slist_node_traits<void*>, (boost::intrusive::link_mode_type)0, boost::intrusive::dft_tag, 2u>, false>::operator_arrow(boost::move_detail::bool_<false>) const ../../boost/intrusive/detail/slist_iterator.hpp:112
    #2 0x4430c0 in boost::intrusive::slist_iterator<boost::intrusive::bhtraits<boost::intrusive::slist_base_hook<boost::intrusive::void_pointer<void*>, boost::intrusive::link_mode<(boost::intrusive::link_mode_type)0>, void>, boost::intrusive::slist_node_traits<void*>, (boost::intrusive::link_mode_type)0, boost::intrusive::dft_tag, 2u>, false>::operator->() const ../../boost/intrusive/detail/slist_iterator.hpp:104
    #3 0x441f3c in boost::container::dtl::basic_multiallocation_chain<void*>::extract_data() ../../boost/container/detail/multiallocation_chain.hpp:174
    #4 0x401553 in boost::container::dtl::fake_segment_manager::deallocate_many(boost::container::dtl::basic_multiallocation_chain<void*>&) ../../boost/container/detail/pool_common_alloc.hpp:52
    #5 0x49d135 in boost::container::dtl::private_adaptive_node_pool_impl_common<boost::container::dtl::fake_segment_manager, 6u>::priv_clear(unsigned long, unsigned long, unsigned long) ../../boost/container/detail/adaptive_node_pool_impl.hpp:937
    #6 0x497fdd in boost::container::dtl::private_adaptive_node_pool_impl_ct<boost::container::dtl::fake_segment_manager, 2ul, 32ul, 256ul, 1ul, 6u>::~private_adaptive_node_pool_impl_ct() ../../boost/container/detail/adaptive_node_pool_impl.hpp:1081
    #7 0x48ff6e in boost::container::dtl::private_adaptive_node_pool<32ul, 256ul, 2ul, 1ul>::~private_adaptive_node_pool() ../../boost/container/detail/adaptive_node_pool.hpp:51
    #8 0x4900f6 in boost::container::dtl::shared_adaptive_node_pool<32ul, 256ul, 2ul, 1ul>::~shared_adaptive_node_pool() ../../boost/container/detail/adaptive_node_pool.hpp:112
    #9 0x7f72648991a8  (/lib/x86_64-linux-gnu/libc.so.6+0x3c1a8)
    #10 0x7f72648991f4 in exit (/lib/x86_64-linux-gnu/libc.so.6+0x3c1f4)
    #11 0x7f726487ef4b in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21f4b)
    #12 0x4010e8  (/home/travis/build/jeking3/boost-root/bin.v2/libs/container/test/tree_test.test/gcc-8/debug/cxxstd-14-iso/visibility-hidden/tree_test+0x4010e8)
EXIT STATUS: 1
====== END OUTPUT ======

https://travis-ci.org/jeking3/container/jobs/454295437#L1556

gcc.compile.c++ ../../bin.v2/libs/container/test/resource_adaptor_test.test/gcc-8/debug/cxxstd-03-iso/visibility-hidden/resource_adaptor_test.o
gcc.link ../../bin.v2/libs/container/test/resource_adaptor_test.test/gcc-8/debug/cxxstd-03-iso/visibility-hidden/resource_adaptor_test
testing.capture-output ../../bin.v2/libs/container/test/resource_adaptor_test.test/gcc-8/debug/cxxstd-03-iso/visibility-hidden/resource_adaptor_test.run
====== BEGIN OUTPUT ======
../../boost/container/pmr/resource_adaptor.hpp:175:16: runtime error: reference binding to misaligned address 0x7ffd4b1992b5 for type 'struct resource_adaptor_imp', which requires 8 byte alignment
0x7ffd4b1992b5: note: pointer points here
 92 19 4b fd 01 00 00  b5 92 19 4b fd 7f 00 00  b5 92 19 4b fd 7f 00 00  e0 92 19 4b fd 7f 00 00  b5
             ^ 
    #0 0x4077c2 in boost::container::pmr::resource_adaptor<propagation_test_allocator<char, 0u, false> >::resource_adaptor(boost::rv<propagation_test_allocator<char, 0u, false> >&) ../../boost/container/pmr/resource_adaptor.hpp:175
    #1 0x4023b2 in test_rvalue_alloc_constructor() ../../libs/container/test/resource_adaptor_test.cpp:57
    #2 0x404b7a in main ../../libs/container/test/resource_adaptor_test.cpp:182
    #3 0x7f730bc92f44 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21f44)
    #4 0x401108  (/home/travis/build/jeking3/boost-root/bin.v2/libs/container/test/resource_adaptor_test.test/gcc-8/debug/cxxstd-03-iso/visibility-hidden/resource_adaptor_test+0x401108)
EXIT STATUS: 1
====== END OUTPUT ======

Invalid merge on flat_multiset

Hello, there seems to be a bug in a merge if there is no reallocation.

Reproduce:

using test_multiset = boost::container::flat_multiset<long>;

test_multiset dst;

for (size_t i = 0; i < 5; ++i)
{
    dst.insert(1);
}

for (size_t i = 0; i < 5; ++i)
{
    dst.insert(2);
}

test_multiset src;

for (size_t i = 0; i < 10; ++i)
{
    src.insert(2);
}

dst.reserve(20);
dst.merge(src);

// failure with reserve, success without
BOOST_CHECK(std::is_sorted(dst.cbegin(), dst.cend()));

flat_map/map::insert_or_assign with hint has wrong return types

Those overloads return "std::pair<iterator, bool>" instead of just "iterator". It must be fixed and better unit tested.

Pointer cast in copy_n_and_update function will break the strict-aliasing rule

container/include/boost/container/detail/advanced_insert_int.hpp

Line 385 in 9137957

value_type *vp = static_cast<value_type *>(static_cast<void *>(&v));\

A pointer cast above in copy_n_and_update function will break the strict-aliasing rule, and will get undefined behavior with aggressive optimization

flat_map::lower_bound and upper_bound have wrong/misleading docs.

lower_bound(const key_type & x) says it returns:
An iterator pointing to the first element with key not less than >>k<<, or >>a.<<end() if such an element is not found.

This has mislabeled variables and should be:
An iterator pointing to the first element with key not less than >>x<<, or >>end()<< if such an element is not found.

upper_bound(const key_type & x) says it returns:
An iterator pointing to the first element with key >>not less<< than x, or end() if such an element is not found.

This isn't consistent with the implementation or the usual definition of upper_bound, and should read:
An iterator pointing to the first element with key >>greater<< than x, or end() if such an element is not found.

This applies to the docs for all the other overloads too.

The relevant part in the current online docs starts here:
https://www.boost.org/doc/libs/1_71_0/doc/html/boost/container/flat_map.html#idm45836572453456-bb

In repo:

container/include/boost/container/flat_map.hpp

Line 1378 in d9341ec

//! <b>Returns</b>: An iterator pointing to the first element with key not less

insert_or_assign not work with hint

The following code doesn't compiles :

https://wandbox.org/permlink/GltFoHe4IcVW9oBd

#include <boost/container/flat_map.hpp>

int main() {
    boost::container::flat_map<int, int> map;    
    map.insert_or_assign(map.begin(), 1,1);
    return 0;
}

Race condition when using boost::container::vector with boost::interprocess::rbtree_best_fit

Following minimal test case:

#include <iostream>
#include <thread>
#include <vector>

#include <boost/container/vector.hpp>
#include <boost/interprocess/managed_mapped_file.hpp>
#include <boost/interprocess/allocators/allocator.hpp>

using MappedFile = boost::interprocess::basic_managed_mapped_file<char,
                   boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family>,
                   boost::interprocess::iset_index>;

template <typename T>
using Allocator = boost::interprocess::allocator<T, MappedFile::segment_manager>;

using VectorInt = boost::container::vector<int, Allocator<int>>;

void fillVector(Allocator<void> alloc)
{
  try {
    Allocator<VectorInt> vAlloc(alloc);
    auto ptr = vAlloc.allocate(1);
    vAlloc.construct(ptr, alloc);

    while (true)
    {
      ptr->push_back(42);
    }
  }
  catch (const std::exception& ex)
  {
    std::cerr << ex.what() << '\n';
  }
}

int main()
{
  MappedFile file(boost::interprocess::create_only, "MyBlock", 2*1024*1024ul, nullptr, {});
  Allocator<void> alloc(file.get_segment_manager());

  std::thread th1([alloc]{ fillVector(alloc);});
  std::thread th2([alloc]{ fillVector(alloc);});

  th1.join();
  th2.join();

  return 0;
}

is considered as racy by ThreadSanitizer:

WARNING: ThreadSanitizer: data race (pid=63884)
  Write of size 4 at 0x7f5553a00d10 by thread T1:
    #0 void boost::interprocess::allocator<int, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> >::construct<int>(boost::interprocess::offset_ptr<int, long, unsigned long, 0ul> const&, int&&) boost/interprocess/allocators/allocator.hpp:264 (ip_tsan+0x0000004115c5)
    #1 void boost::container::allocator_traits<boost::interprocess::allocator<int, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> > >::priv_construct<int, int>(boost::move_detail::integral_constant<bool, true>, boost::interprocess::allocator<int, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> >&, int*, int&&) boost/container/allocator_traits.hpp:411 (ip_tsan+0x000000408cec)
    #2 void boost::container::allocator_traits<boost::interprocess::allocator<int, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> > >::construct<int, int>(boost::interprocess::allocator<int, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> >&, int*, int&&) boost/container/allocator_traits.hpp:360 (ip_tsan+0x000000408cec)
    #3 void boost::container::vector<int, boost::interprocess::allocator<int, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> > >::priv_push_back<int>(int&&) boost/container/vector.hpp:2573 (ip_tsan+0x000000408cec)
    #4 boost::container::vector<int, boost::interprocess::allocator<int, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> > >::push_back(int&&) boost/container/vector.hpp:1857 (ip_tsan+0x00000040340b)
    #5 fillVector(boost::interprocess::allocator<void, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> >) ip_tsan.cpp:27 (ip_tsan+0x00000040340b)
    #6 operator() ip_tsan.cpp:41 (ip_tsan+0x0000004034d7)
    #7 __invoke_impl<void, main()::<lambda()> > c++/7.2.0/bits/invoke.h:60 (ip_tsan+0x0000004039c5)
    #8 __invoke<main()::<lambda()> > c++/7.2.0/bits/invoke.h:95 (ip_tsan+0x0000004036de)
    #9 _M_invoke<0> c++/7.2.0/thread:234 (ip_tsan+0x0000004046c0)
    #10 operator() c++/7.2.0/thread:243 (ip_tsan+0x00000040460d)
    #11 _M_run c++/7.2.0/thread:186 (ip_tsan+0x000000404572)
    #12 <null> <null> (libstdc++.so.6+0x0000000df8ed)

  Previous write of size 8 at 0x7f5553a00d10 by thread T2 (mutexes: write M9):
    #0 boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>::priv_check_and_allocate(unsigned long, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>::block_ctrl*, unsigned long&) boost/interprocess/mem_algo/rbtree_best_fit.hpp:1257 (ip_tsan+0x000000410945)
    #1 boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>::priv_allocate(int, unsigned long, unsigned long&, void*&, unsigned long) boost/interprocess/mem_algo/rbtree_best_fit.hpp:977 (ip_tsan+0x00000040c33c)
    #2 boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>::allocate(unsigned long) boost/interprocess/mem_algo/rbtree_best_fit.hpp:673 (ip_tsan+0x000000409b0d)
    #3 boost::interprocess::segment_manager_base<boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul> >::allocate(unsigned long) boost/interprocess/segment_manager.hpp:177 (ip_tsan+0x000000408743)
    #4 boost::interprocess::allocator<boost::container::vector<int, boost::interprocess::allocator<int, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> >::allocate(unsigned long, boost::interprocess::offset_ptr<void const, long, unsigned long, 0ul>) boost/interprocess/allocators/allocator.hpp:153 (ip_tsan+0x000000407982)
    #5 fillVector(boost::interprocess::allocator<void, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> >) ip_tsan.cpp:22 (ip_tsan+0x0000004032c5)
    #6 operator() ip_tsan.cpp:42 (ip_tsan+0x000000403531)
    #7 __invoke_impl<void, main()::<lambda()> > c++/7.2.0/bits/invoke.h:60 (ip_tsan+0x000000403b75)
    #8 __invoke<main()::<lambda()> > c++/7.2.0/bits/invoke.h:95 (ip_tsan+0x0000004037fa)
    #9 _M_invoke<0> c++/7.2.0/thread:234 (ip_tsan+0x000000404668)
    #10 operator() c++/7.2.0/thread:243 (ip_tsan+0x0000004045bd)
    #11 _M_run c++/7.2.0/thread:186 (ip_tsan+0x000000404528)
    #12 <null> <null> (libstdc++.so.6+0x0000000df8ed)

  Mutex M9 (0x7f5553a00010) created at:
    #0 pthread_mutex_init <null> (libtsan.so.0+0x0000000291ae)
    #1 boost::interprocess::ipcdetail::mutex_initializer::mutex_initializer(pthread_mutex_t&, pthread_mutexattr_t&) boost/interprocess/sync/posix/pthread_helpers.hpp:85 (ip_tsan+0x000000406b91)
    #2 boost::interprocess::ipcdetail::posix_mutex::posix_mutex() boost/interprocess/sync/posix/mutex.hpp:84 (ip_tsan+0x000000406cd1)
    #3 boost::interprocess::interprocess_mutex::interprocess_mutex() boost/interprocess/sync/interprocess_mutex.hpp:153 (ip_tsan+0x000000406e7a)
    #4 boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>::header_t::header_t() boost/interprocess/mem_algo/rbtree_best_fit.hpp:150 (ip_tsan+0x00000041f2b4)
    #5 boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>::rbtree_best_fit(unsigned long, unsigned long) boost/interprocess/mem_algo/rbtree_best_fit.hpp:445 (ip_tsan+0x00000041f324)
    #6 boost::interprocess::segment_manager_base<boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul> >::segment_manager_base(unsigned long, unsigned long) boost/interprocess/segment_manager.hpp:105 (ip_tsan+0x000000418dbf)
    #7 boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index>::segment_manager(unsigned long) boost/interprocess/segment_manager.hpp:419 (ip_tsan+0x000000415e0b)
    #8 boost::interprocess::ipcdetail::basic_managed_memory_impl<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index, 16ul>::create_impl(void*, unsigned long) boost/interprocess/detail/managed_memory_impl.hpp:180 (ip_tsan+0x000000412038)
    #9 boost::interprocess::ipcdetail::create_open_func<boost::interprocess::ipcdetail::basic_managed_memory_impl<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index, 16ul> >::operator()(void*, unsigned long, bool) const boost/interprocess/detail/managed_memory_impl.hpp:743 (ip_tsan+0x00000040eee6)
    #10 void boost::interprocess::ipcdetail::managed_open_or_create_impl<boost::interprocess::ipcdetail::file_wrapper, 16ul, true, false>::priv_open_or_create<boost::interprocess::ipcdetail::create_open_func<boost::interprocess::ipcdetail::basic_managed_memory_impl<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index, 16ul> > >(boost::interprocess::ipcdetail::create_enum_t, char const* const&, unsigned long, boost::interprocess::mode_t, void const*, boost::interprocess::permissions const&, boost::interprocess::ipcdetail::create_open_func<boost::interprocess::ipcdetail::basic_managed_memory_impl<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index, 16ul> >) boost/interprocess/detail/managed_open_or_create_impl.hpp:413 (ip_tsan+0x00000040b2d5)
    #11 boost::interprocess::ipcdetail::managed_open_or_create_impl<boost::interprocess::ipcdetail::file_wrapper, 16ul, true, false>::managed_open_or_create_impl<boost::interprocess::ipcdetail::create_open_func<boost::interprocess::ipcdetail::basic_managed_memory_impl<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index, 16ul> > >(boost::interprocess::create_only_t, char const* const&, unsigned long, boost::interprocess::mode_t, void const*, boost::interprocess::ipcdetail::create_open_func<boost::interprocess::ipcdetail::basic_managed_memory_impl<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index, 16ul> > const&, boost::interprocess::permissions const&) boost/interprocess/detail/managed_open_or_create_impl.hpp:185 (ip_tsan+0x000000408eff)
    #12 boost::interprocess::basic_managed_mapped_file<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index>::basic_managed_mapped_file(boost::interprocess::create_only_t, char const*, unsigned long, void const*, boost::interprocess::permissions const&) boost/interprocess/managed_mapped_file.hpp:101 (ip_tsan+0x000000407be2)
    #13 main ip_tsan.cpp:38 (ip_tsan+0x00000040359a)

  Thread T1 (tid=63886, running) created by main thread at:
    #0 pthread_create <null> (libtsan.so.0+0x0000000289a0)
    #1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) <null> (libstdc++.so.6+0x0000000dfc24)
    #2 main ip_tsan.cpp:41 (ip_tsan+0x0000004035e2)

  Thread T2 (tid=63887, running) created by main thread at:
    #0 pthread_create <null> (libtsan.so.0+0x0000000289a0)
    #1 std::thread::_M_start_thread(std::unique_ptr<std::thread::_State, std::default_delete<std::thread::_State> >, void (*)()) <null> (libstdc++.so.6+0x0000000dfc24)
    #2 main ip_tsan.cpp:42 (ip_tsan+0x000000403608)

SUMMARY: ThreadSanitizer: data race boost/interprocess/allocators/allocator.hpp:264 in void boost::interprocess::allocator<int, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0ul>, 0ul>, boost::interprocess::iset_index> >::construct<int>(boost::interprocess::offset_ptr<int, long, unsigned long, 0ul> const&, int&&)

Build fails on clang-5 with libstdc++7-dev (C++17 issue)

Setup:

  clang-5:  &clang-5  { apt: { packages: [ "clang-5.0",
                                           "libstdc++-7-dev" ], sources: [ "llvm-toolchain-trusty-5.0",
                                                                           "ubuntu-toolchain-r-test"   ] } }

Command:

/home/travis/build/jeking3/boost-root/b2 . toolset=clang-5.0 cxxstd=03,11,14,17 variant=release,debug -j3

Output:

https://travis-ci.org/jeking3/container/jobs/454295432#L1582

clang-linux.compile.c++.without-pth ../../bin.v2/libs/container/test/set_test.test/clang-linux-5.0/release/cxxstd-17-iso/visibility-hidden/set_test.o
../../libs/container/test/set_test.cpp:622:19: error: no viable constructor or deduction guide for deduction of template arguments of 'multiset'
      auto gold = std::multiset({ 1, 2, 3 });
                  ^
...
1 error generated.
  "clang++" -c -x c++ -std=c++17 -fvisibility-inlines-hidden -fPIC -m64 -O3 -Wall -fvisibility=hidden -Wno-inline  -DBOOST_ALL_NO_LIB=1 -DBOOST_CONTAINER_DYN_LINK=1 -DNDEBUG -I"../.." -o "../../bin.v2/libs/container/test/set_test.test/clang-linux-5.0/release/cxxstd-17-iso/visibility-hidden/set_test.o" "../../libs/container/test/set_test.cpp"
...failed clang-linux.compile.c++.without-pth ../../bin.v2/libs/container/test/set_test.test/clang-linux-5.0/release/cxxstd-17-iso/visibility-hidden/set_test.o...

compile problems on Android ndk r16 beta 1

Hello, in attempt to build boost for android with more or less reasonable strict settings (-Werror) I uncovered some bugs.

clang-darwin.compile.c android-build/boost/bin.v2/ 
libs/container/build/clang-darwin-5.0~x86/debug/address- 
model-32/link-static/target-os-android/threading-multi/alloc_lib.o 
In file included from libs/container/src/alloc_lib.c:19: 
libs/container/src/dlmalloc_ext_2_8_6.c:1097:8: error: variable 'ret' is 
used uninitialized whenever 'if' condition is false [-Werror,-Wsometimes- 
uninitialized] 
   if (!PREACTION(m)) { 
       ^~~~~~~~~~~~~ 
libs/container/src/dlmalloc_ext_2_8_6.c:1125:11: note: uninitialized use 
occurs here 
   return ret; 
          ^~~ 
libs/container/src/dlmalloc_ext_2_8_6.c:1097:4: note: remove the 'if' if 
its condition is always true 
   if (!PREACTION(m)) { 
   ^~~~~~~~~~~~~~~~~~~ 
libs/container/src/dlmalloc_ext_2_8_6.c:1095:4: note: variable 'ret' is 
declared here 
   boost_cont_malloc_stats_t ret; 
   ^ 
1 error generated. 
    "/usr/local/opt/android-ndk/android-ndk-r16-beta1// 
toolchains/llvm/prebuilt/darwin-x86_64/bin/clang++" 
"-DBOOST_AC_USE_PTHREADS" "-DBOOST_SP_USE_PTHREADS" "-fvisibility=hidden" 
"-fvisibility-inlines-hidden" "-Wno-unused-local-typedef" -x c -O0 -g -O0 
-fno-inline -Wall -g --target=i686-none-linux-android 
--gcc-toolchain=/usr/local/opt/android-ndk/android-ndk- 
r16-beta1//toolchains/x86-4.9/prebuilt/darwin-x86_64 
--sysroot=/usr/local/opt/android-ndk/android-ndk-r16-beta1//sysroot 
-isystem /usr/local/opt/android-ndk/android-ndk-r16-beta1// 
sources/cxx-stl/llvm-libc++/include -isystem /usr/local/opt/android-ndk/ 
android-ndk-r16-beta1//sources/cxx-stl/llvm-libc++abi/include -isystem 
/usr/local/opt/android-ndk/android-ndk-r16-beta1//sources/android/support/include 
-isystem /usr/local/opt/android-ndk/android-ndk-r16-beta1//sysroot/usr/include 
-isystem /usr/local/opt/android-ndk/android-ndk-r16-beta1// 
sysroot/usr/include/i686-linux-android -DANDROID -D__ANDROID_API__=21 
-ffunction-sections -funwind-tables -fstack-protector-strong 
-fno-limit-debug-info -fPIC -no-canonical-prefixes -mstackrealign 
-Wa,--noexecstack -Wformat -Werror=format-security -Wall -Werror -Wshadow 
-march=i686 -DBOOST_ALL_NO_LIB=1 -DBOOST_CONTAINER_STATIC_LINK=1 
-D_LITTLE_ENDIAN -I"." -c -o "android-build/boost/bin.v2/ 
libs/container/build/clang-darwin-5.0~x86/debug/address- 
model-32/link-static/target-os-android/threading-multi/alloc_lib.o" 
"libs/container/src/alloc_lib.c"

This is using clang toolchain on Android NDK r16 beta1.

Reference to user-config.jam for the build

Alignment ignored in resource_adaptor?

resource_adaptor rebinds the caller's Allocator type to char, which destroys the alignment information. Then in allocate it ignores the alignment parameter. Is this the right thing to do?

Comparing strings does not compile in gcc 7+ in C++17 mode

The following program does not compile in GCC 7, in C++17 mode:

#include <boost/container/string.hpp>

int main()
{
    boost::container::string s1, s2;
    return s1 == s2;
}

This might be a bug in GCC (it works in clang), but I am not sure. It boils to the following situation, which does not compile in GCC 7 (C++17):

template <class T, class U = int>
    class C
    {};

template <class T, class U>
    void f(const C<T, U>&) {}

template <class T, template <class> class CT>
    void f(CT<T>) {}

int main()
{
    C<int> s;
    f(s);
}

flat_map deduction guides are ambiguous

The flat_map and flat_multimap deduction guides are ambiguous. More specifically, the (InputIterator, InputIterator, Allocator const&) and (InputIterator, InputIterator, Compare const&) guides clash.

Repro:

#include <boost/container/flat_map.hpp>
#include <functional>

void f()
{
    std::pair<int, bool> v;
    boost::container::flat_map m(&v, &v + 1, std::greater<int>());
}

Clang 8:

test.cpp(7,32):  error: ambiguous deduction for template arguments of 'flat_map'
    boost::container::flat_map m(&v, &v + 1, std::greater<int>());
                               ^
.../boost/container/flat_map.hpp(1556,1):  note: candidate function [with InputIterator = std::pair<int, bool> *, Allocator = std::greater<int>] flat_map(InputIterator, InputIterator, Allocator const&) ->
^
.../boost/container/flat_map.hpp(1563,1):  note: candidate function [with InputIterator = std::pair<int, bool> *, Compare = std::greater<int>]
flat_map(InputIterator, InputIterator, Compare const&) ->
^
1 error generated.

MSVC 19.15.26726:

D:\> cl -std:c++latest -Zc:__cplusplus -c test.cpp
test.cpp
.../boost/container/flat_map.hpp(1563): error C2642: two deduction guide declarations for the same class template cannot have equivalent parameter list
.../boost/container/flat_map.hpp(1556): note: see previous definition of 'flat_map'
.../boost/container/flat_map.hpp(1588): error C2642: two deduction guide declarations for the same class template cannot have equivalent parameter list
.../boost/container/flat_map.hpp(1581): note: see previous definition of 'flat_map'
.../boost/container/flat_map.hpp(2828): error C2642: two deduction guide declarations for the same class template cannot have equivalent parameter list
.../boost/container/flat_map.hpp(2821): note: see previous definition of 'flat_multimap'
.../boost/container/flat_map.hpp(2853): error C2642: two deduction guide declarations for the same class template cannot have equivalent parameter list
.../boost/container/flat_map.hpp(2846): note: see previous definition of 'flat_multimap'

GCC:

<source>: In function 'void f()':
<source>:7:73: error: class template argument deduction failed:
             boost::container::flat_map m(&v, &v + 1, std::greater<int>());
                                                                         ^
<source>:7:73: error: call of overloaded 'flat_map(std::pair<int, bool>*, std::pair<int, bool>*, std::greater<int>)' is ambiguous
In file included from <source>:1:
.../boost/container/flat_map.hpp:1556:1: note: candidate: 'boost::container::flat_map(InputIterator, InputIterator, const Allocator&)-> boost::container::flat_map<typename boost::move_detail::remove_const<typename boost::movelib::iterator_traits<I>::value_type::first_type>::type, typename boost::movelib::iterator_traits<I>::value_type::second_type, std::less<typename boost::move_detail::remove_const<typename boost::movelib::iterator_traits<I>::value_type::first_type>::type>, Allocator> [with InputIterator = std::pair<int, bool>*; Allocator = std::greater<int>; typename boost::move_detail::remove_const<typename boost::movelib::iterator_traits<I>::value_type::first_type>::type = int; typename boost::movelib::iterator_traits<I>::value_type::second_type = bool]'
 flat_map(InputIterator, InputIterator, Allocator const&) ->
 ^~~~~~~~
.../boost/container/flat_map.hpp:1563:1: note: candidate: 'boost::container::flat_map(InputIterator, InputIterator, const Compare&)-> boost::container::flat_map<typename boost::move_detail::remove_const<typename boost::movelib::iterator_traits<I>::value_type::first_type>::type, typename boost::movelib::iterator_traits<I>::value_type::second_type, Compare> [with InputIterator = std::pair<int, bool>*; Compare = std::greater<int>; typename boost::movelib::iterator_traits<I>::value_type::second_type = bool; typename boost::move_detail::remove_const<typename boost::movelib::iterator_traits<I>::value_type::first_type>::type = int]'
 flat_map(InputIterator, InputIterator, Compare const&) ->
 ^~~~~~~~
Compiler returned: 1

vector.hpp: argument list for class template missing

I am currently trying to include several boost headers which themselves rely on boost/container/vector.hpp in our code project, but compilation with the Intel compiler Intel 19.0.0.117 20180804 leads to the following errors:

.../boost-1.69.0/include/boost/container/vector.hpp(3369): error: argument list for class template "boost::container::vector" is missing
  vector(InputIterator, InputIterator) ->
  ^

.../boost-1.69.0/include/boost/container/vector.hpp(3369): error: expected a ")"
  vector(InputIterator, InputIterator) ->
                      ^

.../boost-1.69.0/include/boost/container/vector.hpp(3369): error: expected a ";"
  vector(InputIterator, InputIterator) ->
                                       ^

boost 1.69.0 was built with:

bootstrap.sh --without-libraries= --with-toolset=intel-linux
b2 toolset=intel-linux install

I tried to reproduce this on older versions of both compiler and boost. Intel 18 and boost 1.66.0 seem to be compatible. Could you try to reproduce this?

See dealii/dealii#7546 for further information.

flat_set: undefined behaviour on empty range

Hello,

the following code triggers the undefined behaviour sanitiser:

#include <cstdint>
#include <boost/container/flat_set.hpp>

using PacketSet = boost::container::flat_set<std::uint32_t>;

int main(int argc, const char * argv[]) {

    const PacketSet empty;
    PacketSet target;
    target.insert(empty.begin(), empty.end());

    return 0;
}

Output is:

boost/V1.67.0_6/boost/container/vector.hpp:125:14: runtime error: reference binding to null pointer of type 'unsigned int'
boost/V1.67.0_6/boost/container/vector.hpp:128:76: runtime error: reference binding to null pointer of type 'unsigned int'
boost/V1.67.0_6/boost/intrusive/pointer_traits.hpp:292:49: runtime error: reference binding to null pointer of type 'unsigned int'
boost/V1.67.0_6/boost/move/detail/meta_utils.hpp:270:49: runtime error: reference binding to null pointer of type 'unsigned int'
boost/V1.67.0_6/boost/move/detail/meta_utils.hpp:246:55: runtime error: reference binding to null pointer of type 'unsigned int'
boost/V1.67.0_6/boost/move/detail/meta_utils.hpp:247:57: runtime error: reference binding to null pointer of type 'unsigned int'
boost/V1.67.0_6/boost/move/detail/meta_utils.hpp:270:9: runtime error: reference binding to null pointer of type 'unsigned int'

Thanks,
Gregor

warning: 'sbrk' is deprecated

While building 1.68.0 beta 1 on x86_64 linux cross-compiling to OSX 10.9 with clang++ 5.0.2, I get this warning:

"x86_64-apple-darwin13-clang++-libc++" -x c -m64 -O3 -Wall -Wno-inline  -DBOOST_ALL_NO_LIB=1 -DBOOST_ASIO_NO_DEPRECATED -DBOOST_CONTAINER_STATIC_LINK=1 -DBOOST_FILESYSTEM_NO_DEPRECATED -DBOOST_LOG_WITHOUT_EVENT_LOG -DNDEBUG -I"." -c -o "bin.v2/libs/container/build/clang-darwin-5.0/release/link-static/target-os-darwin/threading-multi/alloc_lib.o" "libs/container/src/alloc_lib.c"
In file included from libs/container/src/alloc_lib.c:24:
In file included from libs/container/src/dlmalloc_ext_2_8_6.c:36:
libs/container/src/dlmalloc_2_8_6.c:4085:27: warning: 'sbrk' is deprecated [-Wdeprecated-declarations]
      char* base = (char*)CALL_MORECORE(0);
                          ^
libs/container/src/dlmalloc_2_8_6.c:1714:37: note: expanded from macro 'CALL_MORECORE'
        #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
                                    ^
libs/container/src/dlmalloc_2_8_6.c:666:26: note: expanded from macro 'MORECORE_DEFAULT'
#define MORECORE_DEFAULT sbrk
                         ^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/unistd.h:580:1: note: 'sbrk' has been explicitly marked deprecated here
__deprecated
^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/sys/cdefs.h:156:37: note: expanded from macro '__deprecated'
#define __deprecated    __attribute__((deprecated))
                                       ^
In file included from libs/container/src/alloc_lib.c:24:
In file included from libs/container/src/dlmalloc_ext_2_8_6.c:36:
libs/container/src/dlmalloc_2_8_6.c:4095:27: warning: 'sbrk' is deprecated [-Wdeprecated-declarations]
            (br = (char*)(CALL_MORECORE(ssize))) == base) {
                          ^
libs/container/src/dlmalloc_2_8_6.c:1714:37: note: expanded from macro 'CALL_MORECORE'
        #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
                                    ^
libs/container/src/dlmalloc_2_8_6.c:666:26: note: expanded from macro 'MORECORE_DEFAULT'
#define MORECORE_DEFAULT sbrk
                         ^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/unistd.h:580:1: note: 'sbrk' has been explicitly marked deprecated here
__deprecated
^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/sys/cdefs.h:156:37: note: expanded from macro '__deprecated'
#define __deprecated    __attribute__((deprecated))
                                       ^
In file included from libs/container/src/alloc_lib.c:24:
In file included from libs/container/src/dlmalloc_ext_2_8_6.c:36:
libs/container/src/dlmalloc_2_8_6.c:4106:25: warning: 'sbrk' is deprecated [-Wdeprecated-declarations]
          (br = (char*)(CALL_MORECORE(ssize))) == ss->base+ss->size) {
                        ^
libs/container/src/dlmalloc_2_8_6.c:1714:37: note: expanded from macro 'CALL_MORECORE'
        #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
                                    ^
libs/container/src/dlmalloc_2_8_6.c:666:26: note: expanded from macro 'MORECORE_DEFAULT'
#define MORECORE_DEFAULT sbrk
                         ^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/unistd.h:580:1: note: 'sbrk' has been explicitly marked deprecated here
__deprecated
^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/sys/cdefs.h:156:37: note: expanded from macro '__deprecated'
#define __deprecated    __attribute__((deprecated))
                                       ^
In file included from libs/container/src/alloc_lib.c:24:
In file included from libs/container/src/dlmalloc_ext_2_8_6.c:36:
libs/container/src/dlmalloc_2_8_6.c:4118:32: warning: 'sbrk' is deprecated [-Wdeprecated-declarations]
            char* end = (char*)CALL_MORECORE(esize);
                               ^
libs/container/src/dlmalloc_2_8_6.c:1714:37: note: expanded from macro 'CALL_MORECORE'
        #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
                                    ^
libs/container/src/dlmalloc_2_8_6.c:666:26: note: expanded from macro 'MORECORE_DEFAULT'
#define MORECORE_DEFAULT sbrk
                         ^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/unistd.h:580:1: note: 'sbrk' has been explicitly marked deprecated here
__deprecated
^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/sys/cdefs.h:156:37: note: expanded from macro '__deprecated'
#define __deprecated    __attribute__((deprecated))
                                       ^
In file included from libs/container/src/alloc_lib.c:24:
In file included from libs/container/src/dlmalloc_ext_2_8_6.c:36:
libs/container/src/dlmalloc_2_8_6.c:4122:22: warning: 'sbrk' is deprecated [-Wdeprecated-declarations]
              (void) CALL_MORECORE(-ssize);
                     ^
libs/container/src/dlmalloc_2_8_6.c:1714:37: note: expanded from macro 'CALL_MORECORE'
        #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
                                    ^
libs/container/src/dlmalloc_2_8_6.c:666:26: note: expanded from macro 'MORECORE_DEFAULT'
#define MORECORE_DEFAULT sbrk
                         ^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/unistd.h:580:1: note: 'sbrk' has been explicitly marked deprecated here
__deprecated
^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/sys/cdefs.h:156:37: note: expanded from macro '__deprecated'
#define __deprecated    __attribute__((deprecated))
                                       ^
In file included from libs/container/src/alloc_lib.c:24:
In file included from libs/container/src/dlmalloc_ext_2_8_6.c:36:
libs/container/src/dlmalloc_2_8_6.c:4153:20: warning: 'sbrk' is deprecated [-Wdeprecated-declarations]
      br = (char*)(CALL_MORECORE(asize));
                   ^
libs/container/src/dlmalloc_2_8_6.c:1714:37: note: expanded from macro 'CALL_MORECORE'
        #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
                                    ^
libs/container/src/dlmalloc_2_8_6.c:666:26: note: expanded from macro 'MORECORE_DEFAULT'
#define MORECORE_DEFAULT sbrk
                         ^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/unistd.h:580:1: note: 'sbrk' has been explicitly marked deprecated here
__deprecated
^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/sys/cdefs.h:156:37: note: expanded from macro '__deprecated'
#define __deprecated    __attribute__((deprecated))
                                       ^
In file included from libs/container/src/alloc_lib.c:24:
In file included from libs/container/src/dlmalloc_ext_2_8_6.c:36:
libs/container/src/dlmalloc_2_8_6.c:4154:21: warning: 'sbrk' is deprecated [-Wdeprecated-declarations]
      end = (char*)(CALL_MORECORE(0));
                    ^
libs/container/src/dlmalloc_2_8_6.c:1714:37: note: expanded from macro 'CALL_MORECORE'
        #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
                                    ^
libs/container/src/dlmalloc_2_8_6.c:666:26: note: expanded from macro 'MORECORE_DEFAULT'
#define MORECORE_DEFAULT sbrk
                         ^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/unistd.h:580:1: note: 'sbrk' has been explicitly marked deprecated here
__deprecated
^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/sys/cdefs.h:156:37: note: expanded from macro '__deprecated'
#define __deprecated    __attribute__((deprecated))
                                       ^
In file included from libs/container/src/alloc_lib.c:24:
In file included from libs/container/src/dlmalloc_ext_2_8_6.c:36:
libs/container/src/dlmalloc_2_8_6.c:4323:36: warning: 'sbrk' is deprecated [-Wdeprecated-declarations]
            char* old_br = (char*)(CALL_MORECORE(0));
                                   ^
libs/container/src/dlmalloc_2_8_6.c:1714:37: note: expanded from macro 'CALL_MORECORE'
        #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
                                    ^
libs/container/src/dlmalloc_2_8_6.c:666:26: note: expanded from macro 'MORECORE_DEFAULT'
#define MORECORE_DEFAULT sbrk
                         ^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/unistd.h:580:1: note: 'sbrk' has been explicitly marked deprecated here
__deprecated
^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/sys/cdefs.h:156:37: note: expanded from macro '__deprecated'
#define __deprecated    __attribute__((deprecated))
                                       ^
In file included from libs/container/src/alloc_lib.c:24:
In file included from libs/container/src/dlmalloc_ext_2_8_6.c:36:
libs/container/src/dlmalloc_2_8_6.c:4325:38: warning: 'sbrk' is deprecated [-Wdeprecated-declarations]
              char* rel_br = (char*)(CALL_MORECORE(-extra));
                                     ^
libs/container/src/dlmalloc_2_8_6.c:1714:37: note: expanded from macro 'CALL_MORECORE'
        #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
                                    ^
libs/container/src/dlmalloc_2_8_6.c:666:26: note: expanded from macro 'MORECORE_DEFAULT'
#define MORECORE_DEFAULT sbrk
                         ^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/unistd.h:580:1: note: 'sbrk' has been explicitly marked deprecated here
__deprecated
^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/sys/cdefs.h:156:37: note: expanded from macro '__deprecated'
#define __deprecated    __attribute__((deprecated))
                                       ^
In file included from libs/container/src/alloc_lib.c:24:
In file included from libs/container/src/dlmalloc_ext_2_8_6.c:36:
libs/container/src/dlmalloc_2_8_6.c:4326:38: warning: 'sbrk' is deprecated [-Wdeprecated-declarations]
              char* new_br = (char*)(CALL_MORECORE(0));
                                     ^
libs/container/src/dlmalloc_2_8_6.c:1714:37: note: expanded from macro 'CALL_MORECORE'
        #define CALL_MORECORE(S)    MORECORE_DEFAULT(S)
                                    ^
libs/container/src/dlmalloc_2_8_6.c:666:26: note: expanded from macro 'MORECORE_DEFAULT'
#define MORECORE_DEFAULT sbrk
                         ^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/unistd.h:580:1: note: 'sbrk' has been explicitly marked deprecated here
__deprecated
^
/softs/osxcross-10.9-5.0.2/bin/../SDK/MacOSX10.9.sdk/usr/include/sys/cdefs.h:156:37: note: expanded from macro '__deprecated'
#define __deprecated    __attribute__((deprecated))
                                       ^
10 warnings generated.

Mark small_vector move operations noexcept

It should be possible to mark small_vector move constructor and move assignment noexcept if the corresponding move operations of the value_type are noexcept. This would be useful in multiple contexts, like generating noexcept defaulted constructors and operators in classes that contain small_vector objects.

small_vector::push_back without reallocation is 3 times slower than the libstdc++ std::vector::push_back

Compilers inline the priv_forward_range_insert_no_capacity function and that function touches a lot of local variables. The compilers are forced to free up some registers and they push data on the stack.

As a result here's how the small_vector::push_back looks like:

test_boost(boost::container::small_vector<int, 8ul, void, void>&):
  push r15
  push r14
  push r13
  push r12
  push rbp
  push rbx
  mov rbx, rdi
  sub rsp, 8
  mov rax, QWORD PTR [rdi+8]
  mov rdx, QWORD PTR [rdi]
  mov rcx, QWORD PTR [rdi+16]
  lea rbp, [rdx+rax*4]
  cmp rax, rcx
  jnb .L7
  add rax, 1
  mov DWORD PTR [rbp+0], 42
  mov QWORD PTR [rdi+8], rax
.L6:
  add rsp, 8
  pop rbx
  pop rbp
  pop r12
  pop r13
  pop r14
  pop r15
  ret

While the std::vector::push_back looks like the following:

test_std(std::vector<int, std::allocator<int> >&):
  sub rsp, 24
  mov rsi, QWORD PTR [rdi+8]
  mov DWORD PTR [rsp+12], 42
  cmp rsi, QWORD PTR [rdi+16]
  je .L20
  mov DWORD PTR [rsi], 42
  add rsi, 4
  mov QWORD PTR [rdi+8], rsi
  add rsp, 24
  ret

Godbolt playground: https://godbolt.org/z/CvRqMY

Note that adding BOOST_NOINLINE to priv_forward_range_insert_no_capacity does not help.

hash_value

Dear all,

it would be nice if the container library had overloads for hashing (both Boost as std), e.g.:

namespace boost
{
    template<typename Value, std::size_t Capacity>
    std::size_t hash_value(const boost::container::static_vector<Value, Capacity>& crvec)
    {
        return boost::hash_range(crvec.cbegin(), crvec.cend());
    }
}

Infinite or Dead Cycles on MacOS using Boost::Containers

Hello, I have:

MacOS Mojave (10.14.6)
QT with system GCC/G++(4.2.1) / CLang(Apple LLVM version 10.0.1 (clang-1001.0.46.4))
qmake build system
Boost 1.71.0
Homebrew (Installed boost via it)
Some code with boost::containers::list.

App, which uses cycle, looks like:

for(auto cmp : components)
            if (auto res = dynamic_cast<T*>(cmp))
                return res;

Where components is

boost::container::list<Component*> components;

or even

BOOST_FOREACH(auto cmp, components){
...
}

crashes with segmentation fault error, when launched in usual mode, or debugger infinitely loops on iteration here:

Any fixes, suggestions or advices? There's no such errors on linux or windows.

Report:

Process:               NukeEngine-Editor [39320]
Path:                  /Users/USER/*/NukeEngine-Editor
Identifier:            NukeEngine-Editor
Version:               0
Code Type:             X86-64 (Native)
Parent Process:        qtcreator_process_stub [39319]
Responsible:           NukeEngine-Editor [39320]
User ID:               501

Date/Time:             2019-09-16 00:15:00.209 +0300
OS Version:            Mac OS X 10.14.6 (18G87)
Report Version:        12
Anonymous UUID:        F54BCEB5-EF43-944C-909A-3A1C6C87627E


Time Awake Since Boot: 38000 seconds

System Integrity Protection: disabled

Crashed Thread:        0  Dispatch queue: com.apple.main-thread

Exception Type:        EXC_BAD_ACCESS (SIGSEGV)
Exception Codes:       KERN_INVALID_ADDRESS at 0x00000000000000f0
Exception Note:        EXC_CORPSE_NOTIFY

Termination Signal:    Segmentation fault: 11
Termination Reason:    Namespace SIGNAL, Code 0xb
Terminating Process:   exc handler [39320]

VM Regions Near 0xf0:
--> 
    __TEXT                 000000010a196000-000000010a1f6000 [  384K] r-x/rwx SM=COW  /Users/USER/*

Thread 0 Crashed:: Dispatch queue: com.apple.main-thread
0   NukeEngine-Editor             	0x000000010a1aa61f boost::intrusive::list_node_traits<void*>::get_next(boost::intrusive::list_node<void*>* const&) + 15 (list_node.hpp:63)
1   NukeEngine-Editor             	0x000000010a1cffc4 boost::intrusive::list_impl<boost::intrusive::bhtraits<boost::container::dtl::list_node<NukeComponent*, void*>, boost::intrusive::list_node_traits<void*>, (boost::intrusive::link_mode_type)0, boost::intrusive::dft_tag, 1u>, unsigned long, true, void>::begin() + 52 (list.hpp:398)
2   NukeEngine-Editor             	0x000000010a1a3029 boost::container::list<NukeComponent*, void>::begin() + 57 (list.hpp:526)
3   NukeEngine-Editor             	0x000000010a1a3c38 Camera* GameObject::GetComponent<Camera>() + 40 (GameObject.h:36)
4   NukeEngine-Editor             	0x000000010a1a178b EditorUI::SetUp() + 2171 (editorui.h:202)
5   NukeEngine-Editor             	0x000000010a1a0e61 editorinit() + 17 (editorui.h:1059)
6   NukeEngine-Editor             	0x000000010a1ea19a boost::detail::function::void_function_invoker0<void (*)(), void>::invoke(boost::detail::function::function_buffer&) + 26 (function_template.hpp:118)
7   NukeEngine-Editor             	0x000000010a1aaf2a boost::function0<void>::operator()() const + 122 (function_template.hpp:763)
8   NukeEngine-Editor             	0x000000010a1d2ac7 NukeBGFX::init(int, int) + 455 (nukebgfx.h:119)
9   NukeEngine-Editor             	0x000000010a1d2d90 Camera::Init(GameObject*) + 160 (Camera.h:253)
10  NukeEngine-Editor             	0x000000010a1d2cdc Camera::Camera(GameObject*, iRender*) + 188 (Camera.h:55)
11  NukeEngine-Editor             	0x000000010a1a3885 Camera::Camera(GameObject*, iRender*) + 37 (Camera.h:55)
12  NukeEngine-Editor             	0x000000010a1a36ad InitEngine() + 189 (main.cpp:112)
13  NukeEngine-Editor             	0x000000010a1a4679 main + 41 (main.cpp:206)
14  libdyld.dylib                 	0x00007fff646563d5 start + 1

flat_map::insert ambiguous with initializer list & pairs that need to convert

This still seems broken, there's an old trac issue here about it. Are the trickery pokery with movable_value_type even needed on modern compilers? If not it would be nice if these overloads could be conditionally removed in these cases.

moved from small_vector and static_vector calls destructor on elements in static part

When a small_vector or static_vector is moved from they continue ownership of elements:

using Container = boost::small_vector<TypeWithNonTrivialDestructor, 3>;
Container c1;
c1.resize(3);
Container c2(std::move(c1));
// on scope exit, 6 calls are made, 2 per each element

See full code and reproduction here: https://godbolt.org/z/MHA31e

This is possibly not a bug, as the underlying elements are moved from correctly.

However, it is a very counter intuitive behavior that makes it very tricky to use as a drop in replacement for std::vector.

Documentation of boost::container::vector::vector(vector&& x) simply says:

Effects: Move constructor. Moves x's resources to *this.

This is somewhat misleading. Documentation could be improved (specialized?) for these special containers by emphasizing this subtle behavior.

A bench test appears to lock up in Visual Studio 2015 64-bit release mode, default /std

Build job:

https://ci.appveyor.com/project/jeking3/container/builds/20276121/job/3fj1m0948n8bamon

It runs for an hour and times out. This has happened on two different builds, so I think it's specific to Visual Studio 2015. I added the bench directory to the top level Jamfile in a preflight CI pull request in my fork. Given this has happened twice, I thought I would report it.

container::vector::erase memory leak

In boost container 1.68 and 1.67, the following code on boost::container::vector would trigger a memory leak:

while (true)
{
    vector<vector<int>> vv{ {1}, {1} };
    vv[0].reserve(1000000);
    vv.erase(vv.begin());
    vv.insert(vv.begin(), { 1 });
}

Below are some analysis of the cause of the problem.

To avoid confusions, we firstly do the following representation:

vector<int> v0 = vv[0];
vector<int> v1 = vv[1];
auto i0 = vv.begin();

Looking into the implementation of vv.erase(i0) gives a clue about the problem:

iterator erase(const_iterator position)
{
    BOOST_ASSERT(this->priv_in_range(position));
    const pointer p = vector_iterator_get_ptr(position);
    T *const pos_ptr = boost::movelib::to_raw_pointer(p);
    T *const beg_ptr = this->priv_raw_begin();
    T *const new_end_ptr = ::boost::container::move(pos_ptr + 1, beg_ptr + this->m_holder.m_size, pos_ptr);
    //Move elements forward and destroy last
    this->priv_destroy_last(pos_ptr != new_end_ptr);
    return iterator(p);
}

In this case, vv::erase(i0) firstly calls v0 = move(v1) using v0's move asignment operator which delegates the task to v0.priv_move_assign(move(v1)):

template<class OtherAllocator>
void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x
    , typename dtl::disable_if_or
        < void
        , dtl::is_version<OtherAllocator, 0>
        , dtl::is_different<OtherAllocator, allocator_type>
        >::type * = 0)
{
............
    //Resources can be transferred if both allocators are
    //going to be equal after this function (either propagated or already equal)
    if(are_both_propagable){
        //Destroy objects but retain memory in case x reuses it in the future
        this->clear();
        this->m_holder.swap_resources(x.m_holder);
    }
.............
}

As it says in the the comment "//Destroy objects but retain memory in case x reuses it in the future", calling v0.clear() and v0->m_holder.swap_resources(v1.m_holder) makes v1 holding v0's unfreed memory(v0.clear() will not free v0's memory).

Then going back to vv.erase(i0). It then tries to destroy v1 which is holding v0's unfreed memory by calling vv.priv_destroy_last(true):

void priv_destroy_last(const bool moved = false) BOOST_NOEXCEPT_OR_NOTHROW
{
    (void)moved;
    const bool skip_destructor = value_traits::trivial_dctr || (value_traits::trivial_dctr_after_move && moved);
    if(!skip_destructor){
        value_type* const p = this->priv_raw_end() - 1;
        allocator_traits_type::destroy(this->get_stored_allocator(), p);
    }
    --this->m_holder.m_size;
}

It, however, tells that value::traits::trivial_dctr_after_move (which is vector<int>::traits::trivial_dctr_after_move) is true and skips the destructor of v1 which is holding v0's unfreed memory, and thereby creates a memory leak.

static_vector: Can't emplace a non-movable non-copyable type.

The following code fails to compile, because it tries to move X instead of constructing it in-place. Note that using emplace_back is fine.
Tested on godbolt.org with no additional compiler options on:

boost 1.64.0, 1.68.0 / x86-64 gcc 7.x, 8.x
boost 1.64.0, 1.68.0 / x86-64 clang 4.0.x, 5.0.0, 6.0.0
boost 1.64.0, 1.68.0 / x86-64 MSVC 19 2017 RTW

#include <boost/container/static_vector.hpp>

struct X {
  X() = delete;
  X(X const&) = delete;
  X(X&&) = delete;
  X& operator=(X const&) = delete;
  X& operator=(X&&) = delete;

  int a;
  bool b;
  X(int a, bool b) {
  }
};

int main() {
    boost::container::static_vector<X, 1> v;
    v.emplace(v.cend(), 4, true);
    // v.emplace_back(4, true); // ok
    return 0;
}

MSVC + boost 1.70 compilation error when windows.h is already included (detail/thread_mutex.hpp)

There is an ADL problem with boost 1.70.0 that did not occur for us with 1.67.0.

When BOOST_USE_WINDOWS_H is not defined but windows.h has already been included, the calls to InitializeCriticalSection(Ex), EnterCriticalSection, LeaveCriticalSection and DeleteCriticalSection are ambiguous.

I have pasted the problematic part on godbold where you can see the bug:
Godbolt of bug
If you uncomment the line //#define WORKAROUND a simple fix is applied.

file with error: detail/thread_mutex.hpp

error C2668: 'boost::container::dtl::InitializeCriticalSection': ambiguous call to overloaded function
note: could be 'void boost::container::dtl::InitializeCriticalSection(_RTL_CRITICAL_SECTION *)'
C:/WinSdk/Include/10.0.17763.0/um\synchapi.h(123): note: or 'void InitializeCriticalSection(LPCRITICAL_SECTION)' [found using argument-dependent lookup]
note: while trying to match the argument list '(_RTL_CRITICAL_SECTION *)'

error C2668: 'boost::container::dtl::EnterCriticalSection': ambiguous call to overloaded function
note: could be 'void boost::container::dtl::EnterCriticalSection(_RTL_CRITICAL_SECTION *)'
C:/WinSdk/Include/10.0.17763.0/um\synchapi.h(133): note: or 'void EnterCriticalSection(LPCRITICAL_SECTION)' [found using argument-dependent lookup]
note: while trying to match the argument list '(_RTL_CRITICAL_SECTION *)'

error C2668: 'boost::container::dtl::LeaveCriticalSection': ambiguous call to overloaded function
note: could be 'void boost::container::dtl::LeaveCriticalSection(_RTL_CRITICAL_SECTION *)'
C:/WinSdk/Include/10.0.17763.0/um\synchapi.h(141): note: or 'void LeaveCriticalSection(LPCRITICAL_SECTION)' [found using argument-dependent lookup]
note: while trying to match the argument list '(_RTL_CRITICAL_SECTION *)'

error C2668: 'boost::container::dtl::DeleteCriticalSection': ambiguous call to overloaded function
note: could be 'void boost::container::dtl::DeleteCriticalSection(_RTL_CRITICAL_SECTION *)'
C:/WinSdk/Include/10.0.17763.0/um\synchapi.h(194): note: or 'void DeleteCriticalSection(LPCRITICAL_SECTION)' [found using argument-dependent lookup]
note: while trying to match the argument list '(_RTL_CRITICAL_SECTION *)'

Vector with custom allocator does not support value types with operator&

Commit 42c6be5 broke use of vector with custom allocator and types that define operator&.

Repro on godbolt:

#include <boost/container/vector.hpp>

struct X;

template<typename T>
struct XRef
{
    explicit XRef(T* ptr) noexcept : ptr(ptr) {}
    operator T*() const noexcept { return ptr; }
    T* ptr;
};

struct X
{
    XRef<X const> operator&() const noexcept { return XRef<X const>(this); }
    XRef<X>       operator&()       noexcept { return XRef<X>(this); }
};

int main()
{
    boost::container::vector<X> x(5);
    return 0;
}

It comes down to construct and destroy calls using &v instead of addressof(v).

vector::resize() compilation error with msvc-10..12: data is not a member of boost::detail::aligned_storage...

Detected in Geometry R-tree tests. See https://www.boost.org/development/tests/develop/developer/geometry-index.html for msvc-10..12 x64 on x64, e.g.: https://www.boost.org/development/tests/develop/developer/output/teeks99-09-m-win2012R2-32on64-boost-bin-v2-libs-geometry-index-test-rtree-interprocess-rtree_interprocess_rstar_dyn-test-msvc-12-0-dbg-async-excpt-on-thrdp-wn32-thrd-mlt.html

For convenience, the error is:

D:\teeks99-09\run\boost_root\boost/container/detail/advanced_insert_int.hpp(132) : error C2039: 'data' : is not a member of 'boost::detail::aligned_storage::aligned_storage_imp<24,8>'
        D:\teeks99-09\run\boost_root\boost/container/detail/advanced_insert_int.hpp(129) : while compiling class template member function 'void boost::container::dtl::insert_value_initialized_n_proxy<boost::container::new_allocator<T>,T *>::copy_n_and_update(Allocator &,Iterator,unsigned int) const'
        with
        [
            T=child_contents
,            Allocator=boost::container::new_allocator<child_contents>
,            Iterator=child_contents *
        ]
        D:\teeks99-09\run\boost_root\boost/container/vector.hpp(2983) : see reference to function template instantiation 'void boost::container::dtl::insert_value_initialized_n_proxy<boost::container::new_allocator<T>,T *>::copy_n_and_update(Allocator &,Iterator,unsigned int) const' being compiled
        with
        [
            T=child_contents
,            Allocator=boost::container::new_allocator<child_contents>
,            Iterator=child_contents *
        ]

The vector::resize() is called in the R-tree here: https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp#L83
container_from_elements_type is defined here:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/node/node_elements.hpp#L97
and is simply
boost::container::vector<child_contents>
Element child_contents is boost::tuple<size_t, double, double>.

I tired with type different than boost::tuple<...> but of the same size (tuple elements as members), the result is the same. However synthetic test, so creating a vector of elements of the same size and alignment and resizing it outside the R-tree code passes. Funnily enough (in the R-tree) creating a vector of desired size with ctor instead of creating wieh default ctor and resizing it works, so instead of this:

typename rtree::container_from_elements_type<children_type, child_contents>::type children_contents;
children_contents.resize(children_count);

this:

typename rtree::container_from_elements_type<children_type, child_contents_t>::type
    children_contents(children_count);

I'll try to prepare a limited/synthetic case for this issue but in the meanwhile maybe do you have an idea why this may be the case?

`pmr::monotonic_buffer_resource::allocate()` can return a pointer to freed memory after `release()` is called

As implemented, calling release() on a pmr::monotonic_buffer_resource leaves it in an inconsistent state, and this means calling allocate() can return a pointer to memory freed by the call to release().

The 1.65.1 implementation of release() only resets one of the member variables:

void monotonic_buffer_resource::release() BOOST_NOEXCEPT
{  m_memory_blocks.release();  }

The member variables m_current_buffer and m_current_buffer_size (used in do_allocate()) are untouched.

Implement C++17 MoveAssignable requirements for self-move assignments

In C++17, self-move assignment is no longer undefined behavior:

MoveAssignable requirements [moveassignable]

[ Note: rv must still meet the requirements of the library
component that is using it, whether or not t and rv refer to the same object. The
operations listed in those requirements must work as specified whether rv has been moved
from or not. — end note ]

All Boost.Container classes should be updated to guarantee MoveAssignable requirements

Fails on msvc-12.0, 14.0, 14.1

See

https://ci.appveyor.com/project/boostorg/boost/build/1.0.3616

Iterator zero incrementing leads to assert on empty vector.

This construction leads to assert:

  auto it = v.begin(); // empty vector
  it += 0; // <---- assert here

basic_string::npos is missing its definition

Mostly this isn't noticed because it's a constant, but if you take its address (perhaps implicitly through some function that takes parameters by reference) you'll get a link-time error:

$ cat foo.cpp
#include <boost/container/string.hpp>
#include <iostream>

int main() {
  std::cout << &boost::container::string::npos << "\n";
  return 0;
}
$ g++ foo.cpp
foo.cpp:5: error: undefined reference to 'boost::container::basic_string<char, std::char_traits<char>, boost::container::new_allocator<char> >::npos'
collect2: error: ld returned 1 exit status

Build on cygwin (32-bit) fails

Setup:

    - FLAVOR: cygwin (64-bit)
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
      ADDPATH: C:\cygwin64\bin;
      B2_ADDRESS_MODEL: address-model=64
      CXXSTD: 11,17
      # https://github.com/boostorg/test/issues/144
      DEFINES: define=_POSIX_C_SOURCE=200112L define=__USE_ISOC99
      THREADING: threadapi=pthread
      TOOLSET: gcc

Command:

b2 libs/container toolset=gcc cxxstd=03,11  define=_POSIX_C_SOURCE=200112L threadapi=pthread address-model=32   variant=release,debug -j3

Output:

https://ci.appveyor.com/project/jeking3/container/build/job/umhtyg2l308r44jj?fullLog=true#L2001

gcc.link bin.v2\libs\container\test\string_test.test\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden\string_test.exe
testing.capture-output bin.v2\libs\container\test\string_test.test\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden\string_test.run
====== BEGIN OUTPUT ======
 
EXIT STATUS: 1 
====== END OUTPUT ======
    set Path=C:\projects\boost-root\bin.v2\libs\container\build\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden;C:\cygwin\bin;C:\cygwin\lib;C:\cygwin\lib32;C:\cygwin\lib64;%Path%
    set status=0
    if %status% NEQ 0 (
        echo Skipping test execution due to testing.execute=off
        exit 0
    )
     "bin.v2\libs\container\test\string_test.test\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden\string_test.exe"   > "bin.v2\libs\container\test\string_test.test\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden\string_test.output" 2>&1 
    set status=%ERRORLEVEL%
    echo. >> "bin.v2\libs\container\test\string_test.test\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden\string_test.output"
    echo EXIT STATUS: %status% >> "bin.v2\libs\container\test\string_test.test\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden\string_test.output"
    if %status% EQU 0 (
        copy "bin.v2\libs\container\test\string_test.test\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden\string_test.output" "bin.v2\libs\container\test\string_test.test\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden\string_test.run"
    )
    set verbose=0
    if %status% NEQ 0 (
        set verbose=1
    )
    if %verbose% EQU 1 (
        echo ====== BEGIN OUTPUT ======
        type "bin.v2\libs\container\test\string_test.test\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden\string_test.output"
        echo ====== END OUTPUT ======
    )
    exit %status%
...failed testing.capture-output bin.v2\libs\container\test\string_test.test\gcc-6.4.0\release\cxxstd-11-iso\target-os-cygwin\visibility-hidden\string_test.run...

flat_set: Heap overflow

Hello,

the following code results in a heap buffer overflow detected by ASAN:

#include <cstdint>
#include <boost/container/flat_set.hpp>

using PacketSet = boost::container::flat_set<std::uint32_t>;

int main(int argc, const char * argv[]) {

    PacketSet a{1u};
    PacketSet b{1u, 2u};
    PacketSet c{1u, 2u, 4u};
    PacketSet d{1u, 2u, 3u, 4u, 5u};

    PacketSet final;

    final.merge(a);
    final.merge(b);
    final.merge(c);
    final.merge(d);

    return 0;
}

A bisection points to: Add improved range insertion to flat associative containers...

Thanks,
Gregor

Fails to build for Android: cannot convert argument of incomplete type 'void *' to 'std::align_val_t' for 2nd argument

Trying to build boost-container 1.69.0 for Android with the current AOSP master toolchain fails:

In file included from external/boost-container/src/pool_resource.cpp:18:
external/boost-container/include/boost/container/detail/block_slist.hpp:97:34: error: no matching function for call to 'operator new'
      block_slist_header &mb  = *::new((void*)p) DerivedFromBlockSlistHeader;
                                 ^~
external/boost-container/include/boost/container/detail/block_slist.hpp:142:40: note: in instantiation of member function 'boost::container::pmr::block_slist_base<boost::container::pmr::block_slist_header>::allocate' requested here
   {  return this->block_slist_base<>::allocate(size, m_upstream_rsrc);  }
                                       ^
note: candidate function not viable: cannot convert argument of incomplete type 'void *' to 'std::align_val_t' for 2nd argument
note: candidate function not viable: requires 1 argument, but 2 were provided
external/boost-container/include/boost/container/detail/placement_new.hpp:24:14: note: candidate function not viable: requires 3 arguments, but 2 were provided
inline void *operator new(std::size_t, void *p, boost_container_new_t)
             ^
In file included from external/boost-container/src/pool_resource.cpp:17:
In file included from external/boost-container/include/boost/container/detail/pool_resource.hpp:21:
external/boost-container/include/boost/container/detail/block_list.hpp:103:33: error: no matching function for call to 'operator new'
      block_list_header &mb  = *::new((void*)p) DerivedFromBlockListHeader;
                                ^~
external/boost-container/src/pool_resource.cpp:213:31: note: in instantiation of member function 'boost::container::pmr::block_list_base<boost::container::pmr::block_list_header>::allocate' requested here
      return m_oversized_list.allocate(bytes, m_upstream);
                              ^
note: candidate function not viable: cannot convert argument of incomplete type 'void *' to 'std::align_val_t' for 2nd argument
note: candidate function not viable: requires 1 argument, but 2 were provided
external/boost-container/include/boost/container/detail/placement_new.hpp:24:14: note: candidate function not viable: requires 3 arguments, but 2 were provided
inline void *operator new(std::size_t, void *p, boost_container_new_t)
             ^
2 errors generated.
17:07:56 ninja failed with: exit status 1

Not sure why it would think of void* as an incomplete type... Haven't looked into it a lot, but so far it looks like it may be a toolchain bug.

	template<class C2>
	BOOST_CONTAINER_FORCEINLINE void merge_unique(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source)
	{
	this->insert( boost::make_move_iterator(source.begin())
	, boost::make_move_iterator(source.end()));
	}

	template<class C2>
	BOOST_CONTAINER_FORCEINLINE void merge_equal(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source)
	{
	this->insert( boost::make_move_iterator(source.begin())
	, boost::make_move_iterator(source.end()));
	}

boostorg / container Goto Github PK

container's Introduction

Boost.Container

License

Properties

Build Status

Directories

More information

container's People

Contributors

Stargazers

Watchers

Forkers

container's Issues

Recommend Projects

Recommend Topics

Recommend Org