[Container] Strange flat_set crash with std::inserter

::operator() (this=0x7fffffffd598, lhs=@0x7ffff61c6320: 61595138, rhs=@0x454000: <error reading variable>) at ../yy/build/boost/boost/container/detail/flat_tree.hpp:66 #2 0x0000000000404367 in boost::container::container_detail::flat_tree<unsigned long, unsigned long, boost::container::container_detail::identity<unsigned long>, std::__1::less<unsigned long>, std::__1::allocator<unsigned long> ::priv_insert_unique_prepare (this=0x7fffffffd598, pos=..., val=@0x7ffff61c6320: 61595138, commit_data=...) at ../yy/build/boost/boost/container/detail/flat_tree.hpp:824 #3 0x0000000000404275 in boost::container::container_detail::flat_tree<unsigned long, unsigned long, boost::container::container_detail::identity<unsigned long>, std::__1::less<unsigned long>, std::__1::allocator<unsigned long> ::insert_unique (this=0x7fffffffd598, pos=..., val=@0x7ffff61c6320:
::priv_insert<unsigned long const&> (this=0x7fffffffd598, p=..., x=@0x7ffff61c6320: 61595138) at ../yy/build/boost/boost/container/flat_set.hpp:688 #5 0x00000000004041bd in boost::container::flat_set<unsigned long, std::__1::less<unsigned long>, std::__1::allocator<unsigned long> ::insert (this=0x7fffffffd598, arg1=..., x=@0x7ffff61c6320: 61595138) at ../yy/build/boost/boost/container/flat_set.hpp:508 #6 0x0000000000401de4 in operator* (this=0x7fffffffd750,
Hi all It seems that when I copy a sorted but non-unique range of randomly generated numbers to an output iterator generated from std::inserter to a boost::flat_set it crashes. At first I assumed it was because boost::flat_set doesn't have stable iterators, but it seems that the implementation of std::insert_iterator does the right thing by reassigning its internal iterator to the result of the insert operation before incrementing it. Apologies for not being able to reduce the problem further, but this one is a little strange, the following code demonstrates the problem (and some variations that do work) in boost 1.54: #include <boost/container/flat_set.hpp> #include <algorithm> #include <iterator> #include <numeric> #include <vector> template<typename ContainerT> void Populate(std::vector<size_t> const& input) { ContainerT container; std::copy( std::begin(input), std::end(input), std::inserter(container, std::end(container))); } int main() { const size_t Count = 1000000; std::vector<size_t> random_numbers; random_numbers.reserve(Count); std::generate_n( std::back_inserter(random_numbers), Count, &std::rand); std::vector<size_t> sorted_numbers(random_numbers); std::sort(std::begin(sorted_numbers), std::end(sorted_numbers)); std::vector<size_t> unique_sorted_numbers; unique_sorted_numbers.reserve(Count); std::unique_copy( std::begin(sorted_numbers), std::end(sorted_numbers), std::back_inserter(unique_sorted_numbers)); using namespace boost::container; Populate<flat_set<size_t>>(unique_sorted_numbers); // ok Populate<flat_multiset<size_t>>(sorted_numbers); // ok Populate<flat_set<size_t>>(sorted_numbers); // segfault, line 39 } It might be a little hard to reproduce with the rand() in there, I'm on 64bit Ubuntu 13.04 and it's reproducible with Clang 3.3 with libc++ and GCC 4.8.1. Here's the backtrace from Clang: #0 0x0000000000403aec in operator() (this=0x7fffffffd598, __x=@0x7ffff61c6320: 61595138, __y=@0x454000: <error reading variable>) at /usr/include/c++/v1/__functional_base:61 #1 boost::container::container_detail::flat_tree_value_compare<std::__1::less<unsigned long>, unsigned long, boost::container::container_detail::identity<unsigned long> 61595138) at ../yy/build/boost/boost/container/detail/flat_tree.hpp:354 #4 0x000000000040421d in boost::container::flat_set<unsigned long, std::__1::less<unsigned long>, std::__1::allocator<unsigned long> this=0x7fffffffd750, this=0x7fffffffd750, __value_=@0x7ffff61c6320: 61595138) at /usr/include/c++/v1/iterator:718 #7 __unwrap_iter<std::__1::insert_iterator<boost::container::flat_set<unsigned long, std::__1::less<unsigned long>, std::__1::allocator<unsigned long>
(__i=..., __first=..., __last=..., __result=...) at /usr/include/c++/v1/algorithm:1717 #8 end<boost::container::flat_set<unsigned long, std::__1::less<unsigned long>, std::__1::allocator<unsigned long> > > (__c=..., __x=..., __i=..., __first=..., __last=..., __result=...) at /usr/include/c++/v1/algorithm:1741 #9 Populate<boost::container::flat_set<unsigned long, std::__1::less<unsigned long>, std::__1::allocator<unsigned long> > > (input=...) at flat_set_crash.cpp:13 #10 0x00000000004017a6 in main () at flat_set_crash.cpp:39
or from GCC if you prefer: #0 0x0000000000404bed in std::less<unsigned long>::operator() (this=0x7fffffffdd10, __x=@0x7ffff62e7320: 61595138, __y=@0x453000: <error reading variable>) at /usr/include/c++/4.8/bits/stl_function.h:235 #1 0x00000000004047f9 in boost::container::container_detail::flat_tree_value_compare<std::less<unsigned long>, unsigned long, boost::container::container_detail::identity<unsigned long>
::operator() (this=0x7fffffffdd10, lhs=@0x7ffff62e7320: 61595138, rhs=@0x453000: <error reading variable>) at ../yy/build/boost/boost/container/detail/flat_tree.hpp:66 #2 0x0000000000404389 in boost::container::container_detail::flat_tree<unsigned long, unsigned long, boost::container::container_detail::identity<unsigned long>, std::less<unsigned long>, std::allocator<unsigned long> ::priv_insert_unique_prepare (this=0x7fffffffdd10, pos=..., val=@0x7ffff62e7320: 61595138, commit_data=...) at ../yy/build/boost/boost/container/detail/flat_tree.hpp:824 #3 0x000000000040420a in boost::container::container_detail::flat_tree<unsigned long, unsigned long, boost::container::container_detail::identity<unsigned long>, std::less<unsigned long>, std::allocator<unsigned long> >::insert_unique (this=0x7fffffffdd10, pos=..., val=@0x7ffff62e7320: 61595138) at ../yy/build/boost/boost/container/detail/flat_tree.hpp:354 #4 0x00000000004040ef in boost::container::flat_set<unsigned long, std::less<unsigned long>, std::allocator<unsigned long> ::priv_insert<unsigned long const&> (this=0x7fffffffdd10, p=..., x=@0x7ffff62e7320: 61595138) at ../yy/build/boost/boost/container/flat_set.hpp:688 #5 0x0000000000403fa5 in boost::container::flat_set<unsigned long, std::less<unsigned long>, std::allocator<unsigned long> >::insert (this=0x7fffffffdd10, arg1=..., x=@0x7ffff62e7320: 61595138) at ../yy/build/boost/boost/container/flat_set.hpp:508 #6 0x0000000000403b71 in std::insert_iterator<boost::container::flat_set<unsigned long, std::less<unsigned long>, std::allocator<unsigned long> > >::operator= (this=0x7fffffffdbd0, __value=@0x7ffff62e7320: 61595138) at /usr/include/c++/4.8/bits/stl_iterator.h:640 #7 0x000000000040350a in std::__copy_move<false, false, std::random_access_iterator_tag>::__copy_m<unsigned long const*, std::insert_iterator<boost::container::flat_set<unsigned long, std::less<unsigned long>, std::allocator<unsigned long> > > > (__first=0x7ffff62e7320, __last=0x7ffff6a50210, __result=...) at /usr/include/c++/4.8/bits/stl_algobase.h:335 #8 0x0000000000402c2f in std::__copy_move_a<false, unsigned long const*, std::insert_iterator<boost::container::flat_set<unsigned long, std::less<unsigned long>, std::allocator<unsigned long> > > > (__first=0x7ffff62af010, __last=0x7ffff6a50210, __result=...) at /usr/include/c++/4.8/bits/stl_algobase.h:390 #9 0x000000000040237f in std::__copy_move_a2<false, __gnu_cxx::__normal_iterator<unsigned long const*, std::vector<unsigned long, std::allocator<unsigned long> > >, std::insert_iterator<boost::container::flat_set<unsigned long, std::less<unsigned long>, std::allocator<unsigned long> > > > (__first=1210, __last=0, __result=...) at /usr/include/c++/4.8/bits/stl_algobase.h:428 #10 0x0000000000401b70 in std::copy<__gnu_cxx::__normal_iterator<unsigned long const*, std::vector<unsigned long, std::allocator<unsigned long> > >, std::insert_iterator<boost::container::flat_set<unsigned long, std::less<unsigned long>, std::allocator<unsigned long> > > > (__first=1210, __last=0, __result=...) at /usr/include/c++/4.8/bits/stl_algobase.h:460 #11 0x000000000040120f in Populate<boost::container::flat_set<unsigned long, std::less<unsigned long>, std::allocator<unsigned long> > > (input=std::vector of length 1000000, capacity 1000000 = {...}) at flat_set_crash.cpp:10 #12 0x0000000000400c50 in main () at flat_set_crash.cpp:39 (gdb)
Since my refactoring of the code above, the crash location has changed, it used to be in: boost::container::vector::priv_forward_range_insert_at_end_expand_forward boost/container/vector.hpp:2205 unique_sorted_numbers.size() is 999752. Unfortunately producing a sequential list of numbers with std::iota and then changing one of them to the proceeding value didn't repro the problem. Ben

El 06/09/2013 14:35, Ben Pope escribió:
Hi all
It seems that when I copy a sorted but non-unique range of randomly generated numbers to an output iterator generated from std::inserter to a boost::flat_set it crashes.
At first I assumed it was because boost::flat_set doesn't have stable iterators, but it seems that the implementation of std::insert_iterator does the right thing by reassigning its internal iterator to the result of the insert operation before incrementing it.
Apologies for not being able to reduce the problem further, but this one is a little strange, the following code demonstrates the problem (and some variations that do work) in boost 1.54:
Thanks for the report and the test case. I think tt's a bug in the insertion with hint function in flat_tree. I'll open a ticket for this. Best, Ion
participants (2)
-
Ben Pope
-
Ion Gaztañaga