stl_deque.h

mingw32.rar

       *
       *  This function will erase the elements in the range [first,last) and
       *  shorten the %deque accordingly.
       *
       *  The user is cautioned that
       *  this function only erases the elements, and that if the elements
       *  themselves are pointers, the pointed-to memory is not touched in any
       *  way.  Managing the pointer is the user's responsibilty.
       */
      iterator
      erase(iterator __first, iterator __last);

      /**
       *  @brief  Swaps data with another %deque.
       *  @param  x  A %deque of the same element and allocator types.
       *
       *  This exchanges the elements between two deques in constant time.
       *  (Four pointers, so it should be quite fast.)
       *  Note that the global std::swap() function is specialized such that
       *  std::swap(d1,d2) will feed to this function.
       */
      void
      swap(deque& __x)
      {
	std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
	std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
	std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
	std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
      }

      /**
       *  Erases all the elements.  Note that this function only erases the
       *  elements, and that if the elements themselves are pointers, the
       *  pointed-to memory is not touched in any way.  Managing the pointer is
       *  the user's responsibilty.
       */
      void clear();

    protected:
      // Internal constructor functions follow.

      // called by the range constructor to implement [23.1.1]/9
      template<typename _Integer>
        void
        _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
        {
	  _M_initialize_map(__n);
	  _M_fill_initialize(__x);
	}

      // called by the range constructor to implement [23.1.1]/9
      template<typename _InputIterator>
        void
        _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
			       __false_type)
        {
	  typedef typename iterator_traits<_InputIterator>::iterator_category
	    _IterCategory;
	  _M_range_initialize(__first, __last, _IterCategory());
	}

      // called by the second initialize_dispatch above
      //@{
      /**
       *  @if maint
       *  @brief Fills the deque with whatever is in [first,last).
       *  @param  first  An input iterator.
       *  @param  last  An input iterator.
       *  @return   Nothing.
       *
       *  If the iterators are actually forward iterators (or better), then the
       *  memory layout can be done all at once.  Else we move forward using
       *  push_back on each value from the iterator.
       *  @endif
       */
      template<typename _InputIterator>
        void
        _M_range_initialize(_InputIterator __first, _InputIterator __last,
			    input_iterator_tag);

      // called by the second initialize_dispatch above
      template<typename _ForwardIterator>
        void
        _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
			    forward_iterator_tag);
      //@}

      /**
       *  @if maint
       *  @brief Fills the %deque with copies of value.
       *  @param  value  Initial value.
       *  @return   Nothing.
       *  @pre _M_start and _M_finish have already been initialized, but none of
       *       the %deque's elements have yet been constructed.
       *
       *  This function is called only when the user provides an explicit size
       *  (with or without an explicit exemplar value).
       *  @endif
       */
      void
      _M_fill_initialize(const value_type& __value);

      // Internal assign functions follow.  The *_aux functions do the actual
      // assignment work for the range versions.

      // called by the range assign to implement [23.1.1]/9
      template<typename _Integer>
        void
        _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
        {
	  _M_fill_assign(static_cast<size_type>(__n),
			 static_cast<value_type>(__val));
	}

      // called by the range assign to implement [23.1.1]/9
      template<typename _InputIterator>
        void
        _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
			   __false_type)
        {
	  typedef typename iterator_traits<_InputIterator>::iterator_category
	    _IterCategory;
	  _M_assign_aux(__first, __last, _IterCategory());
	}

      // called by the second assign_dispatch above
      template<typename _InputIterator>
        void
        _M_assign_aux(_InputIterator __first, _InputIterator __last,
		      input_iterator_tag);

      // called by the second assign_dispatch above
      template<typename _ForwardIterator>
        void
        _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
		      forward_iterator_tag)
        {
	  const size_type __len = std::distance(__first, __last);
	  if (__len > size())
	    {
	      _ForwardIterator __mid = __first;
	      std::advance(__mid, size());
	      std::copy(__first, __mid, begin());
	      insert(end(), __mid, __last);
	    }
	  else
	    erase(std::copy(__first, __last, begin()), end());
	}

      // Called by assign(n,t), and the range assign when it turns out to be the
      // same thing.
      void
      _M_fill_assign(size_type __n, const value_type& __val)
      {
	if (__n > size())
	  {
	    std::fill(begin(), end(), __val);
	    insert(end(), __n - size(), __val);
	  }
	else
	  {
	    erase(begin() + __n, end());
	    std::fill(begin(), end(), __val);
	  }
      }

      //@{
      /**
       *  @if maint
       *  @brief Helper functions for push_* and pop_*.
       *  @endif
       */
      void _M_push_back_aux(const value_type&);
      void _M_push_front_aux(const value_type&);
      void _M_pop_back_aux();
      void _M_pop_front_aux();
      //@}

      // Internal insert functions follow.  The *_aux functions do the actual
      // insertion work when all shortcuts fail.

      // called by the range insert to implement [23.1.1]/9
      template<typename _Integer>
        void
        _M_insert_dispatch(iterator __pos,
			   _Integer __n, _Integer __x, __true_type)
        {
	  _M_fill_insert(__pos, static_cast<size_type>(__n),
			 static_cast<value_type>(__x));
	}

      // called by the range insert to implement [23.1.1]/9
      template<typename _InputIterator>
        void
        _M_insert_dispatch(iterator __pos,
			   _InputIterator __first, _InputIterator __last,
			   __false_type)
        {
	  typedef typename iterator_traits<_InputIterator>::iterator_category
	    _IterCategory;
          _M_range_insert_aux(__pos, __first, __last, _IterCategory());
	}

      // called by the second insert_dispatch above
      template<typename _InputIterator>
        void
        _M_range_insert_aux(iterator __pos, _InputIterator __first,
			    _InputIterator __last, input_iterator_tag);

      // called by the second insert_dispatch above
      template<typename _ForwardIterator>
        void
        _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
			    _ForwardIterator __last, forward_iterator_tag);

      // Called by insert(p,n,x), and the range insert when it turns out to be
      // the same thing.  Can use fill functions in optimal situations,
      // otherwise passes off to insert_aux(p,n,x).
      void
      _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);

      // called by insert(p,x)
      iterator
      _M_insert_aux(iterator __pos, const value_type& __x);

      // called by insert(p,n,x) via fill_insert
      void
      _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);

      // called by range_insert_aux for forward iterators
      template<typename _ForwardIterator>
        void
        _M_insert_aux(iterator __pos,
		      _ForwardIterator __first, _ForwardIterator __last,
		      size_type __n);

      //@{
      /**
       *  @if maint
       *  @brief Memory-handling helpers for the previous internal insert
       *         functions.
       *  @endif
       */
      iterator
      _M_reserve_elements_at_front(size_type __n)
      {
	const size_type __vacancies = this->_M_impl._M_start._M_cur
	                              - this->_M_impl._M_start._M_first;
	if (__n > __vacancies)
	  _M_new_elements_at_front(__n - __vacancies);
	return this->_M_impl._M_start - difference_type(__n);
      }

      iterator
      _M_reserve_elements_at_back(size_type __n)
      {
	const size_type __vacancies = (this->_M_impl._M_finish._M_last
				       - this->_M_impl._M_finish._M_cur) - 1;
	if (__n > __vacancies)
	  _M_new_elements_at_back(__n - __vacancies);
	return this->_M_impl._M_finish + difference_type(__n);
      }

      void
      _M_new_elements_at_front(size_type __new_elements);

      void
      _M_new_elements_at_back(size_type __new_elements);
      //@}


      //@{
      /**
       *  @if maint
       *  @brief Memory-handling helpers for the major %map.
       *
       *  Makes sure the _M_map has space for new nodes.  Does not actually add
       *  the nodes.  Can invalidate _M_map pointers.  (And consequently, %deque
       *  iterators.)
       *  @endif
       */
      void
      _M_reserve_map_at_back (size_type __nodes_to_add = 1)
      {
	if (__nodes_to_add + 1 > this->_M_impl._M_map_size
	    - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
	  _M_reallocate_map(__nodes_to_add, false);
      }

      void
      _M_reserve_map_at_front (size_type __nodes_to_add = 1)
      {
	if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node - this->_M_impl._M_map))
	  _M_reallocate_map(__nodes_to_add, true);
      }

      void
      _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
      //@}
    };


  /**
   *  @brief  Deque equality comparison.
   *  @param  x  A %deque.
   *  @param  y  A %deque of the same type as @a x.
   *  @return  True iff the size and elements of the deques are equal.
   *
   *  This is an equivalence relation.  It is linear in the size of the
   *  deques.  Deques are considered equivalent if their sizes are equal,
   *  and if corresponding elements compare equal.
  */
  template<typename _Tp, typename _Alloc>
    inline bool
    operator==(const deque<_Tp, _Alloc>& __x,
                         const deque<_Tp, _Alloc>& __y)
    { return __x.size() == __y.size()
             && std::equal(__x.begin(), __x.end(), __y.begin()); }

  /**
   *  @brief  Deque ordering relation.
   *  @param  x  A %deque.
   *  @param  y  A %deque of the same type as @a x.
   *  @return  True iff @a x is lexicographically less than @a y.
   *
   *  This is a total ordering relation.  It is linear in the size of the
   *  deques.  The elements must be comparable with @c <.
   *
   *  See std::lexicographical_compare() for how the determination is made.
  */
  template<typename _Tp, typename _Alloc>
    inline bool
    operator<(const deque<_Tp, _Alloc>& __x,
	      const deque<_Tp, _Alloc>& __y)
    { return lexicographical_compare(__x.begin(), __x.end(),
				     __y.begin(), __y.end()); }

  /// Based on operator==
  template<typename _Tp, typename _Alloc>
    inline bool
    operator!=(const deque<_Tp, _Alloc>& __x,
	       const deque<_Tp, _Alloc>& __y)
    { return !(__x == __y); }

  /// Based on operator<
  template<typename _Tp, typename _Alloc>
    inline bool
    operator>(const deque<_Tp, _Alloc>& __x,
	      const deque<_Tp, _Alloc>& __y)
    { return __y < __x; }

  /// Based on operator<
  template<typename _Tp, typename _Alloc>
    inline bool
    operator<=(const deque<_Tp, _Alloc>& __x,
	       const deque<_Tp, _Alloc>& __y)
    { return !(__y < __x); }

  /// Based on operator<
  template<typename _Tp, typename _Alloc>
    inline bool
    operator>=(const deque<_Tp, _Alloc>& __x,
	       const deque<_Tp, _Alloc>& __y)
    { return !(__x < __y); }

  /// See std::deque::swap().
  template<typename _Tp, typename _Alloc>
    inline void
    swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
    { __x.swap(__y); }
} // namespace std

#endif /* _DEQUE_H */