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