boost/container/detail/flat_tree.hpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2005-2013. 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 #if defined(_MSC_VER)
  15 #  pragma once
  16 #endif
  17
  18 #include <boost/container/detail/config_begin.hpp>
  19 #include <boost/container/detail/workaround.hpp>
  20
  21 #include <boost/container/container_fwd.hpp>
  22
  23 #include <algorithm>
  24 #include <functional>
  25 #include <utility>
  26
  27 #include <boost/type_traits/has_trivial_destructor.hpp>
  28 #include <boost/move/utility_core.hpp>
  29
  30 #include <boost/container/detail/utilities.hpp>
  31 #include <boost/container/detail/pair.hpp>
  32 #include <boost/container/vector.hpp>
  33 #include <boost/container/detail/value_init.hpp>
  34 #include <boost/container/detail/destroyers.hpp>
  35 #include <boost/container/allocator_traits.hpp>
  36 #ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
  37 #include <boost/intrusive/pointer_traits.hpp>
  38 #endif
  39 #include <boost/aligned_storage.hpp>
  40 #include <boost/move/make_unique.hpp>
  41
  42 namespace boost {
  43
  44 namespace container {
  45
  46 namespace container_detail {
  47
  48 template<class Compare, class Value, class KeyOfValue>
  49 class flat_tree_value_compare
  50    : private Compare
  51 {
  52    typedef Value              first_argument_type;
  53    typedef Value              second_argument_type;
  54    typedef bool               return_type;
  55    public:
  56    flat_tree_value_compare()
  57       : Compare()
  58    {}
  59
  60    flat_tree_value_compare(const Compare &pred)
  61       : Compare(pred)
  62    {}
  63
  64    bool operator()(const Value& lhs, const Value& rhs) const
  65    {
  66       KeyOfValue key_extract;
  67       return Compare::operator()(key_extract(lhs), key_extract(rhs));
  68    }
  69
  70    const Compare &get_comp() const
  71       {  return *this;  }
  72
  73    Compare &get_comp()
  74       {  return *this;  }
  75 };
  76
  77 template<class Pointer>
  78 struct get_flat_tree_iterators
  79 {
  80    #ifdef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
  81    typedef Pointer                                    iterator;
  82    typedef typename boost::intrusive::
  83       pointer_traits<Pointer>::element_type           iterator_element_type;
  84    typedef typename boost::intrusive::
  85       pointer_traits<Pointer>:: template
  86          rebind_pointer<const iterator_element_type>::type  const_iterator;
  87    #else //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
  88    typedef typename boost::container::container_detail::
  89       vec_iterator<Pointer, false>                    iterator;
  90    typedef typename boost::container::container_detail::
  91       vec_iterator<Pointer, true >                    const_iterator;
  92    #endif   //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
  93    typedef boost::container::container_detail::
  94       reverse_iterator<iterator>                      reverse_iterator;
  95    typedef boost::container::container_detail::
  96       reverse_iterator<const_iterator>                const_reverse_iterator;
  97 };
  98
  99 template <class Key, class Value, class KeyOfValue,
 100           class Compare, class A>
 101 class flat_tree
 102 {
 103    typedef boost::container::vector<Value, A>  vector_t;
 104    typedef A                                   allocator_t;
 105
 106    public:
 107    typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare;
 108
 109  private:
 110    struct Data
 111       //Inherit from value_compare to do EBO
 112       : public value_compare
 113    {
 114       BOOST_COPYABLE_AND_MOVABLE(Data)
 115
 116       public:
 117       Data()
 118          : value_compare(), m_vect()
 119       {}
 120
 121       explicit Data(const Data &d)
 122          : value_compare(static_cast<const value_compare&>(d)), m_vect(d.m_vect)
 123       {}
 124
 125       Data(BOOST_RV_REF(Data) d)
 126          : value_compare(boost::move(static_cast<value_compare&>(d))), m_vect(boost::move(d.m_vect))
 127       {}
 128
 129       Data(const Data &d, const A &a)
 130          : value_compare(static_cast<const value_compare&>(d)), m_vect(d.m_vect, a)
 131       {}
 132
 133       Data(BOOST_RV_REF(Data) d, const A &a)
 134          : value_compare(boost::move(static_cast<value_compare&>(d))), m_vect(boost::move(d.m_vect), a)
 135       {}
 136
 137       explicit Data(const Compare &comp)
 138          : value_compare(comp), m_vect()
 139       {}
 140
 141       Data(const Compare &comp, const allocator_t &alloc)
 142          : value_compare(comp), m_vect(alloc)
 143       {}
 144
 145       explicit Data(const allocator_t &alloc)
 146          : value_compare(), m_vect(alloc)
 147       {}
 148
 149       Data& operator=(BOOST_COPY_ASSIGN_REF(Data) d)
 150       {
 151          this->value_compare::operator=(d);
 152          m_vect = d.m_vect;
 153          return *this;
 154       }
 155
 156       Data& operator=(BOOST_RV_REF(Data) d)
 157       {
 158          this->value_compare::operator=(boost::move(static_cast<value_compare &>(d)));
 159          m_vect = boost::move(d.m_vect);
 160          return *this;
 161       }
 162
 163       void swap(Data &d)
 164       {
 165          value_compare& mycomp    = *this, & othercomp = d;
 166          boost::container::swap_dispatch(mycomp, othercomp);
 167          this->m_vect.swap(d.m_vect);
 168       }
 169
 170       vector_t m_vect;
 171    };
 172
 173    Data m_data;
 174    BOOST_COPYABLE_AND_MOVABLE(flat_tree)
 175
 176    public:
 177
 178    typedef typename vector_t::value_type              value_type;
 179    typedef typename vector_t::pointer                 pointer;
 180    typedef typename vector_t::const_pointer           const_pointer;
 181    typedef typename vector_t::reference               reference;
 182    typedef typename vector_t::const_reference         const_reference;
 183    typedef Key                                        key_type;
 184    typedef Compare                                    key_compare;
 185    typedef typename vector_t::allocator_type          allocator_type;
 186    typedef typename vector_t::size_type               size_type;
 187    typedef typename vector_t::difference_type         difference_type;
 188    typedef typename vector_t::iterator                iterator;
 189    typedef typename vector_t::const_iterator          const_iterator;
 190    typedef typename vector_t::reverse_iterator        reverse_iterator;
 191    typedef typename vector_t::const_reverse_iterator  const_reverse_iterator;
 192
 193    //!Standard extension
 194    typedef allocator_type                             stored_allocator_type;
 195
 196    private:
 197    typedef allocator_traits<stored_allocator_type> stored_allocator_traits;
 198
 199    public:
 200    flat_tree()
 201       : m_data()
 202    { }
 203
 204    explicit flat_tree(const Compare& comp)
 205       : m_data(comp)
 206    { }
 207
 208    flat_tree(const Compare& comp, const allocator_type& a)
 209       : m_data(comp, a)
 210    { }
 211
 212    explicit flat_tree(const allocator_type& a)
 213       : m_data(a)
 214    { }
 215
 216    flat_tree(const flat_tree& x)
 217       :  m_data(x.m_data)
 218    { }
 219
 220    flat_tree(BOOST_RV_REF(flat_tree) x)
 221       :  m_data(boost::move(x.m_data))
 222    { }
 223
 224    flat_tree(const flat_tree& x, const allocator_type &a)
 225       :  m_data(x.m_data, a)
 226    { }
 227
 228    flat_tree(BOOST_RV_REF(flat_tree) x, const allocator_type &a)
 229       :  m_data(boost::move(x.m_data), a)
 230    { }
 231
 232    template <class InputIterator>
 233    flat_tree( ordered_range_t, InputIterator first, InputIterator last
 234             , const Compare& comp     = Compare()
 235             , const allocator_type& a = allocator_type())
 236       : m_data(comp, a)
 237    { this->m_data.m_vect.insert(this->m_data.m_vect.end(), first, last); }
 238
 239    template <class InputIterator>
 240    flat_tree( bool unique_insertion
 241             , InputIterator first, InputIterator last
 242             , const Compare& comp     = Compare()
 243             , const allocator_type& a = allocator_type())
 244       : m_data(comp, a)
 245    {
 246       //Use cend() as hint to achieve linear time for
 247       //ordered ranges as required by the standard
 248       //for the constructor
 249       //Call end() every iteration as reallocation might have invalidated iterators
 250       if(unique_insertion){
 251          for ( ; first != last; ++first){
 252             this->insert_unique(this->cend(), *first);
 253          }
 254       }
 255       else{
 256          for ( ; first != last; ++first){
 257             this->insert_equal(this->cend(), *first);
 258          }
 259       }
 260    }
 261
 262    ~flat_tree()
 263    {}
 264
 265    flat_tree&  operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x)
 266    {  m_data = x.m_data;   return *this;  }
 267
 268    flat_tree&  operator=(BOOST_RV_REF(flat_tree) mx)
 269    {  m_data = boost::move(mx.m_data); return *this;  }
 270
 271    public:
 272    // accessors:
 273    Compare key_comp() const
 274    { return this->m_data.get_comp(); }
 275
 276    value_compare value_comp() const
 277    { return this->m_data; }
 278
 279    allocator_type get_allocator() const
 280    { return this->m_data.m_vect.get_allocator(); }
 281
 282    const stored_allocator_type &get_stored_allocator() const
 283    {  return this->m_data.m_vect.get_stored_allocator(); }
 284
 285    stored_allocator_type &get_stored_allocator()
 286    {  return this->m_data.m_vect.get_stored_allocator(); }
 287
 288    iterator begin()
 289    { return this->m_data.m_vect.begin(); }
 290
 291    const_iterator begin() const
 292    { return this->cbegin(); }
 293
 294    const_iterator cbegin() const
 295    { return this->m_data.m_vect.begin(); }
 296
 297    iterator end()
 298    { return this->m_data.m_vect.end(); }
 299
 300    const_iterator end() const
 301    { return this->cend(); }
 302
 303    const_iterator cend() const
 304    { return this->m_data.m_vect.end(); }
 305
 306    reverse_iterator rbegin()
 307    { return reverse_iterator(this->end()); }
 308
 309    const_reverse_iterator rbegin() const
 310    {  return this->crbegin();  }
 311
 312    const_reverse_iterator crbegin() const
 313    {  return const_reverse_iterator(this->cend());  }
 314
 315    reverse_iterator rend()
 316    { return reverse_iterator(this->begin()); }
 317
 318    const_reverse_iterator rend() const
 319    { return this->crend(); }
 320
 321    const_reverse_iterator crend() const
 322    { return const_reverse_iterator(this->cbegin()); }
 323
 324    bool empty() const
 325    { return this->m_data.m_vect.empty(); }
 326
 327    size_type size() const
 328    { return this->m_data.m_vect.size(); }
 329
 330    size_type max_size() const
 331    { return this->m_data.m_vect.max_size(); }
 332
 333    void swap(flat_tree& other)
 334    {  this->m_data.swap(other.m_data);  }
 335
 336    public:
 337    // insert/erase
 338    std::pair<iterator,bool> insert_unique(const value_type& val)
 339    {
 340       std::pair<iterator,bool> ret;
 341       insert_commit_data data;
 342       ret.second = this->priv_insert_unique_prepare(val, data);
 343       ret.first = ret.second ? this->priv_insert_commit(data, val)
 344                              : iterator(vector_iterator_get_ptr(data.position));
 345       return ret;
 346    }
 347
 348    std::pair<iterator,bool> insert_unique(BOOST_RV_REF(value_type) val)
 349    {
 350       std::pair<iterator,bool> ret;
 351       insert_commit_data data;
 352       ret.second = this->priv_insert_unique_prepare(val, data);
 353       ret.first = ret.second ? this->priv_insert_commit(data, boost::move(val))
 354                              : iterator(vector_iterator_get_ptr(data.position));
 355       return ret;
 356    }
 357
 358    iterator insert_equal(const value_type& val)
 359    {
 360       iterator i = this->upper_bound(KeyOfValue()(val));
 361       i = this->m_data.m_vect.insert(i, val);
 362       return i;
 363    }
 364
 365    iterator insert_equal(BOOST_RV_REF(value_type) mval)
 366    {
 367       iterator i = this->upper_bound(KeyOfValue()(mval));
 368       i = this->m_data.m_vect.insert(i, boost::move(mval));
 369       return i;
 370    }
 371
 372    iterator insert_unique(const_iterator pos, const value_type& val)
 373    {
 374       std::pair<iterator,bool> ret;
 375       insert_commit_data data;
 376       return this->priv_insert_unique_prepare(pos, val, data)
 377             ? this->priv_insert_commit(data, val)
 378             : iterator(vector_iterator_get_ptr(data.position));
 379    }
 380
 381    iterator insert_unique(const_iterator pos, BOOST_RV_REF(value_type) val)
 382    {
 383       std::pair<iterator,bool> ret;
 384       insert_commit_data data;
 385       return this->priv_insert_unique_prepare(pos, val, data)
 386          ? this->priv_insert_commit(data, boost::move(val))
 387          : iterator(vector_iterator_get_ptr(data.position));
 388    }
 389
 390    iterator insert_equal(const_iterator pos, const value_type& val)
 391    {
 392       insert_commit_data data;
 393       this->priv_insert_equal_prepare(pos, val, data);
 394       return this->priv_insert_commit(data, val);
 395    }
 396
 397    iterator insert_equal(const_iterator pos, BOOST_RV_REF(value_type) mval)
 398    {
 399       insert_commit_data data;
 400       this->priv_insert_equal_prepare(pos, mval, data);
 401       return this->priv_insert_commit(data, boost::move(mval));
 402    }
 403
 404    template <class InIt>
 405    void insert_unique(InIt first, InIt last)
 406    {
 407       for ( ; first != last; ++first){
 408          this->insert_unique(*first);
 409       }
 410    }
 411
 412    template <class InIt>
 413    void insert_equal(InIt first, InIt last
 414       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 415       , typename container_detail::enable_if_c
 416          < container_detail::is_input_iterator<InIt>::value
 417          >::type * = 0
 418       #endif
 419       )
 420    {  this->priv_insert_equal_loop(first, last);  }
 421
 422    template <class InIt>
 423    void insert_equal(InIt first, InIt last
 424       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 425       , typename container_detail::enable_if_c
 426          < !container_detail::is_input_iterator<InIt>::value
 427          >::type * = 0
 428       #endif
 429       )
 430    {
 431       const size_type len = static_cast<size_type>(std::distance(first, last));
 432       this->reserve(this->size()+len);
 433       this->priv_insert_equal_loop(first, last);
 434    }
 435
 436    //Ordered
 437
 438    template <class InIt>
 439    void insert_equal(ordered_range_t, InIt first, InIt last
 440       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 441       , typename container_detail::enable_if_c
 442          < container_detail::is_input_iterator<InIt>::value
 443          >::type * = 0
 444       #endif
 445       )
 446    {  this->priv_insert_equal_loop_ordered(first, last); }
 447
 448    template <class FwdIt>
 449    void insert_equal(ordered_range_t, FwdIt first, FwdIt last
 450       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 451       , typename container_detail::enable_if_c
 452          < !container_detail::is_input_iterator<FwdIt>::value &&
 453          container_detail::is_forward_iterator<FwdIt>::value
 454          >::type * = 0
 455       #endif
 456       )
 457    {
 458       const size_type len = static_cast<size_type>(std::distance(first, last));
 459       this->reserve(this->size()+len);
 460       this->priv_insert_equal_loop_ordered(first, last);
 461    }
 462
 463    template <class BidirIt>
 464    void insert_equal(ordered_range_t, BidirIt first, BidirIt last
 465       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 466       , typename container_detail::enable_if_c
 467          < !container_detail::is_input_iterator<BidirIt>::value &&
 468            !container_detail::is_forward_iterator<BidirIt>::value
 469          >::type * = 0
 470       #endif
 471       )
 472    {   this->priv_insert_ordered_range(false, first, last);   }
 473
 474    template <class InIt>
 475    void insert_unique(ordered_unique_range_t, InIt first, InIt last
 476       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 477       , typename container_detail::enable_if_c
 478          < container_detail::is_input_iterator<InIt>::value ||
 479            container_detail::is_forward_iterator<InIt>::value
 480          >::type * = 0
 481       #endif
 482       )
 483    {
 484       const_iterator pos(this->cend());
 485       for ( ; first != last; ++first){
 486          pos = this->insert_unique(pos, *first);
 487          ++pos;
 488       }
 489    }
 490
 491    template <class BidirIt>
 492    void insert_unique(ordered_unique_range_t, BidirIt first, BidirIt last
 493       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 494       , typename container_detail::enable_if_c
 495          < !(container_detail::is_input_iterator<BidirIt>::value ||
 496              container_detail::is_forward_iterator<BidirIt>::value)
 497          >::type * = 0
 498       #endif
 499       )
 500    {   this->priv_insert_ordered_range(true, first, last);   }
 501
 502    #ifdef BOOST_CONTAINER_PERFECT_FORWARDING
 503
 504    template <class... Args>
 505    std::pair<iterator, bool> emplace_unique(Args&&... args)
 506    {
 507       aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v;
 508       value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));
 509       stored_allocator_type &a = this->get_stored_allocator();
 510       stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
 511       value_destructor<stored_allocator_type> d(a, val);
 512       return this->insert_unique(::boost::move(val));
 513    }
 514
 515    template <class... Args>
 516    iterator emplace_hint_unique(const_iterator hint, Args&&... args)
 517    {
 518       aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v;
 519       value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));
 520       stored_allocator_type &a = this->get_stored_allocator();
 521       stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
 522       value_destructor<stored_allocator_type> d(a, val);
 523       return this->insert_unique(hint, ::boost::move(val));
 524    }
 525
 526    template <class... Args>
 527    iterator emplace_equal(Args&&... args)
 528    {
 529       aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v;
 530       value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));
 531       stored_allocator_type &a = this->get_stored_allocator();
 532       stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
 533       value_destructor<stored_allocator_type> d(a, val);
 534       return this->insert_equal(::boost::move(val));
 535    }
 536
 537    template <class... Args>
 538    iterator emplace_hint_equal(const_iterator hint, Args&&... args)
 539    {
 540       aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v;
 541       value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));
 542       stored_allocator_type &a = this->get_stored_allocator();
 543       stored_allocator_traits::construct(a, &val, ::boost::forward<Args>(args)... );
 544       value_destructor<stored_allocator_type> d(a, val);
 545       return this->insert_equal(hint, ::boost::move(val));
 546    }
 547
 548    #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
 549
 550    #define BOOST_PP_LOCAL_MACRO(n)                                                        \
 551    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
 552    std::pair<iterator, bool>                                                              \
 553       emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _))                  \
 554    {                                                                                      \
 555       aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v;             \
 556       value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));              \
 557       stored_allocator_type &a = this->get_stored_allocator();                            \
 558       stored_allocator_traits::construct(a, &val                                          \
 559          BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) );                \
 560       value_destructor<stored_allocator_type> d(a, val);                                  \
 561       return this->insert_unique(::boost::move(val));                                     \
 562    }                                                                                      \
 563                                                                                           \
 564    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
 565    iterator emplace_hint_unique(const_iterator hint                                       \
 566                         BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _))      \
 567    {                                                                                      \
 568       aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v;             \
 569       value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));              \
 570       stored_allocator_type &a = this->get_stored_allocator();                            \
 571       stored_allocator_traits::construct(a, &val                                          \
 572          BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) );                \
 573       value_destructor<stored_allocator_type> d(a, val);                                  \
 574       return this->insert_unique(hint, ::boost::move(val));                               \
 575    }                                                                                      \
 576                                                                                           \
 577    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
 578    iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _))             \
 579    {                                                                                      \
 580       aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v;             \
 581       value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));              \
 582       stored_allocator_type &a = this->get_stored_allocator();                            \
 583       stored_allocator_traits::construct(a, &val                                          \
 584          BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) );                \
 585       value_destructor<stored_allocator_type> d(a,  val);                                 \
 586       return this->insert_equal(::boost::move(val));                                      \
 587    }                                                                                      \
 588                                                                                           \
 589    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
 590    iterator emplace_hint_equal(const_iterator hint                                        \
 591                       BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _))        \
 592    {                                                                                      \
 593       aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v;             \
 594       value_type &val = *static_cast<value_type *>(static_cast<void *>(&v));              \
 595       stored_allocator_type &a = this->get_stored_allocator();                            \
 596       stored_allocator_traits::construct(a, &val                                          \
 597          BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) );                \
 598       value_destructor<stored_allocator_type> d(a,  val);                                 \
 599       return this->insert_equal(hint, ::boost::move(val));                                \
 600    }                                                                                      \
 601    //!
 602    #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
 603    #include BOOST_PP_LOCAL_ITERATE()
 604
 605    #endif   //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
 606
 607    iterator erase(const_iterator position)
 608    {  return this->m_data.m_vect.erase(position);  }
 609
 610    size_type erase(const key_type& k)
 611    {
 612       std::pair<iterator,iterator > itp = this->equal_range(k);
 613       size_type ret = static_cast<size_type>(itp.second-itp.first);
 614       if (ret){
 615          this->m_data.m_vect.erase(itp.first, itp.second);
 616       }
 617       return ret;
 618    }
 619
 620    iterator erase(const_iterator first, const_iterator last)
 621    {  return this->m_data.m_vect.erase(first, last);  }
 622
 623    void clear()
 624    {  this->m_data.m_vect.clear();  }
 625
 626    //! <b>Effects</b>: Tries to deallocate the excess of memory created
 627    //    with previous allocations. The size of the vector is unchanged
 628    //!
 629    //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
 630    //!
 631    //! <b>Complexity</b>: Linear to size().
 632    void shrink_to_fit()
 633    {  this->m_data.m_vect.shrink_to_fit();  }
 634
 635    // set operations:
 636    iterator find(const key_type& k)
 637    {
 638       iterator i = this->lower_bound(k);
 639       iterator end_it = this->end();
 640       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
 641          i = end_it;
 642       }
 643       return i;
 644    }
 645
 646    const_iterator find(const key_type& k) const
 647    {
 648       const_iterator i = this->lower_bound(k);
 649
 650       const_iterator end_it = this->cend();
 651       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
 652          i = end_it;
 653       }
 654       return i;
 655    }
 656
 657    // set operations:
 658    size_type count(const key_type& k) const
 659    {
 660       std::pair<const_iterator, const_iterator> p = this->equal_range(k);
 661       size_type n = p.second - p.first;
 662       return n;
 663    }
 664
 665    iterator lower_bound(const key_type& k)
 666    {  return this->priv_lower_bound(this->begin(), this->end(), k);  }
 667
 668    const_iterator lower_bound(const key_type& k) const
 669    {  return this->priv_lower_bound(this->cbegin(), this->cend(), k);  }
 670
 671    iterator upper_bound(const key_type& k)
 672    {  return this->priv_upper_bound(this->begin(), this->end(), k);  }
 673
 674    const_iterator upper_bound(const key_type& k) const
 675    {  return this->priv_upper_bound(this->cbegin(), this->cend(), k);  }
 676
 677    std::pair<iterator,iterator> equal_range(const key_type& k)
 678    {  return this->priv_equal_range(this->begin(), this->end(), k);  }
 679
 680    std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
 681    {  return this->priv_equal_range(this->cbegin(), this->cend(), k);  }
 682
 683    std::pair<iterator, iterator> lower_bound_range(const key_type& k)
 684    {  return this->priv_lower_bound_range(this->begin(), this->end(), k);  }
 685
 686    std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
 687    {  return this->priv_lower_bound_range(this->cbegin(), this->cend(), k);  }
 688
 689    size_type capacity() const
 690    { return this->m_data.m_vect.capacity(); }
 691
 692    void reserve(size_type cnt)
 693    { this->m_data.m_vect.reserve(cnt);   }
 694
 695    friend bool operator==(const flat_tree& x, const flat_tree& y)
 696    {
 697       return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin());
 698    }
 699
 700    friend bool operator<(const flat_tree& x, const flat_tree& y)
 701    {
 702       return std::lexicographical_compare(x.begin(), x.end(),
 703                                           y.begin(), y.end());
 704    }
 705
 706    friend bool operator!=(const flat_tree& x, const flat_tree& y)
 707       {  return !(x == y); }
 708
 709    friend bool operator>(const flat_tree& x, const flat_tree& y)
 710       {  return y < x;  }
 711
 712    friend bool operator<=(const flat_tree& x, const flat_tree& y)
 713       {  return !(y < x);  }
 714
 715    friend bool operator>=(const flat_tree& x, const flat_tree& y)
 716       {  return !(x < y);  }
 717
 718    friend void swap(flat_tree& x, flat_tree& y)
 719       {  x.swap(y);  }
 720
 721    private:
 722    struct insert_commit_data
 723    {
 724       const_iterator position;
 725    };
 726
 727    // insert/erase
 728    void priv_insert_equal_prepare
 729       (const_iterator pos, const value_type& val, insert_commit_data &data)
 730    {
 731       // N1780
 732       //   To insert val at pos:
 733       //   if pos == end || val <= *pos
 734       //      if pos == begin || val >= *(pos-1)
 735       //         insert val before pos
 736       //      else
 737       //         insert val before upper_bound(val)
 738       //   else
 739       //      insert val before lower_bound(val)
 740       const value_compare &val_cmp = this->m_data;
 741
 742       if(pos == this->cend() || !val_cmp(*pos, val)){
 743          if (pos == this->cbegin() || !val_cmp(val, pos[-1])){
 744             data.position = pos;
 745          }
 746          else{
 747             data.position =
 748                this->priv_upper_bound(this->cbegin(), pos, KeyOfValue()(val));
 749          }
 750       }
 751       else{
 752          data.position =
 753             this->priv_lower_bound(pos, this->cend(), KeyOfValue()(val));
 754       }
 755    }
 756
 757    bool priv_insert_unique_prepare
 758       (const_iterator b, const_iterator e, const value_type& val, insert_commit_data &commit_data)
 759    {
 760       const value_compare &val_cmp  = this->m_data;
 761       commit_data.position = this->priv_lower_bound(b, e, KeyOfValue()(val));
 762       return commit_data.position == e || val_cmp(val, *commit_data.position);
 763    }
 764
 765    bool priv_insert_unique_prepare
 766       (const value_type& val, insert_commit_data &commit_data)
 767    {  return this->priv_insert_unique_prepare(this->cbegin(), this->cend(), val, commit_data);   }
 768
 769    bool priv_insert_unique_prepare
 770       (const_iterator pos, const value_type& val, insert_commit_data &commit_data)
 771    {
 772       //N1780. Props to Howard Hinnant!
 773       //To insert val at pos:
 774       //if pos == end || val <= *pos
 775       //   if pos == begin || val >= *(pos-1)
 776       //      insert val before pos
 777       //   else
 778       //      insert val before upper_bound(val)
 779       //else if pos+1 == end || val <= *(pos+1)
 780       //   insert val after pos
 781       //else
 782       //   insert val before lower_bound(val)
 783       const value_compare &val_cmp = this->m_data;
 784       const const_iterator cend_it = this->cend();
 785       if(pos == cend_it || val_cmp(val, *pos)){ //Check if val should go before end
 786          const const_iterator cbeg = this->cbegin();
 787          commit_data.position = pos;
 788          if(pos == cbeg){  //If container is empty then insert it in the beginning
 789             return true;
 790          }
 791          const_iterator prev(pos);
 792          --prev;
 793          if(val_cmp(*prev, val)){   //If previous element was less, then it should go between prev and pos
 794             return true;
 795          }
 796          else if(!val_cmp(val, *prev)){   //If previous was equal then insertion should fail
 797             commit_data.position = prev;
 798             return false;
 799          }
 800          else{ //Previous was bigger so insertion hint was pointless, dispatch to hintless insertion
 801                //but reduce the search between beg and prev as prev is bigger than val
 802             return this->priv_insert_unique_prepare(cbeg, prev, val, commit_data);
 803          }
 804       }
 805       else{
 806          //The hint is before the insertion position, so insert it
 807          //in the remaining range [pos, end)
 808          return this->priv_insert_unique_prepare(pos, cend_it, val, commit_data);
 809       }
 810    }
 811
 812    template<class Convertible>
 813    iterator priv_insert_commit
 814       (insert_commit_data &commit_data, BOOST_FWD_REF(Convertible) convertible)
 815    {
 816       return this->m_data.m_vect.insert
 817          ( commit_data.position
 818          , boost::forward<Convertible>(convertible));
 819    }
 820
 821    template <class RanIt>
 822    RanIt priv_lower_bound(RanIt first, const RanIt last,
 823                           const key_type & key) const
 824    {
 825       const Compare &key_cmp = this->m_data.get_comp();
 826       KeyOfValue key_extract;
 827       size_type len = static_cast<size_type>(last - first);
 828       RanIt middle;
 829
 830       while (len) {
 831          size_type step = len >> 1;
 832          middle = first;
 833          middle += step;
 834
 835          if (key_cmp(key_extract(*middle), key)) {
 836             first = ++middle;
 837             len -= step + 1;
 838          }
 839          else{
 840             len = step;
 841          }
 842       }
 843       return first;
 844    }
 845
 846    template <class RanIt>
 847    RanIt priv_upper_bound(RanIt first, const RanIt last,
 848                           const key_type & key) const
 849    {
 850       const Compare &key_cmp = this->m_data.get_comp();
 851       KeyOfValue key_extract;
 852       size_type len = static_cast<size_type>(last - first);
 853       RanIt middle;
 854
 855       while (len) {
 856          size_type step = len >> 1;
 857          middle = first;
 858          middle += step;
 859
 860          if (key_cmp(key, key_extract(*middle))) {
 861             len = step;
 862          }
 863          else{
 864             first = ++middle;
 865             len -= step + 1;
 866          }
 867       }
 868       return first;
 869    }
 870
 871    template <class RanIt>
 872    std::pair<RanIt, RanIt>
 873       priv_equal_range(RanIt first, RanIt last, const key_type& key) const
 874    {
 875       const Compare &key_cmp = this->m_data.get_comp();
 876       KeyOfValue key_extract;
 877       size_type len = static_cast<size_type>(last - first);
 878       RanIt middle;
 879
 880       while (len) {
 881          size_type step = len >> 1;
 882          middle = first;
 883          middle += step;
 884
 885          if (key_cmp(key_extract(*middle), key)){
 886             first = ++middle;
 887             len -= step + 1;
 888          }
 889          else if (key_cmp(key, key_extract(*middle))){
 890             len = step;
 891          }
 892          else {
 893             //Middle is equal to key
 894             last = first;
 895             last += len;
 896             return std::pair<RanIt, RanIt>
 897                ( this->priv_lower_bound(first, middle, key)
 898                , this->priv_upper_bound(++middle, last, key));
 899          }
 900       }
 901       return std::pair<RanIt, RanIt>(first, first);
 902    }
 903
 904    template<class RanIt>
 905    std::pair<RanIt, RanIt> priv_lower_bound_range(RanIt first, RanIt last, const key_type& k) const
 906    {
 907       const Compare &key_cmp = this->m_data.get_comp();
 908       KeyOfValue key_extract;
 909       RanIt lb(this->priv_lower_bound(first, last, k)), ub(lb);
 910       if(lb != last && static_cast<difference_type>(!key_cmp(k, key_extract(*lb)))){
 911          ++ub;
 912       }
 913       return std::pair<RanIt, RanIt>(lb, ub);
 914    }
 915
 916    template<class InIt>
 917    void priv_insert_equal_loop(InIt first, InIt last)
 918    {
 919       for ( ; first != last; ++first){
 920          this->insert_equal(*first);
 921       }
 922    }
 923
 924    template<class InIt>
 925    void priv_insert_equal_loop_ordered(InIt first, InIt last)
 926    {
 927       const_iterator pos(this->cend());
 928       for ( ; first != last; ++first){
 929          //If ordered, then try hint version
 930          //to achieve constant-time complexity per insertion
 931          pos = this->insert_equal(pos, *first);
 932          ++pos;
 933       }
 934    }
 935
 936    template <class BidirIt>
 937    void priv_insert_ordered_range(const bool unique_values, BidirIt first, BidirIt last)
 938    {
 939       size_type len = static_cast<size_type>(std::distance(first, last));
 940       //Prereserve all memory so that iterators are not invalidated
 941       this->reserve(this->size()+len);
 942       //Auxiliary data for insertion positions.
 943       const size_type BurstSize = len;
 944       const ::boost::movelib::unique_ptr<size_type[]> positions =
 945          ::boost::movelib::make_unique_definit<size_type[]>(BurstSize);
 946
 947       const const_iterator b(this->cbegin());
 948       const const_iterator ce(this->cend());
 949       const_iterator pos(b);
 950       const value_compare &val_cmp = this->m_data;
 951       //Loop in burst sizes
 952       bool back_insert = false;
 953       while(len && !back_insert){
 954          const size_type burst = len < BurstSize ? len : BurstSize;
 955          size_type unique_burst = 0u;
 956          size_type checked = 0;
 957          for(; checked != burst; ++checked){
 958             //Get the insertion position for each key, use std::iterator_traits<BidirIt>::value_type
 959             //because it can be different from container::value_type
 960             //(e.g. conversion between std::pair<A, B> -> boost::container::pair<A, B>
 961             const typename std::iterator_traits<BidirIt>::value_type & val = *first;
 962             pos = const_cast<const flat_tree&>(*this).priv_lower_bound(pos, ce, KeyOfValue()(val));
 963             //Check if already present
 964             if (pos != ce){
 965                ++first;
 966                --len;
 967                positions[checked] = (unique_values && !val_cmp(val, *pos)) ?
 968                    size_type(-1) : (++unique_burst, static_cast<size_type>(pos - b));
 969             }
 970             else{ //this element and the remaining should be back inserted
 971                back_insert = true;
 972                break;
 973             }
 974          }
 975          if(unique_burst){
 976             //Insert all in a single step in the precalculated positions
 977             this->m_data.m_vect.insert_ordered_at(unique_burst, positions.get() + checked, first);
 978             //Next search position updated, iterator still valid because we've preserved the vector
 979             pos += unique_burst;
 980          }
 981       }
 982       //The remaining range should be back inserted
 983       if(unique_values){
 984          while(len--){
 985             BidirIt next(first);
 986             ++next;
 987             if(next == last || val_cmp(*first, *next)){
 988                const bool room = this->m_data.m_vect.stable_emplace_back(*first);
 989                (void)room;
 990                BOOST_ASSERT(room);
 991             }
 992             first = next;
 993          }
 994          BOOST_ASSERT(first == last);
 995       }
 996       else{
 997          BOOST_ASSERT(size_type(std::distance(first, last)) == len);
 998          if(len)
 999             this->m_data.m_vect.insert(this->m_data.m_vect.cend(), len, first, last);
1000       }
1001    }
1002 };
1003
1004 }  //namespace container_detail {
1005
1006 }  //namespace container {
1007 /*
1008 //!has_trivial_destructor_after_move<> == true_type
1009 //!specialization for optimizations
1010 template <class K, class V, class KOV,
1011 class C, class A>
1012 struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<K, V, KOV, C, A> >
1013 {
1014    static const bool value = has_trivial_destructor_after_move<A>::value && has_trivial_destructor_after_move<C>::value;
1015 };
1016 */
1017 }  //namespace boost {
1018
1019 #include <boost/container/detail/config_end.hpp>
1020
1021 #endif // BOOST_CONTAINER_FLAT_TREE_HPP