ceph/src/boost/boost/container/detail/flat_tree.hpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost
   4 // Software License, Version 1.0. (See accompanying file
   5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // See http://www.boost.org/libs/container for documentation.
   8 //
   9 ////////////////////////////////////////////////////////////////////////////////
  10
  11 #ifndef BOOST_CONTAINER_FLAT_TREE_HPP
  12 #define BOOST_CONTAINER_FLAT_TREE_HPP
  13
  14 #ifndef BOOST_CONFIG_HPP
  15 #  include <boost/config.hpp>
  16 #endif
  17
  18 #if defined(BOOST_HAS_PRAGMA_ONCE)
  19 #  pragma once
  20 #endif
  21
  22 #include <boost/container/detail/config_begin.hpp>
  23 #include <boost/container/detail/workaround.hpp>
  24
  25 #include <boost/container/container_fwd.hpp>
  26
  27 #include <boost/move/utility_core.hpp>
  28
  29 #include <boost/container/detail/pair.hpp>
  30 #include <boost/container/vector.hpp>
  31 #include <boost/container/allocator_traits.hpp>
  32
  33 #include <boost/container/detail/value_init.hpp>
  34 #include <boost/container/detail/destroyers.hpp>
  35 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
  36 #include <boost/container/detail/iterator.hpp>
  37 #include <boost/container/detail/is_sorted.hpp>
  38 #include <boost/container/detail/type_traits.hpp>
  39 #include <boost/container/detail/iterators.hpp>
  40 #include <boost/container/detail/mpl.hpp>
  41 #include <boost/container/detail/is_contiguous_container.hpp>
  42 #include <boost/container/detail/is_container.hpp>
  43
  44 #include <boost/intrusive/detail/minimal_pair_header.hpp>      //pair
  45
  46 #include <boost/move/make_unique.hpp>
  47 #include <boost/move/iterator.hpp>
  48 #include <boost/move/adl_move_swap.hpp>
  49 #include <boost/move/algo/adaptive_sort.hpp>
  50 #include <boost/move/algo/detail/pdqsort.hpp>
  51
  52 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
  53 #include <boost/move/detail/fwd_macros.hpp>
  54 #endif
  55
  56 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  57
  58 //merge_unique
  59 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME merge_unique
  60 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
  61 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
  62 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 3
  63 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 3
  64 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
  65
  66 //merge_equal
  67 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME merge
  68 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
  69 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
  70 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 3
  71 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 3
  72 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
  73
  74 //index_of
  75 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME index_of
  76 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
  77 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
  78 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
  79 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
  80 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
  81
  82 //nth
  83 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME nth
  84 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
  85 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
  86 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
  87 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
  88 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
  89
  90 //reserve
  91 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME reserve
  92 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
  93 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
  94 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
  95 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
  96 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
  97
  98 //capacity
  99 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME capacity
 100 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
 101 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
 102 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 0
 103 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 0
 104 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
 105
 106 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 107
 108 namespace boost {
 109 namespace container {
 110 namespace dtl {
 111
 112 ///////////////////////////////////////
 113 //
 114 // Helper functions to merge elements
 115 //
 116 ///////////////////////////////////////
 117
 118 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(stored_allocator_type)
 119
 120 ///////////////////////////////////////
 121 //
 122 //  flat_tree_container_inplace_merge
 123 //
 124 ///////////////////////////////////////
 125 template<class SequenceContainer, class Compare>
 126 void flat_tree_container_inplace_merge //is_contiguous_container == true
 127    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp , dtl::true_)
 128 {
 129    typedef typename SequenceContainer::value_type  value_type;
 130    value_type *const braw = boost::movelib::iterator_to_raw_pointer(dest.begin());
 131    value_type *const iraw = boost::movelib::iterator_to_raw_pointer(it);
 132    value_type *const eraw = boost::movelib::iterator_to_raw_pointer(dest.end());
 133    boost::movelib::adaptive_merge(braw, iraw, eraw, comp, eraw, dest.capacity()- dest.size());
 134 }
 135
 136 template<class SequenceContainer, class Compare>
 137 void flat_tree_container_inplace_merge //is_contiguous_container == false
 138    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp, dtl::false_)
 139 {
 140    boost::movelib::adaptive_merge(dest.begin(), it, dest.end(), comp);
 141 }
 142
 143 ///////////////////////////////////////
 144 //
 145 //  flat_tree_container_inplace_sort_ending
 146 //
 147 ///////////////////////////////////////
 148 template<class SequenceContainer, class Compare>
 149 void flat_tree_container_inplace_sort_ending //is_contiguous_container == true
 150    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp, dtl::true_)
 151 {
 152    typedef typename SequenceContainer::value_type  value_type;
 153    value_type *const iraw = boost::movelib::iterator_to_raw_pointer(it);
 154    value_type *const eraw = boost::movelib::iterator_to_raw_pointer(dest.end());
 155    boost::movelib::adaptive_sort(iraw, eraw, comp, eraw, dest.capacity()- dest.size());
 156 }
 157
 158 template<class SequenceContainer, class Compare>
 159 void flat_tree_container_inplace_sort_ending //is_contiguous_container == false
 160    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp , dtl::false_)
 161 {
 162    boost::movelib::adaptive_sort(it, dest.end(), comp);
 163 }
 164
 165 ///////////////////////////////////////
 166 //
 167 //          flat_tree_merge
 168 //
 169 ///////////////////////////////////////
 170 template<class SequenceContainer, class Iterator, class Compare>
 171 BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_equal
 172    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::true_)
 173 {
 174    dest.merge(first, last, comp);
 175 }
 176
 177 template<class SequenceContainer, class Iterator, class Compare>
 178 BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_equal   //has_merge_unique == false
 179    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::false_)
 180 {
 181    typedef typename SequenceContainer::iterator    iterator;
 182    iterator const it = dest.insert( dest.end(), first, last );
 183    dtl::bool_<is_contiguous_container<SequenceContainer>::value> contiguous_tag;
 184    (flat_tree_container_inplace_merge)(dest, it, comp, contiguous_tag);
 185 }
 186
 187 ///////////////////////////////////////
 188 //
 189 //       flat_tree_merge_unique
 190 //
 191 ///////////////////////////////////////
 192 template<class SequenceContainer, class Iterator, class Compare>
 193 BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_unique  //has_merge_unique == true
 194    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::true_)
 195 {
 196    dest.merge_unique(first, last, comp);
 197 }
 198
 199 template<class SequenceContainer, class Iterator, class Compare>
 200 BOOST_CONTAINER_FORCEINLINE void flat_tree_merge_unique  //has_merge_unique == false
 201    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::false_)
 202 {
 203    typedef typename SequenceContainer::iterator    iterator;
 204    typedef typename SequenceContainer::size_type   size_type;
 205
 206    size_type const old_sz = dest.size();
 207    iterator const first_new = dest.insert(dest.cend(), first, last );
 208    iterator e = boost::movelib::inplace_set_unique_difference(first_new, dest.end(), dest.begin(), first_new, comp);
 209    dest.erase(e, dest.end());
 210    dtl::bool_<is_contiguous_container<SequenceContainer>::value> contiguous_tag;
 211    (flat_tree_container_inplace_merge)(dest, dest.begin()+old_sz, comp, contiguous_tag);
 212 }
 213
 214 ///////////////////////////////////////
 215 //
 216 //         flat_tree_index_of
 217 //
 218 ///////////////////////////////////////
 219 template<class SequenceContainer, class Iterator>
 220 BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
 221    flat_tree_index_of   // has_index_of == true
 222       (SequenceContainer& cont, Iterator p, dtl::true_)
 223 {
 224    return cont.index_of(p);
 225 }
 226
 227 template<class SequenceContainer, class Iterator>
 228 BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
 229    flat_tree_index_of   // has_index_of == false
 230       (SequenceContainer& cont, Iterator p, dtl::false_)
 231 {
 232    typedef typename SequenceContainer::size_type size_type;
 233    return static_cast<size_type>(p - cont.begin());
 234 }
 235
 236 ///////////////////////////////////////
 237 //
 238 //         flat_tree_nth
 239 //
 240 ///////////////////////////////////////
 241 template<class Iterator, class SequenceContainer>
 242 BOOST_CONTAINER_FORCEINLINE Iterator
 243    flat_tree_nth  // has_nth == true
 244       (SequenceContainer& cont, typename SequenceContainer::size_type n, dtl::true_)
 245 {
 246    return cont.nth(n);
 247 }
 248
 249 template<class Iterator, class SequenceContainer>
 250 BOOST_CONTAINER_FORCEINLINE Iterator
 251    flat_tree_nth  // has_nth == false
 252       (SequenceContainer& cont, typename SequenceContainer::size_type n, dtl::false_)
 253 {
 254    return cont.begin()+ n;
 255 }
 256
 257 ///////////////////////////////////////
 258 //
 259 //    flat_tree_get_stored_allocator
 260 //
 261 ///////////////////////////////////////
 262 template<class SequenceContainer>
 263 BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::stored_allocator_type &
 264    flat_tree_get_stored_allocator   // has_get_stored_allocator == true
 265       (SequenceContainer& cont, dtl::true_)
 266 {
 267    return cont.get_stored_allocator();
 268 }
 269
 270 template<class SequenceContainer>
 271 BOOST_CONTAINER_FORCEINLINE const typename SequenceContainer::stored_allocator_type &
 272    flat_tree_get_stored_allocator   // has_get_stored_allocator == true
 273       (const SequenceContainer& cont, dtl::true_)
 274 {
 275    return cont.get_stored_allocator();
 276 }
 277
 278 template<class SequenceContainer>
 279 BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::allocator_type
 280    flat_tree_get_stored_allocator   // has_get_stored_allocator == false
 281       (SequenceContainer& cont, dtl::false_)
 282 {
 283    return cont.get_allocator();
 284 }
 285
 286 ///////////////////////////////////////
 287 //
 288 //    flat_tree_adopt_sequence_equal
 289 //
 290 ///////////////////////////////////////
 291 template<class SequenceContainer, class Compare>
 292 void flat_tree_sort_contiguous_to_adopt // is_contiguous_container == true
 293    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp)
 294 {
 295    if(tseq.capacity() >= (seq.capacity() - seq.size())) {
 296       tseq.clear();
 297       boost::movelib::adaptive_sort
 298       (boost::movelib::iterator_to_raw_pointer(seq.begin())
 299          , boost::movelib::iterator_to_raw_pointer(seq.end())
 300          , comp
 301          , boost::movelib::iterator_to_raw_pointer(tseq.begin())
 302          , tseq.capacity());
 303    }
 304    else{
 305       boost::movelib::adaptive_sort
 306       (boost::movelib::iterator_to_raw_pointer(seq.begin())
 307          , boost::movelib::iterator_to_raw_pointer(seq.end())
 308          , comp
 309          , boost::movelib::iterator_to_raw_pointer(seq.end())
 310          , seq.capacity() - seq.size());
 311    }
 312 }
 313
 314 template<class SequenceContainer, class Compare>
 315 void flat_tree_adopt_sequence_equal // is_contiguous_container == true
 316    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::true_)
 317 {
 318    flat_tree_sort_contiguous_to_adopt(tseq, boost::move(seq), comp);
 319    tseq = boost::move(seq);
 320 }
 321
 322 template<class SequenceContainer, class Compare>
 323 void flat_tree_adopt_sequence_equal // is_contiguous_container == false
 324    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::false_)
 325 {
 326    boost::movelib::adaptive_sort(seq.begin(), seq.end(), comp);
 327    tseq = boost::move(seq);
 328 }
 329
 330 ///////////////////////////////////////
 331 //
 332 //    flat_tree_adopt_sequence_unique
 333 //
 334 ///////////////////////////////////////
 335 template<class SequenceContainer, class Compare>
 336 void flat_tree_adopt_sequence_unique// is_contiguous_container == true
 337    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::true_)
 338 {
 339    boost::movelib::pdqsort
 340       ( boost::movelib::iterator_to_raw_pointer(seq.begin())
 341       , boost::movelib::iterator_to_raw_pointer(seq.end())
 342       , comp);
 343    seq.erase(boost::movelib::unique
 344       (seq.begin(), seq.end(), boost::movelib::negate<Compare>(comp)), seq.cend());
 345    tseq = boost::move(seq);
 346 }
 347
 348 template<class SequenceContainer, class Compare>
 349 void flat_tree_adopt_sequence_unique// is_contiguous_container == false
 350    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::false_)
 351 {
 352    boost::movelib::pdqsort(seq.begin(), seq.end(), comp);
 353    seq.erase(boost::movelib::unique
 354       (seq.begin(), seq.end(), boost::movelib::negate<Compare>(comp)), seq.cend());
 355    tseq = boost::move(seq);
 356 }
 357
 358 ///////////////////////////////////////
 359 //
 360 //       flat_tree_reserve
 361 //
 362 ///////////////////////////////////////
 363 template<class SequenceContainer>
 364 BOOST_CONTAINER_FORCEINLINE void // has_reserve == true
 365    flat_tree_reserve(SequenceContainer &tseq, typename SequenceContainer::size_type cap, dtl::true_)
 366 {
 367    tseq.reserve(cap);
 368 }
 369
 370 template<class SequenceContainer>
 371 BOOST_CONTAINER_FORCEINLINE void // has_reserve == false
 372    flat_tree_reserve(SequenceContainer &, typename SequenceContainer::size_type, dtl::false_)
 373 {
 374 }
 375
 376 ///////////////////////////////////////
 377 //
 378 //       flat_tree_capacity
 379 //
 380 ///////////////////////////////////////
 381 template<class SequenceContainer>   // has_capacity == true
 382 BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
 383    flat_tree_capacity(const SequenceContainer &tseq, dtl::true_)
 384 {
 385    return tseq.capacity();
 386 }
 387
 388 template<class SequenceContainer>   // has_capacity == false
 389 BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
 390    flat_tree_capacity(const SequenceContainer &tseq, dtl::false_)
 391 {
 392    return tseq.size();
 393 }
 394
 395 ///////////////////////////////////////
 396 //
 397 //       flat_tree_value_compare
 398 //
 399 ///////////////////////////////////////
 400
 401 template<class Compare, class Value, class KeyOfValue>
 402 class flat_tree_value_compare
 403    : private Compare
 404 {
 405    typedef Value              first_argument_type;
 406    typedef Value              second_argument_type;
 407    typedef bool               return_type;
 408    public:
 409    flat_tree_value_compare()
 410       : Compare()
 411    {}
 412
 413    flat_tree_value_compare(const Compare &pred)
 414       : Compare(pred)
 415    {}
 416
 417    bool operator()(const Value& lhs, const Value& rhs) const
 418    {
 419       KeyOfValue key_extract;
 420       return Compare::operator()(key_extract(lhs), key_extract(rhs));
 421    }
 422
 423    const Compare &get_comp() const
 424       {  return *this;  }
 425
 426    Compare &get_comp()
 427       {  return *this;  }
 428 };
 429
 430
 431 ///////////////////////////////////////
 432 //
 433 //       select_container_type
 434 //
 435 ///////////////////////////////////////
 436 template < class Value, class AllocatorOrContainer
 437          , bool = boost::container::dtl::is_container<AllocatorOrContainer>::value
 438          >
 439 struct select_container_type
 440 {
 441    typedef AllocatorOrContainer type;
 442 };
 443
 444 template <class Value, class AllocatorOrContainer>
 445 struct select_container_type<Value, AllocatorOrContainer, false>
 446 {
 447    typedef boost::container::vector<Value, typename real_allocator<Value, AllocatorOrContainer>::type> type;
 448 };
 449
 450
 451 ///////////////////////////////////////
 452 //
 453 //          flat_tree
 454 //
 455 ///////////////////////////////////////
 456 template <class Value, class KeyOfValue,
 457           class Compare, class AllocatorOrContainer>
 458 class flat_tree
 459 {
 460    public:
 461    typedef typename select_container_type<Value, AllocatorOrContainer>::type container_type;
 462    typedef container_type sequence_type;  //For backwards compatibility
 463
 464    private:
 465    typedef typename container_type::allocator_type        allocator_t;
 466    typedef allocator_traits<allocator_t>                 allocator_traits_type;
 467
 468    public:
 469    typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare;
 470
 471    private:
 472
 473    struct Data
 474       //Inherit from value_compare to do EBO
 475       : public value_compare
 476    {
 477       BOOST_COPYABLE_AND_MOVABLE(Data)
 478
 479       public:
 480       Data()
 481          : value_compare(), m_seq()
 482       {}
 483
 484       explicit Data(const allocator_t &alloc)
 485          : value_compare(), m_seq(alloc)
 486       {}
 487
 488       explicit Data(const Compare &comp)
 489          : value_compare(comp), m_seq()
 490       {}
 491
 492       Data(const Compare &comp, const allocator_t &alloc)
 493          : value_compare(comp), m_seq(alloc)
 494       {}
 495
 496       explicit Data(const Data &d)
 497          : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq)
 498       {}
 499
 500       Data(BOOST_RV_REF(Data) d)
 501          : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq))
 502       {}
 503
 504       Data(const Data &d, const allocator_t &a)
 505          : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq, a)
 506       {}
 507
 508       Data(BOOST_RV_REF(Data) d, const allocator_t &a)
 509          : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq), a)
 510       {}
 511
 512       Data& operator=(BOOST_COPY_ASSIGN_REF(Data) d)
 513       {
 514          this->value_compare::operator=(d);
 515          m_seq = d.m_seq;
 516          return *this;
 517       }
 518
 519       Data& operator=(BOOST_RV_REF(Data) d)
 520       {
 521          this->value_compare::operator=(boost::move(static_cast<value_compare &>(d)));
 522          m_seq = boost::move(d.m_seq);
 523          return *this;
 524       }
 525
 526       void swap(Data &d)
 527       {
 528          value_compare& mycomp    = *this, & othercomp = d;
 529          boost::adl_move_swap(mycomp, othercomp);
 530          this->m_seq.swap(d.m_seq);
 531       }
 532
 533       container_type m_seq;
 534    };
 535
 536    Data m_data;
 537    BOOST_COPYABLE_AND_MOVABLE(flat_tree)
 538
 539    public:
 540
 541    typedef typename container_type::value_type               value_type;
 542    typedef typename container_type::pointer                  pointer;
 543    typedef typename container_type::const_pointer            const_pointer;
 544    typedef typename container_type::reference                reference;
 545    typedef typename container_type::const_reference          const_reference;
 546    typedef typename KeyOfValue::type                        key_type;
 547    typedef Compare                                          key_compare;
 548    typedef typename container_type::allocator_type           allocator_type;
 549    typedef typename container_type::size_type                size_type;
 550    typedef typename container_type::difference_type          difference_type;
 551    typedef typename container_type::iterator                 iterator;
 552    typedef typename container_type::const_iterator           const_iterator;
 553    typedef typename container_type::reverse_iterator         reverse_iterator;
 554    typedef typename container_type::const_reverse_iterator   const_reverse_iterator;
 555
 556    //!Standard extension
 557    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
 558       (boost::container::dtl::, container_type
 559       ,stored_allocator_type, allocator_type)               stored_allocator_type;
 560
 561    static const bool has_stored_allocator_type =
 562       BOOST_INTRUSIVE_HAS_TYPE(boost::container::dtl::, container_type, stored_allocator_type);
 563
 564    private:
 565    typedef allocator_traits<stored_allocator_type> stored_allocator_traits;
 566
 567    public:
 568    typedef typename dtl::if_c
 569       <has_stored_allocator_type, const stored_allocator_type &, allocator_type>::type get_stored_allocator_const_return_t;
 570
 571    typedef typename dtl::if_c
 572       <has_stored_allocator_type, stored_allocator_type &, allocator_type>::type get_stored_allocator_noconst_return_t;
 573
 574    BOOST_CONTAINER_FORCEINLINE flat_tree()
 575       : m_data()
 576    { }
 577
 578    BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const Compare& comp)
 579       : m_data(comp)
 580    { }
 581
 582    BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const allocator_type& a)
 583       : m_data(a)
 584    { }
 585
 586    BOOST_CONTAINER_FORCEINLINE flat_tree(const Compare& comp, const allocator_type& a)
 587       : m_data(comp, a)
 588    { }
 589
 590    BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x)
 591       :  m_data(x.m_data)
 592    { }
 593
 594    BOOST_CONTAINER_FORCEINLINE flat_tree(BOOST_RV_REF(flat_tree) x)
 595       BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
 596       :  m_data(boost::move(x.m_data))
 597    { }
 598
 599    BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x, const allocator_type &a)
 600       :  m_data(x.m_data, a)
 601    { }
 602
 603    BOOST_CONTAINER_FORCEINLINE flat_tree(BOOST_RV_REF(flat_tree) x, const allocator_type &a)
 604       :  m_data(boost::move(x.m_data), a)
 605    { }
 606
 607    template <class InputIterator>
 608    BOOST_CONTAINER_FORCEINLINE
 609    flat_tree( ordered_range_t, InputIterator first, InputIterator last)
 610       : m_data()
 611    {
 612       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
 613       BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
 614    }
 615
 616    template <class InputIterator>
 617    BOOST_CONTAINER_FORCEINLINE
 618    flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
 619       : m_data(comp)
 620    {
 621       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
 622       BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
 623    }
 624
 625    template <class InputIterator>
 626    BOOST_CONTAINER_FORCEINLINE
 627    flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
 628       : m_data(comp, a)
 629    {
 630       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
 631       BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
 632    }
 633
 634    template <class InputIterator>
 635    BOOST_CONTAINER_FORCEINLINE
 636    flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last)
 637       : m_data()
 638    {
 639       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
 640       BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
 641    }
 642
 643    template <class InputIterator>
 644    BOOST_CONTAINER_FORCEINLINE
 645    flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
 646       : m_data(comp)
 647    {
 648       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
 649       BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
 650    }
 651
 652    template <class InputIterator>
 653    BOOST_CONTAINER_FORCEINLINE
 654    flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
 655       : m_data(comp, a)
 656    {
 657       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
 658       BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
 659    }
 660
 661    template <class InputIterator>
 662    BOOST_CONTAINER_FORCEINLINE
 663    flat_tree( bool unique_insertion, InputIterator first, InputIterator last)
 664       : m_data()
 665    {
 666       this->priv_range_insertion_construct(unique_insertion, first, last);
 667    }
 668
 669    template <class InputIterator>
 670    BOOST_CONTAINER_FORCEINLINE
 671    flat_tree( bool unique_insertion, InputIterator first, InputIterator last
 672             , const Compare& comp)
 673       : m_data(comp)
 674    {
 675       this->priv_range_insertion_construct(unique_insertion, first, last);
 676    }
 677
 678    template <class InputIterator>
 679    BOOST_CONTAINER_FORCEINLINE
 680    flat_tree( bool unique_insertion, InputIterator first, InputIterator last
 681             , const allocator_type& a)
 682       : m_data(a)
 683    {
 684       this->priv_range_insertion_construct(unique_insertion, first, last);
 685    }
 686
 687    template <class InputIterator>
 688    BOOST_CONTAINER_FORCEINLINE
 689    flat_tree( bool unique_insertion, InputIterator first, InputIterator last
 690             , const Compare& comp, const allocator_type& a)
 691       : m_data(comp, a)
 692    {
 693       this->priv_range_insertion_construct(unique_insertion, first, last);
 694    }
 695
 696    BOOST_CONTAINER_FORCEINLINE ~flat_tree()
 697    {}
 698
 699    BOOST_CONTAINER_FORCEINLINE flat_tree&  operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x)
 700    {  m_data = x.m_data;   return *this;  }
 701
 702    BOOST_CONTAINER_FORCEINLINE flat_tree&  operator=(BOOST_RV_REF(flat_tree) x)
 703       BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
 704                           allocator_traits_type::is_always_equal::value) &&
 705                            boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
 706    {  m_data = boost::move(x.m_data); return *this;  }
 707
 708    BOOST_CONTAINER_FORCEINLINE const value_compare &priv_value_comp() const
 709    { return static_cast<const value_compare &>(this->m_data); }
 710
 711    BOOST_CONTAINER_FORCEINLINE value_compare &priv_value_comp()
 712    { return static_cast<value_compare &>(this->m_data); }
 713
 714    BOOST_CONTAINER_FORCEINLINE const key_compare &priv_key_comp() const
 715    { return this->priv_value_comp().get_comp(); }
 716
 717    BOOST_CONTAINER_FORCEINLINE key_compare &priv_key_comp()
 718    { return this->priv_value_comp().get_comp(); }
 719
 720    struct insert_commit_data
 721    {
 722       const_iterator position;
 723    };
 724
 725    public:
 726    // accessors:
 727    BOOST_CONTAINER_FORCEINLINE Compare key_comp() const
 728    { return this->m_data.get_comp(); }
 729
 730    BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
 731    { return this->m_data; }
 732
 733    BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const
 734    { return this->m_data.m_seq.get_allocator(); }
 735
 736    BOOST_CONTAINER_FORCEINLINE get_stored_allocator_const_return_t get_stored_allocator() const
 737    {
 738       return flat_tree_get_stored_allocator(this->m_data.m_seq, dtl::bool_<has_stored_allocator_type>());
 739    }
 740
 741    BOOST_CONTAINER_FORCEINLINE get_stored_allocator_noconst_return_t get_stored_allocator()
 742    {
 743       return flat_tree_get_stored_allocator(this->m_data.m_seq, dtl::bool_<has_stored_allocator_type>());
 744    }
 745
 746    BOOST_CONTAINER_FORCEINLINE iterator begin()
 747    { return this->m_data.m_seq.begin(); }
 748
 749    BOOST_CONTAINER_FORCEINLINE const_iterator begin() const
 750    { return this->cbegin(); }
 751
 752    BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const
 753    { return this->m_data.m_seq.begin(); }
 754
 755    BOOST_CONTAINER_FORCEINLINE iterator end()
 756    { return this->m_data.m_seq.end(); }
 757
 758    BOOST_CONTAINER_FORCEINLINE const_iterator end() const
 759    { return this->cend(); }
 760
 761    BOOST_CONTAINER_FORCEINLINE const_iterator cend() const
 762    { return this->m_data.m_seq.end(); }
 763
 764    BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin()
 765    { return reverse_iterator(this->end()); }
 766
 767    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const
 768    {  return this->crbegin();  }
 769
 770    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const
 771    {  return const_reverse_iterator(this->cend());  }
 772
 773    BOOST_CONTAINER_FORCEINLINE reverse_iterator rend()
 774    { return reverse_iterator(this->begin()); }
 775
 776    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const
 777    { return this->crend(); }
 778
 779    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const
 780    { return const_reverse_iterator(this->cbegin()); }
 781
 782    BOOST_CONTAINER_FORCEINLINE bool empty() const
 783    { return this->m_data.m_seq.empty(); }
 784
 785    BOOST_CONTAINER_FORCEINLINE size_type size() const
 786    { return this->m_data.m_seq.size(); }
 787
 788    BOOST_CONTAINER_FORCEINLINE size_type max_size() const
 789    { return this->m_data.m_seq.max_size(); }
 790
 791    BOOST_CONTAINER_FORCEINLINE void swap(flat_tree& other)
 792       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
 793                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value )
 794    {  this->m_data.swap(other.m_data);  }
 795
 796    public:
 797    // insert/erase
 798    std::pair<iterator,bool> insert_unique(const value_type& val)
 799    {
 800       std::pair<iterator,bool> ret;
 801       insert_commit_data data;
 802       ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data);
 803       ret.first = ret.second ? this->priv_insert_commit(data, val)
 804                              : this->begin() + (data.position - this->cbegin());
 805                              //: iterator(vector_iterator_get_ptr(data.position));
 806       return ret;
 807    }
 808
 809    std::pair<iterator,bool> insert_unique(BOOST_RV_REF(value_type) val)
 810    {
 811       std::pair<iterator,bool> ret;
 812       insert_commit_data data;
 813       ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data);
 814       ret.first = ret.second ? this->priv_insert_commit(data, boost::move(val))
 815                              : this->begin() + (data.position - this->cbegin());
 816                              //: iterator(vector_iterator_get_ptr(data.position));
 817       return ret;
 818    }
 819
 820    iterator insert_equal(const value_type& val)
 821    {
 822       iterator i = this->upper_bound(KeyOfValue()(val));
 823       i = this->m_data.m_seq.insert(i, val);
 824       return i;
 825    }
 826
 827    iterator insert_equal(BOOST_RV_REF(value_type) mval)
 828    {
 829       iterator i = this->upper_bound(KeyOfValue()(mval));
 830       i = this->m_data.m_seq.insert(i, boost::move(mval));
 831       return i;
 832    }
 833
 834    iterator insert_unique(const_iterator hint, const value_type& val)
 835    {
 836       BOOST_ASSERT(this->priv_in_range_or_end(hint));
 837       insert_commit_data data;
 838       return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
 839             ? this->priv_insert_commit(data, val)
 840             : this->begin() + (data.position - this->cbegin());
 841             //: iterator(vector_iterator_get_ptr(data.position));
 842    }
 843
 844    iterator insert_unique(const_iterator hint, BOOST_RV_REF(value_type) val)
 845    {
 846       BOOST_ASSERT(this->priv_in_range_or_end(hint));
 847       insert_commit_data data;
 848       return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
 849          ? this->priv_insert_commit(data, boost::move(val))
 850          : this->begin() + (data.position - this->cbegin());
 851          //: iterator(vector_iterator_get_ptr(data.position));
 852    }
 853
 854    iterator insert_equal(const_iterator hint, const value_type& val)
 855    {
 856       BOOST_ASSERT(this->priv_in_range_or_end(hint));
 857       insert_commit_data data;
 858       this->priv_insert_equal_prepare(hint, val, data);
 859       return this->priv_insert_commit(data, val);
 860    }
 861
 862    iterator insert_equal(const_iterator hint, BOOST_RV_REF(value_type) mval)
 863    {
 864       BOOST_ASSERT(this->priv_in_range_or_end(hint));
 865       insert_commit_data data;
 866       this->priv_insert_equal_prepare(hint, mval, data);
 867       return this->priv_insert_commit(data, boost::move(mval));
 868    }
 869
 870    template <class InIt>
 871    void insert_unique(InIt first, InIt last)
 872    {
 873       dtl::bool_<is_contiguous_container<container_type>::value> contiguous_tag;
 874       container_type &seq = this->m_data.m_seq;
 875       value_compare &val_cmp = this->priv_value_comp();
 876
 877       //Step 1: put new elements in the back
 878       typename container_type::iterator const it = seq.insert(seq.cend(), first, last);
 879
 880       //Step 2: sort them
 881       boost::movelib::pdqsort(it, seq.end(), val_cmp);
 882
 883       //Step 3: only left unique values from the back not already present in the original range
 884       typename container_type::iterator const e = boost::movelib::inplace_set_unique_difference
 885          (it, seq.end(), seq.begin(), it, val_cmp);
 886
 887       seq.erase(e, seq.cend());
 888       //it might be invalidated by erasing [e, seq.end) if e == it
 889       if (it != e)
 890       {
 891          //Step 4: merge both ranges
 892          (flat_tree_container_inplace_merge)(seq, it, this->priv_value_comp(), contiguous_tag);
 893       }
 894    }
 895
 896    template <class InIt>
 897    void insert_equal(InIt first, InIt last)
 898    {
 899       dtl::bool_<is_contiguous_container<container_type>::value> contiguous_tag;
 900       container_type &seq = this->m_data.m_seq;
 901       typename container_type::iterator const it = seq.insert(seq.cend(), first, last);
 902       (flat_tree_container_inplace_sort_ending)(seq, it, this->priv_value_comp(), contiguous_tag);
 903       (flat_tree_container_inplace_merge)      (seq, it, this->priv_value_comp(), contiguous_tag);
 904    }
 905
 906    //Ordered
 907
 908    template <class InIt>
 909    void insert_equal(ordered_range_t, InIt first, InIt last)
 910    {
 911       const bool value = boost::container::dtl::
 912          has_member_function_callable_with_merge_unique<container_type, InIt, InIt, value_compare>::value;
 913       (flat_tree_merge_equal)(this->m_data.m_seq, first, last, this->priv_value_comp(), dtl::bool_<value>());
 914    }
 915
 916    template <class InIt>
 917    void insert_unique(ordered_unique_range_t, InIt first, InIt last)
 918    {
 919       const bool value = boost::container::dtl::
 920          has_member_function_callable_with_merge_unique<container_type, InIt, InIt, value_compare>::value;
 921       (flat_tree_merge_unique)(this->m_data.m_seq, first, last, this->priv_value_comp(), dtl::bool_<value>());
 922    }
 923
 924    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 925
 926    template <class... Args>
 927    std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args)
 928    {
 929       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
 930       value_type *pval = reinterpret_cast<value_type *>(v.data);
 931       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
 932       stored_allocator_traits::construct(a, pval, ::boost::forward<Args>(args)... );
 933       value_destructor<stored_allocator_type, value_type> d(a, *pval);
 934       return this->insert_unique(::boost::move(*pval));
 935    }
 936
 937    template <class... Args>
 938    iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args)
 939    {
 940       //hint checked in insert_unique
 941       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
 942       value_type *pval = reinterpret_cast<value_type *>(v.data);
 943       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
 944       stored_allocator_traits::construct(a, pval, ::boost::forward<Args>(args)... );
 945       value_destructor<stored_allocator_type, value_type> d(a, *pval);
 946       return this->insert_unique(hint, ::boost::move(*pval));
 947    }
 948
 949    template <class... Args>
 950    iterator emplace_equal(BOOST_FWD_REF(Args)... args)
 951    {
 952       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
 953       value_type *pval = reinterpret_cast<value_type *>(v.data);
 954       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
 955       stored_allocator_traits::construct(a, pval, ::boost::forward<Args>(args)... );
 956       value_destructor<stored_allocator_type, value_type> d(a, *pval);
 957       return this->insert_equal(::boost::move(*pval));
 958    }
 959
 960    template <class... Args>
 961    iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args)
 962    {
 963       //hint checked in insert_equal
 964       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
 965       value_type *pval = reinterpret_cast<value_type *>(v.data);
 966       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
 967       stored_allocator_traits::construct(a, pval, ::boost::forward<Args>(args)... );
 968       value_destructor<stored_allocator_type, value_type> d(a, *pval);
 969       return this->insert_equal(hint, ::boost::move(*pval));
 970    }
 971
 972    template <class KeyType, class... Args>
 973    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace
 974       (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args)
 975    {
 976       std::pair<iterator,bool> ret;
 977       insert_commit_data data;
 978       const key_type & k = key;
 979       ret.second = hint == const_iterator()
 980          ? this->priv_insert_unique_prepare(k, data)
 981          : this->priv_insert_unique_prepare(hint, k, data);
 982
 983       if(!ret.second){
 984          ret.first  = this->nth(data.position - this->cbegin());
 985       }
 986       else{
 987          typedef typename emplace_functor_type<try_emplace_t, KeyType, Args...>::type func_t;
 988          typedef emplace_iterator<value_type, func_t, difference_type> it_t;
 989          func_t func(try_emplace_t(), ::boost::forward<KeyType>(key), ::boost::forward<Args>(args)...);
 990          ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());
 991       }
 992       return ret;
 993    }
 994
 995    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 996
 997    #define BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE(N) \
 998    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
 999    std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
1000    {\
1001       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
1002       value_type *pval = reinterpret_cast<value_type *>(v.data);\
1003       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
1004       stored_allocator_traits::construct(a, pval BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1005       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
1006       return this->insert_unique(::boost::move(*pval));\
1007    }\
1008    \
1009    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1010    iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1011    {\
1012       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
1013       value_type *pval = reinterpret_cast<value_type *>(v.data);\
1014       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
1015       stored_allocator_traits::construct(a, pval BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1016       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
1017       return this->insert_unique(hint, ::boost::move(*pval));\
1018    }\
1019    \
1020    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1021    iterator emplace_equal(BOOST_MOVE_UREF##N)\
1022    {\
1023       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
1024       value_type *pval = reinterpret_cast<value_type *>(v.data);\
1025       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
1026       stored_allocator_traits::construct(a, pval BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1027       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
1028       return this->insert_equal(::boost::move(*pval));\
1029    }\
1030    \
1031    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1032    iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1033    {\
1034       typename dtl::aligned_storage <sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
1035       value_type *pval = reinterpret_cast<value_type *>(v.data);\
1036       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
1037       stored_allocator_traits::construct(a, pval BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1038       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
1039       return this->insert_equal(hint, ::boost::move(*pval));\
1040    }\
1041    template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\
1042    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\
1043       try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1044    {\
1045       std::pair<iterator,bool> ret;\
1046       insert_commit_data data;\
1047       const key_type & k = key;\
1048       ret.second = hint == const_iterator()\
1049          ? this->priv_insert_unique_prepare(k, data)\
1050          : this->priv_insert_unique_prepare(hint, k, data);\
1051       \
1052       if(!ret.second){\
1053          ret.first  = this->nth(data.position - this->cbegin());\
1054       }\
1055       else{\
1056          typedef typename emplace_functor_type<try_emplace_t, KeyType BOOST_MOVE_I##N BOOST_MOVE_TARG##N>::type func_t;\
1057          typedef emplace_iterator<value_type, func_t, difference_type> it_t;\
1058          func_t func(try_emplace_t(), ::boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1059          ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());\
1060       }\
1061       return ret;\
1062    }\
1063    //
1064    BOOST_MOVE_ITERATE_0TO7(BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE)
1065    #undef BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE
1066
1067    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1068
1069    template<class KeyType, class M>
1070    std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj)
1071    {
1072       const key_type& k = key;
1073       std::pair<iterator,bool> ret;
1074       insert_commit_data data;
1075       ret.second = hint == const_iterator()
1076          ? this->priv_insert_unique_prepare(k, data)
1077          : this->priv_insert_unique_prepare(hint, k, data);
1078       if(!ret.second){
1079          ret.first  = this->nth(data.position - this->cbegin());
1080          ret.first->second = boost::forward<M>(obj);
1081       }
1082       else{
1083          typedef typename emplace_functor_type<KeyType, M>::type func_t;
1084          typedef emplace_iterator<value_type, func_t, difference_type> it_t;
1085          func_t func(boost::forward<KeyType>(key), boost::forward<M>(obj));
1086          ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());
1087       }
1088       return ret;
1089    }
1090
1091    BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator position)
1092    {  return this->m_data.m_seq.erase(position);  }
1093
1094    size_type erase(const key_type& k)
1095    {
1096       std::pair<iterator,iterator > itp = this->equal_range(k);
1097       size_type ret = static_cast<size_type>(itp.second-itp.first);
1098       if (ret){
1099          this->m_data.m_seq.erase(itp.first, itp.second);
1100       }
1101       return ret;
1102    }
1103
1104    BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last)
1105    {  return this->m_data.m_seq.erase(first, last);  }
1106
1107    BOOST_CONTAINER_FORCEINLINE void clear()
1108    {  this->m_data.m_seq.clear();  }
1109
1110    //! <b>Effects</b>: Tries to deallocate the excess of memory created
1111    //    with previous allocations. The size of the vector is unchanged
1112    //!
1113    //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1114    //!
1115    //! <b>Complexity</b>: Linear to size().
1116    BOOST_CONTAINER_FORCEINLINE void shrink_to_fit()
1117    {  this->m_data.m_seq.shrink_to_fit();  }
1118
1119    BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1120    {
1121       const bool value = boost::container::dtl::
1122          has_member_function_callable_with_nth<container_type, size_type>::value;
1123       return flat_tree_nth<iterator>(this->m_data.m_seq, n, dtl::bool_<value>());
1124    }
1125
1126    BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1127    {
1128       const bool value = boost::container::dtl::
1129          has_member_function_callable_with_nth<container_type, size_type>::value;
1130       return flat_tree_nth<const_iterator>(this->m_data.m_seq, n, dtl::bool_<value>());
1131    }
1132
1133    BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1134    {
1135       const bool value = boost::container::dtl::
1136          has_member_function_callable_with_index_of<container_type, iterator>::value;
1137       return flat_tree_index_of(this->m_data.m_seq, p, dtl::bool_<value>());
1138    }
1139
1140    BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1141    {
1142       const bool value = boost::container::dtl::
1143          has_member_function_callable_with_index_of<container_type, const_iterator>::value;
1144       return flat_tree_index_of(this->m_data.m_seq, p, dtl::bool_<value>());
1145    }
1146
1147    // set operations:
1148    iterator find(const key_type& k)
1149    {
1150       iterator i = this->lower_bound(k);
1151       iterator end_it = this->end();
1152       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
1153          i = end_it;
1154       }
1155       return i;
1156    }
1157
1158    const_iterator find(const key_type& k) const
1159    {
1160       const_iterator i = this->lower_bound(k);
1161
1162       const_iterator end_it = this->cend();
1163       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
1164          i = end_it;
1165       }
1166       return i;
1167    }
1168
1169    template<class K>
1170    typename dtl::enable_if_transparent<key_compare, K, iterator>::type
1171       find(const K& k)
1172    {
1173       iterator i = this->lower_bound(k);
1174       iterator end_it = this->end();
1175       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
1176          i = end_it;
1177       }
1178       return i;
1179    }
1180
1181    template<class K>
1182    typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
1183       find(const K& k) const
1184    {
1185       const_iterator i = this->lower_bound(k);
1186
1187       const_iterator end_it = this->cend();
1188       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
1189          i = end_it;
1190       }
1191       return i;
1192    }
1193
1194    size_type count(const key_type& k) const
1195    {
1196       std::pair<const_iterator, const_iterator> p = this->equal_range(k);
1197       size_type n = p.second - p.first;
1198       return n;
1199    }
1200
1201    template<class K>
1202    typename dtl::enable_if_transparent<key_compare, K, size_type>::type
1203       count(const K& k) const
1204    {
1205       std::pair<const_iterator, const_iterator> p = this->equal_range(k);
1206       size_type n = p.second - p.first;
1207       return n;
1208    }
1209
1210    BOOST_CONTAINER_FORCEINLINE bool contains(const key_type& x) const
1211    {  return this->find(x) != this->cend();  }
1212
1213    template<typename K>
1214    BOOST_CONTAINER_FORCEINLINE
1215       typename dtl::enable_if_transparent<key_compare, K, bool>::type
1216          contains(const K& x) const
1217    {  return this->find(x) != this->cend();  }
1218
1219    template<class C2>
1220    BOOST_CONTAINER_FORCEINLINE void merge_unique(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source)
1221    {
1222       this->insert_unique( boost::make_move_iterator(source.begin())
1223                          , boost::make_move_iterator(source.end()));
1224    }
1225
1226    template<class C2>
1227    BOOST_CONTAINER_FORCEINLINE void merge_equal(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source)
1228    {
1229       this->insert_equal( boost::make_move_iterator(source.begin())
1230                         , boost::make_move_iterator(source.end()));
1231    }
1232
1233    BOOST_CONTAINER_FORCEINLINE void merge_unique(flat_tree& source)
1234    {
1235       const bool value = boost::container::dtl::
1236          has_member_function_callable_with_merge_unique<container_type, iterator, iterator, value_compare>::value;
1237       (flat_tree_merge_unique)
1238          ( this->m_data.m_seq
1239          , boost::make_move_iterator(source.m_data.m_seq.begin())
1240          , boost::make_move_iterator(source.m_data.m_seq.end())
1241          , this->priv_value_comp()
1242          , dtl::bool_<value>());
1243    }
1244
1245    BOOST_CONTAINER_FORCEINLINE void merge_equal(flat_tree& source)
1246    {
1247       const bool value = boost::container::dtl::
1248          has_member_function_callable_with_merge<container_type, iterator, iterator, value_compare>::value;
1249       (flat_tree_merge_equal)
1250          ( this->m_data.m_seq
1251          , boost::make_move_iterator(source.m_data.m_seq.begin())
1252          , boost::make_move_iterator(source.m_data.m_seq.end())
1253          , this->priv_value_comp()
1254          , dtl::bool_<value>());
1255    }
1256
1257    BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k)
1258    {  return this->priv_lower_bound(this->begin(), this->end(), k);  }
1259
1260    BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const
1261    {  return this->priv_lower_bound(this->cbegin(), this->cend(), k);  }
1262
1263    template<class K>
1264    BOOST_CONTAINER_FORCEINLINE
1265       typename dtl::enable_if_transparent<key_compare, K, iterator>::type
1266          lower_bound(const K& k)
1267    {  return this->priv_lower_bound(this->begin(), this->end(), k);  }
1268
1269    template<class K>
1270    BOOST_CONTAINER_FORCEINLINE
1271       typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
1272          lower_bound(const K& k) const
1273    {  return this->priv_lower_bound(this->cbegin(), this->cend(), k);  }
1274
1275    BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k)
1276    {  return this->priv_upper_bound(this->begin(), this->end(), k);  }
1277
1278    BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const
1279    {  return this->priv_upper_bound(this->cbegin(), this->cend(), k);  }
1280
1281    template<class K>
1282    BOOST_CONTAINER_FORCEINLINE
1283       typename dtl::enable_if_transparent<key_compare, K,iterator>::type
1284    upper_bound(const K& k)
1285    {  return this->priv_upper_bound(this->begin(), this->end(), k);  }
1286
1287    template<class K>
1288    BOOST_CONTAINER_FORCEINLINE
1289       typename dtl::enable_if_transparent<key_compare, K,const_iterator>::type
1290          upper_bound(const K& k) const
1291    {  return this->priv_upper_bound(this->cbegin(), this->cend(), k);  }
1292
1293    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& k)
1294    {  return this->priv_equal_range(this->begin(), this->end(), k);  }
1295
1296    BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
1297    {  return this->priv_equal_range(this->cbegin(), this->cend(), k);  }
1298
1299    template<class K>
1300    BOOST_CONTAINER_FORCEINLINE
1301       typename dtl::enable_if_transparent<key_compare, K,std::pair<iterator,iterator> >::type
1302          equal_range(const K& k)
1303    {  return this->priv_equal_range(this->begin(), this->end(), k);  }
1304
1305    template<class K>
1306    BOOST_CONTAINER_FORCEINLINE
1307       typename dtl::enable_if_transparent<key_compare, K,std::pair<const_iterator,const_iterator> >::type
1308          equal_range(const K& k) const
1309    {  return this->priv_equal_range(this->cbegin(), this->cend(), k);  }
1310
1311
1312    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, iterator> lower_bound_range(const key_type& k)
1313    {  return this->priv_lower_bound_range(this->begin(), this->end(), k);  }
1314
1315    BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
1316    {  return this->priv_lower_bound_range(this->cbegin(), this->cend(), k);  }
1317
1318    template<class K>
1319    BOOST_CONTAINER_FORCEINLINE
1320       typename dtl::enable_if_transparent<key_compare, K,std::pair<iterator,iterator> >::type
1321          lower_bound_range(const K& k)
1322    {  return this->priv_lower_bound_range(this->begin(), this->end(), k);  }
1323
1324    template<class K>
1325    BOOST_CONTAINER_FORCEINLINE
1326       typename dtl::enable_if_transparent<key_compare, K,std::pair<const_iterator,const_iterator> >::type
1327          lower_bound_range(const K& k) const
1328    {  return this->priv_lower_bound_range(this->cbegin(), this->cend(), k);  }
1329
1330    BOOST_CONTAINER_FORCEINLINE size_type capacity() const
1331    {
1332       const bool value = boost::container::dtl::
1333          has_member_function_callable_with_capacity<container_type>::value;
1334       return (flat_tree_capacity)(this->m_data.m_seq, dtl::bool_<value>());
1335    }
1336
1337    BOOST_CONTAINER_FORCEINLINE void reserve(size_type cnt)
1338    {
1339       const bool value = boost::container::dtl::
1340          has_member_function_callable_with_reserve<container_type, size_type>::value;
1341       (flat_tree_reserve)(this->m_data.m_seq, cnt, dtl::bool_<value>());
1342    }
1343
1344    BOOST_CONTAINER_FORCEINLINE container_type extract_sequence()
1345    {
1346       return boost::move(m_data.m_seq);
1347    }
1348
1349    BOOST_CONTAINER_FORCEINLINE container_type &get_sequence_ref()
1350    {
1351       return m_data.m_seq;
1352    }
1353
1354    BOOST_CONTAINER_FORCEINLINE void adopt_sequence_equal(BOOST_RV_REF(container_type) seq)
1355    {
1356       (flat_tree_adopt_sequence_equal)( m_data.m_seq, boost::move(seq), this->priv_value_comp()
1357          , dtl::bool_<is_contiguous_container<container_type>::value>());
1358    }
1359
1360    BOOST_CONTAINER_FORCEINLINE void adopt_sequence_unique(BOOST_RV_REF(container_type) seq)
1361    {
1362       (flat_tree_adopt_sequence_unique)(m_data.m_seq, boost::move(seq), this->priv_value_comp()
1363          , dtl::bool_<is_contiguous_container<container_type>::value>());
1364    }
1365
1366    void adopt_sequence_equal(ordered_range_t, BOOST_RV_REF(container_type) seq)
1367    {
1368       BOOST_ASSERT((is_sorted)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
1369       m_data.m_seq = boost::move(seq);
1370    }
1371
1372    void adopt_sequence_unique(ordered_unique_range_t, BOOST_RV_REF(container_type) seq)
1373    {
1374       BOOST_ASSERT((is_sorted_and_unique)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
1375       m_data.m_seq = boost::move(seq);
1376    }
1377
1378    BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_tree& x, const flat_tree& y)
1379    {
1380       return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());
1381    }
1382
1383    BOOST_CONTAINER_FORCEINLINE friend bool operator<(const flat_tree& x, const flat_tree& y)
1384    {
1385       return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
1386    }
1387
1388    BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const flat_tree& x, const flat_tree& y)
1389       {  return !(x == y); }
1390
1391    BOOST_CONTAINER_FORCEINLINE friend bool operator>(const flat_tree& x, const flat_tree& y)
1392       {  return y < x;  }
1393
1394    BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const flat_tree& x, const flat_tree& y)
1395       {  return !(y < x);  }
1396
1397    BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const flat_tree& x, const flat_tree& y)
1398       {  return !(x < y);  }
1399
1400    BOOST_CONTAINER_FORCEINLINE friend void swap(flat_tree& x, flat_tree& y)
1401       {  x.swap(y);  }
1402
1403    private:
1404
1405    template <class InputIterator>
1406    void priv_range_insertion_construct( bool unique_insertion, InputIterator first, InputIterator last)
1407    {
1408       //Use cend() as hint to achieve linear time for
1409       //ordered ranges as required by the standard
1410       //for the constructor
1411       //Call end() every iteration as reallocation might have invalidated iterators
1412       if(unique_insertion){
1413          this->insert_unique(first, last);
1414       }
1415       else{
1416          this->insert_equal (first, last);
1417       }
1418    }
1419
1420    BOOST_CONTAINER_FORCEINLINE bool priv_in_range_or_end(const_iterator pos) const
1421    {
1422       return (this->begin() <= pos) && (pos <= this->end());
1423    }
1424
1425    // insert/erase
1426    void priv_insert_equal_prepare
1427       (const_iterator pos, const value_type& val, insert_commit_data &data)
1428    {
1429       // N1780
1430       //   To insert val at pos:
1431       //   if pos == end || val <= *pos
1432       //      if pos == begin || val >= *(pos-1)
1433       //         insert val before pos
1434       //      else
1435       //         insert val before upper_bound(val)
1436       //   else
1437       //      insert val before lower_bound(val)
1438       const value_compare &val_cmp = this->m_data;
1439
1440       if(pos == this->cend() || !val_cmp(*pos, val)){
1441          if (pos == this->cbegin() || !val_cmp(val, pos[-1])){
1442             data.position = pos;
1443          }
1444          else{
1445             data.position =
1446                this->priv_upper_bound(this->cbegin(), pos, KeyOfValue()(val));
1447          }
1448       }
1449       else{
1450          data.position =
1451             this->priv_lower_bound(pos, this->cend(), KeyOfValue()(val));
1452       }
1453    }
1454
1455    bool priv_insert_unique_prepare
1456       (const_iterator b, const_iterator e, const key_type& k, insert_commit_data &commit_data)
1457    {
1458       const key_compare &key_cmp  = this->priv_key_comp();
1459       commit_data.position = this->priv_lower_bound(b, e, k);
1460       return commit_data.position == e || key_cmp(k, KeyOfValue()(*commit_data.position));
1461    }
1462
1463    BOOST_CONTAINER_FORCEINLINE bool priv_insert_unique_prepare
1464       (const key_type& k, insert_commit_data &commit_data)
1465    {  return this->priv_insert_unique_prepare(this->cbegin(), this->cend(), k, commit_data);   }
1466
1467    bool priv_insert_unique_prepare
1468       (const_iterator pos, const key_type& k, insert_commit_data &commit_data)
1469    {
1470       //N1780. Props to Howard Hinnant!
1471       //To insert k at pos:
1472       //if pos == end || k <= *pos
1473       //   if pos == begin || k >= *(pos-1)
1474       //      insert k before pos
1475       //   else
1476       //      insert k before upper_bound(k)
1477       //else if pos+1 == end || k <= *(pos+1)
1478       //   insert k after pos
1479       //else
1480       //   insert k before lower_bound(k)
1481       const key_compare &key_cmp = this->priv_key_comp();
1482       const const_iterator cend_it = this->cend();
1483       if(pos == cend_it || key_cmp(k, KeyOfValue()(*pos))){ //Check if k should go before end
1484          const const_iterator cbeg = this->cbegin();
1485          commit_data.position = pos;
1486          if(pos == cbeg){  //If container is empty then insert it in the beginning
1487             return true;
1488          }
1489          const_iterator prev(pos);
1490          --prev;
1491          if(key_cmp(KeyOfValue()(*prev), k)){   //If previous element was less, then it should go between prev and pos
1492             return true;
1493          }
1494          else if(!key_cmp(k, KeyOfValue()(*prev))){   //If previous was equal then insertion should fail
1495             commit_data.position = prev;
1496             return false;
1497          }
1498          else{ //Previous was bigger so insertion hint was pointless, dispatch to hintless insertion
1499                //but reduce the search between beg and prev as prev is bigger than k
1500             return this->priv_insert_unique_prepare(cbeg, prev, k, commit_data);
1501          }
1502       }
1503       else{
1504          //The hint is before the insertion position, so insert it
1505          //in the remaining range [pos, end)
1506          return this->priv_insert_unique_prepare(pos, cend_it, k, commit_data);
1507       }
1508    }
1509
1510    template<class Convertible>
1511    BOOST_CONTAINER_FORCEINLINE iterator priv_insert_commit
1512       (insert_commit_data &commit_data, BOOST_FWD_REF(Convertible) convertible)
1513    {
1514       return this->m_data.m_seq.insert
1515          ( commit_data.position
1516          , boost::forward<Convertible>(convertible));
1517    }
1518
1519    template <class RanIt, class K>
1520    RanIt priv_lower_bound(RanIt first, const RanIt last,
1521                           const K & key) const
1522    {
1523       const Compare &key_cmp = this->m_data.get_comp();
1524       KeyOfValue key_extract;
1525       size_type len = static_cast<size_type>(last - first);
1526       RanIt middle;
1527
1528       while (len) {
1529          size_type step = len >> 1;
1530          middle = first;
1531          middle += step;
1532
1533          if (key_cmp(key_extract(*middle), key)) {
1534             first = ++middle;
1535             len -= step + 1;
1536          }
1537          else{
1538             len = step;
1539          }
1540       }
1541       return first;
1542    }
1543
1544    template <class RanIt, class K>
1545    RanIt priv_upper_bound
1546       (RanIt first, const RanIt last,const K & key) const
1547    {
1548       const Compare &key_cmp = this->m_data.get_comp();
1549       KeyOfValue key_extract;
1550       size_type len = static_cast<size_type>(last - first);
1551       RanIt middle;
1552
1553       while (len) {
1554          size_type step = len >> 1;
1555          middle = first;
1556          middle += step;
1557
1558          if (key_cmp(key, key_extract(*middle))) {
1559             len = step;
1560          }
1561          else{
1562             first = ++middle;
1563             len -= step + 1;
1564          }
1565       }
1566       return first;
1567    }
1568
1569    template <class RanIt, class K>
1570    std::pair<RanIt, RanIt>
1571       priv_equal_range(RanIt first, RanIt last, const K& key) const
1572    {
1573       const Compare &key_cmp = this->m_data.get_comp();
1574       KeyOfValue key_extract;
1575       size_type len = static_cast<size_type>(last - first);
1576       RanIt middle;
1577
1578       while (len) {
1579          size_type step = len >> 1;
1580          middle = first;
1581          middle += step;
1582
1583          if (key_cmp(key_extract(*middle), key)){
1584             first = ++middle;
1585             len -= step + 1;
1586          }
1587          else if (key_cmp(key, key_extract(*middle))){
1588             len = step;
1589          }
1590          else {
1591             //Middle is equal to key
1592             last = first;
1593             last += len;
1594             RanIt const first_ret = this->priv_lower_bound(first, middle, key);
1595             return std::pair<RanIt, RanIt>
1596                ( first_ret, this->priv_upper_bound(++middle, last, key));
1597          }
1598       }
1599       return std::pair<RanIt, RanIt>(first, first);
1600    }
1601
1602    template<class RanIt, class K>
1603    std::pair<RanIt, RanIt> priv_lower_bound_range(RanIt first, RanIt last, const K& k) const
1604    {
1605       const Compare &key_cmp = this->m_data.get_comp();
1606       KeyOfValue key_extract;
1607       RanIt lb(this->priv_lower_bound(first, last, k)), ub(lb);
1608       if(lb != last && !key_cmp(k, key_extract(*lb))){
1609          ++ub;
1610       }
1611       return std::pair<RanIt, RanIt>(lb, ub);
1612    }
1613 };
1614
1615 }  //namespace dtl {
1616
1617 }  //namespace container {
1618
1619 //!has_trivial_destructor_after_move<> == true_type
1620 //!specialization for optimizations
1621 template <class T, class KeyOfValue,
1622 class Compare, class AllocatorOrContainer>
1623 struct has_trivial_destructor_after_move<boost::container::dtl::flat_tree<T, KeyOfValue, Compare, AllocatorOrContainer> >
1624 {
1625    typedef boost::container::dtl::flat_tree<T, KeyOfValue, Compare, AllocatorOrContainer> flat_tree;
1626    typedef typename flat_tree::container_type container_type;
1627    typedef typename flat_tree::key_compare key_compare;
1628    static const bool value = ::boost::has_trivial_destructor_after_move<container_type>::value &&
1629                              ::boost::has_trivial_destructor_after_move<key_compare>::value;
1630 };
1631
1632 }  //namespace boost {
1633
1634 #include <boost/container/detail/config_end.hpp>
1635
1636 #endif // BOOST_CONTAINER_FLAT_TREE_HPP