view release on metacpan or  search on metacpan

include/boost/container/detail/flat_tree.hpp  view on Meta::CPAN

   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;

   //!Standard extension
   typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
      (boost::container::dtl::, container_type
      ,stored_allocator_type, allocator_type)               stored_allocator_type;

   static const 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;

   BOOST_CONTAINER_FORCEINLINE flat_tree()
      : m_data()
   { }

   BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const Compare& comp)
      : m_data(comp)
   { }

   BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const allocator_type& a)
      : m_data(a)
   { }

   BOOST_CONTAINER_FORCEINLINE flat_tree(const Compare& comp, const allocator_type& a)
      : m_data(comp, a)
   { }

   BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x)
      :  m_data(x.m_data)
   { }

   BOOST_CONTAINER_FORCEINLINE 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))
   { }

   BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x, const allocator_type &a)
      :  m_data(x.m_data, a)
   { }

   BOOST_CONTAINER_FORCEINLINE flat_tree(BOOST_RV_REF(flat_tree) x, const allocator_type &a)
      :  m_data(boost::move(x.m_data), a)
   { }

   template <class InputIterator>
   BOOST_CONTAINER_FORCEINLINE
   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>
   BOOST_CONTAINER_FORCEINLINE
   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>
   BOOST_CONTAINER_FORCEINLINE
   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>
   BOOST_CONTAINER_FORCEINLINE
   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>
   BOOST_CONTAINER_FORCEINLINE
   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>
   BOOST_CONTAINER_FORCEINLINE
   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>
   BOOST_CONTAINER_FORCEINLINE
   flat_tree( bool unique_insertion, InputIterator first, InputIterator last)
      : m_data()
   {
      this->priv_range_insertion_construct(unique_insertion, first, last);
   }

   template <class InputIterator>
   BOOST_CONTAINER_FORCEINLINE
   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>
   BOOST_CONTAINER_FORCEINLINE
   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>
   BOOST_CONTAINER_FORCEINLINE
   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);
   }

   BOOST_CONTAINER_FORCEINLINE ~flat_tree()
   {}

   BOOST_CONTAINER_FORCEINLINE flat_tree&  operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x)
   {  m_data = x.m_data;   return *this;  }

   BOOST_CONTAINER_FORCEINLINE 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;  }

   BOOST_CONTAINER_FORCEINLINE const value_compare &priv_value_comp() const
   { return static_cast<const value_compare &>(this->m_data); }

   BOOST_CONTAINER_FORCEINLINE value_compare &priv_value_comp()
   { return static_cast<value_compare &>(this->m_data); }

   BOOST_CONTAINER_FORCEINLINE const key_compare &priv_key_comp() const
   { return this->priv_value_comp().get_comp(); }

   BOOST_CONTAINER_FORCEINLINE key_compare &priv_key_comp()
   { return this->priv_value_comp().get_comp(); }

   struct insert_commit_data
   {
      const_iterator position;
   };

   public:
   // accessors:
   BOOST_CONTAINER_FORCEINLINE Compare key_comp() const
   { return this->m_data.get_comp(); }

   BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
   { return this->m_data; }

   BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const
   { return this->m_data.m_seq.get_allocator(); }

   BOOST_CONTAINER_FORCEINLINE 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_FORCEINLINE 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_FORCEINLINE iterator begin()
   { return this->m_data.m_seq.begin(); }

   BOOST_CONTAINER_FORCEINLINE const_iterator begin() const
   { return this->cbegin(); }

   BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const
   { return this->m_data.m_seq.begin(); }

   BOOST_CONTAINER_FORCEINLINE iterator end()
   { return this->m_data.m_seq.end(); }

   BOOST_CONTAINER_FORCEINLINE const_iterator end() const
   { return this->cend(); }

   BOOST_CONTAINER_FORCEINLINE const_iterator cend() const
   { return this->m_data.m_seq.end(); }

   BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin()
   { return reverse_iterator(this->end()); }

   BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const
   {  return this->crbegin();  }

   BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const
   {  return const_reverse_iterator(this->cend());  }

   BOOST_CONTAINER_FORCEINLINE reverse_iterator rend()
   { return reverse_iterator(this->begin()); }

   BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const
   { return this->crend(); }

   BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const
   { return const_reverse_iterator(this->cbegin()); }

   BOOST_CONTAINER_FORCEINLINE bool empty() const
   { return this->m_data.m_seq.empty(); }

   BOOST_CONTAINER_FORCEINLINE size_type size() const
   { return this->m_data.m_seq.size(); }

   BOOST_CONTAINER_FORCEINLINE size_type max_size() const
   { return this->m_data.m_seq.max_size(); }

   BOOST_CONTAINER_FORCEINLINE 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));
   }

include/boost/container/detail/flat_tree.hpp  view on Meta::CPAN

         ret.first  = this->nth(data.position - this->cbegin());\
      }\
      else{\
         typedef typename emplace_functor_type<try_emplace_t, KeyType BOOST_MOVE_I##N BOOST_MOVE_TARG##N>::type func_t;\
         typedef emplace_iterator<value_type, func_t, difference_type> it_t;\
         func_t func(try_emplace_t(), ::boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
         ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());\
      }\
      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(data.position - this->cbegin());
         ret.first->second = boost::forward<M>(obj);
      }
      else{
         typedef typename emplace_functor_type<KeyType, M>::type func_t;
         typedef emplace_iterator<value_type, func_t, difference_type> it_t;
         func_t func(boost::forward<KeyType>(key), boost::forward<M>(obj));
         ret.first = this->m_data.m_seq.insert(data.position, it_t(func), it_t());
      }
      return ret;
   }

   BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator position)
   {  return this->m_data.m_seq.erase(position);  }

   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;
   }

   BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last)
   {  return this->m_data.m_seq.erase(first, last);  }

   BOOST_CONTAINER_FORCEINLINE 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().
   BOOST_CONTAINER_FORCEINLINE void shrink_to_fit()
   {  this->m_data.m_seq.shrink_to_fit();  }

   BOOST_CONTAINER_FORCEINLINE 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_FORCEINLINE 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_FORCEINLINE 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_FORCEINLINE 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:
   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;
   }

   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>
   typename dtl::enable_if_transparent<key_compare, K, iterator>::type
      find(const K& k)
   {
      iterator i = this->lower_bound(k);