Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-07-05 08:28:40 

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