summaryrefslogtreecommitdiff
path: root/boost/container/detail
diff options
context:
space:
mode:
Diffstat (limited to 'boost/container/detail')
-rw-r--r--boost/container/detail/adaptive_node_pool_impl.hpp16
-rw-r--r--boost/container/detail/advanced_insert_int.hpp10
-rw-r--r--boost/container/detail/algorithm.hpp122
-rw-r--r--boost/container/detail/copy_move_algo.hpp69
-rw-r--r--boost/container/detail/destroyers.hpp10
-rw-r--r--boost/container/detail/flat_tree.hpp332
-rw-r--r--boost/container/detail/iterator_to_raw_pointer.hpp29
-rw-r--r--boost/container/detail/multiallocation_chain.hpp6
-rw-r--r--boost/container/detail/node_alloc_holder.hpp34
-rw-r--r--boost/container/detail/node_pool_impl.hpp4
-rw-r--r--boost/container/detail/pair.hpp61
-rw-r--r--boost/container/detail/pair_key_mapped_of_value.hpp55
-rw-r--r--boost/container/detail/to_raw_pointer.hpp33
-rw-r--r--boost/container/detail/tree.hpp145
14 files changed, 636 insertions, 290 deletions
diff --git a/boost/container/detail/adaptive_node_pool_impl.hpp b/boost/container/detail/adaptive_node_pool_impl.hpp
index 24c81dda3b..54db19dff2 100644
--- a/boost/container/detail/adaptive_node_pool_impl.hpp
+++ b/boost/container/detail/adaptive_node_pool_impl.hpp
@@ -28,10 +28,10 @@
// container/detail
#include <boost/container/detail/pool_common.hpp>
#include <boost/container/detail/iterator.hpp>
-#include <boost/container/detail/iterator_to_raw_pointer.hpp>
+#include <boost/move/detail/iterator_to_raw_pointer.hpp>
#include <boost/container/detail/math_functions.hpp>
#include <boost/container/detail/mpl.hpp>
-#include <boost/container/detail/to_raw_pointer.hpp>
+#include <boost/move/detail/to_raw_pointer.hpp>
#include <boost/container/detail/type_traits.hpp>
// intrusive
#include <boost/intrusive/pointer_traits.hpp>
@@ -378,7 +378,7 @@ class private_adaptive_node_pool_impl
//!Returns the segment manager. Never throws
segment_manager_base_type* get_segment_manager_base()const
- { return container_detail::to_raw_pointer(mp_segment_mngr_base); }
+ { return boost::movelib::to_raw_pointer(mp_segment_mngr_base); }
//!Allocates array of count elements. Can throw
void *allocate_node()
@@ -390,7 +390,7 @@ class private_adaptive_node_pool_impl
free_nodes_t &free_nodes = m_block_container.begin()->free_nodes;
BOOST_ASSERT(!free_nodes.empty());
const size_type free_nodes_count = free_nodes.size();
- void *first_node = container_detail::to_raw_pointer(free_nodes.pop_front());
+ void *first_node = boost::movelib::to_raw_pointer(free_nodes.pop_front());
if(free_nodes.empty()){
block_container_traits_t::erase_first(m_block_container);
}
@@ -401,7 +401,7 @@ class private_adaptive_node_pool_impl
else{
multiallocation_chain chain;
this->priv_append_from_new_blocks(1, chain, IsAlignOnly());
- return container_detail::to_raw_pointer(chain.pop_front());
+ return boost::movelib::to_raw_pointer(chain.pop_front());
}
}
@@ -492,7 +492,7 @@ class private_adaptive_node_pool_impl
free_nodes_iterator itf(nodes.begin()), itbf(itbb);
size_type splice_node_count = size_type(-1);
while(itf != ite){
- void *pElem = container_detail::to_raw_pointer(container_detail::iterator_to_raw_pointer(itf));
+ void *pElem = boost::movelib::to_raw_pointer(boost::movelib::iterator_to_raw_pointer(itf));
block_info_t &block_info = *this->priv_block_from_node(pElem);
BOOST_ASSERT(block_info.free_nodes.size() < m_real_num_node);
++splice_node_count;
@@ -631,7 +631,7 @@ class private_adaptive_node_pool_impl
BOOST_ASSERT(to_deallocate->free_nodes.size() == mp_impl->m_real_num_node);
BOOST_ASSERT(0 == to_deallocate->hdr_offset);
hdr_offset_holder *hdr_off_holder =
- mp_impl->priv_first_subblock_from_block(container_detail::to_raw_pointer(to_deallocate));
+ mp_impl->priv_first_subblock_from_block(boost::movelib::to_raw_pointer(to_deallocate));
m_chain.push_back(hdr_off_holder);
}
@@ -763,7 +763,7 @@ class private_adaptive_node_pool_impl
//First add all possible nodes to the chain
const size_type left = total_elements - chain.size();
const size_type max_chain = (num_node < left) ? num_node : left;
- mem_address = static_cast<char *>(container_detail::to_raw_pointer
+ mem_address = static_cast<char *>(boost::movelib::to_raw_pointer
(chain.incorporate_after(chain.last(), void_pointer(mem_address), m_real_node_size, max_chain)));
//Now store remaining nodes in the free list
if(const size_type max_free = num_node - max_chain){
diff --git a/boost/container/detail/advanced_insert_int.hpp b/boost/container/detail/advanced_insert_int.hpp
index 1050857c46..20adb523a6 100644
--- a/boost/container/detail/advanced_insert_int.hpp
+++ b/boost/container/detail/advanced_insert_int.hpp
@@ -31,7 +31,7 @@
#include <boost/container/detail/type_traits.hpp>
#include <boost/container/detail/iterator.hpp>
#include <boost/container/detail/iterators.hpp>
-#include <boost/container/detail/iterator_to_raw_pointer.hpp>
+#include <boost/move/detail/iterator_to_raw_pointer.hpp>
#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
#include <boost/move/detail/fwd_macros.hpp>
#endif
@@ -157,7 +157,7 @@ struct insert_copy_proxy
void uninitialized_copy_n_and_update(Allocator &a, Iterator p, size_type n) const
{
BOOST_ASSERT(n == 1); (void)n;
- alloc_traits::construct( a, iterator_to_raw_pointer(p), v_);
+ alloc_traits::construct( a, boost::movelib::iterator_to_raw_pointer(p), v_);
}
void copy_n_and_update(Allocator &, Iterator p, size_type n) const
@@ -184,7 +184,7 @@ struct insert_move_proxy
void uninitialized_copy_n_and_update(Allocator &a, Iterator p, size_type n) const
{
BOOST_ASSERT(n == 1); (void)n;
- alloc_traits::construct( a, iterator_to_raw_pointer(p), ::boost::move(v_) );
+ alloc_traits::construct( a, boost::movelib::iterator_to_raw_pointer(p), ::boost::move(v_) );
}
void copy_n_and_update(Allocator &, Iterator p, size_type n) const
@@ -240,7 +240,7 @@ struct insert_nonmovable_emplace_proxy
void priv_uninitialized_copy_some_and_update(Allocator &a, const index_tuple<IdxPack...>&, Iterator p, size_type n)
{
BOOST_ASSERT(n == 1); (void)n;
- alloc_traits::construct( a, iterator_to_raw_pointer(p), ::boost::forward<Args>(get<IdxPack>(this->args_))... );
+ alloc_traits::construct( a, boost::movelib::iterator_to_raw_pointer(p), ::boost::forward<Args>(get<IdxPack>(this->args_))... );
}
protected:
@@ -354,7 +354,7 @@ struct insert_nonmovable_emplace_proxy##N\
void uninitialized_copy_n_and_update(Allocator &a, Iterator p, size_type n)\
{\
BOOST_ASSERT(n == 1); (void)n;\
- alloc_traits::construct(a, iterator_to_raw_pointer(p) BOOST_MOVE_I##N BOOST_MOVE_MFWD##N);\
+ alloc_traits::construct(a, boost::movelib::iterator_to_raw_pointer(p) BOOST_MOVE_I##N BOOST_MOVE_MFWD##N);\
}\
\
void copy_n_and_update(Allocator &, Iterator, size_type)\
diff --git a/boost/container/detail/algorithm.hpp b/boost/container/detail/algorithm.hpp
index 67e7876345..11844220e1 100644
--- a/boost/container/detail/algorithm.hpp
+++ b/boost/container/detail/algorithm.hpp
@@ -29,6 +29,128 @@ namespace container {
using boost::intrusive::algo_equal;
using boost::intrusive::algo_lexicographical_compare;
+template<class Func>
+class binder1st
+{
+ public:
+ typedef typename Func::second_argument_type argument_type;
+ typedef typename Func::result_type result_type;
+
+ binder1st(const Func& func, const typename Func::first_argument_type& arg)
+ : op(func), value(arg)
+ {}
+
+ result_type operator()(const argument_type& arg) const
+ { return op(value, arg); }
+
+ result_type operator()(argument_type& arg) const
+ { return op(value, arg); }
+
+ private:
+ Func op;
+ typename Func::first_argument_type value;
+};
+
+template<class Func, class T>
+inline binder1st<Func> bind1st(const Func& func, const T& arg)
+{ return boost::container::binder1st<Func>(func, arg); }
+
+template<class Func>
+class binder2nd
+{
+ public:
+ typedef typename Func::first_argument_type argument_type;
+ typedef typename Func::result_type result_type;
+
+ binder2nd(const Func& func, const typename Func::second_argument_type& arg)
+ : op(func), value(arg)
+ {}
+
+ result_type operator()(const argument_type& arg) const
+ { return op(arg, value); }
+
+ result_type operator()(argument_type& arg) const
+ { return op(arg, value); }
+
+ private:
+ Func op;
+ typename Func::second_argument_type value;
+};
+
+template<class Func, class T>
+inline binder2nd<Func> bind2nd(const Func& func, const T& arg)
+{
+ return (boost::container::binder2nd<Func>(func, arg));
+}
+
+template<class Func>
+class unary_negate
+{
+ public:
+ typedef typename Func::argument_type argument_type;
+ typedef typename Func::result_type result_type;
+
+ explicit unary_negate(const Func& func)
+ : m_func(func)
+ {}
+
+ bool operator()(const typename Func::argument_type& arg) const
+ { return !m_func(arg); }
+
+ private:
+ Func m_func;
+};
+
+template<class Func> inline
+unary_negate<Func> not1(const Func& func)
+{
+ return boost::container::unary_negate<Func>(func);
+}
+
+template<class InputIt, class UnaryPredicate>
+InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
+{
+ for (; first != last; ++first) {
+ if (p(*first)) {
+ return first;
+ }
+ }
+ return last;
+}
+
+template<class InputIt, class ForwardIt, class BinaryPredicate>
+InputIt find_first_of(InputIt first1, InputIt last1, ForwardIt first2, ForwardIt last2, BinaryPredicate p)
+{
+ for (; first1 != last1; ++first1) {
+ for (ForwardIt it = first2; it != last2; ++it) {
+ if (p(*first1, *it)) {
+ return first1;
+ }
+ }
+ }
+ return last1;
+}
+
+template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
+ForwardIt1 search(ForwardIt1 first1, ForwardIt1 last1,
+ ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p)
+{
+ for (; ; ++first1) {
+ ForwardIt1 it = first1;
+ for (ForwardIt2 it2 = first2; ; ++it, ++it2) {
+ if (it2 == last2) {
+ return first1;
+ }
+ if (it == last1) {
+ return last1;
+ }
+ if (!p(*it, *it2)) {
+ break;
+ }
+ }
+ }
+}
+
} //namespace container {
} //namespace boost {
diff --git a/boost/container/detail/copy_move_algo.hpp b/boost/container/detail/copy_move_algo.hpp
index dda311aa33..9044960e79 100644
--- a/boost/container/detail/copy_move_algo.hpp
+++ b/boost/container/detail/copy_move_algo.hpp
@@ -22,7 +22,7 @@
#include <boost/container/allocator_traits.hpp>
// container/detail
#include <boost/container/detail/iterator.hpp>
-#include <boost/container/detail/iterator_to_raw_pointer.hpp>
+#include <boost/move/detail/iterator_to_raw_pointer.hpp>
#include <boost/container/detail/mpl.hpp>
#include <boost/container/detail/type_traits.hpp>
#include <boost/container/detail/construct_in_place.hpp>
@@ -178,7 +178,7 @@ inline F memmove(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
typedef typename boost::container::iterator_traits<I>::value_type value_type;
typename boost::container::iterator_traits<I>::difference_type n = boost::container::iterator_distance(f, l);
if(n){
- std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n);
+ std::memmove(boost::movelib::iterator_to_raw_pointer(r), boost::movelib::iterator_to_raw_pointer(f), sizeof(value_type)*n);
boost::container::iterator_advance(r, n);
}
return r;
@@ -192,7 +192,7 @@ F memmove_n(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
{
typedef typename boost::container::iterator_traits<I>::value_type value_type;
if(n){
- std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n);
+ std::memmove(boost::movelib::iterator_to_raw_pointer(r), boost::movelib::iterator_to_raw_pointer(f), sizeof(value_type)*n);
boost::container::iterator_advance(r, n);
}
return r;
@@ -206,7 +206,7 @@ I memmove_n_source(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
{
if(n){
typedef typename boost::container::iterator_traits<I>::value_type value_type;
- std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n);
+ std::memmove(boost::movelib::iterator_to_raw_pointer(r), boost::movelib::iterator_to_raw_pointer(f), sizeof(value_type)*n);
boost::container::iterator_advance(f, n);
}
return f;
@@ -220,7 +220,7 @@ I memmove_n_source_dest(I f, U n, F &r) BOOST_NOEXCEPT_OR_NOTHROW
{
typedef typename boost::container::iterator_traits<I>::value_type value_type;
if(n){
- std::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n);
+ std::memmove(boost::movelib::iterator_to_raw_pointer(r), boost::movelib::iterator_to_raw_pointer(f), sizeof(value_type)*n);
boost::container::iterator_advance(f, n);
boost::container::iterator_advance(r, n);
}
@@ -295,13 +295,13 @@ inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F
F back = r;
BOOST_TRY{
while (f != l) {
- allocator_traits<Allocator>::construct(a, container_detail::iterator_to_raw_pointer(r), boost::move(*f));
+ allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), boost::move(*f));
++f; ++r;
}
}
BOOST_CATCH(...){
for (; back != r; ++back){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(back));
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
}
BOOST_RETHROW;
}
@@ -340,13 +340,13 @@ inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F
F back = r;
BOOST_TRY{
while (n--) {
- allocator_traits<Allocator>::construct(a, container_detail::iterator_to_raw_pointer(r), boost::move(*f));
+ allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), boost::move(*f));
++f; ++r;
}
}
BOOST_CATCH(...){
for (; back != r; ++back){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(back));
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
}
BOOST_RETHROW;
}
@@ -385,13 +385,13 @@ inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F
F back = r;
BOOST_TRY{
while (n--) {
- allocator_traits<Allocator>::construct(a, container_detail::iterator_to_raw_pointer(r), boost::move(*f));
+ allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), boost::move(*f));
++f; ++r;
}
}
BOOST_CATCH(...){
for (; back != r; ++back){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(back));
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
}
BOOST_RETHROW;
}
@@ -430,13 +430,13 @@ inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F
F back = r;
BOOST_TRY{
while (f != l) {
- allocator_traits<Allocator>::construct(a, container_detail::iterator_to_raw_pointer(r), *f);
+ allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), *f);
++f; ++r;
}
}
BOOST_CATCH(...){
for (; back != r; ++back){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(back));
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
}
BOOST_RETHROW;
}
@@ -475,13 +475,13 @@ inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F
F back = r;
BOOST_TRY{
while (n--) {
- allocator_traits<Allocator>::construct(a, container_detail::iterator_to_raw_pointer(r), *f);
+ allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), *f);
++f; ++r;
}
}
BOOST_CATCH(...){
for (; back != r; ++back){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(back));
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
}
BOOST_RETHROW;
}
@@ -520,13 +520,13 @@ inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F
F back = r;
BOOST_TRY{
while (n--) {
- boost::container::construct_in_place(a, container_detail::iterator_to_raw_pointer(r), f);
+ boost::container::construct_in_place(a, boost::movelib::iterator_to_raw_pointer(r), f);
++f; ++r;
}
}
BOOST_CATCH(...){
for (; back != r; ++back){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(back));
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
}
BOOST_RETHROW;
}
@@ -564,13 +564,13 @@ inline typename container_detail::disable_if_memzero_initializable<F, F>::type
F back = r;
BOOST_TRY{
while (n--) {
- allocator_traits<Allocator>::construct(a, container_detail::iterator_to_raw_pointer(r));
+ allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r));
++r;
}
}
BOOST_CATCH(...){
for (; back != r; ++back){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(back));
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
}
BOOST_RETHROW;
}
@@ -585,7 +585,7 @@ inline typename container_detail::enable_if_memzero_initializable<F, F>::type
uninitialized_value_init_alloc_n(Allocator &, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
{
typedef typename boost::container::iterator_traits<F>::value_type value_type;
- std::memset((void*)container_detail::iterator_to_raw_pointer(r), 0, sizeof(value_type)*n);
+ std::memset((void*)boost::movelib::iterator_to_raw_pointer(r), 0, sizeof(value_type)*n);
boost::container::iterator_advance(r, n);
return r;
}
@@ -611,13 +611,13 @@ inline F uninitialized_default_init_alloc_n(Allocator &a, typename boost::contai
F back = r;
BOOST_TRY{
while (n--) {
- allocator_traits<Allocator>::construct(a, container_detail::iterator_to_raw_pointer(r), default_init);
+ allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), default_init);
++r;
}
}
BOOST_CATCH(...){
for (; back != r; ++back){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(back));
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
}
BOOST_RETHROW;
}
@@ -647,13 +647,13 @@ inline void uninitialized_fill_alloc(Allocator &a, F f, F l, const T &t)
F back = f;
BOOST_TRY{
while (f != l) {
- allocator_traits<Allocator>::construct(a, container_detail::iterator_to_raw_pointer(f), t);
+ allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(f), t);
++f;
}
}
BOOST_CATCH(...){
for (; back != l; ++back){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(back));
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
}
BOOST_RETHROW;
}
@@ -683,13 +683,13 @@ inline F uninitialized_fill_alloc_n(Allocator &a, const T &v, typename boost::co
F back = r;
BOOST_TRY{
while (n--) {
- allocator_traits<Allocator>::construct(a, container_detail::iterator_to_raw_pointer(r), v);
+ allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), v);
++r;
}
}
BOOST_CATCH(...){
for (; back != r; ++back){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(back));
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
}
BOOST_RETHROW;
}
@@ -890,7 +890,7 @@ inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, F>
typedef typename boost::container::iterator_traits<I>::value_type value_type;
const typename boost::container::iterator_traits<I>::difference_type n = boost::container::iterator_distance(f, l);
r -= n;
- std::memmove((container_detail::iterator_to_raw_pointer)(r), (container_detail::iterator_to_raw_pointer)(f), sizeof(value_type)*n);
+ std::memmove((boost::movelib::iterator_to_raw_pointer)(r), (boost::movelib::iterator_to_raw_pointer)(f), sizeof(value_type)*n);
return r;
}
@@ -963,8 +963,9 @@ template
inline typename container_detail::disable_if_trivially_destructible<I, void>::type
destroy_alloc_n(Allocator &a, I f, U n)
{
- while(n--){
- allocator_traits<Allocator>::destroy(a, container_detail::iterator_to_raw_pointer(f));
+ while(n){
+ --n;
+ allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(f));
++f;
}
}
@@ -1021,9 +1022,9 @@ inline typename container_detail::enable_if_c
storage_type storage;
const std::size_t n_i_bytes = sizeof(value_type)*n_i;
- void *const large_ptr = static_cast<void*>(container_detail::iterator_to_raw_pointer(large_range_f));
- void *const short_ptr = static_cast<void*>(container_detail::iterator_to_raw_pointer(short_range_f));
- void *const stora_ptr = static_cast<void*>(container_detail::iterator_to_raw_pointer(storage));
+ void *const large_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(large_range_f));
+ void *const short_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(short_range_f));
+ void *const stora_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(storage));
std::memcpy(stora_ptr, large_ptr, n_i_bytes);
std::memcpy(large_ptr, short_ptr, n_i_bytes);
std::memcpy(short_ptr, stora_ptr, n_i_bytes);
@@ -1052,8 +1053,8 @@ inline typename container_detail::enable_if_c
const std::size_t sizeof_storage = sizeof(storage);
std::size_t n_i_bytes = sizeof(value_type)*n_i;
- char *large_ptr = static_cast<char*>(static_cast<void*>(container_detail::iterator_to_raw_pointer(large_range_f)));
- char *short_ptr = static_cast<char*>(static_cast<void*>(container_detail::iterator_to_raw_pointer(short_range_f)));
+ char *large_ptr = static_cast<char*>(static_cast<void*>(boost::movelib::iterator_to_raw_pointer(large_range_f)));
+ char *short_ptr = static_cast<char*>(static_cast<void*>(boost::movelib::iterator_to_raw_pointer(short_range_f)));
char *stora_ptr = static_cast<char*>(static_cast<void*>(&storage));
std::size_t szt_times = n_i_bytes/sizeof_storage;
diff --git a/boost/container/detail/destroyers.hpp b/boost/container/detail/destroyers.hpp
index 52b44c0363..b110561a4a 100644
--- a/boost/container/detail/destroyers.hpp
+++ b/boost/container/detail/destroyers.hpp
@@ -25,7 +25,7 @@
#include <boost/container/detail/workaround.hpp>
#include <boost/container/allocator_traits.hpp>
-#include <boost/container/detail/to_raw_pointer.hpp>
+#include <boost/move/detail/to_raw_pointer.hpp>
#include <boost/container/detail/version_type.hpp>
namespace boost {
@@ -152,7 +152,7 @@ struct scoped_destroy_deallocator
~scoped_destroy_deallocator()
{
if(m_ptr){
- AllocTraits::destroy(m_alloc, container_detail::to_raw_pointer(m_ptr));
+ AllocTraits::destroy(m_alloc, boost::movelib::to_raw_pointer(m_ptr));
priv_deallocate(m_ptr, alloc_version());
}
}
@@ -202,7 +202,7 @@ struct scoped_destructor_n
~scoped_destructor_n()
{
if(!m_p) return;
- value_type *raw_ptr = container_detail::to_raw_pointer(m_p);
+ value_type *raw_ptr = boost::movelib::to_raw_pointer(m_p);
while(m_n--){
AllocTraits::destroy(m_a, raw_ptr++);
}
@@ -317,7 +317,7 @@ class allocator_destroyer
void operator()(const pointer &p)
{
- AllocTraits::destroy(a_, container_detail::to_raw_pointer(p));
+ AllocTraits::destroy(a_, boost::movelib::to_raw_pointer(p));
this->priv_deallocate(p, alloc_version());
}
};
@@ -339,7 +339,7 @@ class allocator_destroyer_and_chain_builder
void operator()(const typename Allocator::pointer &p)
{
- allocator_traits<Allocator>::destroy(a_, container_detail::to_raw_pointer(p));
+ allocator_traits<Allocator>::destroy(a_, boost::movelib::to_raw_pointer(p));
c_.push_back(p);
}
};
diff --git a/boost/container/detail/flat_tree.hpp b/boost/container/detail/flat_tree.hpp
index 93984d18e5..9aab87308a 100644
--- a/boost/container/detail/flat_tree.hpp
+++ b/boost/container/detail/flat_tree.hpp
@@ -28,25 +28,30 @@
#include <boost/container/detail/pair.hpp>
#include <boost/container/vector.hpp>
+#include <boost/container/allocator_traits.hpp>
+
#include <boost/container/detail/value_init.hpp>
#include <boost/container/detail/destroyers.hpp>
#include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
#include <boost/container/detail/iterator.hpp>
#include <boost/container/detail/is_sorted.hpp>
-#include <boost/container/allocator_traits.hpp>
+#include <boost/container/detail/type_traits.hpp>
+#include <boost/container/detail/iterators.hpp>
+
#ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
#include <boost/intrusive/pointer_traits.hpp>
#endif
-#include <boost/container/detail/type_traits.hpp>
-#include <boost/container/detail/iterators.hpp>
+#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
+
#include <boost/move/make_unique.hpp>
+#include <boost/move/iterator.hpp>
#include <boost/move/adl_move_swap.hpp>
+#include <boost/move/algo/adaptive_sort.hpp>
+
#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
#include <boost/move/detail/fwd_macros.hpp>
#endif
-#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
-#include <boost/move/iterator.hpp>
namespace boost {
namespace container {
@@ -105,14 +110,17 @@ template <class Value, class KeyOfValue,
class Compare, class Allocator>
class flat_tree
{
- typedef boost::container::vector<Value, Allocator> vector_t;
+ public:
+ typedef boost::container::vector<Value, Allocator> sequence_type;
+
+ private:
typedef Allocator allocator_t;
typedef allocator_traits<Allocator> allocator_traits_type;
public:
typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare;
- private:
+ private:
struct Data
//Inherit from value_compare to do EBO
: public value_compare
@@ -121,48 +129,48 @@ class flat_tree
public:
Data()
- : value_compare(), m_vect()
+ : value_compare(), m_seq()
{}
- explicit Data(const Data &d)
- : value_compare(static_cast<const value_compare&>(d)), m_vect(d.m_vect)
+ explicit Data(const allocator_t &alloc)
+ : value_compare(), m_seq(alloc)
{}
- Data(BOOST_RV_REF(Data) d)
- : value_compare(boost::move(static_cast<value_compare&>(d))), m_vect(boost::move(d.m_vect))
+ explicit Data(const Compare &comp)
+ : value_compare(comp), m_seq()
{}
- Data(const Data &d, const Allocator &a)
- : value_compare(static_cast<const value_compare&>(d)), m_vect(d.m_vect, a)
+ Data(const Compare &comp, const allocator_t &alloc)
+ : value_compare(comp), m_seq(alloc)
{}
- Data(BOOST_RV_REF(Data) d, const Allocator &a)
- : value_compare(boost::move(static_cast<value_compare&>(d))), m_vect(boost::move(d.m_vect), a)
+ explicit Data(const Data &d)
+ : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq)
{}
- explicit Data(const Compare &comp)
- : value_compare(comp), m_vect()
+ Data(BOOST_RV_REF(Data) d)
+ : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq))
{}
- Data(const Compare &comp, const allocator_t &alloc)
- : value_compare(comp), m_vect(alloc)
+ Data(const Data &d, const Allocator &a)
+ : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq, a)
{}
- explicit Data(const allocator_t &alloc)
- : value_compare(), m_vect(alloc)
+ Data(BOOST_RV_REF(Data) d, const Allocator &a)
+ : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq), a)
{}
Data& operator=(BOOST_COPY_ASSIGN_REF(Data) d)
{
this->value_compare::operator=(d);
- m_vect = d.m_vect;
+ m_seq = d.m_seq;
return *this;
}
Data& operator=(BOOST_RV_REF(Data) d)
{
this->value_compare::operator=(boost::move(static_cast<value_compare &>(d)));
- m_vect = boost::move(d.m_vect);
+ m_seq = boost::move(d.m_seq);
return *this;
}
@@ -170,10 +178,10 @@ class flat_tree
{
value_compare& mycomp = *this, & othercomp = d;
boost::adl_move_swap(mycomp, othercomp);
- this->m_vect.swap(d.m_vect);
+ this->m_seq.swap(d.m_seq);
}
- vector_t m_vect;
+ sequence_type m_seq;
};
Data m_data;
@@ -181,23 +189,23 @@ class flat_tree
public:
- typedef typename vector_t::value_type value_type;
- typedef typename vector_t::pointer pointer;
- typedef typename vector_t::const_pointer const_pointer;
- typedef typename vector_t::reference reference;
- typedef typename vector_t::const_reference const_reference;
- typedef typename KeyOfValue::type key_type;
- typedef Compare key_compare;
- typedef typename vector_t::allocator_type allocator_type;
- typedef typename vector_t::size_type size_type;
- typedef typename vector_t::difference_type difference_type;
- typedef typename vector_t::iterator iterator;
- typedef typename vector_t::const_iterator const_iterator;
- typedef typename vector_t::reverse_iterator reverse_iterator;
- typedef typename vector_t::const_reverse_iterator const_reverse_iterator;
+ typedef typename sequence_type::value_type value_type;
+ typedef typename sequence_type::pointer pointer;
+ typedef typename sequence_type::const_pointer const_pointer;
+ typedef typename sequence_type::reference reference;
+ typedef typename sequence_type::const_reference const_reference;
+ typedef typename KeyOfValue::type key_type;
+ typedef Compare key_compare;
+ typedef typename sequence_type::allocator_type allocator_type;
+ typedef typename sequence_type::size_type size_type;
+ typedef typename sequence_type::difference_type difference_type;
+ typedef typename sequence_type::iterator iterator;
+ typedef typename sequence_type::const_iterator const_iterator;
+ typedef typename sequence_type::reverse_iterator reverse_iterator;
+ typedef typename sequence_type::const_reverse_iterator const_reverse_iterator;
//!Standard extension
- typedef allocator_type stored_allocator_type;
+ typedef allocator_type stored_allocator_type;
private:
typedef allocator_traits<stored_allocator_type> stored_allocator_traits;
@@ -211,14 +219,14 @@ class flat_tree
: m_data(comp)
{ }
- BOOST_CONTAINER_FORCEINLINE flat_tree(const Compare& comp, const allocator_type& a)
- : m_data(comp, a)
- { }
-
BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const allocator_type& a)
: m_data(a)
{ }
+ BOOST_CONTAINER_FORCEINLINE flat_tree(const Compare& comp, const allocator_type& a)
+ : m_data(comp, a)
+ { }
+
BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x)
: m_data(x.m_data)
{ }
@@ -237,46 +245,92 @@ class flat_tree
{ }
template <class InputIterator>
- flat_tree( ordered_range_t, InputIterator first, InputIterator last
- , const Compare& comp = Compare()
- , const allocator_type& a = allocator_type())
+ BOOST_CONTAINER_FORCEINLINE
+ flat_tree( ordered_range_t, InputIterator first, InputIterator last)
+ : m_data()
+ {
+ this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
+ BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
+ }
+
+ template <class InputIterator>
+ BOOST_CONTAINER_FORCEINLINE
+ flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
+ : m_data(comp)
+ {
+ this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
+ BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
+ }
+
+ template <class InputIterator>
+ BOOST_CONTAINER_FORCEINLINE
+ flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
: m_data(comp, a)
{
- this->m_data.m_vect.insert(this->m_data.m_vect.end(), first, last);
- BOOST_ASSERT((is_sorted)(this->m_data.m_vect.cbegin(), this->m_data.m_vect.cend(), this->priv_value_comp()));
+ this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
+ BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
+ }
+
+ template <class InputIterator>
+ BOOST_CONTAINER_FORCEINLINE
+ flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last)
+ : m_data()
+ {
+ this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
+ BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
}
template <class InputIterator>
- flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last
- , const Compare& comp = Compare()
- , const allocator_type& a = allocator_type())
+ BOOST_CONTAINER_FORCEINLINE
+ flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
+ : m_data(comp)
+ {
+ this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
+ BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
+ }
+
+ template <class InputIterator>
+ BOOST_CONTAINER_FORCEINLINE
+ flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
: m_data(comp, a)
{
- this->m_data.m_vect.insert(this->m_data.m_vect.end(), first, last);
- BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_vect.cbegin(), this->m_data.m_vect.cend(), this->priv_value_comp()));
+ this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
+ BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
}
template <class InputIterator>
- flat_tree( bool unique_insertion
- , InputIterator first, InputIterator last
- , const Compare& comp = Compare()
- , const allocator_type& a = allocator_type())
+ BOOST_CONTAINER_FORCEINLINE
+ flat_tree( bool unique_insertion, InputIterator first, InputIterator last)
+ : m_data()
+ {
+ this->priv_range_insertion_construct(unique_insertion, first, last);
+ }
+
+ template <class InputIterator>
+ BOOST_CONTAINER_FORCEINLINE
+ flat_tree( bool unique_insertion, InputIterator first, InputIterator last
+ , const Compare& comp)
+ : m_data(comp)
+ {
+ this->priv_range_insertion_construct(unique_insertion, first, last);
+ }
+
+ template <class InputIterator>
+ BOOST_CONTAINER_FORCEINLINE
+ flat_tree( bool unique_insertion, InputIterator first, InputIterator last
+ , const allocator_type& a)
+ : m_data(a)
+ {
+ this->priv_range_insertion_construct(unique_insertion, first, last);
+ }
+
+ template <class InputIterator>
+ BOOST_CONTAINER_FORCEINLINE
+ flat_tree( bool unique_insertion, InputIterator first, InputIterator last
+ , const Compare& comp, const allocator_type& a)
: m_data(comp, a)
{
- //Use cend() as hint to achieve linear time for
- //ordered ranges as required by the standard
- //for the constructor
- //Call end() every iteration as reallocation might have invalidated iterators
- if(unique_insertion){
- for ( ; first != last; ++first){
- this->insert_unique(this->cend(), *first);
- }
- }
- else{
- for ( ; first != last; ++first){
- this->insert_equal(this->cend(), *first);
- }
- }
+ this->priv_range_insertion_construct(unique_insertion, first, last);
}
BOOST_CONTAINER_FORCEINLINE ~flat_tree()
@@ -312,31 +366,31 @@ class flat_tree
{ return this->m_data; }
BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const
- { return this->m_data.m_vect.get_allocator(); }
+ { return this->m_data.m_seq.get_allocator(); }
BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const
- { return this->m_data.m_vect.get_stored_allocator(); }
+ { return this->m_data.m_seq.get_stored_allocator(); }
BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator()
- { return this->m_data.m_vect.get_stored_allocator(); }
+ { return this->m_data.m_seq.get_stored_allocator(); }
BOOST_CONTAINER_FORCEINLINE iterator begin()
- { return this->m_data.m_vect.begin(); }
+ { return this->m_data.m_seq.begin(); }
BOOST_CONTAINER_FORCEINLINE const_iterator begin() const
{ return this->cbegin(); }
BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const
- { return this->m_data.m_vect.begin(); }
+ { return this->m_data.m_seq.begin(); }
BOOST_CONTAINER_FORCEINLINE iterator end()
- { return this->m_data.m_vect.end(); }
+ { return this->m_data.m_seq.end(); }
BOOST_CONTAINER_FORCEINLINE const_iterator end() const
{ return this->cend(); }
BOOST_CONTAINER_FORCEINLINE const_iterator cend() const
- { return this->m_data.m_vect.end(); }
+ { return this->m_data.m_seq.end(); }
BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin()
{ return reverse_iterator(this->end()); }
@@ -357,13 +411,13 @@ class flat_tree
{ return const_reverse_iterator(this->cbegin()); }
BOOST_CONTAINER_FORCEINLINE bool empty() const
- { return this->m_data.m_vect.empty(); }
+ { return this->m_data.m_seq.empty(); }
BOOST_CONTAINER_FORCEINLINE size_type size() const
- { return this->m_data.m_vect.size(); }
+ { return this->m_data.m_seq.size(); }
BOOST_CONTAINER_FORCEINLINE size_type max_size() const
- { return this->m_data.m_vect.max_size(); }
+ { return this->m_data.m_seq.max_size(); }
BOOST_CONTAINER_FORCEINLINE void swap(flat_tree& other)
BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
@@ -395,14 +449,14 @@ class flat_tree
iterator insert_equal(const value_type& val)
{
iterator i = this->upper_bound(KeyOfValue()(val));
- i = this->m_data.m_vect.insert(i, val);
+ i = this->m_data.m_seq.insert(i, val);
return i;
}
iterator insert_equal(BOOST_RV_REF(value_type) mval)
{
iterator i = this->upper_bound(KeyOfValue()(mval));
- i = this->m_data.m_vect.insert(i, boost::move(mval));
+ i = this->m_data.m_seq.insert(i, boost::move(mval));
return i;
}
@@ -509,7 +563,7 @@ class flat_tree
>::type * = 0
#endif
)
- { this->m_data.m_vect.merge(first, last, static_cast<const value_compare &>(this->m_data)); }
+ { this->m_data.m_seq.merge(first, last, static_cast<const value_compare &>(this->m_data)); }
template <class InIt>
void insert_unique(ordered_unique_range_t, InIt first, InIt last
@@ -538,7 +592,7 @@ class flat_tree
>::type * = 0
#endif
)
- { this->m_data.m_vect.merge_unique(first, last, static_cast<const value_compare &>(this->m_data)); }
+ { this->m_data.m_seq.merge_unique(first, last, static_cast<const value_compare &>(this->m_data)); }
#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
@@ -606,7 +660,7 @@ class flat_tree
typedef typename emplace_functor_type<try_emplace_t, KeyType, Args...>::type func_t;
typedef emplace_iterator<value_type, func_t, difference_type> it_t;
func_t func(try_emplace_t(), ::boost::forward<KeyType>(key), ::boost::forward<Args>(args)...);
- ret.first = this->m_data.m_vect.insert(data.position, it_t(func), it_t());
+ ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());
}
return ret;
}
@@ -675,7 +729,7 @@ class flat_tree
typedef typename emplace_functor_type<try_emplace_t, KeyType BOOST_MOVE_I##N BOOST_MOVE_TARG##N>::type func_t;\
typedef emplace_iterator<value_type, func_t, difference_type> it_t;\
func_t func(try_emplace_t(), ::boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
- ret.first = this->m_data.m_vect.insert(data.position, it_t(func), it_t());\
+ ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());\
}\
return ret;\
}\
@@ -702,29 +756,29 @@ class flat_tree
typedef typename emplace_functor_type<KeyType, M>::type func_t;
typedef emplace_iterator<value_type, func_t, difference_type> it_t;
func_t func(boost::forward<KeyType>(key), boost::forward<M>(obj));
- ret.first = this->m_data.m_vect.insert(data.position, it_t(func), it_t());
+ ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());
}
return ret;
}
BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator position)
- { return this->m_data.m_vect.erase(position); }
+ { return this->m_data.m_seq.erase(position); }
size_type erase(const key_type& k)
{
std::pair<iterator,iterator > itp = this->equal_range(k);
size_type ret = static_cast<size_type>(itp.second-itp.first);
if (ret){
- this->m_data.m_vect.erase(itp.first, itp.second);
+ this->m_data.m_seq.erase(itp.first, itp.second);
}
return ret;
}
BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last)
- { return this->m_data.m_vect.erase(first, last); }
+ { return this->m_data.m_seq.erase(first, last); }
BOOST_CONTAINER_FORCEINLINE void clear()
- { this->m_data.m_vect.clear(); }
+ { this->m_data.m_seq.clear(); }
//! <b>Effects</b>: Tries to deallocate the excess of memory created
// with previous allocations. The size of the vector is unchanged
@@ -733,19 +787,19 @@ class flat_tree
//!
//! <b>Complexity</b>: Linear to size().
BOOST_CONTAINER_FORCEINLINE void shrink_to_fit()
- { this->m_data.m_vect.shrink_to_fit(); }
+ { this->m_data.m_seq.shrink_to_fit(); }
BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
- { return this->m_data.m_vect.nth(n); }
+ { return this->m_data.m_seq.nth(n); }
BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
- { return this->m_data.m_vect.nth(n); }
+ { return this->m_data.m_seq.nth(n); }
BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
- { return this->m_data.m_vect.index_of(p); }
+ { return this->m_data.m_seq.index_of(p); }
BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
- { return this->m_data.m_vect.index_of(p); }
+ { return this->m_data.m_seq.index_of(p); }
// set operations:
iterator find(const key_type& k)
@@ -793,7 +847,7 @@ class flat_tree
void merge_unique(flat_tree& source)
{
- this->m_data.m_vect.merge_unique
+ this->m_data.m_seq.merge_unique
( boost::make_move_iterator(source.begin())
, boost::make_move_iterator(source.end())
, static_cast<const value_compare &>(this->m_data));
@@ -801,7 +855,7 @@ class flat_tree
void merge_equal(flat_tree& source)
{
- this->m_data.m_vect.merge
+ this->m_data.m_seq.merge
( boost::make_move_iterator(source.begin())
, boost::make_move_iterator(source.end())
, static_cast<const value_compare &>(this->m_data));
@@ -832,10 +886,61 @@ class flat_tree
{ return this->priv_lower_bound_range(this->cbegin(), this->cend(), k); }
BOOST_CONTAINER_FORCEINLINE size_type capacity() const
- { return this->m_data.m_vect.capacity(); }
+ { return this->m_data.m_seq.capacity(); }
BOOST_CONTAINER_FORCEINLINE void reserve(size_type cnt)
- { this->m_data.m_vect.reserve(cnt); }
+ { this->m_data.m_seq.reserve(cnt); }
+
+ BOOST_CONTAINER_FORCEINLINE sequence_type extract_sequence()
+ {
+ return boost::move(m_data.m_seq);
+ }
+
+ BOOST_CONTAINER_FORCEINLINE sequence_type &get_sequence_ref()
+ {
+ return m_data.m_seq;
+ }
+
+ void adopt_sequence_equal(BOOST_RV_REF(sequence_type) seq)
+ {
+ sequence_type &tseq = m_data.m_seq;
+ boost::movelib::adaptive_sort
+ ( boost::movelib::iterator_to_raw_pointer(seq.begin())
+ , boost::movelib::iterator_to_raw_pointer(seq.end())
+ , this->priv_value_comp()
+ , boost::movelib::iterator_to_raw_pointer(tseq.begin() + tseq.size())
+ , tseq.capacity() - tseq.size());
+ tseq = boost::move(seq);
+ }
+
+ void adopt_sequence_equal(ordered_range_t, BOOST_RV_REF(sequence_type) seq)
+ {
+ BOOST_ASSERT((is_sorted)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
+ sequence_type &tseq = m_data.m_seq;
+ tseq = boost::move(seq);
+ }
+
+ void adopt_sequence_unique(BOOST_RV_REF(sequence_type) seq)
+ {
+ sequence_type &tseq = m_data.m_seq;
+ boost::movelib::adaptive_sort
+ ( boost::movelib::iterator_to_raw_pointer(seq.begin())
+ , boost::movelib::iterator_to_raw_pointer(seq.end())
+ , this->priv_value_comp()
+ , boost::movelib::iterator_to_raw_pointer(tseq.begin() + tseq.size())
+ , tseq.capacity() - tseq.size());
+ seq.erase( boost::movelib::unique
+ (seq.begin(), seq.end(), boost::movelib::negate<value_compare>(this->m_data.get_comp()))
+ , seq.cend());
+ tseq = boost::move(seq);
+ }
+
+ void adopt_sequence_unique(ordered_unique_range_t, BOOST_RV_REF(sequence_type) seq)
+ {
+ BOOST_ASSERT((is_sorted_and_unique)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
+ sequence_type &tseq = m_data.m_seq;
+ tseq = boost::move(seq);
+ }
BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_tree& x, const flat_tree& y)
{
@@ -864,6 +969,25 @@ class flat_tree
private:
+ template <class InputIterator>
+ void priv_range_insertion_construct( bool unique_insertion, InputIterator first, InputIterator last)
+ {
+ //Use cend() as hint to achieve linear time for
+ //ordered ranges as required by the standard
+ //for the constructor
+ //Call end() every iteration as reallocation might have invalidated iterators
+ if(unique_insertion){
+ for ( ; first != last; ++first){
+ this->insert_unique(this->cend(), *first);
+ }
+ }
+ else{
+ for ( ; first != last; ++first){
+ this->insert_equal(this->cend(), *first);
+ }
+ }
+ }
+
BOOST_CONTAINER_FORCEINLINE bool priv_in_range_or_end(const_iterator pos) const
{
return (this->begin() <= pos) && (pos <= this->end());
@@ -963,7 +1087,7 @@ class flat_tree
BOOST_CONTAINER_FORCEINLINE iterator priv_insert_commit
(insert_commit_data &commit_data, BOOST_FWD_REF(Convertible) convertible)
{
- return this->m_data.m_vect.insert
+ return this->m_data.m_seq.insert
( commit_data.position
, boost::forward<Convertible>(convertible));
}
diff --git a/boost/container/detail/iterator_to_raw_pointer.hpp b/boost/container/detail/iterator_to_raw_pointer.hpp
index 83736d8bb1..8c7c880035 100644
--- a/boost/container/detail/iterator_to_raw_pointer.hpp
+++ b/boost/container/detail/iterator_to_raw_pointer.hpp
@@ -18,38 +18,13 @@
# pragma once
#endif
-#include <boost/container/detail/iterator.hpp>
-#include <boost/container/detail/to_raw_pointer.hpp>
-#include <boost/intrusive/pointer_traits.hpp>
+#include <boost/move/detail/iterator_to_raw_pointer.hpp>
namespace boost {
namespace container {
namespace container_detail {
-template <class T>
-inline T* iterator_to_pointer(T* i)
-{ return i; }
-
-template <class Iterator>
-inline typename boost::container::iterator_traits<Iterator>::pointer
- iterator_to_pointer(const Iterator &i)
-{ return i.operator->(); }
-
-template <class Iterator>
-struct iterator_to_element_ptr
-{
- typedef typename boost::container::iterator_traits<Iterator>::pointer pointer;
- typedef typename boost::intrusive::pointer_traits<pointer>::element_type element_type;
- typedef element_type* type;
-};
-
-template <class Iterator>
-inline typename iterator_to_element_ptr<Iterator>::type
- iterator_to_raw_pointer(const Iterator &i)
-{
- return ::boost::intrusive::detail::to_raw_pointer
- ( ::boost::container::container_detail::iterator_to_pointer(i) );
-}
+using ::boost::movelib::iterator_to_raw_pointer;
} //namespace container_detail {
} //namespace container {
diff --git a/boost/container/detail/multiallocation_chain.hpp b/boost/container/detail/multiallocation_chain.hpp
index 32f87c8ae9..bce1b8651f 100644
--- a/boost/container/detail/multiallocation_chain.hpp
+++ b/boost/container/detail/multiallocation_chain.hpp
@@ -24,7 +24,7 @@
// container
#include <boost/container/container_fwd.hpp>
// container/detail
-#include <boost/container/detail/to_raw_pointer.hpp>
+#include <boost/move/detail/to_raw_pointer.hpp>
#include <boost/container/detail/transform_iterator.hpp>
#include <boost/container/detail/type_traits.hpp>
// intrusive
@@ -63,7 +63,7 @@ class basic_multiallocation_chain
pointer_traits<node_ptr> node_ptr_traits;
static node & to_node(const VoidPointer &p)
- { return *static_cast<node*>(static_cast<void*>(container_detail::to_raw_pointer(p))); }
+ { return *static_cast<node*>(static_cast<void*>(boost::movelib::to_raw_pointer(p))); }
static VoidPointer from_node(node &n)
{ return node_ptr_traits::pointer_to(n); }
@@ -152,7 +152,7 @@ class basic_multiallocation_chain
char_ptr prev_elem = elem;
elem += unit_bytes;
for(size_type i = 0; i != num_units-1; ++i, elem += unit_bytes){
- ::new (container_detail::to_raw_pointer(prev_elem)) void_pointer(elem);
+ ::new (boost::movelib::to_raw_pointer(prev_elem)) void_pointer(elem);
prev_elem = elem;
}
slist_impl_.incorporate_after(after_this, to_node_ptr(b), to_node_ptr(prev_elem), num_units);
diff --git a/boost/container/detail/node_alloc_holder.hpp b/boost/container/detail/node_alloc_holder.hpp
index 7ef5d2883e..b6e602e884 100644
--- a/boost/container/detail/node_alloc_holder.hpp
+++ b/boost/container/detail/node_alloc_holder.hpp
@@ -30,10 +30,10 @@
#include <boost/container/detail/allocator_version_traits.hpp>
#include <boost/container/detail/construct_in_place.hpp>
#include <boost/container/detail/destroyers.hpp>
-#include <boost/container/detail/iterator_to_raw_pointer.hpp>
+#include <boost/move/detail/iterator_to_raw_pointer.hpp>
#include <boost/container/detail/mpl.hpp>
#include <boost/container/detail/placement_new.hpp>
-#include <boost/container/detail/to_raw_pointer.hpp>
+#include <boost/move/detail/to_raw_pointer.hpp>
#include <boost/container/detail/type_traits.hpp>
#include <boost/container/detail/version_type.hpp>
// intrusive
@@ -106,23 +106,23 @@ struct node_alloc_holder
: members_(a)
{}
+ //Constructors for associative containers
+ node_alloc_holder(const value_compare &c, const ValAlloc &a)
+ : members_(a, c)
+ {}
+
explicit node_alloc_holder(const node_alloc_holder &x)
: members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()))
{}
+ node_alloc_holder(const node_alloc_holder &x, const value_compare &c)
+ : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()), c)
+ {}
+
explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x)
: members_(boost::move(x.node_alloc()))
{ this->icont().swap(x.icont()); }
- //Constructors for associative containers
- explicit node_alloc_holder(const value_compare &c, const ValAlloc &a)
- : members_(a, c)
- {}
-
- explicit node_alloc_holder(const value_compare &c, const node_alloc_holder &x)
- : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()), c)
- {}
-
explicit node_alloc_holder(const value_compare &c)
: members_(c)
{}
@@ -171,7 +171,7 @@ struct node_alloc_holder
node_deallocator.release();
//This does not throw
typedef typename Node::hook_type hook_type;
- ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
+ ::new(static_cast<hook_type*>(boost::movelib::to_raw_pointer(p)), boost_container_new_t()) hook_type;
return (p);
}
@@ -189,7 +189,7 @@ struct node_alloc_holder
BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
node_deallocator.release();\
typedef typename Node::hook_type hook_type;\
- ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;\
+ ::new(static_cast<hook_type*>(boost::movelib::to_raw_pointer(p)), boost_container_new_t()) hook_type;\
return (p);\
}\
//
@@ -207,7 +207,7 @@ struct node_alloc_holder
node_deallocator.release();
//This does not throw
typedef typename Node::hook_type hook_type;
- ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
+ ::new(static_cast<hook_type*>(boost::movelib::to_raw_pointer(p)), boost_container_new_t()) hook_type;
return (p);
}
@@ -230,13 +230,13 @@ struct node_alloc_holder
node_deallocator.release();
//This does not throw
typedef typename Node::hook_type hook_type;
- ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
+ ::new(static_cast<hook_type*>(boost::movelib::to_raw_pointer(p)), boost_container_new_t()) hook_type;
return (p);
}
void destroy_node(const NodePtr &nodep)
{
- allocator_traits<NodeAlloc>::destroy(this->node_alloc(), container_detail::to_raw_pointer(nodep));
+ allocator_traits<NodeAlloc>::destroy(this->node_alloc(), boost::movelib::to_raw_pointer(nodep));
this->deallocate_one(nodep);
}
@@ -266,7 +266,7 @@ struct node_alloc_holder
Deallocator node_deallocator(NodePtr(), nalloc);
container_detail::scoped_destructor<NodeAlloc> sdestructor(nalloc, 0);
while(n--){
- p = container_detail::iterator_to_raw_pointer(itbeg);
+ p = boost::movelib::iterator_to_raw_pointer(itbeg);
node_deallocator.set(p);
++itbeg;
//This can throw
diff --git a/boost/container/detail/node_pool_impl.hpp b/boost/container/detail/node_pool_impl.hpp
index 4febf19e90..024bf306c5 100644
--- a/boost/container/detail/node_pool_impl.hpp
+++ b/boost/container/detail/node_pool_impl.hpp
@@ -25,7 +25,7 @@
#include <boost/container/detail/math_functions.hpp>
#include <boost/container/detail/mpl.hpp>
#include <boost/container/detail/pool_common.hpp>
-#include <boost/container/detail/to_raw_pointer.hpp>
+#include <boost/move/detail/to_raw_pointer.hpp>
#include <boost/container/detail/type_traits.hpp>
#include <boost/intrusive/pointer_traits.hpp>
@@ -92,7 +92,7 @@ class private_node_pool_impl
//!Returns the segment manager. Never throws
segment_manager_base_type* get_segment_manager_base()const
- { return container_detail::to_raw_pointer(mp_segment_mngr_base); }
+ { return boost::movelib::to_raw_pointer(mp_segment_mngr_base); }
void *allocate_node()
{ return this->priv_alloc_node(); }
diff --git a/boost/container/detail/pair.hpp b/boost/container/detail/pair.hpp
index 4abff4b4d8..4755e569b2 100644
--- a/boost/container/detail/pair.hpp
+++ b/boost/container/detail/pair.hpp
@@ -35,16 +35,62 @@
#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
#include <boost/move/utility_core.hpp>
-#include<boost/move/detail/fwd_macros.hpp>
+#include <boost/move/detail/fwd_macros.hpp>
namespace boost {
namespace tuples {
struct null_type;
+template <
+ class T0, class T1, class T2,
+ class T3, class T4, class T5,
+ class T6, class T7, class T8,
+ class T9>
+class tuple;
+
} //namespace tuples {
} //namespace boost {
+namespace boost {
+namespace container {
+namespace pair_impl {
+
+template <class TupleClass>
+struct is_boost_tuple
+{
+ static const bool value = false;
+};
+
+template <
+ class T0, class T1, class T2,
+ class T3, class T4, class T5,
+ class T6, class T7, class T8,
+ class T9>
+struct is_boost_tuple< boost::tuples::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
+{
+ static const bool value = true;
+};
+
+template<class Tuple>
+struct disable_if_boost_tuple
+ : boost::container::container_detail::disable_if< is_boost_tuple<Tuple> >
+{};
+
+template<class T>
+struct is_tuple_null
+{
+ static const bool value = false;
+};
+
+template<>
+struct is_tuple_null<boost::tuples::null_type>
+{
+ static const bool value = true;
+};
+
+}}}
+
#if defined(BOOST_MSVC) && (_CPPLIB_VER == 520)
//MSVC 2010 tuple marker
namespace std { namespace tr1 { struct _Nil; }}
@@ -236,7 +282,12 @@ struct pair
BOOST_MOVE_I_IF(BOOST_MOVE_OR(N,M)) BOOST_MOVE_CLASS##N BOOST_MOVE_I_IF(BOOST_MOVE_AND(N,M)) BOOST_MOVE_CLASSQ##M > \
pair( piecewise_construct_t\
, BoostTuple<BOOST_MOVE_TARG##N BOOST_MOVE_I##N BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,N),::boost::tuples::null_type)> p\
- , BoostTuple<BOOST_MOVE_TARGQ##M BOOST_MOVE_I##M BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,M),::boost::tuples::null_type)> q)\
+ , BoostTuple<BOOST_MOVE_TARGQ##M BOOST_MOVE_I##M BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,M),::boost::tuples::null_type)> q\
+ , typename container_detail::enable_if_c\
+ < pair_impl::is_boost_tuple< BoostTuple<BOOST_MOVE_TARG##N BOOST_MOVE_I##N BOOST_MOVE_REPEAT(BOOST_MOVE_SUB(10,N),::boost::tuples::null_type)> >::value &&\
+ !(pair_impl::is_tuple_null<BOOST_MOVE_LAST_TARG##N>::value || pair_impl::is_tuple_null<BOOST_MOVE_LAST_TARGQ##M>::value) \
+ >::type* = 0\
+ )\
: first(BOOST_MOVE_TMPL_GET##N), second(BOOST_MOVE_TMPL_GETQ##M)\
{ (void)p; (void)q; }\
//
@@ -254,7 +305,8 @@ struct pair
{ (void) t1; (void)t2; }
public:
- template<template<class ...> class Tuple, class... Args1, class... Args2>
+ template< template<class ...> class Tuple, class... Args1, class... Args2
+ , class = typename pair_impl::disable_if_boost_tuple< Tuple<Args1...> >::type>
pair(piecewise_construct_t, Tuple<Args1...> t1, Tuple<Args2...> t2)
: pair(t1, t2, typename build_number_seq<sizeof...(Args1)>::type(), typename build_number_seq<sizeof...(Args2)>::type())
{}
@@ -270,7 +322,8 @@ struct pair
{ (void)t; return T(::boost::forward<Args>(get<Indexes>(t))...); }
public:
- template<template<class ...> class Tuple, class... Args1, class... Args2>
+ template< template<class ...> class Tuple, class... Args1, class... Args2
+ , class = typename pair_impl::disable_if_boost_tuple< Tuple<Args1...> >::type>
pair(piecewise_construct_t, Tuple<Args1...> t1, Tuple<Args2...> t2)
: first (build_from_args<first_type> (::boost::move(t1)))
, second (build_from_args<second_type>(::boost::move(t2)))
diff --git a/boost/container/detail/pair_key_mapped_of_value.hpp b/boost/container/detail/pair_key_mapped_of_value.hpp
new file mode 100644
index 0000000000..6112b87826
--- /dev/null
+++ b/boost/container/detail/pair_key_mapped_of_value.hpp
@@ -0,0 +1,55 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/container for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+#ifndef BOOST_CONTAINER_PAIR_KEY_MAPPED_OF_VALUE_HPP
+#define BOOST_CONTAINER_PAIR_KEY_MAPPED_OF_VALUE_HPP
+
+#ifndef BOOST_CONFIG_HPP
+# include <boost/config.hpp>
+#endif
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+# pragma once
+#endif
+
+#include <boost/container/detail/config_begin.hpp>
+#include <boost/container/detail/workaround.hpp>
+
+namespace boost {
+namespace container {
+
+template<class Key, class Mapped>
+struct pair_key_mapped_of_value
+{
+ typedef Key key_type;
+ typedef Mapped mapped_type;
+
+ template<class Pair>
+ const key_type & key_of_value(const Pair &p) const
+ { return p.first; }
+
+ template<class Pair>
+ const mapped_type & mapped_of_value(const Pair &p) const
+ { return p.second; }
+
+ template<class Pair>
+ key_type & key_of_value(Pair &p) const
+ { return const_cast<key_type&>(p.first); }
+
+ template<class Pair>
+ mapped_type & mapped_of_value(Pair &p) const
+ { return p.second; }
+
+};
+
+}}
+
+#include <boost/container/detail/config_end.hpp>
+
+#endif // BOOST_CONTAINER_PAIR_KEY_MAPPED_OF_VALUE_HPP
diff --git a/boost/container/detail/to_raw_pointer.hpp b/boost/container/detail/to_raw_pointer.hpp
deleted file mode 100644
index 0b4445a942..0000000000
--- a/boost/container/detail/to_raw_pointer.hpp
+++ /dev/null
@@ -1,33 +0,0 @@
-//////////////////////////////////////////////////////////////////////////////
-//
-// (C) Copyright Ion Gaztanaga 2014-2015. Distributed under the Boost
-// Software License, Version 1.0. (See accompanying file
-// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
-//
-// See http://www.boost.org/libs/container for documentation.
-//
-//////////////////////////////////////////////////////////////////////////////
-#ifndef BOOST_CONTAINER_DETAIL_TO_RAW_POINTER_HPP
-#define BOOST_CONTAINER_DETAIL_TO_RAW_POINTER_HPP
-
-#ifndef BOOST_CONFIG_HPP
-# include <boost/config.hpp>
-#endif
-
-#if defined(BOOST_HAS_PRAGMA_ONCE)
-# pragma once
-#endif
-
-#include <boost/intrusive/detail/to_raw_pointer.hpp>
-
-namespace boost {
-namespace container {
-namespace container_detail {
-
-using ::boost::intrusive::detail::to_raw_pointer;
-
-} //namespace container_detail {
-} //namespace container {
-} //namespace boost {
-
-#endif //#ifndef BOOST_CONTAINER_DETAIL_TO_RAW_POINTER_HPP
diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp
index 853d0ad843..99baf3a257 100644
--- a/boost/container/detail/tree.hpp
+++ b/boost/container/detail/tree.hpp
@@ -493,7 +493,7 @@ class tree
typedef boost::container::reverse_iterator
<const_iterator> const_reverse_iterator;
typedef node_handle
- < Node, value_type, allocator_type, void> node_type;
+ < NodeAlloc, void> node_type;
typedef insert_return_type_base
<iterator, node_type> insert_return_type;
@@ -509,7 +509,11 @@ class tree
: AllocHolder()
{}
- BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a = allocator_type())
+ BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp)
+ : AllocHolder(ValComp(comp))
+ {}
+
+ BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a)
: AllocHolder(ValComp(comp), a)
{}
@@ -518,85 +522,110 @@ class tree
{}
template <class InputIterator>
- tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp,
- const allocator_type& a
- #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- , typename container_detail::enable_if_or
- < void
- , container_detail::is_same<alloc_version, version_1>
- , container_detail::is_input_iterator<InputIterator>
- >::type * = 0
- #endif
- )
+ tree(bool unique_insertion, InputIterator first, InputIterator last)
+ : AllocHolder(value_compare(key_compare()))
+ {
+ this->tree_construct(unique_insertion, first, last);
+ //AllocHolder clears in case of exception
+ }
+
+ template <class InputIterator>
+ tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp)
+ : AllocHolder(value_compare(comp))
+ {
+ this->tree_construct(unique_insertion, first, last);
+ //AllocHolder clears in case of exception
+ }
+
+ template <class InputIterator>
+ tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a)
: AllocHolder(value_compare(comp), a)
{
+ this->tree_construct(unique_insertion, first, last);
+ //AllocHolder clears in case of exception
+ }
+
+ //construct with ordered range
+ template <class InputIterator>
+ tree( ordered_range_t, InputIterator first, InputIterator last)
+ : AllocHolder(value_compare(key_compare()))
+ {
+ this->tree_construct(ordered_range_t(), first, last);
+ }
+
+ template <class InputIterator>
+ tree( ordered_range_t, InputIterator first, InputIterator last, const key_compare& comp)
+ : AllocHolder(value_compare(comp))
+ {
+ this->tree_construct(ordered_range_t(), first, last);
+ }
+
+ template <class InputIterator>
+ tree( ordered_range_t, InputIterator first, InputIterator last
+ , const key_compare& comp, const allocator_type& a)
+ : AllocHolder(value_compare(comp), a)
+ {
+ this->tree_construct(ordered_range_t(), first, last);
+ }
+
+ private:
+
+ template <class InputIterator>
+ void tree_construct(bool unique_insertion, InputIterator first, InputIterator last)
+ {
//Use cend() as hint to achieve linear time for
//ordered ranges as required by the standard
//for the constructor
- const const_iterator end_it(this->cend());
if(unique_insertion){
+ const const_iterator end_it(this->cend());
for ( ; first != last; ++first){
this->insert_unique_convertible(end_it, *first);
}
}
else{
- for ( ; first != last; ++first){
- this->insert_equal_convertible(end_it, *first);
- }
+ this->tree_construct_non_unique(first, last);
}
}
template <class InputIterator>
- tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp,
- const allocator_type& a
+ void tree_construct_non_unique(InputIterator first, InputIterator last
#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- , typename container_detail::disable_if_or
+ , typename container_detail::enable_if_or
< void
, container_detail::is_same<alloc_version, version_1>
, container_detail::is_input_iterator<InputIterator>
>::type * = 0
#endif
)
- : AllocHolder(value_compare(comp), a)
{
- if(unique_insertion){
- //Use cend() as hint to achieve linear time for
- //ordered ranges as required by the standard
- //for the constructor
- const const_iterator end_it(this->cend());
- for ( ; first != last; ++first){
- this->insert_unique_convertible(end_it, *first);
- }
- }
- else{
- //Optimized allocation and construction
- this->allocate_many_and_construct
- ( first, boost::container::iterator_distance(first, last)
- , insert_equal_end_hint_functor<Node, Icont>(this->icont()));
+ //Use cend() as hint to achieve linear time for
+ //ordered ranges as required by the standard
+ //for the constructor
+ const const_iterator end_it(this->cend());
+ for ( ; first != last; ++first){
+ this->insert_equal_convertible(end_it, *first);
}
}
template <class InputIterator>
- tree( ordered_range_t, InputIterator first, InputIterator last
- , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type()
- #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- , typename container_detail::enable_if_or
+ void tree_construct_non_unique(InputIterator first, InputIterator last
+ #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+ , typename container_detail::disable_if_or
< void
, container_detail::is_same<alloc_version, version_1>
, container_detail::is_input_iterator<InputIterator>
>::type * = 0
- #endif
+ #endif
)
- : AllocHolder(value_compare(comp), a)
{
- for ( ; first != last; ++first){
- this->push_back_impl(*first);
- }
+ //Optimized allocation and construction
+ this->allocate_many_and_construct
+ ( first, boost::container::iterator_distance(first, last)
+ , insert_equal_end_hint_functor<Node, Icont>(this->icont()));
}
template <class InputIterator>
- tree( ordered_range_t, InputIterator first, InputIterator last
- , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type()
+ void tree_construct( ordered_range_t, InputIterator first, InputIterator last
#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
, typename container_detail::disable_if_or
< void
@@ -605,16 +634,34 @@ class tree
>::type * = 0
#endif
)
- : AllocHolder(value_compare(comp), a)
{
//Optimized allocation and construction
this->allocate_many_and_construct
( first, boost::container::iterator_distance(first, last)
, container_detail::push_back_functor<Node, Icont>(this->icont()));
+ //AllocHolder clears in case of exception
+ }
+
+ template <class InputIterator>
+ void tree_construct( ordered_range_t, InputIterator first, InputIterator last
+ #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+ , typename container_detail::enable_if_or
+ < void
+ , container_detail::is_same<alloc_version, version_1>
+ , container_detail::is_input_iterator<InputIterator>
+ >::type * = 0
+ #endif
+ )
+ {
+ for ( ; first != last; ++first){
+ this->push_back_impl(*first);
+ }
}
+ public:
+
BOOST_CONTAINER_FORCEINLINE tree(const tree& x)
- : AllocHolder(x.value_comp(), x)
+ : AllocHolder(x, x.value_comp())
{
this->icont().clone_from
(x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
@@ -630,6 +677,7 @@ class tree
{
this->icont().clone_from
(x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
+ //AllocHolder clears in case of exception
}
tree(BOOST_RV_REF(tree) x, const allocator_type &a)
@@ -642,6 +690,7 @@ class tree
this->icont().clone_from
(boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc()));
}
+ //AllocHolder clears in case of exception
}
BOOST_CONTAINER_FORCEINLINE ~tree()
@@ -1142,7 +1191,7 @@ class tree
this->insert_unique_check(hint, KeyOfValue()(nh.value()), data);
if(ret.second){
irt.inserted = true;
- irt.position = iterator(this->icont().insert_unique_commit(*nh.get_node_pointer(), data));
+ irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data));
nh.release();
}
else{
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-27 14:42:06 +0000