Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-09-17 08:25:06 

0001 ////////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost
0004 // Software License, Version 1.0. (See accompanying file
0005 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // See http://www.boost.org/libs/container for documentation.
0008 //
0009 ////////////////////////////////////////////////////////////////////////////////
0010 
0011 #ifndef BOOST_CONTAINER_FLAT_TREE_HPP
0012 #define BOOST_CONTAINER_FLAT_TREE_HPP
0013 
0014 #ifndef BOOST_CONFIG_HPP
0015 #  include <boost/config.hpp>
0016 #endif
0017 
0018 #if defined(BOOST_HAS_PRAGMA_ONCE)
0019 #  pragma once
0020 #endif
0021 
0022 #include <boost/container/detail/config_begin.hpp>
0023 #include <boost/container/detail/workaround.hpp>
0024 
0025 #include <boost/container/container_fwd.hpp>
0026 
0027 #include <boost/move/utility_core.hpp>
0028 
0029 #include <boost/container/vector.hpp>
0030 #include <boost/container/allocator_traits.hpp>
0031 
0032 #include <boost/container/detail/value_init.hpp>
0033 #include <boost/container/detail/destroyers.hpp>
0034 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
0035 #include <boost/container/detail/iterator.hpp>
0036 #include <boost/container/detail/is_sorted.hpp>
0037 #include <boost/container/detail/type_traits.hpp>
0038 #include <boost/container/detail/iterators.hpp>
0039 #include <boost/container/detail/mpl.hpp>
0040 #include <boost/container/detail/is_contiguous_container.hpp>
0041 #include <boost/container/detail/is_container.hpp>
0042 
0043 #include <boost/intrusive/detail/minimal_pair_header.hpp>      //pair
0044 
0045 #include <boost/move/iterator.hpp>
0046 #include <boost/move/adl_move_swap.hpp>
0047 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
0048 #include <boost/move/detail/to_raw_pointer.hpp>
0049 #include <boost/move/detail/force_ptr.hpp>
0050 #include <boost/move/detail/launder.hpp>
0051 #include <boost/move/algo/adaptive_sort.hpp>
0052 #include <boost/move/algo/detail/pdqsort.hpp>
0053 
0054 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0055 #include <boost/move/detail/fwd_macros.hpp>
0056 #endif
0057 
0058 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0059 
0060 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
0061 #pragma GCC diagnostic push
0062 #pragma GCC diagnostic ignored "-Wunused-result"
0063 #endif
0064 
0065 //merge_unique
0066 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME merge_unique
0067 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
0068 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
0069 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 3
0070 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 3
0071 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
0072 
0073 //merge_equal
0074 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME merge
0075 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
0076 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
0077 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 3
0078 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 3
0079 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
0080 
0081 //index_of
0082 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME index_of
0083 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
0084 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
0085 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
0086 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
0087 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
0088 
0089 //nth
0090 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME nth
0091 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
0092 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
0093 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
0094 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
0095 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
0096 
0097 //reserve
0098 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME reserve
0099 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
0100 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
0101 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
0102 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
0103 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
0104 
0105 //capacity
0106 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME capacity
0107 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
0108 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
0109 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 0
0110 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 0
0111 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
0112 
0113 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
0114 #pragma GCC diagnostic pop
0115 #endif
0116 
0117 
0118 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0119 
0120 namespace boost {
0121 namespace container {
0122 namespace dtl {
0123 
0124 
0125 ///////////////////////////////////////
0126 //
0127 // Helper functions to merge elements
0128 //
0129 ///////////////////////////////////////
0130 
0131 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(stored_allocator_type)
0132 
0133 ///////////////////////////////////////
0134 //
0135 //  flat_tree_container_inplace_merge
0136 //
0137 ///////////////////////////////////////
0138 template<class SequenceContainer, class Compare>
0139 inline void flat_tree_container_inplace_merge //is_contiguous_container == true
0140    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp , dtl::true_)
0141 {
0142    typedef typename SequenceContainer::value_type value_type;
0143    typedef typename SequenceContainer::size_type  size_type;
0144 
0145    value_type *const braw = boost::movelib::to_raw_pointer(dest.data());
0146    value_type *const iraw = boost::movelib::iterator_to_raw_pointer(it);
0147    //Don't use iterator_to_raw_pointer for end as debug iterators can assert when
0148    //"operator ->" is used with the end iterator
0149    value_type *const eraw = braw + dest.size();
0150    size_type dest_unused_storage_size = 0;
0151    value_type *const dest_unused_storage_addr =
0152       unused_storage<SequenceContainer>::get(dest, dest_unused_storage_size);
0153    boost::movelib::adaptive_merge
0154       (braw, iraw, eraw, comp, dest_unused_storage_addr, dest_unused_storage_size);
0155 }
0156 
0157 template<class SequenceContainer, class Compare>
0158 inline void flat_tree_container_inplace_merge //is_contiguous_container == false
0159    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp, dtl::false_)
0160 {
0161    boost::movelib::adaptive_merge(dest.begin(), it, dest.end(), comp);
0162 }
0163 
0164 ///////////////////////////////////////
0165 //
0166 //  flat_tree_container_inplace_sort_ending
0167 //
0168 ///////////////////////////////////////
0169 template<class SequenceContainer, class Compare>
0170 inline void flat_tree_container_inplace_sort_ending //is_contiguous_container == true
0171    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp, dtl::true_)
0172 {
0173    typedef typename SequenceContainer::value_type value_type;
0174    typedef typename SequenceContainer::size_type  size_type;
0175 
0176    value_type *const iraw = boost::movelib::iterator_to_raw_pointer(it);
0177    //Don't use iterator_to_raw_pointer for end as debug iterators can assert when
0178    //"operator ->" is used with the end iterator
0179    value_type* const eraw = boost::movelib::to_raw_pointer(dest.data()) + dest.size();
0180 
0181    size_type dest_unused_storage_size;
0182    value_type* const dest_unused_storage_addr =
0183       unused_storage<SequenceContainer>::get(dest, dest_unused_storage_size);
0184    boost::movelib::adaptive_sort
0185       (iraw, eraw, comp, dest_unused_storage_addr, dest_unused_storage_size);
0186 }
0187 
0188 template<class SequenceContainer, class Compare>
0189 inline void flat_tree_container_inplace_sort_ending //is_contiguous_container == false
0190    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp , dtl::false_)
0191 {
0192    boost::movelib::adaptive_sort(it, dest.end(), comp);
0193 }
0194 
0195 ///////////////////////////////////////
0196 //
0197 //          flat_tree_merge
0198 //
0199 ///////////////////////////////////////
0200 template<class SequenceContainer, class Iterator, class Compare>
0201 inline void flat_tree_merge_equal
0202    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::true_)
0203 {
0204    dest.merge(first, last, comp);
0205 }
0206 
0207 template<class SequenceContainer, class Iterator, class Compare>
0208 inline void flat_tree_merge_equal   //has_merge_unique == false
0209    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::false_)
0210 {
0211    if(first != last) {
0212       typedef typename SequenceContainer::iterator    iterator;
0213       iterator const it = dest.insert( dest.end(), first, last);
0214       BOOST_ASSERT((is_sorted)(it, dest.end(), comp));
0215       dtl::bool_<is_contiguous_container<SequenceContainer>::value> contiguous_tag;
0216       (flat_tree_container_inplace_merge)(dest, it, comp, contiguous_tag);
0217    }
0218 }
0219 
0220 ///////////////////////////////////////
0221 //
0222 //       flat_tree_merge_unique
0223 //
0224 ///////////////////////////////////////
0225 template<class SequenceContainer, class Iterator, class Compare>
0226 inline void flat_tree_merge_unique  //has_merge_unique == true
0227    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::true_)
0228 {
0229    dest.merge_unique(first, last, comp);
0230 }
0231 
0232 template<class SequenceContainer, class Iterator, class Compare>
0233 inline void flat_tree_merge_unique  //has_merge_unique == false
0234    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::false_)
0235 {
0236    if (first != last) {
0237       typedef typename SequenceContainer::iterator          iterator;
0238       typedef typename SequenceContainer::size_type         size_type;
0239       typedef typename SequenceContainer::difference_type   difference_type;
0240 
0241       size_type const old_sz = dest.size();
0242       iterator const first_new = dest.insert(dest.cend(), first, last);
0243       //We can't assert "is_sorted_and_unique" because the sequence can come from a multiset
0244       BOOST_ASSERT((is_sorted)(first_new, dest.end(), comp));
0245       iterator e = boost::movelib::inplace_set_unique_difference(first_new, dest.end(), dest.begin(), first_new, comp);
0246       dest.erase(e, dest.end());
0247       dtl::bool_<is_contiguous_container<SequenceContainer>::value> contiguous_tag;
0248       (flat_tree_container_inplace_merge)(dest, dest.begin() + difference_type(old_sz), comp, contiguous_tag);
0249    }
0250 }
0251 
0252 ///////////////////////////////////////
0253 //
0254 //         flat_tree_index_of
0255 //
0256 ///////////////////////////////////////
0257 template<class SequenceContainer, class Iterator>
0258 inline typename SequenceContainer::size_type
0259    flat_tree_index_of   // has_index_of == true
0260       (SequenceContainer& cont, Iterator p, dtl::true_)
0261 {
0262    return cont.index_of(p);
0263 }
0264 
0265 template<class SequenceContainer, class Iterator>
0266 inline typename SequenceContainer::size_type
0267    flat_tree_index_of   // has_index_of == false
0268       (SequenceContainer& cont, Iterator p, dtl::false_)
0269 {
0270    typedef typename SequenceContainer::size_type size_type;
0271    return static_cast<size_type>(p - cont.begin());
0272 }
0273 
0274 ///////////////////////////////////////
0275 //
0276 //         flat_tree_nth
0277 //
0278 ///////////////////////////////////////
0279 template<class Iterator, class SequenceContainer>
0280 inline Iterator
0281    flat_tree_nth  // has_nth == true
0282       (SequenceContainer& cont, typename SequenceContainer::size_type n, dtl::true_)
0283 {
0284    return cont.nth(n);
0285 }
0286 
0287 template<class Iterator, class SequenceContainer>
0288 inline Iterator
0289    flat_tree_nth  // has_nth == false
0290       (SequenceContainer& cont, typename SequenceContainer::size_type n, dtl::false_)
0291 {
0292    return cont.begin()+ typename SequenceContainer::difference_type(n);
0293 }
0294 
0295 ///////////////////////////////////////
0296 //
0297 //    flat_tree_get_stored_allocator
0298 //
0299 ///////////////////////////////////////
0300 template<class SequenceContainer>
0301 inline typename SequenceContainer::stored_allocator_type &
0302    flat_tree_get_stored_allocator   // has_get_stored_allocator == true
0303       (SequenceContainer& cont, dtl::true_)
0304 {
0305    return cont.get_stored_allocator();
0306 }
0307 
0308 template<class SequenceContainer>
0309 inline const typename SequenceContainer::stored_allocator_type &
0310    flat_tree_get_stored_allocator   // has_get_stored_allocator == true
0311       (const SequenceContainer& cont, dtl::true_)
0312 {
0313    return cont.get_stored_allocator();
0314 }
0315 
0316 template<class SequenceContainer>
0317 inline typename SequenceContainer::allocator_type
0318    flat_tree_get_stored_allocator   // has_get_stored_allocator == false
0319       (SequenceContainer& cont, dtl::false_)
0320 {
0321    return cont.get_allocator();
0322 }
0323 
0324 ///////////////////////////////////////
0325 //
0326 //    flat_tree_adopt_sequence_equal
0327 //
0328 ///////////////////////////////////////
0329 template<class SequenceContainer, class Compare>
0330 void flat_tree_sort_contiguous_to_adopt // is_contiguous_container == true
0331    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp)
0332 {
0333    typedef typename SequenceContainer::value_type value_type;
0334    typedef typename SequenceContainer::size_type  size_type;
0335 
0336    size_type tseq_unused_storage_size, seq_unused_storage_size;
0337    value_type* const tseq_unused_storage_addr =
0338       unused_storage<SequenceContainer>::get(tseq, tseq_unused_storage_size);
0339    value_type* const seq_unused_storage_addr  =
0340       unused_storage<SequenceContainer>::get(seq,  seq_unused_storage_size);
0341 
0342    tseq.clear();
0343    const bool use_tseq_storage = tseq_unused_storage_size > seq_unused_storage_size;
0344 
0345    value_type * const seq_beg = boost::movelib::iterator_to_raw_pointer(seq.data());
0346 
0347    boost::movelib::adaptive_sort
0348       ( seq_beg
0349       , seq_beg + seq.size()
0350       , comp
0351       , use_tseq_storage ? tseq_unused_storage_addr : seq_unused_storage_addr
0352       , use_tseq_storage ? tseq_unused_storage_size : seq_unused_storage_size);
0353 }
0354 
0355 template<class SequenceContainer, class Compare>
0356 inline void flat_tree_adopt_sequence_equal // is_contiguous_container == true
0357    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::true_)
0358 {
0359    flat_tree_sort_contiguous_to_adopt(tseq, boost::move(seq), comp);
0360    tseq = boost::move(seq);
0361 }
0362 
0363 template<class SequenceContainer, class Compare>
0364 inline void flat_tree_adopt_sequence_equal // is_contiguous_container == false
0365    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::false_)
0366 {
0367    boost::movelib::adaptive_sort(seq.begin(), seq.end(), comp);
0368    tseq = boost::move(seq);
0369 }
0370 
0371 ///////////////////////////////////////
0372 //
0373 //    flat_tree_adopt_sequence_unique
0374 //
0375 ///////////////////////////////////////
0376 template<class SequenceContainer, class Compare>
0377 void flat_tree_adopt_sequence_unique// is_contiguous_container == true
0378    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::true_)
0379 {
0380    typedef typename SequenceContainer::value_type value_type;
0381    value_type * const seq_beg = boost::movelib::iterator_to_raw_pointer(seq.data());
0382    boost::movelib::pdqsort
0383       ( seq_beg
0384       , seq_beg + seq.size()
0385       , comp);
0386    seq.erase(boost::movelib::unique
0387       (seq.begin(), seq.end(), boost::movelib::negate<Compare>(comp)), seq.cend());
0388    tseq = boost::move(seq);
0389 }
0390 
0391 template<class SequenceContainer, class Compare>
0392 void flat_tree_adopt_sequence_unique// is_contiguous_container == false
0393    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::false_)
0394 {
0395    boost::movelib::pdqsort(seq.begin(), seq.end(), comp);
0396    seq.erase(boost::movelib::unique
0397       (seq.begin(), seq.end(), boost::movelib::negate<Compare>(comp)), seq.cend());
0398    tseq = boost::move(seq);
0399 }
0400 
0401 ///////////////////////////////////////
0402 //
0403 //       flat_tree_reserve
0404 //
0405 ///////////////////////////////////////
0406 template<class SequenceContainer>
0407 inline void // has_reserve == true
0408    flat_tree_reserve(SequenceContainer &tseq, typename SequenceContainer::size_type cap, dtl::true_)
0409 {
0410    tseq.reserve(cap);
0411 }
0412 
0413 template<class SequenceContainer>
0414 inline void // has_reserve == false
0415    flat_tree_reserve(SequenceContainer &, typename SequenceContainer::size_type, dtl::false_)
0416 {
0417 }
0418 
0419 ///////////////////////////////////////
0420 //
0421 //       flat_tree_capacity
0422 //
0423 ///////////////////////////////////////
0424 template<class SequenceContainer>   // has_capacity == true
0425 inline typename SequenceContainer::size_type
0426    flat_tree_capacity(const SequenceContainer &tseq, dtl::true_)
0427 {
0428    return tseq.capacity();
0429 }
0430 
0431 template<class SequenceContainer>   // has_capacity == false
0432 inline typename SequenceContainer::size_type
0433    flat_tree_capacity(const SequenceContainer &tseq, dtl::false_)
0434 {
0435    return tseq.size();
0436 }
0437 
0438 ///////////////////////////////////////
0439 //
0440 //       flat_tree_value_compare
0441 //
0442 ///////////////////////////////////////
0443 
0444 template<class Compare, class Value, class KeyOfValue>
0445 class flat_tree_value_compare
0446    : private Compare
0447 {
0448    typedef Value              first_argument_type;
0449    typedef Value              second_argument_type;
0450    typedef bool               return_type;
0451    public:
0452    inline flat_tree_value_compare()
0453       : Compare()
0454    {}
0455 
0456    inline flat_tree_value_compare(const Compare &pred)
0457       : Compare(pred)
0458    {}
0459 
0460    inline bool operator()(const Value& lhs, const Value& rhs) const
0461    {
0462       KeyOfValue key_extract;
0463       return Compare::operator()(key_extract(lhs), key_extract(rhs));
0464    }
0465 
0466    inline const Compare &get_comp() const
0467       {  return *this;  }
0468 
0469    inline Compare &get_comp()
0470       {  return *this;  }
0471 };
0472 
0473 
0474 ///////////////////////////////////////
0475 //
0476 //       select_flat_tree_container_type
0477 //
0478 ///////////////////////////////////////
0479 template < class Value, class AllocatorOrContainer
0480          , bool = boost::container::dtl::is_container<AllocatorOrContainer>::value
0481          >
0482 struct select_flat_tree_container_type
0483 {
0484    typedef AllocatorOrContainer type;
0485 };
0486 
0487 template <class Value, class AllocatorOrVoid>
0488 struct select_flat_tree_container_type<Value, AllocatorOrVoid, false>
0489 {
0490    typedef boost::container::vector<Value, AllocatorOrVoid> type;
0491 };
0492 
0493 
0494 ///////////////////////////////////////
0495 //
0496 //          flat_tree
0497 //
0498 ///////////////////////////////////////
0499 template <class Value, class KeyOfValue,
0500           class Compare, class AllocatorOrContainer>
0501 class flat_tree
0502 {
0503    public:
0504    typedef typename select_flat_tree_container_type<Value, AllocatorOrContainer>::type container_type;
0505    typedef container_type sequence_type;  //For backwards compatibility
0506 
0507    private:
0508    typedef typename container_type::allocator_type        allocator_t;
0509    typedef allocator_traits<allocator_t>                 allocator_traits_type;
0510 
0511    public:
0512    typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare;
0513 
0514    private:
0515    
0516    struct Data
0517       //Inherit from value_compare to do EBO
0518       : public value_compare
0519    {
0520       BOOST_COPYABLE_AND_MOVABLE(Data)
0521 
0522       public:
0523       inline Data()
0524          : value_compare(), m_seq()
0525       {}
0526 
0527       inline explicit Data(const allocator_t &alloc)
0528          : value_compare(), m_seq(alloc)
0529       {}
0530 
0531       inline explicit Data(const Compare &comp)
0532          : value_compare(comp), m_seq()
0533       {}
0534 
0535       inline Data(const Compare &comp, const allocator_t &alloc)
0536          : value_compare(comp), m_seq(alloc)
0537       {}
0538 
0539       inline explicit Data(const Data &d)
0540          : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq)
0541       {}
0542 
0543       inline Data(BOOST_RV_REF(Data) d)
0544          : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq))
0545       {}
0546 
0547       inline Data(const Data &d, const allocator_t &a)
0548          : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq, a)
0549       {}
0550 
0551       inline Data(BOOST_RV_REF(Data) d, const allocator_t &a)
0552          : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq), a)
0553       {}
0554 
0555       Data& operator=(BOOST_COPY_ASSIGN_REF(Data) d)
0556       {
0557          this->value_compare::operator=(d);
0558          m_seq = d.m_seq;
0559          return *this;
0560       }
0561 
0562       Data& operator=(BOOST_RV_REF(Data) d)
0563       {
0564          this->value_compare::operator=(boost::move(static_cast<value_compare &>(d)));
0565          m_seq = boost::move(d.m_seq);
0566          return *this;
0567       }
0568 
0569       void swap(Data &d)
0570       {
0571          value_compare& mycomp    = *this, & othercomp = d;
0572          boost::adl_move_swap(mycomp, othercomp);
0573          this->m_seq.swap(d.m_seq);
0574       }
0575 
0576       container_type m_seq;
0577    };
0578 
0579    Data m_data;
0580    BOOST_COPYABLE_AND_MOVABLE(flat_tree)
0581 
0582    public:
0583 
0584    typedef typename container_type::value_type              value_type;
0585    typedef typename container_type::pointer                 pointer;
0586    typedef typename container_type::const_pointer           const_pointer;
0587    typedef typename container_type::reference               reference;
0588    typedef typename container_type::const_reference         const_reference;
0589    typedef typename KeyOfValue::type                        key_type;
0590    typedef Compare                                          key_compare;
0591    typedef typename container_type::allocator_type          allocator_type;
0592    typedef typename container_type::size_type               size_type;
0593    typedef typename container_type::difference_type         difference_type;
0594    typedef typename container_type::iterator                iterator;
0595    typedef typename container_type::const_iterator          const_iterator;
0596    typedef typename container_type::reverse_iterator        reverse_iterator;
0597    typedef typename container_type::const_reverse_iterator  const_reverse_iterator;
0598 
0599    //`allocator_type::value_type` must match container's `value type`. If this
0600    //assertion fails, please review your allocator definition. 
0601    BOOST_CONTAINER_STATIC_ASSERT((is_same<value_type, typename allocator_traits_type::value_type>::value));
0602 
0603    //!Standard extension
0604    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
0605       (boost::container::dtl::, container_type
0606       ,stored_allocator_type, allocator_type)               stored_allocator_type;
0607 
0608    BOOST_STATIC_CONSTEXPR bool has_stored_allocator_type =
0609       BOOST_INTRUSIVE_HAS_TYPE(boost::container::dtl::, container_type, stored_allocator_type);
0610 
0611    private:
0612    typedef allocator_traits<stored_allocator_type> stored_allocator_traits;
0613 
0614    public:
0615    typedef typename dtl::if_c
0616       <has_stored_allocator_type, const stored_allocator_type &, allocator_type>::type get_stored_allocator_const_return_t;
0617 
0618    typedef typename dtl::if_c
0619       <has_stored_allocator_type, stored_allocator_type &, allocator_type>::type get_stored_allocator_noconst_return_t;
0620 
0621    inline flat_tree()
0622       : m_data()
0623    { }
0624 
0625    inline explicit flat_tree(const Compare& comp)
0626       : m_data(comp)
0627    { }
0628 
0629    inline explicit flat_tree(const allocator_type& a)
0630       : m_data(a)
0631    { }
0632 
0633    inline flat_tree(const Compare& comp, const allocator_type& a)
0634       : m_data(comp, a)
0635    { }
0636 
0637    inline flat_tree(const flat_tree& x)
0638       :  m_data(x.m_data)
0639    { }
0640 
0641    inline flat_tree(BOOST_RV_REF(flat_tree) x)
0642       BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
0643       :  m_data(boost::move(x.m_data))
0644    { }
0645 
0646    inline flat_tree(const flat_tree& x, const allocator_type &a)
0647       :  m_data(x.m_data, a)
0648    { }
0649 
0650    inline flat_tree(BOOST_RV_REF(flat_tree) x, const allocator_type &a)
0651       :  m_data(boost::move(x.m_data), a)
0652    { }
0653 
0654    template <class InputIterator>
0655    inline
0656    flat_tree( ordered_range_t, InputIterator first, InputIterator last)
0657       : m_data()
0658    {
0659       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
0660       BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
0661    }
0662 
0663    template <class InputIterator>
0664    inline
0665    flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
0666       : m_data(comp)
0667    {
0668       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
0669       BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
0670    }
0671 
0672    template <class InputIterator>
0673    inline
0674    flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
0675       : m_data(comp, a)
0676    {
0677       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
0678       BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
0679    }
0680 
0681    template <class InputIterator>
0682    inline
0683    flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last)
0684       : m_data()
0685    {
0686       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
0687       BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
0688    }
0689 
0690    template <class InputIterator>
0691    inline
0692    flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
0693       : m_data(comp)
0694    {
0695       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
0696       BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
0697    }
0698 
0699    template <class InputIterator>
0700    inline
0701    flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
0702       : m_data(comp, a)
0703    {
0704       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
0705       BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
0706    }
0707 
0708    template <class InputIterator>
0709    inline
0710    flat_tree( bool unique_insertion, InputIterator first, InputIterator last)
0711       : m_data()
0712    {
0713       this->priv_range_insertion_construct(unique_insertion, first, last);
0714    }
0715 
0716    template <class InputIterator>
0717    inline
0718    flat_tree( bool unique_insertion, InputIterator first, InputIterator last
0719             , const Compare& comp)
0720       : m_data(comp)
0721    {
0722       this->priv_range_insertion_construct(unique_insertion, first, last);
0723    }
0724 
0725    template <class InputIterator>
0726    inline
0727    flat_tree( bool unique_insertion, InputIterator first, InputIterator last
0728             , const allocator_type& a)
0729       : m_data(a)
0730    {
0731       this->priv_range_insertion_construct(unique_insertion, first, last);
0732    }
0733 
0734    template <class InputIterator>
0735    inline
0736    flat_tree( bool unique_insertion, InputIterator first, InputIterator last
0737             , const Compare& comp, const allocator_type& a)
0738       : m_data(comp, a)
0739    {
0740       this->priv_range_insertion_construct(unique_insertion, first, last);
0741    }
0742 
0743    inline ~flat_tree()
0744    {
0745    }
0746 
0747    inline flat_tree&  operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x)
0748    {  m_data = x.m_data;   return *this;  }
0749 
0750    inline flat_tree&  operator=(BOOST_RV_REF(flat_tree) x)
0751       BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
0752                           allocator_traits_type::is_always_equal::value) &&
0753                            boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
0754    {  m_data = boost::move(x.m_data); return *this;  }
0755 
0756    inline const value_compare &priv_value_comp() const
0757    { return static_cast<const value_compare &>(this->m_data); }
0758 
0759    inline value_compare &priv_value_comp()
0760    { return static_cast<value_compare &>(this->m_data); }
0761 
0762    inline const key_compare &priv_key_comp() const
0763    { return this->priv_value_comp().get_comp(); }
0764 
0765    inline key_compare &priv_key_comp()
0766    { return this->priv_value_comp().get_comp(); }
0767 
0768    struct insert_commit_data
0769    {
0770       const_iterator position;
0771    };
0772 
0773    public:
0774    // accessors:
0775    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0776       Compare key_comp() const
0777    { return this->m_data.get_comp(); }
0778 
0779    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0780       value_compare value_comp() const
0781    { return this->m_data; }
0782 
0783    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0784       allocator_type get_allocator() const
0785    { return this->m_data.m_seq.get_allocator(); }
0786 
0787    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0788       get_stored_allocator_const_return_t get_stored_allocator() const
0789    {
0790       return flat_tree_get_stored_allocator(this->m_data.m_seq, dtl::bool_<has_stored_allocator_type>());
0791    }
0792 
0793    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0794       get_stored_allocator_noconst_return_t get_stored_allocator()
0795    {
0796       return flat_tree_get_stored_allocator(this->m_data.m_seq, dtl::bool_<has_stored_allocator_type>());
0797    }
0798 
0799    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0800       iterator begin()
0801    { return this->m_data.m_seq.begin(); }
0802 
0803    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0804       const_iterator begin() const
0805    { return this->cbegin(); }
0806 
0807    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0808       const_iterator cbegin() const
0809    { return this->m_data.m_seq.begin(); }
0810 
0811    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0812       iterator end()
0813    { return this->m_data.m_seq.end(); }
0814 
0815    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0816       const_iterator end() const
0817    { return this->cend(); }
0818 
0819    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0820       const_iterator cend() const
0821    { return this->m_data.m_seq.end(); }
0822 
0823    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0824       reverse_iterator rbegin()
0825    { return reverse_iterator(this->end()); }
0826 
0827    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0828       const_reverse_iterator rbegin() const
0829    {  return this->crbegin();  }
0830 
0831    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0832       const_reverse_iterator crbegin() const
0833    {  return const_reverse_iterator(this->cend());  }
0834 
0835    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0836       reverse_iterator rend()
0837    { return reverse_iterator(this->begin()); }
0838 
0839    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0840       const_reverse_iterator rend() const
0841    { return this->crend(); }
0842 
0843    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0844       const_reverse_iterator crend() const
0845    { return const_reverse_iterator(this->cbegin()); }
0846 
0847    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0848       bool empty() const
0849    { return this->m_data.m_seq.empty(); }
0850 
0851    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0852       size_type size() const
0853    { return this->m_data.m_seq.size(); }
0854 
0855    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0856       size_type max_size() const
0857    { return this->m_data.m_seq.max_size(); }
0858 
0859    inline void swap(flat_tree& other)
0860       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
0861                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value )
0862    {  this->m_data.swap(other.m_data);  }
0863 
0864    public:
0865    // insert/erase
0866    std::pair<iterator,bool> insert_unique(const value_type& val)
0867    {
0868       std::pair<iterator,bool> ret;
0869       insert_commit_data data;
0870       ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data);
0871       ret.first = ret.second ? this->priv_insert_commit(data, val)
0872                              : this->begin() + (data.position - this->cbegin());
0873                              //: iterator(vector_iterator_get_ptr(data.position));
0874       return ret;
0875    }
0876 
0877    std::pair<iterator,bool> insert_unique(BOOST_RV_REF(value_type) val)
0878    {
0879       std::pair<iterator,bool> ret;
0880       insert_commit_data data;
0881       ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data);
0882       ret.first = ret.second ? this->priv_insert_commit(data, boost::move(val))
0883                              : this->begin() + (data.position - this->cbegin());
0884                              //: iterator(vector_iterator_get_ptr(data.position));
0885       return ret;
0886    }
0887 
0888    iterator insert_equal(const value_type& val)
0889    {
0890       iterator i = this->upper_bound(KeyOfValue()(val));
0891       i = this->m_data.m_seq.insert(i, val);
0892       return i;
0893    }
0894 
0895    iterator insert_equal(BOOST_RV_REF(value_type) mval)
0896    {
0897       iterator i = this->upper_bound(KeyOfValue()(mval));
0898       i = this->m_data.m_seq.insert(i, boost::move(mval));
0899       return i;
0900    }
0901 
0902    iterator insert_unique(const_iterator hint, const value_type& val)
0903    {
0904       BOOST_ASSERT(this->priv_in_range_or_end(hint));
0905       insert_commit_data data;
0906       return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
0907             ? this->priv_insert_commit(data, val)
0908             : this->begin() + (data.position - this->cbegin());
0909             //: iterator(vector_iterator_get_ptr(data.position));
0910    }
0911 
0912    iterator insert_unique(const_iterator hint, BOOST_RV_REF(value_type) val)
0913    {
0914       BOOST_ASSERT(this->priv_in_range_or_end(hint));
0915       insert_commit_data data;
0916       return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
0917          ? this->priv_insert_commit(data, boost::move(val))
0918          : this->begin() + (data.position - this->cbegin());
0919          //: iterator(vector_iterator_get_ptr(data.position));
0920    }
0921 
0922    iterator insert_equal(const_iterator hint, const value_type& val)
0923    {
0924       BOOST_ASSERT(this->priv_in_range_or_end(hint));
0925       insert_commit_data data;
0926       this->priv_insert_equal_prepare(hint, val, data);
0927       return this->priv_insert_commit(data, val);
0928    }
0929 
0930    iterator insert_equal(const_iterator hint, BOOST_RV_REF(value_type) mval)
0931    {
0932       BOOST_ASSERT(this->priv_in_range_or_end(hint));
0933       insert_commit_data data;
0934       this->priv_insert_equal_prepare(hint, mval, data);
0935       return this->priv_insert_commit(data, boost::move(mval));
0936    }
0937 
0938    template <class InIt>
0939    void insert_unique(InIt first, InIt last)
0940    {
0941       dtl::bool_<is_contiguous_container<container_type>::value> contiguous_tag;
0942       container_type &seq = this->m_data.m_seq;
0943       value_compare &val_cmp = this->priv_value_comp();
0944 
0945       //Step 1: put new elements in the back
0946       typename container_type::iterator const it = seq.insert(seq.cend(), first, last);
0947 
0948       //Step 2: sort them
0949       boost::movelib::pdqsort(it, seq.end(), val_cmp);
0950 
0951       //Step 3: only left unique values from the back not already present in the original range
0952       typename container_type::iterator const e = boost::movelib::inplace_set_unique_difference
0953          (it, seq.end(), seq.begin(), it, val_cmp);
0954 
0955       //it might be invalidated by erasing [e, seq.end) if e == it, so check it before
0956       const bool remaining = e != it;
0957       seq.erase(e, seq.cend());
0958       if (remaining)
0959       {
0960          //Step 4: merge both ranges
0961          (flat_tree_container_inplace_merge)(seq, it, this->priv_value_comp(), contiguous_tag);
0962       }
0963    }
0964 
0965    template <class InIt>
0966    void insert_equal(InIt first, InIt last)
0967    {
0968       if (first != last) {
0969          dtl::bool_<is_contiguous_container<container_type>::value> contiguous_tag;
0970          container_type &seq = this->m_data.m_seq;
0971          typename container_type::iterator const it = seq.insert(seq.cend(), first, last);
0972          (flat_tree_container_inplace_sort_ending)(seq, it, this->priv_value_comp(), contiguous_tag);
0973          (flat_tree_container_inplace_merge)      (seq, it, this->priv_value_comp(), contiguous_tag);
0974       }
0975    }
0976 
0977    //Ordered
0978 
0979    template <class InIt>
0980    void insert_equal(ordered_range_t, InIt first, InIt last)
0981    {
0982       const bool value = boost::container::dtl::
0983          has_member_function_callable_with_merge_unique<container_type, InIt, InIt, value_compare>::value;
0984       (flat_tree_merge_equal)(this->m_data.m_seq, first, last, this->priv_value_comp(), dtl::bool_<value>());
0985    }
0986 
0987    template <class InIt>
0988    void insert_unique(ordered_unique_range_t, InIt first, InIt last)
0989    {
0990       const bool value = boost::container::dtl::
0991          has_member_function_callable_with_merge_unique<container_type, InIt, InIt, value_compare>::value;
0992       (flat_tree_merge_unique)(this->m_data.m_seq, first, last, this->priv_value_comp(), dtl::bool_<value>());
0993    }
0994 
0995    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0996 
0997    template <class... Args>
0998    std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args)
0999    {
1000       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
1001       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
1002       stored_allocator_traits::construct(a, (value_type *)(&v), ::boost::forward<Args>(args)... );
1003       value_type *pval = move_detail::launder_cast<value_type *>(&v);
1004       value_destructor<stored_allocator_type, value_type> d(a, *pval);
1005       return this->insert_unique(::boost::move(*pval));
1006    }
1007 
1008    template <class... Args>
1009    iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args)
1010    {
1011       //hint checked in insert_unique
1012       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
1013       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
1014       stored_allocator_traits::construct(a, (value_type*)(&v), ::boost::forward<Args>(args)... );
1015       value_type *pval = move_detail::launder_cast<value_type *>(&v);
1016       value_destructor<stored_allocator_type, value_type> d(a, *pval);
1017       return this->insert_unique(hint, ::boost::move(*pval));
1018    }
1019 
1020    template <class... Args>
1021    iterator emplace_equal(BOOST_FWD_REF(Args)... args)
1022    {
1023       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
1024       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
1025       stored_allocator_traits::construct(a, (value_type*)(&v), ::boost::forward<Args>(args)... );
1026       value_type *pval = move_detail::launder_cast<value_type *>(&v);
1027       value_destructor<stored_allocator_type, value_type> d(a, *pval);
1028       return this->insert_equal(::boost::move(*pval));
1029    }
1030 
1031    template <class... Args>
1032    iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args)
1033    {
1034       //hint checked in insert_equal
1035       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
1036       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
1037       stored_allocator_traits::construct(a, (value_type*)(&v), ::boost::forward<Args>(args)... );
1038       value_type *pval = move_detail::launder_cast<value_type *>(&v);
1039       value_destructor<stored_allocator_type, value_type> d(a, *pval);
1040       return this->insert_equal(hint, ::boost::move(*pval));
1041    }
1042 
1043    template <class KeyType, class... Args>
1044    inline std::pair<iterator, bool> try_emplace
1045       (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args)
1046    {
1047       std::pair<iterator,bool> ret;
1048       insert_commit_data data;
1049       const key_type & k = key;
1050       ret.second = hint == const_iterator()
1051          ? this->priv_insert_unique_prepare(k, data)
1052          : this->priv_insert_unique_prepare(hint, k, data);
1053 
1054       if(!ret.second){
1055          ret.first  = this->nth(size_type(data.position - this->cbegin()));
1056       }
1057       else{
1058          ret.first = this->m_data.m_seq.emplace(data.position, try_emplace_t(), ::boost::forward<KeyType>(key), ::boost::forward<Args>(args)...);
1059       }
1060       return ret;
1061    }
1062 
1063    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1064 
1065    #define BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE(N) \
1066    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1067    std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
1068    {\
1069       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
1070       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
1071       stored_allocator_traits::construct(a, (value_type *)(&v) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1072       value_type *pval = move_detail::launder_cast<value_type *>(&v);\
1073       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
1074       return this->insert_unique(::boost::move(*pval));\
1075    }\
1076    \
1077    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1078    iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1079    {\
1080       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
1081       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
1082       stored_allocator_traits::construct(a, (value_type *)(&v) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1083       value_type *pval = move_detail::launder_cast<value_type *>(&v);\
1084       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
1085       return this->insert_unique(hint, ::boost::move(*pval));\
1086    }\
1087    \
1088    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1089    iterator emplace_equal(BOOST_MOVE_UREF##N)\
1090    {\
1091       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
1092       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
1093       stored_allocator_traits::construct(a, (value_type *)(&v) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1094       value_type *pval = move_detail::launder_cast<value_type *>(&v);\
1095       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
1096       return this->insert_equal(::boost::move(*pval));\
1097    }\
1098    \
1099    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1100    iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1101    {\
1102       typename dtl::aligned_storage <sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
1103       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
1104       stored_allocator_traits::construct(a, (value_type *)(&v) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1105       value_type *pval = move_detail::launder_cast<value_type *>(&v);\
1106       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
1107       return this->insert_equal(hint, ::boost::move(*pval));\
1108    }\
1109    template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\
1110    inline std::pair<iterator, bool>\
1111       try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1112    {\
1113       std::pair<iterator,bool> ret;\
1114       insert_commit_data data;\
1115       const key_type & k = key;\
1116       ret.second = hint == const_iterator()\
1117          ? this->priv_insert_unique_prepare(k, data)\
1118          : this->priv_insert_unique_prepare(hint, k, data);\
1119       \
1120       if(!ret.second){\
1121          ret.first  = this->nth(size_type(data.position - this->cbegin()));\
1122       }\
1123       else{\
1124          ret.first = this->m_data.m_seq.emplace(data.position, try_emplace_t(), ::boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1125       }\
1126       return ret;\
1127    }\
1128    //
1129    BOOST_MOVE_ITERATE_0TO7(BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE)
1130    #undef BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE
1131 
1132    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1133 
1134    template<class KeyType, class M>
1135    std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj)
1136    {
1137       const key_type& k = key;
1138       std::pair<iterator,bool> ret;
1139       insert_commit_data data;
1140       ret.second = hint == const_iterator()
1141          ? this->priv_insert_unique_prepare(k, data)
1142          : this->priv_insert_unique_prepare(hint, k, data);
1143       if(!ret.second){
1144          ret.first  = this->nth(size_type(data.position - this->cbegin()));
1145          ret.first->second = boost::forward<M>(obj);
1146       }
1147       else{
1148          ret.first = this->m_data.m_seq.emplace(data.position, boost::forward<KeyType>(key), boost::forward<M>(obj));
1149       }
1150       return ret;
1151    }
1152 
1153    size_type erase(const key_type& k)
1154    {
1155       std::pair<iterator,iterator > itp = this->equal_range(k);
1156       size_type ret = static_cast<size_type>(itp.second-itp.first);
1157       if (ret){
1158          this->m_data.m_seq.erase(itp.first, itp.second);
1159       }
1160       return ret;
1161    }
1162 
1163    size_type erase_unique(const key_type& k)
1164    {
1165       const_iterator i = static_cast<const flat_tree &>(*this).find(k);
1166       size_type ret = static_cast<size_type>(i != this->cend());
1167       if (ret)
1168          this->erase(i);
1169       return ret;
1170    }
1171 
1172    template <class K>
1173    inline typename dtl::enable_if_c<
1174       dtl::is_transparent<key_compare>::value &&      //transparent
1175       !dtl::is_convertible<K, iterator>::value &&     //not convertible to iterator
1176       !dtl::is_convertible<K, const_iterator>::value  //not convertible to const_iterator
1177       , size_type>::type
1178       erase(const K& k)
1179    {
1180       std::pair<iterator, iterator > itp = this->equal_range(k);
1181       size_type ret = static_cast<size_type>(itp.second - itp.first);
1182       if (ret) {
1183          this->m_data.m_seq.erase(itp.first, itp.second);
1184       }
1185       return ret;
1186    }
1187 
1188    template <class K>
1189    inline typename dtl::enable_if_c<
1190       dtl::is_transparent<key_compare>::value &&      //transparent
1191       !dtl::is_convertible<K, iterator>::value &&     //not convertible to iterator
1192       !dtl::is_convertible<K, const_iterator>::value  //not convertible to const_iterator
1193       , size_type>::type
1194       erase_unique(const K& k)
1195    {
1196       const_iterator i = static_cast<const flat_tree&>(*this).find(k);
1197       size_type ret = static_cast<size_type>(i != this->cend());
1198       if (ret)
1199          this->erase(i);
1200       return ret;
1201    }
1202 
1203    inline iterator erase(const_iterator position)
1204    {  return this->m_data.m_seq.erase(position);  }
1205 
1206    inline iterator erase(const_iterator first, const_iterator last)
1207    {  return this->m_data.m_seq.erase(first, last);  }
1208 
1209    inline void clear()
1210    {  this->m_data.m_seq.clear();  }
1211 
1212    //! <b>Effects</b>: Tries to deallocate the excess of memory created
1213    //    with previous allocations. The size of the vector is unchanged
1214    //!
1215    //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1216    //!
1217    //! <b>Complexity</b>: Linear to size().
1218    inline void shrink_to_fit()
1219    {  this->m_data.m_seq.shrink_to_fit();  }
1220 
1221    inline iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1222    {
1223       const bool value = boost::container::dtl::
1224          has_member_function_callable_with_nth<container_type, size_type>::value;
1225       return flat_tree_nth<iterator>(this->m_data.m_seq, n, dtl::bool_<value>());
1226    }
1227 
1228    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1229       const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1230    {
1231       const bool value = boost::container::dtl::
1232          has_member_function_callable_with_nth<container_type, size_type>::value;
1233       return flat_tree_nth<const_iterator>(this->m_data.m_seq, n, dtl::bool_<value>());
1234    }
1235 
1236    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1237       size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1238    {
1239       const bool value = boost::container::dtl::
1240          has_member_function_callable_with_index_of<container_type, iterator>::value;
1241       return flat_tree_index_of(this->m_data.m_seq, p, dtl::bool_<value>());
1242    }
1243 
1244    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1245       size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1246    {
1247       const bool value = boost::container::dtl::
1248          has_member_function_callable_with_index_of<container_type, const_iterator>::value;
1249       return flat_tree_index_of(this->m_data.m_seq, p, dtl::bool_<value>());
1250    }
1251 
1252    // set operations:
1253    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
1254       iterator find(const key_type& k)
1255    {
1256       iterator i = this->lower_bound(k);
1257       iterator end_it = this->end();
1258       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
1259          i = end_it;
1260       }
1261       return i;
1262    }
1263 
1264    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
1265    const_iterator find(const key_type& k) const
1266    {
1267       const_iterator i = this->lower_bound(k);
1268 
1269       const_iterator end_it = this->cend();
1270       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
1271          i = end_it;
1272       }
1273       return i;
1274    }
1275 
1276    template<class K>
1277    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
1278       typename dtl::enable_if_transparent<key_compare, K, iterator>::type
1279       find(const K& k)
1280    {
1281       iterator i = this->lower_bound(k);
1282       iterator end_it = this->end();
1283       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
1284          i = end_it;
1285       }
1286       return i;
1287    }
1288 
1289    template<class K>
1290    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
1291       typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
1292       find(const K& k) const
1293    {
1294       const_iterator i = this->lower_bound(k);
1295 
1296       const_iterator end_it = this->cend();
1297       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
1298          i = end_it;
1299       }
1300       return i;
1301    }
1302 
1303    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
1304       size_type count(const key_type& k) const
1305    {
1306       std::pair<const_iterator, const_iterator> p = this->equal_range(k);
1307       size_type n = size_type(p.second - p.first);
1308       return n;
1309    }
1310 
1311    template<class K>
1312    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
1313       typename dtl::enable_if_transparent<key_compare, K, size_type>::type
1314       count(const K& k) const
1315    {
1316       std::pair<const_iterator, const_iterator> p = this->equal_range(k);
1317       size_type n = size_type(p.second - p.first);
1318       return n;
1319    }
1320 
1321    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline bool contains(const key_type& x) const
1322    {  return this->find(x) != this->cend();  }
1323 
1324    template<typename K>
1325    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1326       typename dtl::enable_if_transparent<key_compare, K, bool>::type
1327          contains(const K& x) const
1328    {  return this->find(x) != this->cend();  }
1329 
1330    template<class C2>
1331    inline void merge_unique(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source)
1332    {
1333       this->insert_unique( boost::make_move_iterator(source.begin())
1334                          , boost::make_move_iterator(source.end()));
1335    }
1336 
1337    template<class C2>
1338    inline void merge_equal(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source)
1339    {
1340       this->insert_equal( boost::make_move_iterator(source.begin())
1341                         , boost::make_move_iterator(source.end()));
1342    }
1343 
1344    inline void merge_unique(flat_tree& source)
1345    {
1346       const bool value = boost::container::dtl::
1347          has_member_function_callable_with_merge_unique<container_type, iterator, iterator, value_compare>::value;
1348       (flat_tree_merge_unique)
1349          ( this->m_data.m_seq
1350          , boost::make_move_iterator(source.m_data.m_seq.begin())
1351          , boost::make_move_iterator(source.m_data.m_seq.end())
1352          , this->priv_value_comp()
1353          , dtl::bool_<value>());
1354    }
1355 
1356    inline void merge_equal(flat_tree& source)
1357    {
1358       const bool value = boost::container::dtl::
1359          has_member_function_callable_with_merge<container_type, iterator, iterator, value_compare>::value;
1360       (flat_tree_merge_equal)
1361          ( this->m_data.m_seq
1362          , boost::make_move_iterator(source.m_data.m_seq.begin())
1363          , boost::make_move_iterator(source.m_data.m_seq.end())
1364          , this->priv_value_comp()
1365          , dtl::bool_<value>());
1366    }
1367 
1368    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1369       iterator lower_bound(const key_type& k)
1370    {  return this->priv_lower_bound(this->begin(), this->end(), k);  }
1371 
1372    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1373       const_iterator lower_bound(const key_type& k) const
1374    {  return this->priv_lower_bound(this->cbegin(), this->cend(), k);  }
1375 
1376    template<class K>
1377    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline 
1378       typename dtl::enable_if_transparent<key_compare, K, iterator>::type
1379          lower_bound(const K& k)
1380    {  return this->priv_lower_bound(this->begin(), this->end(), k);  }
1381 
1382    template<class K>
1383    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline 
1384       typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
1385          lower_bound(const K& k) const
1386    {  return this->priv_lower_bound(this->cbegin(), this->cend(), k);  }
1387 
1388    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1389       iterator upper_bound(const key_type& k)
1390    {  return this->priv_upper_bound(this->begin(), this->end(), k);  }
1391 
1392    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline 
1393       const_iterator upper_bound(const key_type& k) const
1394    {  return this->priv_upper_bound(this->cbegin(), this->cend(), k);  }
1395 
1396    template<class K>
1397    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1398       typename dtl::enable_if_transparent<key_compare, K,iterator>::type
1399    upper_bound(const K& k)
1400    {  return this->priv_upper_bound(this->begin(), this->end(), k);  }
1401 
1402    template<class K>
1403    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1404       typename dtl::enable_if_transparent<key_compare, K,const_iterator>::type
1405          upper_bound(const K& k) const
1406    {  return this->priv_upper_bound(this->cbegin(), this->cend(), k);  }
1407 
1408    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1409       std::pair<iterator,iterator> equal_range(const key_type& k)
1410    {  return this->priv_equal_range(this->begin(), this->end(), k);  }
1411 
1412    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1413       std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
1414    {  return this->priv_equal_range(this->cbegin(), this->cend(), k);  }
1415 
1416    template<class K>
1417    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1418       typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type
1419          equal_range(const K& k)
1420    {  return this->priv_equal_range(this->begin(), this->end(), k);  }
1421 
1422    template<class K>
1423    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1424       typename dtl::enable_if_transparent<key_compare, K,std::pair<const_iterator,const_iterator> >::type
1425          equal_range(const K& k) const
1426    {  return this->priv_equal_range(this->cbegin(), this->cend(), k);  }
1427 
1428 
1429    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1430       std::pair<iterator, iterator> lower_bound_range(const key_type& k)
1431    {  return this->priv_lower_bound_range(this->begin(), this->end(), k);  }
1432 
1433    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1434       std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
1435    {  return this->priv_lower_bound_range(this->cbegin(), this->cend(), k);  }
1436 
1437    template<class K>
1438    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1439       typename dtl::enable_if_transparent<key_compare, K,std::pair<iterator,iterator> >::type
1440          lower_bound_range(const K& k)
1441    {  return this->priv_lower_bound_range(this->begin(), this->end(), k);  }
1442 
1443    template<class K>
1444    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1445       typename dtl::enable_if_transparent<key_compare, K,std::pair<const_iterator,const_iterator> >::type
1446          lower_bound_range(const K& k) const
1447    {  return this->priv_lower_bound_range(this->cbegin(), this->cend(), k);  }
1448 
1449    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1450       size_type capacity() const
1451    {
1452       const bool value = boost::container::dtl::
1453          has_member_function_callable_with_capacity<container_type>::value;
1454       return (flat_tree_capacity)(this->m_data.m_seq, dtl::bool_<value>());
1455    }
1456 
1457    inline
1458       void reserve(size_type cnt)
1459    {
1460       const bool value = boost::container::dtl::
1461          has_member_function_callable_with_reserve<container_type, size_type>::value;
1462       (flat_tree_reserve)(this->m_data.m_seq, cnt, dtl::bool_<value>());
1463    }
1464 
1465    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1466       container_type extract_sequence()
1467    {  return boost::move(m_data.m_seq);   }
1468 
1469    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1470       container_type &get_sequence_ref()
1471    {  return m_data.m_seq; }
1472 
1473    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1474       const container_type &get_sequence_cref() const
1475    {  return m_data.m_seq; }
1476 
1477    inline void adopt_sequence_equal(BOOST_RV_REF(container_type) seq)
1478    {
1479       (flat_tree_adopt_sequence_equal)( m_data.m_seq, boost::move(seq), this->priv_value_comp()
1480          , dtl::bool_<is_contiguous_container<container_type>::value>());
1481    }
1482 
1483    inline void adopt_sequence_unique(BOOST_RV_REF(container_type) seq)
1484    {
1485       (flat_tree_adopt_sequence_unique)(m_data.m_seq, boost::move(seq), this->priv_value_comp()
1486          , dtl::bool_<is_contiguous_container<container_type>::value>());
1487    }
1488 
1489    void adopt_sequence_equal(ordered_range_t, BOOST_RV_REF(container_type) seq)
1490    {
1491       BOOST_ASSERT((is_sorted)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
1492       m_data.m_seq = boost::move(seq);
1493    }
1494 
1495    void adopt_sequence_unique(ordered_unique_range_t, BOOST_RV_REF(container_type) seq)
1496    {
1497       BOOST_ASSERT((is_sorted_and_unique)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
1498       m_data.m_seq = boost::move(seq);
1499    }
1500 
1501    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1502       friend bool operator==(const flat_tree& x, const flat_tree& y)
1503    {
1504       return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());
1505    }
1506 
1507    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1508       friend bool operator<(const flat_tree& x, const flat_tree& y)
1509    {
1510       return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
1511    }
1512 
1513    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1514       friend bool operator!=(const flat_tree& x, const flat_tree& y)
1515       {  return !(x == y); }
1516 
1517    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1518       friend bool operator>(const flat_tree& x, const flat_tree& y)
1519       {  return y < x;  }
1520 
1521    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1522       friend bool operator<=(const flat_tree& x, const flat_tree& y)
1523       {  return !(y < x);  }
1524 
1525    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1526       friend bool operator>=(const flat_tree& x, const flat_tree& y)
1527       {  return !(x < y);  }
1528 
1529    inline friend void swap(flat_tree& x, flat_tree& y)
1530           BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT(x.swap(y)))
1531       {  x.swap(y);  }
1532 
1533    private:
1534 
1535    template <class InputIterator>
1536    void priv_range_insertion_construct( bool unique_insertion, InputIterator first, InputIterator last)
1537    {
1538       //Use cend() as hint to achieve linear time for
1539       //ordered ranges as required by the standard
1540       //for the constructor
1541       //Call end() every iteration as reallocation might have invalidated iterators
1542       if(unique_insertion){
1543          this->insert_unique(first, last);
1544       }
1545       else{
1546          this->insert_equal (first, last);
1547       }
1548    }
1549 
1550    inline bool priv_in_range_or_end(const_iterator pos) const
1551    {
1552       return (this->begin() <= pos) && (pos <= this->end());
1553    }
1554 
1555    // insert/erase
1556    void priv_insert_equal_prepare
1557       (const_iterator pos, const value_type& val, insert_commit_data &data)
1558    {
1559       // N1780
1560       //   To insert val at pos:
1561       //   if pos == end || val <= *pos
1562       //      if pos == begin || val >= *(pos-1)
1563       //         insert val before pos
1564       //      else
1565       //         insert val before upper_bound(val)
1566       //   else
1567       //      insert val before lower_bound(val)
1568       const value_compare &val_cmp = this->m_data;
1569 
1570       if(pos == this->cend() || !val_cmp(*pos, val)){
1571          if (pos == this->cbegin() || !val_cmp(val, pos[-1])){
1572             data.position = pos;
1573          }
1574          else{
1575             data.position =
1576                this->priv_upper_bound(this->cbegin(), pos, KeyOfValue()(val));
1577          }
1578       }
1579       else{
1580          data.position =
1581             this->priv_lower_bound(pos, this->cend(), KeyOfValue()(val));
1582       }
1583    }
1584 
1585    bool priv_insert_unique_prepare
1586       (const_iterator b, const_iterator e, const key_type& k, insert_commit_data &commit_data)
1587    {
1588       const key_compare &key_cmp  = this->priv_key_comp();
1589       commit_data.position = this->priv_lower_bound(b, e, k);
1590       return commit_data.position == e || key_cmp(k, KeyOfValue()(*commit_data.position));
1591    }
1592 
1593    inline bool priv_insert_unique_prepare
1594       (const key_type& k, insert_commit_data &commit_data)
1595    {  return this->priv_insert_unique_prepare(this->cbegin(), this->cend(), k, commit_data);   }
1596 
1597    bool priv_insert_unique_prepare
1598       (const_iterator pos, const key_type& k, insert_commit_data &commit_data)
1599    {
1600       //N1780. Props to Howard Hinnant!
1601       //To insert k at pos:
1602       //if pos == end || k <= *pos
1603       //   if pos == begin || k >= *(pos-1)
1604       //      insert k before pos
1605       //   else
1606       //      insert k before upper_bound(k)
1607       //else if pos+1 == end || k <= *(pos+1)
1608       //   insert k after pos
1609       //else
1610       //   insert k before lower_bound(k)
1611       const key_compare &key_cmp = this->priv_key_comp();
1612       const const_iterator cend_it = this->cend();
1613       if(pos == cend_it || key_cmp(k, KeyOfValue()(*pos))){ //Check if k should go before end
1614          const const_iterator cbeg = this->cbegin();
1615          commit_data.position = pos;
1616          if(pos == cbeg){  //If container is empty then insert it in the beginning
1617             return true;
1618          }
1619          const_iterator prev(pos);
1620          --prev;
1621          if(key_cmp(KeyOfValue()(*prev), k)){   //If previous element was less, then it should go between prev and pos
1622             return true;
1623          }
1624          else if(!key_cmp(k, KeyOfValue()(*prev))){   //If previous was equal then insertion should fail
1625             commit_data.position = prev;
1626             return false;
1627          }
1628          else{ //Previous was bigger so insertion hint was pointless, dispatch to hintless insertion
1629                //but reduce the search between beg and prev as prev is bigger than k
1630             return this->priv_insert_unique_prepare(cbeg, prev, k, commit_data);
1631          }
1632       }
1633       else{
1634          //The hint is before the insertion position, so insert it
1635          //in the remaining range [pos, end)
1636          return this->priv_insert_unique_prepare(pos, cend_it, k, commit_data);
1637       }
1638    }
1639 
1640    template<class Convertible>
1641    inline iterator priv_insert_commit
1642       (insert_commit_data &commit_data, BOOST_FWD_REF(Convertible) convertible)
1643    {
1644       return this->m_data.m_seq.insert
1645          ( commit_data.position
1646          , boost::forward<Convertible>(convertible));
1647    }
1648 
1649    template <class RanIt, class K>
1650    RanIt priv_lower_bound(RanIt first, const RanIt last,
1651                           const K & key) const
1652    {
1653       const Compare &key_cmp = this->m_data.get_comp();
1654       KeyOfValue key_extract;
1655       size_type len = static_cast<size_type>(last - first);
1656       RanIt middle;
1657 
1658       while (len) {
1659          size_type step = len >> 1;
1660          middle = first;
1661          middle += difference_type(step);
1662 
1663          if (key_cmp(key_extract(*middle), key)) {
1664             first = ++middle;
1665             len -= step + 1;
1666          }
1667          else{
1668             len = step;
1669          }
1670       }
1671       return first;
1672    }
1673 
1674    template <class RanIt, class K>
1675    RanIt priv_upper_bound
1676       (RanIt first, const RanIt last,const K & key) const
1677    {
1678       const Compare &key_cmp = this->m_data.get_comp();
1679       KeyOfValue key_extract;
1680       size_type len = static_cast<size_type>(last - first);
1681       RanIt middle;
1682 
1683       while (len) {
1684          size_type step = len >> 1;
1685          middle = first;
1686          middle += difference_type(step);
1687 
1688          if (key_cmp(key, key_extract(*middle))) {
1689             len = step;
1690          }
1691          else{
1692             first = ++middle;
1693             len -= step + 1;
1694          }
1695       }
1696       return first;
1697    }
1698 
1699    template <class RanIt, class K>
1700    std::pair<RanIt, RanIt>
1701       priv_equal_range(RanIt first, RanIt last, const K& key) const
1702    {
1703       const Compare &key_cmp = this->m_data.get_comp();
1704       KeyOfValue key_extract;
1705       size_type len = static_cast<size_type>(last - first);
1706       RanIt middle;
1707 
1708       while (len) {
1709          size_type step = len >> 1;
1710          middle = first;
1711          middle += difference_type(step);
1712 
1713          if (key_cmp(key_extract(*middle), key)){
1714             first = ++middle;
1715             len -= step + 1;
1716          }
1717          else if (key_cmp(key, key_extract(*middle))){
1718             len = step;
1719          }
1720          else {
1721             //Middle is equal to key
1722             last = first;
1723             last += difference_type(len);
1724             RanIt const first_ret = this->priv_lower_bound(first, middle, key);
1725             return std::pair<RanIt, RanIt>
1726                ( first_ret, this->priv_upper_bound(++middle, last, key));
1727          }
1728       }
1729       return std::pair<RanIt, RanIt>(first, first);
1730    }
1731 
1732    template<class RanIt, class K>
1733    std::pair<RanIt, RanIt> priv_lower_bound_range(RanIt first, RanIt last, const K& k) const
1734    {
1735       const Compare &key_cmp = this->m_data.get_comp();
1736       KeyOfValue key_extract;
1737       RanIt lb(this->priv_lower_bound(first, last, k)), ub(lb);
1738       if(lb != last && !key_cmp(k, key_extract(*lb))){
1739          ++ub;
1740       }
1741       return std::pair<RanIt, RanIt>(lb, ub);
1742    }
1743 };
1744 
1745 }  //namespace dtl {
1746 
1747 }  //namespace container {
1748 
1749 //!has_trivial_destructor_after_move<> == true_type
1750 //!specialization for optimizations
1751 template <class T, class KeyOfValue,
1752 class Compare, class AllocatorOrContainer>
1753 struct has_trivial_destructor_after_move<boost::container::dtl::flat_tree<T, KeyOfValue, Compare, AllocatorOrContainer> >
1754 {
1755    typedef boost::container::dtl::flat_tree<T, KeyOfValue, Compare, AllocatorOrContainer> flat_tree;
1756    typedef typename flat_tree::container_type container_type;
1757    typedef typename flat_tree::key_compare key_compare;
1758    BOOST_STATIC_CONSTEXPR bool value = ::boost::has_trivial_destructor_after_move<container_type>::value &&
1759                              ::boost::has_trivial_destructor_after_move<key_compare>::value;
1760 };
1761 
1762 }  //namespace boost {
1763 
1764 #include <boost/container/detail/config_end.hpp>
1765 
1766 #endif // BOOST_CONTAINER_FLAT_TREE_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!