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