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