Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:30:11 

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