EIC code displayed by LXR master/​include/​boost/​container/​detail/​flat_tree.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-08-08 08:44:13

 ////////////////////////////////////////////////////////////////////////////////
 //
 // (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost
 // Software License, Version 1.0. (See accompanying file
 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 //
 // See http://www.boost.org/libs/container for documentation.
 //
 ////////////////////////////////////////////////////////////////////////////////
 
 #ifndef BOOST_CONTAINER_FLAT_TREE_HPP
 #define BOOST_CONTAINER_FLAT_TREE_HPP
 
 #ifndef BOOST_CONFIG_HPP
 #  include <boost/config.hpp>
 #endif
 
 #if defined(BOOST_HAS_PRAGMA_ONCE)
 #  pragma once
 #endif
 
 #include <boost/container/detail/config_begin.hpp>
 #include <boost/container/detail/workaround.hpp>
 
 #include <boost/container/container_fwd.hpp>
 
 #include <boost/move/utility_core.hpp>
 
 #include <boost/container/vector.hpp>
 #include <boost/container/allocator_traits.hpp>
 
 #include <boost/container/detail/value_init.hpp>
 #include <boost/container/detail/destroyers.hpp>
 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
 #include <boost/container/detail/iterator.hpp>
 #include <boost/container/detail/is_sorted.hpp>
 #include <boost/container/detail/type_traits.hpp>
 #include <boost/container/detail/iterators.hpp>
 #include <boost/container/detail/mpl.hpp>
 #include <boost/container/detail/is_contiguous_container.hpp>
 #include <boost/container/detail/is_container.hpp>
 
 #include <boost/intrusive/detail/minimal_pair_header.hpp>      //pair
 
 #include <boost/move/iterator.hpp>
 #include <boost/move/adl_move_swap.hpp>
 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
 #include <boost/move/detail/to_raw_pointer.hpp>
 #include <boost/move/detail/force_ptr.hpp>
 #include <boost/move/detail/launder.hpp>
 #include <boost/move/algo/adaptive_sort.hpp>
 #include <boost/move/algo/detail/pdqsort.hpp>
 
 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 #include <boost/move/detail/fwd_macros.hpp>
 #endif
 
 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
 #pragma GCC diagnostic push
 #pragma GCC diagnostic ignored "-Wunused-result"
 #endif
 
 //merge_unique
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME merge_unique
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 3
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 3
 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
 
 //merge_equal
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME merge
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 3
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 3
 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
 
 //index_of
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME index_of
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
 
 //nth
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME nth
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
 
 //reserve
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME reserve
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 1
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 1
 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
 
 //capacity
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME capacity
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace dtl {
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END   }}}
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 0
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 0
 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
 
 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
 #pragma GCC diagnostic pop
 #endif
 
 
 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 
 namespace boost {
 namespace container {
 namespace dtl {
 
 
 ///////////////////////////////////////
 //
 // Helper functions to merge elements
 //
 ///////////////////////////////////////
 
 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(stored_allocator_type)
 
 ///////////////////////////////////////
 //
 //  flat_tree_container_inplace_merge
 //
 ///////////////////////////////////////
 template<class SequenceContainer, class Compare>
 inline void flat_tree_container_inplace_merge //is_contiguous_container == true
    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp , dtl::true_)
 {
    typedef typename SequenceContainer::value_type value_type;
    typedef typename SequenceContainer::size_type  size_type;
 
    value_type *const braw = boost::movelib::to_raw_pointer(dest.data());
    value_type *const iraw = boost::movelib::iterator_to_raw_pointer(it);
    //Don't use iterator_to_raw_pointer for end as debug iterators can assert when
    //"operator ->" is used with the end iterator
    value_type *const eraw = braw + dest.size();
    size_type dest_unused_storage_size = 0;
    value_type *const dest_unused_storage_addr =
       unused_storage<SequenceContainer>::get(dest, dest_unused_storage_size);
    boost::movelib::adaptive_merge
       (braw, iraw, eraw, comp, dest_unused_storage_addr, dest_unused_storage_size);
 }
 
 template<class SequenceContainer, class Compare>
 inline void flat_tree_container_inplace_merge //is_contiguous_container == false
    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp, dtl::false_)
 {
    boost::movelib::adaptive_merge(dest.begin(), it, dest.end(), comp);
 }
 
 ///////////////////////////////////////
 //
 //  flat_tree_container_inplace_sort_ending
 //
 ///////////////////////////////////////
 template<class SequenceContainer, class Compare>
 inline void flat_tree_container_inplace_sort_ending //is_contiguous_container == true
    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp, dtl::true_)
 {
    typedef typename SequenceContainer::value_type value_type;
    typedef typename SequenceContainer::size_type  size_type;
 
    value_type *const iraw = boost::movelib::iterator_to_raw_pointer(it);
    //Don't use iterator_to_raw_pointer for end as debug iterators can assert when
    //"operator ->" is used with the end iterator
    value_type* const eraw = boost::movelib::to_raw_pointer(dest.data()) + dest.size();
 
    size_type dest_unused_storage_size;
    value_type* const dest_unused_storage_addr =
       unused_storage<SequenceContainer>::get(dest, dest_unused_storage_size);
    boost::movelib::adaptive_sort
       (iraw, eraw, comp, dest_unused_storage_addr, dest_unused_storage_size);
 }
 
 template<class SequenceContainer, class Compare>
 inline void flat_tree_container_inplace_sort_ending //is_contiguous_container == false
    (SequenceContainer& dest, typename SequenceContainer::iterator it, Compare comp , dtl::false_)
 {
    boost::movelib::adaptive_sort(it, dest.end(), comp);
 }
 
 ///////////////////////////////////////
 //
 //          flat_tree_merge
 //
 ///////////////////////////////////////
 template<class SequenceContainer, class Iterator, class Compare>
 inline void flat_tree_merge_equal
    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::true_)
 {
    dest.merge(first, last, comp);
 }
 
 template<class SequenceContainer, class Iterator, class Compare>
 inline void flat_tree_merge_equal   //has_merge_unique == false
    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::false_)
 {
    if(first != last) {
       typedef typename SequenceContainer::iterator    iterator;
       iterator const it = dest.insert( dest.end(), first, last);
       BOOST_ASSERT((is_sorted)(it, dest.end(), comp));
       dtl::bool_<is_contiguous_container<SequenceContainer>::value> contiguous_tag;
       (flat_tree_container_inplace_merge)(dest, it, comp, contiguous_tag);
    }
 }
 
 ///////////////////////////////////////
 //
 //       flat_tree_merge_unique
 //
 ///////////////////////////////////////
 template<class SequenceContainer, class Iterator, class Compare>
 inline void flat_tree_merge_unique  //has_merge_unique == true
    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::true_)
 {
    dest.merge_unique(first, last, comp);
 }
 
 template<class SequenceContainer, class Iterator, class Compare>
 inline void flat_tree_merge_unique  //has_merge_unique == false
    (SequenceContainer& dest, Iterator first, Iterator last, Compare comp, dtl::false_)
 {
    if (first != last) {
       typedef typename SequenceContainer::iterator          iterator;
       typedef typename SequenceContainer::size_type         size_type;
       typedef typename SequenceContainer::difference_type   difference_type;
 
       size_type const old_sz = dest.size();
       iterator const first_new = dest.insert(dest.cend(), first, last);
       //We can't assert "is_sorted_and_unique" because the sequence can come from a multiset
       BOOST_ASSERT((is_sorted)(first_new, dest.end(), comp));
       iterator e = boost::movelib::inplace_set_unique_difference(first_new, dest.end(), dest.begin(), first_new, comp);
       dest.erase(e, dest.end());
       dtl::bool_<is_contiguous_container<SequenceContainer>::value> contiguous_tag;
       (flat_tree_container_inplace_merge)(dest, dest.begin() + difference_type(old_sz), comp, contiguous_tag);
    }
 }
 
 ///////////////////////////////////////
 //
 //         flat_tree_index_of
 //
 ///////////////////////////////////////
 template<class SequenceContainer, class Iterator>
 inline typename SequenceContainer::size_type
    flat_tree_index_of   // has_index_of == true
       (SequenceContainer& cont, Iterator p, dtl::true_)
 {
    return cont.index_of(p);
 }
 
 template<class SequenceContainer, class Iterator>
 inline typename SequenceContainer::size_type
    flat_tree_index_of   // has_index_of == false
       (SequenceContainer& cont, Iterator p, dtl::false_)
 {
    typedef typename SequenceContainer::size_type size_type;
    return static_cast<size_type>(p - cont.begin());
 }
 
 ///////////////////////////////////////
 //
 //         flat_tree_nth
 //
 ///////////////////////////////////////
 template<class Iterator, class SequenceContainer>
 inline Iterator
    flat_tree_nth  // has_nth == true
       (SequenceContainer& cont, typename SequenceContainer::size_type n, dtl::true_)
 {
    return cont.nth(n);
 }
 
 template<class Iterator, class SequenceContainer>
 inline Iterator
    flat_tree_nth  // has_nth == false
       (SequenceContainer& cont, typename SequenceContainer::size_type n, dtl::false_)
 {
    return cont.begin()+ typename SequenceContainer::difference_type(n);
 }
 
 ///////////////////////////////////////
 //
 //    flat_tree_get_stored_allocator
 //
 ///////////////////////////////////////
 template<class SequenceContainer>
 inline typename SequenceContainer::stored_allocator_type &
    flat_tree_get_stored_allocator   // has_get_stored_allocator == true
       (SequenceContainer& cont, dtl::true_)
 {
    return cont.get_stored_allocator();
 }
 
 template<class SequenceContainer>
 inline const typename SequenceContainer::stored_allocator_type &
    flat_tree_get_stored_allocator   // has_get_stored_allocator == true
       (const SequenceContainer& cont, dtl::true_)
 {
    return cont.get_stored_allocator();
 }
 
 template<class SequenceContainer>
 inline typename SequenceContainer::allocator_type
    flat_tree_get_stored_allocator   // has_get_stored_allocator == false
       (SequenceContainer& cont, dtl::false_)
 {
    return cont.get_allocator();
 }
 
 ///////////////////////////////////////
 //
 //    flat_tree_adopt_sequence_equal
 //
 ///////////////////////////////////////
 template<class SequenceContainer, class Compare>
 void flat_tree_sort_contiguous_to_adopt // is_contiguous_container == true
    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp)
 {
    typedef typename SequenceContainer::value_type value_type;
    typedef typename SequenceContainer::size_type  size_type;
 
    size_type tseq_unused_storage_size, seq_unused_storage_size;
    value_type* const tseq_unused_storage_addr =
       unused_storage<SequenceContainer>::get(tseq, tseq_unused_storage_size);
    value_type* const seq_unused_storage_addr  =
       unused_storage<SequenceContainer>::get(seq,  seq_unused_storage_size);
 
    tseq.clear();
    const bool use_tseq_storage = tseq_unused_storage_size > seq_unused_storage_size;
 
    value_type * const seq_beg = boost::movelib::iterator_to_raw_pointer(seq.data());
 
    boost::movelib::adaptive_sort
       ( seq_beg
       , seq_beg + seq.size()
       , comp
       , use_tseq_storage ? tseq_unused_storage_addr : seq_unused_storage_addr
       , use_tseq_storage ? tseq_unused_storage_size : seq_unused_storage_size);
 }
 
 template<class SequenceContainer, class Compare>
 inline void flat_tree_adopt_sequence_equal // is_contiguous_container == true
    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::true_)
 {
    flat_tree_sort_contiguous_to_adopt(tseq, boost::move(seq), comp);
    tseq = boost::move(seq);
 }
 
 template<class SequenceContainer, class Compare>
 inline void flat_tree_adopt_sequence_equal // is_contiguous_container == false
    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::false_)
 {
    boost::movelib::adaptive_sort(seq.begin(), seq.end(), comp);
    tseq = boost::move(seq);
 }
 
 ///////////////////////////////////////
 //
 //    flat_tree_adopt_sequence_unique
 //
 ///////////////////////////////////////
 template<class SequenceContainer, class Compare>
 void flat_tree_adopt_sequence_unique// is_contiguous_container == true
    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::true_)
 {
    typedef typename SequenceContainer::value_type value_type;
    value_type * const seq_beg = boost::movelib::iterator_to_raw_pointer(seq.data());
    boost::movelib::pdqsort
       ( seq_beg
       , seq_beg + seq.size()
       , comp);
    seq.erase(boost::movelib::unique
       (seq.begin(), seq.end(), boost::movelib::negate<Compare>(comp)), seq.cend());
    tseq = boost::move(seq);
 }
 
 template<class SequenceContainer, class Compare>
 void flat_tree_adopt_sequence_unique// is_contiguous_container == false
    (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::false_)
 {
    boost::movelib::pdqsort(seq.begin(), seq.end(), comp);
    seq.erase(boost::movelib::unique
       (seq.begin(), seq.end(), boost::movelib::negate<Compare>(comp)), seq.cend());
    tseq = boost::move(seq);
 }
 
 ///////////////////////////////////////
 //
 //       flat_tree_reserve
 //
 ///////////////////////////////////////
 template<class SequenceContainer>
 inline void // has_reserve == true
    flat_tree_reserve(SequenceContainer &tseq, typename SequenceContainer::size_type cap, dtl::true_)
 {
    tseq.reserve(cap);
 }
 
 template<class SequenceContainer>
 inline void // has_reserve == false
    flat_tree_reserve(SequenceContainer &, typename SequenceContainer::size_type, dtl::false_)
 {
 }
 
 ///////////////////////////////////////
 //
 //       flat_tree_capacity
 //
 ///////////////////////////////////////
 template<class SequenceContainer>   // has_capacity == true
 inline typename SequenceContainer::size_type
    flat_tree_capacity(const SequenceContainer &tseq, dtl::true_)
 {
    return tseq.capacity();
 }
 
 template<class SequenceContainer>   // has_capacity == false
 inline typename SequenceContainer::size_type
    flat_tree_capacity(const SequenceContainer &tseq, dtl::false_)
 {
    return tseq.size();
 }
 
 ///////////////////////////////////////
 //
 //       flat_tree_value_compare
 //
 ///////////////////////////////////////
 
 template<class Compare, class Value, class KeyOfValue>
 class flat_tree_value_compare
    : private Compare
 {
    typedef Value              first_argument_type;
    typedef Value              second_argument_type;
    typedef bool               return_type;
    public:
    inline flat_tree_value_compare()
       : Compare()
    {}
 
    inline flat_tree_value_compare(const Compare &pred)
       : Compare(pred)
    {}
 
    inline bool operator()(const Value& lhs, const Value& rhs) const
    {
       KeyOfValue key_extract;
       return Compare::operator()(key_extract(lhs), key_extract(rhs));
    }
 
    inline const Compare &get_comp() const
       {  return *this;  }
 
    inline Compare &get_comp()
       {  return *this;  }
 };
 
 
 ///////////////////////////////////////
 //
 //       select_flat_tree_container_type
 //
 ///////////////////////////////////////
 template < class Value, class AllocatorOrContainer
          , bool = boost::container::dtl::is_container<AllocatorOrContainer>::value
          >
 struct select_flat_tree_container_type
 {
    typedef AllocatorOrContainer type;
 };
 
 template <class Value, class AllocatorOrVoid>
 struct select_flat_tree_container_type<Value, AllocatorOrVoid, false>
 {
    typedef boost::container::vector<Value, AllocatorOrVoid> type;
 };
 
 
 ///////////////////////////////////////
 //
 //          flat_tree
 //
 ///////////////////////////////////////
 template <class Value, class KeyOfValue,
           class Compare, class AllocatorOrContainer>
 class flat_tree
 {
    public:
    typedef typename select_flat_tree_container_type<Value, AllocatorOrContainer>::type container_type;
    typedef container_type sequence_type;  //For backwards compatibility
 
    private:
    typedef typename container_type::allocator_type        allocator_t;
    typedef allocator_traits<allocator_t>                 allocator_traits_type;
 
    public:
    typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare;
 
    private:
    
    struct Data
       //Inherit from value_compare to do EBO
       : public value_compare
    {
       BOOST_COPYABLE_AND_MOVABLE(Data)
 
       public:
       inline Data()
          : value_compare(), m_seq()
       {}
 
       inline explicit Data(const allocator_t &alloc)
          : value_compare(), m_seq(alloc)
       {}
 
       inline explicit Data(const Compare &comp)
          : value_compare(comp), m_seq()
       {}
 
       inline Data(const Compare &comp, const allocator_t &alloc)
          : value_compare(comp), m_seq(alloc)
       {}
 
       inline explicit Data(const Data &d)
          : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq)
       {}
 
       inline Data(BOOST_RV_REF(Data) d)
          : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq))
       {}
 
       inline Data(const Data &d, const allocator_t &a)
          : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq, a)
       {}
 
       inline Data(BOOST_RV_REF(Data) d, const allocator_t &a)
          : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq), a)
       {}
 
       Data& operator=(BOOST_COPY_ASSIGN_REF(Data) d)
       {
          this->value_compare::operator=(d);
          m_seq = d.m_seq;
          return *this;
       }
 
       Data& operator=(BOOST_RV_REF(Data) d)
       {
          this->value_compare::operator=(boost::move(static_cast<value_compare &>(d)));
          m_seq = boost::move(d.m_seq);
          return *this;
       }
 
       void swap(Data &d)
       {
          value_compare& mycomp    = *this, & othercomp = d;
          boost::adl_move_swap(mycomp, othercomp);
          this->m_seq.swap(d.m_seq);
       }
 
       container_type m_seq;
    };
 
    Data m_data;
    BOOST_COPYABLE_AND_MOVABLE(flat_tree)
 
    public:
 
    typedef typename container_type::value_type              value_type;
    typedef typename container_type::pointer                 pointer;
    typedef typename container_type::const_pointer           const_pointer;
    typedef typename container_type::reference               reference;
    typedef typename container_type::const_reference         const_reference;
    typedef typename KeyOfValue::type                        key_type;
    typedef Compare                                          key_compare;
    typedef typename container_type::allocator_type          allocator_type;
    typedef typename container_type::size_type               size_type;
    typedef typename container_type::difference_type         difference_type;
    typedef typename container_type::iterator                iterator;
    typedef typename container_type::const_iterator          const_iterator;
    typedef typename container_type::reverse_iterator        reverse_iterator;
    typedef typename container_type::const_reverse_iterator  const_reverse_iterator;
 
    //`allocator_type::value_type` must match container's `value type`. If this
    //assertion fails, please review your allocator definition. 
    BOOST_CONTAINER_STATIC_ASSERT((is_same<value_type, typename allocator_traits_type::value_type>::value));
 
    //!Standard extension
    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
       (boost::container::dtl::, container_type
       ,stored_allocator_type, allocator_type)               stored_allocator_type;
 
    BOOST_STATIC_CONSTEXPR bool has_stored_allocator_type =
       BOOST_INTRUSIVE_HAS_TYPE(boost::container::dtl::, container_type, stored_allocator_type);
 
    private:
    typedef allocator_traits<stored_allocator_type> stored_allocator_traits;
 
    public:
    typedef typename dtl::if_c
       <has_stored_allocator_type, const stored_allocator_type &, allocator_type>::type get_stored_allocator_const_return_t;
 
    typedef typename dtl::if_c
       <has_stored_allocator_type, stored_allocator_type &, allocator_type>::type get_stored_allocator_noconst_return_t;
 
    inline flat_tree()
       : m_data()
    { }
 
    inline explicit flat_tree(const Compare& comp)
       : m_data(comp)
    { }
 
    inline explicit flat_tree(const allocator_type& a)
       : m_data(a)
    { }
 
    inline flat_tree(const Compare& comp, const allocator_type& a)
       : m_data(comp, a)
    { }
 
    inline flat_tree(const flat_tree& x)
       :  m_data(x.m_data)
    { }
 
    inline flat_tree(BOOST_RV_REF(flat_tree) x)
       BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
       :  m_data(boost::move(x.m_data))
    { }
 
    inline flat_tree(const flat_tree& x, const allocator_type &a)
       :  m_data(x.m_data, a)
    { }
 
    inline flat_tree(BOOST_RV_REF(flat_tree) x, const allocator_type &a)
       :  m_data(boost::move(x.m_data), a)
    { }
 
    template <class InputIterator>
    inline
    flat_tree( ordered_range_t, InputIterator first, InputIterator last)
       : m_data()
    {
       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
       BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
    }
 
    template <class InputIterator>
    inline
    flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
       : m_data(comp)
    {
       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
       BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
    }
 
    template <class InputIterator>
    inline
    flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
       : m_data(comp, a)
    {
       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
       BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
    }
 
    template <class InputIterator>
    inline
    flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last)
       : m_data()
    {
       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
       BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
    }
 
    template <class InputIterator>
    inline
    flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
       : m_data(comp)
    {
       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
       BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
    }
 
    template <class InputIterator>
    inline
    flat_tree( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
       : m_data(comp, a)
    {
       this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
       BOOST_ASSERT((is_sorted_and_unique)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
    }
 
    template <class InputIterator>
    inline
    flat_tree( bool unique_insertion, InputIterator first, InputIterator last)
       : m_data()
    {
       this->priv_range_insertion_construct(unique_insertion, first, last);
    }
 
    template <class InputIterator>
    inline
    flat_tree( bool unique_insertion, InputIterator first, InputIterator last
             , const Compare& comp)
       : m_data(comp)
    {
       this->priv_range_insertion_construct(unique_insertion, first, last);
    }
 
    template <class InputIterator>
    inline
    flat_tree( bool unique_insertion, InputIterator first, InputIterator last
             , const allocator_type& a)
       : m_data(a)
    {
       this->priv_range_insertion_construct(unique_insertion, first, last);
    }
 
    template <class InputIterator>
    inline
    flat_tree( bool unique_insertion, InputIterator first, InputIterator last
             , const Compare& comp, const allocator_type& a)
       : m_data(comp, a)
    {
       this->priv_range_insertion_construct(unique_insertion, first, last);
    }
 
    inline ~flat_tree()
    {
    }
 
    inline flat_tree&  operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x)
    {  m_data = x.m_data;   return *this;  }
 
    inline flat_tree&  operator=(BOOST_RV_REF(flat_tree) x)
       BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
                           allocator_traits_type::is_always_equal::value) &&
                            boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
    {  m_data = boost::move(x.m_data); return *this;  }
 
    inline const value_compare &priv_value_comp() const
    { return static_cast<const value_compare &>(this->m_data); }
 
    inline value_compare &priv_value_comp()
    { return static_cast<value_compare &>(this->m_data); }
 
    inline const key_compare &priv_key_comp() const
    { return this->priv_value_comp().get_comp(); }
 
    inline key_compare &priv_key_comp()
    { return this->priv_value_comp().get_comp(); }
 
    struct insert_commit_data
    {
       const_iterator position;
    };
 
    public:
    // accessors:
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       Compare key_comp() const
    { return this->m_data.get_comp(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       value_compare value_comp() const
    { return this->m_data; }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       allocator_type get_allocator() const
    { return this->m_data.m_seq.get_allocator(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       get_stored_allocator_const_return_t get_stored_allocator() const
    {
       return flat_tree_get_stored_allocator(this->m_data.m_seq, dtl::bool_<has_stored_allocator_type>());
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       get_stored_allocator_noconst_return_t get_stored_allocator()
    {
       return flat_tree_get_stored_allocator(this->m_data.m_seq, dtl::bool_<has_stored_allocator_type>());
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       iterator begin()
    { return this->m_data.m_seq.begin(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator begin() const
    { return this->cbegin(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator cbegin() const
    { return this->m_data.m_seq.begin(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       iterator end()
    { return this->m_data.m_seq.end(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator end() const
    { return this->cend(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator cend() const
    { return this->m_data.m_seq.end(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       reverse_iterator rbegin()
    { return reverse_iterator(this->end()); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reverse_iterator rbegin() const
    {  return this->crbegin();  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reverse_iterator crbegin() const
    {  return const_reverse_iterator(this->cend());  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       reverse_iterator rend()
    { return reverse_iterator(this->begin()); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reverse_iterator rend() const
    { return this->crend(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_reverse_iterator crend() const
    { return const_reverse_iterator(this->cbegin()); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       bool empty() const
    { return this->m_data.m_seq.empty(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       size_type size() const
    { return this->m_data.m_seq.size(); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       size_type max_size() const
    { return this->m_data.m_seq.max_size(); }
 
    inline void swap(flat_tree& other)
       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value )
    {  this->m_data.swap(other.m_data);  }
 
    public:
    // insert/erase
    std::pair<iterator,bool> insert_unique(const value_type& val)
    {
       std::pair<iterator,bool> ret;
       insert_commit_data data;
       ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data);
       ret.first = ret.second ? this->priv_insert_commit(data, val)
                              : this->begin() + (data.position - this->cbegin());
                              //: iterator(vector_iterator_get_ptr(data.position));
       return ret;
    }
 
    std::pair<iterator,bool> insert_unique(BOOST_RV_REF(value_type) val)
    {
       std::pair<iterator,bool> ret;
       insert_commit_data data;
       ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data);
       ret.first = ret.second ? this->priv_insert_commit(data, boost::move(val))
                              : this->begin() + (data.position - this->cbegin());
                              //: iterator(vector_iterator_get_ptr(data.position));
       return ret;
    }
 
    iterator insert_equal(const value_type& val)
    {
       iterator i = this->upper_bound(KeyOfValue()(val));
       i = this->m_data.m_seq.insert(i, val);
       return i;
    }
 
    iterator insert_equal(BOOST_RV_REF(value_type) mval)
    {
       iterator i = this->upper_bound(KeyOfValue()(mval));
       i = this->m_data.m_seq.insert(i, boost::move(mval));
       return i;
    }
 
    iterator insert_unique(const_iterator hint, const value_type& val)
    {
       BOOST_ASSERT(this->priv_in_range_or_end(hint));
       insert_commit_data data;
       return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
             ? this->priv_insert_commit(data, val)
             : this->begin() + (data.position - this->cbegin());
             //: iterator(vector_iterator_get_ptr(data.position));
    }
 
    iterator insert_unique(const_iterator hint, BOOST_RV_REF(value_type) val)
    {
       BOOST_ASSERT(this->priv_in_range_or_end(hint));
       insert_commit_data data;
       return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
          ? this->priv_insert_commit(data, boost::move(val))
          : this->begin() + (data.position - this->cbegin());
          //: iterator(vector_iterator_get_ptr(data.position));
    }
 
    iterator insert_equal(const_iterator hint, const value_type& val)
    {
       BOOST_ASSERT(this->priv_in_range_or_end(hint));
       insert_commit_data data;
       this->priv_insert_equal_prepare(hint, val, data);
       return this->priv_insert_commit(data, val);
    }
 
    iterator insert_equal(const_iterator hint, BOOST_RV_REF(value_type) mval)
    {
       BOOST_ASSERT(this->priv_in_range_or_end(hint));
       insert_commit_data data;
       this->priv_insert_equal_prepare(hint, mval, data);
       return this->priv_insert_commit(data, boost::move(mval));
    }
 
    template <class InIt>
    void insert_unique(InIt first, InIt last)
    {
       dtl::bool_<is_contiguous_container<container_type>::value> contiguous_tag;
       container_type &seq = this->m_data.m_seq;
       value_compare &val_cmp = this->priv_value_comp();
 
       //Step 1: put new elements in the back
       typename container_type::iterator const it = seq.insert(seq.cend(), first, last);
 
       //Step 2: sort them
       boost::movelib::pdqsort(it, seq.end(), val_cmp);
 
       //Step 3: only left unique values from the back not already present in the original range
       typename container_type::iterator const e = boost::movelib::inplace_set_unique_difference
          (it, seq.end(), seq.begin(), it, val_cmp);
 
       //it might be invalidated by erasing [e, seq.end) if e == it, so check it before
       const bool remaining = e != it;
       seq.erase(e, seq.cend());
       if (remaining)
       {
          //Step 4: merge both ranges
          (flat_tree_container_inplace_merge)(seq, it, this->priv_value_comp(), contiguous_tag);
       }
    }
 
    template <class InIt>
    void insert_equal(InIt first, InIt last)
    {
       if (first != last) {
          dtl::bool_<is_contiguous_container<container_type>::value> contiguous_tag;
          container_type &seq = this->m_data.m_seq;
          typename container_type::iterator const it = seq.insert(seq.cend(), first, last);
          (flat_tree_container_inplace_sort_ending)(seq, it, this->priv_value_comp(), contiguous_tag);
          (flat_tree_container_inplace_merge)      (seq, it, this->priv_value_comp(), contiguous_tag);
       }
    }
 
    //Ordered
 
    template <class InIt>
    void insert_equal(ordered_range_t, InIt first, InIt last)
    {
       const bool value = boost::container::dtl::
          has_member_function_callable_with_merge_unique<container_type, InIt, InIt, value_compare>::value;
       (flat_tree_merge_equal)(this->m_data.m_seq, first, last, this->priv_value_comp(), dtl::bool_<value>());
    }
 
    template <class InIt>
    void insert_unique(ordered_unique_range_t, InIt first, InIt last)
    {
       const bool value = boost::container::dtl::
          has_member_function_callable_with_merge_unique<container_type, InIt, InIt, value_compare>::value;
       (flat_tree_merge_unique)(this->m_data.m_seq, first, last, this->priv_value_comp(), dtl::bool_<value>());
    }
 
    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 
    template <class... Args>
    std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args)
    {
       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
       stored_allocator_traits::construct(a, (value_type *)(&v), ::boost::forward<Args>(args)... );
       value_type *pval = move_detail::launder_cast<value_type *>(&v);
       value_destructor<stored_allocator_type, value_type> d(a, *pval);
       return this->insert_unique(::boost::move(*pval));
    }
 
    template <class... Args>
    iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args)
    {
       //hint checked in insert_unique
       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
       stored_allocator_traits::construct(a, (value_type*)(&v), ::boost::forward<Args>(args)... );
       value_type *pval = move_detail::launder_cast<value_type *>(&v);
       value_destructor<stored_allocator_type, value_type> d(a, *pval);
       return this->insert_unique(hint, ::boost::move(*pval));
    }
 
    template <class... Args>
    iterator emplace_equal(BOOST_FWD_REF(Args)... args)
    {
       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
       stored_allocator_traits::construct(a, (value_type*)(&v), ::boost::forward<Args>(args)... );
       value_type *pval = move_detail::launder_cast<value_type *>(&v);
       value_destructor<stored_allocator_type, value_type> d(a, *pval);
       return this->insert_equal(::boost::move(*pval));
    }
 
    template <class... Args>
    iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args)
    {
       //hint checked in insert_equal
       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;
       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();
       stored_allocator_traits::construct(a, (value_type*)(&v), ::boost::forward<Args>(args)... );
       value_type *pval = move_detail::launder_cast<value_type *>(&v);
       value_destructor<stored_allocator_type, value_type> d(a, *pval);
       return this->insert_equal(hint, ::boost::move(*pval));
    }
 
    template <class KeyType, class... Args>
    inline std::pair<iterator, bool> try_emplace
       (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args)
    {
       std::pair<iterator,bool> ret;
       insert_commit_data data;
       const key_type & k = key;
       ret.second = hint == const_iterator()
          ? this->priv_insert_unique_prepare(k, data)
          : this->priv_insert_unique_prepare(hint, k, data);
 
       if(!ret.second){
          ret.first  = this->nth(size_type(data.position - this->cbegin()));
       }
       else{
          ret.first = this->m_data.m_seq.emplace(data.position, try_emplace_t(), ::boost::forward<KeyType>(key), ::boost::forward<Args>(args)...);
       }
       return ret;
    }
 
    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 
    #define BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE(N) \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\
    {\
       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
       stored_allocator_traits::construct(a, (value_type *)(&v) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
       value_type *pval = move_detail::launder_cast<value_type *>(&v);\
       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
       return this->insert_unique(::boost::move(*pval));\
    }\
    \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
       stored_allocator_traits::construct(a, (value_type *)(&v) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
       value_type *pval = move_detail::launder_cast<value_type *>(&v);\
       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
       return this->insert_unique(hint, ::boost::move(*pval));\
    }\
    \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    iterator emplace_equal(BOOST_MOVE_UREF##N)\
    {\
       typename dtl::aligned_storage<sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
       stored_allocator_traits::construct(a, (value_type *)(&v) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
       value_type *pval = move_detail::launder_cast<value_type *>(&v);\
       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
       return this->insert_equal(::boost::move(*pval));\
    }\
    \
    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
    iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       typename dtl::aligned_storage <sizeof(value_type), dtl::alignment_of<value_type>::value>::type v;\
       get_stored_allocator_noconst_return_t a = this->get_stored_allocator();\
       stored_allocator_traits::construct(a, (value_type *)(&v) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
       value_type *pval = move_detail::launder_cast<value_type *>(&v);\
       value_destructor<stored_allocator_type, value_type> d(a, *pval);\
       return this->insert_equal(hint, ::boost::move(*pval));\
    }\
    template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\
    inline std::pair<iterator, bool>\
       try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
    {\
       std::pair<iterator,bool> ret;\
       insert_commit_data data;\
       const key_type & k = key;\
       ret.second = hint == const_iterator()\
          ? this->priv_insert_unique_prepare(k, data)\
          : this->priv_insert_unique_prepare(hint, k, data);\
       \
       if(!ret.second){\
          ret.first  = this->nth(size_type(data.position - this->cbegin()));\
       }\
       else{\
          ret.first = this->m_data.m_seq.emplace(data.position, try_emplace_t(), ::boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
       }\
       return ret;\
    }\
    //
    BOOST_MOVE_ITERATE_0TO7(BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE)
    #undef BOOST_CONTAINER_FLAT_TREE_EMPLACE_CODE
 
    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 
    template<class KeyType, class M>
    std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj)
    {
       const key_type& k = key;
       std::pair<iterator,bool> ret;
       insert_commit_data data;
       ret.second = hint == const_iterator()
          ? this->priv_insert_unique_prepare(k, data)
          : this->priv_insert_unique_prepare(hint, k, data);
       if(!ret.second){
          ret.first  = this->nth(size_type(data.position - this->cbegin()));
          ret.first->second = boost::forward<M>(obj);
       }
       else{
          ret.first = this->m_data.m_seq.emplace(data.position, boost::forward<KeyType>(key), boost::forward<M>(obj));
       }
       return ret;
    }
 
    size_type erase(const key_type& k)
    {
       std::pair<iterator,iterator > itp = this->equal_range(k);
       size_type ret = static_cast<size_type>(itp.second-itp.first);
       if (ret){
          this->m_data.m_seq.erase(itp.first, itp.second);
       }
       return ret;
    }
 
    size_type erase_unique(const key_type& k)
    {
       const_iterator i = static_cast<const flat_tree &>(*this).find(k);
       size_type ret = static_cast<size_type>(i != this->cend());
       if (ret)
          this->erase(i);
       return ret;
    }
 
    template <class K>
    inline typename dtl::enable_if_c<
       dtl::is_transparent<key_compare>::value &&      //transparent
       !dtl::is_convertible<K, iterator>::value &&     //not convertible to iterator
       !dtl::is_convertible<K, const_iterator>::value  //not convertible to const_iterator
       , size_type>::type
       erase(BOOST_FWD_REF(K) key)
    {
       const typename remove_cvref<K>::type & k = key;  //Support emulated rvalue references
       std::pair<iterator, iterator > itp = this->equal_range(k);
       size_type ret = static_cast<size_type>(itp.second - itp.first);
       if (ret) {
          this->m_data.m_seq.erase(itp.first, itp.second);
       }
       return ret;
    }
 
    template <class K>
    inline typename dtl::enable_if_c<
       dtl::is_transparent<key_compare>::value &&      //transparent
       !dtl::is_convertible<K, iterator>::value &&     //not convertible to iterator
       !dtl::is_convertible<K, const_iterator>::value  //not convertible to const_iterator
       , size_type>::type
       erase_unique(const K& k)
    {
       const_iterator i = static_cast<const flat_tree&>(*this).find(k);
       size_type ret = static_cast<size_type>(i != this->cend());
       if (ret)
          this->erase(i);
       return ret;
    }
 
    inline iterator erase(const_iterator position)
    {  return this->m_data.m_seq.erase(position);  }
 
    inline iterator erase(const_iterator first, const_iterator last)
    {  return this->m_data.m_seq.erase(first, last);  }
 
    inline void clear()
    {  this->m_data.m_seq.clear();  }
 
    //! <b>Effects</b>: Tries to deallocate the excess of memory created
    //    with previous allocations. The size of the vector is unchanged
    //!
    //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
    //!
    //! <b>Complexity</b>: Linear to size().
    inline void shrink_to_fit()
    {  this->m_data.m_seq.shrink_to_fit();  }
 
    inline iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
    {
       const bool value = boost::container::dtl::
          has_member_function_callable_with_nth<container_type, size_type>::value;
       return flat_tree_nth<iterator>(this->m_data.m_seq, n, dtl::bool_<value>());
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
    {
       const bool value = boost::container::dtl::
          has_member_function_callable_with_nth<container_type, size_type>::value;
       return flat_tree_nth<const_iterator>(this->m_data.m_seq, n, dtl::bool_<value>());
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
    {
       const bool value = boost::container::dtl::
          has_member_function_callable_with_index_of<container_type, iterator>::value;
       return flat_tree_index_of(this->m_data.m_seq, p, dtl::bool_<value>());
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
    {
       const bool value = boost::container::dtl::
          has_member_function_callable_with_index_of<container_type, const_iterator>::value;
       return flat_tree_index_of(this->m_data.m_seq, p, dtl::bool_<value>());
    }
 
    // set operations:
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
       iterator find(const key_type& k)
    {
       iterator i = this->lower_bound(k);
       iterator end_it = this->end();
       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
          i = end_it;
       }
       return i;
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
    const_iterator find(const key_type& k) const
    {
       const_iterator i = this->lower_bound(k);
 
       const_iterator end_it = this->cend();
       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
          i = end_it;
       }
       return i;
    }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
       typename dtl::enable_if_transparent<key_compare, K, iterator>::type
       find(const K& k)
    {
       iterator i = this->lower_bound(k);
       iterator end_it = this->end();
       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
          i = end_it;
       }
       return i;
    }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
       typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
       find(const K& k) const
    {
       const_iterator i = this->lower_bound(k);
 
       const_iterator end_it = this->cend();
       if (i != end_it && this->m_data.get_comp()(k, KeyOfValue()(*i))){
          i = end_it;
       }
       return i;
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
       size_type count(const key_type& k) const
    {
       std::pair<const_iterator, const_iterator> p = this->equal_range(k);
       size_type n = size_type(p.second - p.first);
       return n;
    }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
       typename dtl::enable_if_transparent<key_compare, K, size_type>::type
       count(const K& k) const
    {
       std::pair<const_iterator, const_iterator> p = this->equal_range(k);
       size_type n = size_type(p.second - p.first);
       return n;
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline bool contains(const key_type& x) const
    {  return this->find(x) != this->cend();  }
 
    template<typename K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       typename dtl::enable_if_transparent<key_compare, K, bool>::type
          contains(const K& x) const
    {  return this->find(x) != this->cend();  }
 
    template<class C2>
    inline void merge_unique(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source)
    {
       this->insert_unique( boost::make_move_iterator(source.begin())
                          , boost::make_move_iterator(source.end()));
    }
 
    template<class C2>
    inline void merge_equal(flat_tree<Value, KeyOfValue, C2, AllocatorOrContainer>& source)
    {
       this->insert_equal( boost::make_move_iterator(source.begin())
                         , boost::make_move_iterator(source.end()));
    }
 
    inline void merge_unique(flat_tree& source)
    {
       const bool value = boost::container::dtl::
          has_member_function_callable_with_merge_unique<container_type, iterator, iterator, value_compare>::value;
       (flat_tree_merge_unique)
          ( this->m_data.m_seq
          , boost::make_move_iterator(source.m_data.m_seq.begin())
          , boost::make_move_iterator(source.m_data.m_seq.end())
          , this->priv_value_comp()
          , dtl::bool_<value>());
    }
 
    inline void merge_equal(flat_tree& source)
    {
       const bool value = boost::container::dtl::
          has_member_function_callable_with_merge<container_type, iterator, iterator, value_compare>::value;
       (flat_tree_merge_equal)
          ( this->m_data.m_seq
          , boost::make_move_iterator(source.m_data.m_seq.begin())
          , boost::make_move_iterator(source.m_data.m_seq.end())
          , this->priv_value_comp()
          , dtl::bool_<value>());
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       iterator lower_bound(const key_type& k)
    {  return this->priv_lower_bound(this->begin(), this->end(), k);  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const_iterator lower_bound(const key_type& k) const
    {  return this->priv_lower_bound(this->cbegin(), this->cend(), k);  }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline 
       typename dtl::enable_if_transparent<key_compare, K, iterator>::type
          lower_bound(const K& k)
    {  return this->priv_lower_bound(this->begin(), this->end(), k);  }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline 
       typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type
          lower_bound(const K& k) const
    {  return this->priv_lower_bound(this->cbegin(), this->cend(), k);  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       iterator upper_bound(const key_type& k)
    {  return this->priv_upper_bound(this->begin(), this->end(), k);  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline 
       const_iterator upper_bound(const key_type& k) const
    {  return this->priv_upper_bound(this->cbegin(), this->cend(), k);  }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       typename dtl::enable_if_transparent<key_compare, K,iterator>::type
    upper_bound(const K& k)
    {  return this->priv_upper_bound(this->begin(), this->end(), k);  }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       typename dtl::enable_if_transparent<key_compare, K,const_iterator>::type
          upper_bound(const K& k) const
    {  return this->priv_upper_bound(this->cbegin(), this->cend(), k);  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       std::pair<iterator,iterator> equal_range(const key_type& k)
    {  return this->priv_equal_range(this->begin(), this->end(), k);  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
    {  return this->priv_equal_range(this->cbegin(), this->cend(), k);  }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type
          equal_range(const K& k)
    {  return this->priv_equal_range(this->begin(), this->end(), k);  }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       typename dtl::enable_if_transparent<key_compare, K,std::pair<const_iterator,const_iterator> >::type
          equal_range(const K& k) const
    {  return this->priv_equal_range(this->cbegin(), this->cend(), k);  }
 
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       std::pair<iterator, iterator> lower_bound_range(const key_type& k)
    {  return this->priv_lower_bound_range(this->begin(), this->end(), k);  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const
    {  return this->priv_lower_bound_range(this->cbegin(), this->cend(), k);  }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       typename dtl::enable_if_transparent<key_compare, K,std::pair<iterator,iterator> >::type
          lower_bound_range(const K& k)
    {  return this->priv_lower_bound_range(this->begin(), this->end(), k);  }
 
    template<class K>
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       typename dtl::enable_if_transparent<key_compare, K,std::pair<const_iterator,const_iterator> >::type
          lower_bound_range(const K& k) const
    {  return this->priv_lower_bound_range(this->cbegin(), this->cend(), k);  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       size_type capacity() const
    {
       const bool value = boost::container::dtl::
          has_member_function_callable_with_capacity<container_type>::value;
       return (flat_tree_capacity)(this->m_data.m_seq, dtl::bool_<value>());
    }
 
    inline
       void reserve(size_type cnt)
    {
       const bool value = boost::container::dtl::
          has_member_function_callable_with_reserve<container_type, size_type>::value;
       (flat_tree_reserve)(this->m_data.m_seq, cnt, dtl::bool_<value>());
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       container_type extract_sequence()
    {  return boost::move(m_data.m_seq);   }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       container_type &get_sequence_ref()
    {  return m_data.m_seq; }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       const container_type &get_sequence_cref() const
    {  return m_data.m_seq; }
 
    inline void adopt_sequence_equal(BOOST_RV_REF(container_type) seq)
    {
       (flat_tree_adopt_sequence_equal)( m_data.m_seq, boost::move(seq), this->priv_value_comp()
          , dtl::bool_<is_contiguous_container<container_type>::value>());
    }
 
    inline void adopt_sequence_unique(BOOST_RV_REF(container_type) seq)
    {
       (flat_tree_adopt_sequence_unique)(m_data.m_seq, boost::move(seq), this->priv_value_comp()
          , dtl::bool_<is_contiguous_container<container_type>::value>());
    }
 
    void adopt_sequence_equal(ordered_range_t, BOOST_RV_REF(container_type) seq)
    {
       BOOST_ASSERT((is_sorted)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
       m_data.m_seq = boost::move(seq);
    }
 
    void adopt_sequence_unique(ordered_unique_range_t, BOOST_RV_REF(container_type) seq)
    {
       BOOST_ASSERT((is_sorted_and_unique)(seq.cbegin(), seq.cend(), this->priv_value_comp()));
       m_data.m_seq = boost::move(seq);
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator==(const flat_tree& x, const flat_tree& y)
    {
       return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator<(const flat_tree& x, const flat_tree& y)
    {
       return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
    }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator!=(const flat_tree& x, const flat_tree& y)
       {  return !(x == y); }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator>(const flat_tree& x, const flat_tree& y)
       {  return y < x;  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator<=(const flat_tree& x, const flat_tree& y)
       {  return !(y < x);  }
 
    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
       friend bool operator>=(const flat_tree& x, const flat_tree& y)
       {  return !(x < y);  }
 
    inline friend void swap(flat_tree& x, flat_tree& y)
           BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT(x.swap(y)))
       {  x.swap(y);  }
 
    private:
 
    template <class InputIterator>
    void priv_range_insertion_construct( bool unique_insertion, InputIterator first, InputIterator last)
    {
       //Use cend() as hint to achieve linear time for
       //ordered ranges as required by the standard
       //for the constructor
       //Call end() every iteration as reallocation might have invalidated iterators
       if(unique_insertion){
          this->insert_unique(first, last);
       }
       else{
          this->insert_equal (first, last);
       }
    }
 
    inline bool priv_in_range_or_end(const_iterator pos) const
    {
       return (this->begin() <= pos) && (pos <= this->end());
    }
 
    // insert/erase
    void priv_insert_equal_prepare
       (const_iterator pos, const value_type& val, insert_commit_data &data)
    {
       // N1780
       //   To insert val at pos:
       //   if pos == end || val <= *pos
       //      if pos == begin || val >= *(pos-1)
       //         insert val before pos
       //      else
       //         insert val before upper_bound(val)
       //   else
       //      insert val before lower_bound(val)
       const value_compare &val_cmp = this->m_data;
 
       if(pos == this->cend() || !val_cmp(*pos, val)){
          if (pos == this->cbegin() || !val_cmp(val, pos[-1])){
             data.position = pos;
          }
          else{
             data.position =
                this->priv_upper_bound(this->cbegin(), pos, KeyOfValue()(val));
          }
       }
       else{
          data.position =
             this->priv_lower_bound(pos, this->cend(), KeyOfValue()(val));
       }
    }
 
    bool priv_insert_unique_prepare
       (const_iterator b, const_iterator e, const key_type& k, insert_commit_data &commit_data)
    {
       const key_compare &key_cmp  = this->priv_key_comp();
       commit_data.position = this->priv_lower_bound(b, e, k);
       return commit_data.position == e || key_cmp(k, KeyOfValue()(*commit_data.position));
    }
 
    inline bool priv_insert_unique_prepare
       (const key_type& k, insert_commit_data &commit_data)
    {  return this->priv_insert_unique_prepare(this->cbegin(), this->cend(), k, commit_data);   }
 
    bool priv_insert_unique_prepare
       (const_iterator pos, const key_type& k, insert_commit_data &commit_data)
    {
       //N1780. Props to Howard Hinnant!
       //To insert k at pos:
       //if pos == end || k <= *pos
       //   if pos == begin || k >= *(pos-1)
       //      insert k before pos
       //   else
       //      insert k before upper_bound(k)
       //else if pos+1 == end || k <= *(pos+1)
       //   insert k after pos
       //else
       //   insert k before lower_bound(k)
       const key_compare &key_cmp = this->priv_key_comp();
       const const_iterator cend_it = this->cend();
       if(pos == cend_it || key_cmp(k, KeyOfValue()(*pos))){ //Check if k should go before end
          const const_iterator cbeg = this->cbegin();
          commit_data.position = pos;
          if(pos == cbeg){  //If container is empty then insert it in the beginning
             return true;
          }
          const_iterator prev(pos);
          --prev;
          if(key_cmp(KeyOfValue()(*prev), k)){   //If previous element was less, then it should go between prev and pos
             return true;
          }
          else if(!key_cmp(k, KeyOfValue()(*prev))){   //If previous was equal then insertion should fail
             commit_data.position = prev;
             return false;
          }
          else{ //Previous was bigger so insertion hint was pointless, dispatch to hintless insertion
                //but reduce the search between beg and prev as prev is bigger than k
             return this->priv_insert_unique_prepare(cbeg, prev, k, commit_data);
          }
       }
       else{
          //The hint is before the insertion position, so insert it
          //in the remaining range [pos, end)
          return this->priv_insert_unique_prepare(pos, cend_it, k, commit_data);
       }
    }
 
    template<class Convertible>
    inline iterator priv_insert_commit
       (insert_commit_data &commit_data, BOOST_FWD_REF(Convertible) convertible)
    {
       return this->m_data.m_seq.insert
          ( commit_data.position
          , boost::forward<Convertible>(convertible));
    }
 
    template <class RanIt, class K>
    RanIt priv_lower_bound(RanIt first, const RanIt last,
                           const K & key) const
    {
       const Compare &key_cmp = this->m_data.get_comp();
       KeyOfValue key_extract;
       size_type len = static_cast<size_type>(last - first);
       RanIt middle;
 
       while (len) {
          size_type step = len >> 1;
          middle = first;
          middle += difference_type(step);
 
          if (key_cmp(key_extract(*middle), key)) {
             first = ++middle;
             len -= step + 1;
          }
          else{
             len = step;
          }
       }
       return first;
    }
 
    template <class RanIt, class K>
    RanIt priv_upper_bound
       (RanIt first, const RanIt last,const K & key) const
    {
       const Compare &key_cmp = this->m_data.get_comp();
       KeyOfValue key_extract;
       size_type len = static_cast<size_type>(last - first);
       RanIt middle;
 
       while (len) {
          size_type step = len >> 1;
          middle = first;
          middle += difference_type(step);
 
          if (key_cmp(key, key_extract(*middle))) {
             len = step;
          }
          else{
             first = ++middle;
             len -= step + 1;
          }
       }
       return first;
    }
 
    template <class RanIt, class K>
    std::pair<RanIt, RanIt>
       priv_equal_range(RanIt first, RanIt last, const K& key) const
    {
       const Compare &key_cmp = this->m_data.get_comp();
       KeyOfValue key_extract;
       size_type len = static_cast<size_type>(last - first);
       RanIt middle;
 
       while (len) {
          size_type step = len >> 1;
          middle = first;
          middle += difference_type(step);
 
          if (key_cmp(key_extract(*middle), key)){
             first = ++middle;
             len -= step + 1;
          }
          else if (key_cmp(key, key_extract(*middle))){
             len = step;
          }
          else {
             //Middle is equal to key
             last = first;
             last += difference_type(len);
             RanIt const first_ret = this->priv_lower_bound(first, middle, key);
             return std::pair<RanIt, RanIt>
                ( first_ret, this->priv_upper_bound(++middle, last, key));
          }
       }
       return std::pair<RanIt, RanIt>(first, first);
    }
 
    template<class RanIt, class K>
    std::pair<RanIt, RanIt> priv_lower_bound_range(RanIt first, RanIt last, const K& k) const
    {
       const Compare &key_cmp = this->m_data.get_comp();
       KeyOfValue key_extract;
       RanIt lb(this->priv_lower_bound(first, last, k)), ub(lb);
       if(lb != last && !key_cmp(k, key_extract(*lb))){
          ++ub;
       }
       return std::pair<RanIt, RanIt>(lb, ub);
    }
 };
 
 }  //namespace dtl {
 
 }  //namespace container {
 
 //!has_trivial_destructor_after_move<> == true_type
 //!specialization for optimizations
 template <class T, class KeyOfValue,
 class Compare, class AllocatorOrContainer>
 struct has_trivial_destructor_after_move<boost::container::dtl::flat_tree<T, KeyOfValue, Compare, AllocatorOrContainer> >
 {
    typedef boost::container::dtl::flat_tree<T, KeyOfValue, Compare, AllocatorOrContainer> flat_tree;
    typedef typename flat_tree::container_type container_type;
    typedef typename flat_tree::key_compare key_compare;
    BOOST_STATIC_CONSTEXPR bool value = ::boost::has_trivial_destructor_after_move<container_type>::value &&
                              ::boost::has_trivial_destructor_after_move<key_compare>::value;
 };
 
 }  //namespace boost {
 
 #include <boost/container/detail/config_end.hpp>
 
 #endif // BOOST_CONTAINER_FLAT_TREE_HPP

This page was automatically generated by the 2.3.7 LXR engine. The LXR team