stl_deque.h

gcc-you can use this code to learn something about gcc, and inquire further into linux,

     *  shorten the %deque by one.
     *
     *  The user is cautioned that
     *  this function only erases the element, and that if the element is itself
     *  a pointer, the pointed-to memory is not touched in any way.  Managing
     *  the pointer is the user's responsibilty.
    */
    iterator
    erase(iterator __position);
  
    /**
     *  @brief  Remove a range of elements.
     *  @param  first  Iterator pointing to the first element to be erased.
     *  @param  last  Iterator pointing to one past the last element to be
     *                erased.
     *  @return  An iterator pointing to the element pointed to by @a last
     *           prior to erasing (or end()).
     *
     *  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(_M_start, __x._M_start);
      std::swap(_M_finish, __x._M_finish);
      std::swap(_M_map, __x._M_map);
      std::swap(_M_map_size, __x._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 _InputIter>
      void
      _M_initialize_dispatch(_InputIter __first, _InputIter __last,
                             __false_type)
      {
        typedef typename iterator_traits<_InputIter>::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 _InputIter>
      void
      _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
      {
        typedef typename iterator_traits<_InputIter>::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)
      {
        size_type __len = distance(__first, __last);
        if (__len > size()) {
          _ForwardIterator __mid = __first;
          advance(__mid, size());
          copy(__first, __mid, begin());
          insert(end(), __mid, __last);
        }
        else
          erase(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())
      {
        fill(begin(), end(), __val);
        insert(end(), __n - size(), __val);
      }
      else
      {
        erase(begin() + __n, end());
        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&);
  #ifdef _GLIBCPP_DEPRECATED
    void _M_push_back_aux();
    void _M_push_front_aux();
  #endif
    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);
  
  #ifdef _GLIBCPP_DEPRECATED
    // unused, see comment in implementation
    iterator _M_insert_aux(iterator __pos);
  #endif
  
    //@{
    /**
     *  @if maint
     *  @brief Memory-handling helpers for the previous internal insert
     *         functions.
     *  @endif
    */
    iterator
    _M_reserve_elements_at_front(size_type __n)
    {
      size_type __vacancies = _M_start._M_cur - _M_start._M_first;
      if (__n > __vacancies) 
        _M_new_elements_at_front(__n - __vacancies);
      return _M_start - difference_type(__n);
    }
  
    iterator
    _M_reserve_elements_at_back(size_type __n)
    {
      size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
      if (__n > __vacancies)
        _M_new_elements_at_back(__n - __vacancies);
      return _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 > _M_map_size - (_M_finish._M_node - _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(_M_start._M_node - _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() &&
           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 lexographically 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::lexographical_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 /* __GLIBCPP_INTERNAL_DEQUE_H */