public:
  typedef _Tp value_type;
  typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type  allocator_type;
  typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type _Map_alloc_type;

  typedef _Buf_size_traits <_Tp, __bufsiz > __buf_traits;

  typedef _Deque_iterator<_Tp, _Nonconst_traits<_Tp>,__buf_traits> iterator;
  typedef _Deque_iterator<_Tp, _Const_traits<_Tp>, __buf_traits>   const_iterator;

  _Deque_base(const allocator_type& __a, size_t __num_elements)
    : _M_start(), _M_finish(), _M_map(__STL_CONVERT_ALLOCATOR(__a, _Tp*), (_Tp**)0),
      _M_map_size(__a, (size_t)0) {
	_M_initialize_map(__num_elements);
  }
  _Deque_base(const allocator_type& __a)
    : _M_start(), _M_finish(), _M_map(__STL_CONVERT_ALLOCATOR(__a, _Tp*), (_Tp**)0), 
      _M_map_size(__a, (size_t)0) {
  }
  ~_Deque_base();    
  allocator_type get_allocator() const { return _M_map_size; }

protected:
  void _M_initialize_map(size_t);
  void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
  void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
  enum { _S_initial_map_size = 8 };

protected:
  iterator _M_start;
  iterator _M_finish;
  _STL_alloc_proxy<value_type**, value_type*, _Map_alloc_type>  _M_map;
  _STL_alloc_proxy<size_t, value_type,  allocator_type>   _M_map_size;  
};


// See __deque_buf_size().  The only reason that the default value is 0
//  is as a workaround for bugs in the way that some compilers handle
//  constant expressions.
# if defined ( __STL_NO_DEFAULT_NON_TYPE_PARAM )
template <class _Tp, class _Alloc, size_t __bufsiz> 
# else
template <class _Tp, __STL_DEFAULT_ALLOCATOR_SELECT(_Tp),
  __DFL_NON_TYPE_PARAM(size_t, __bufsiz, 0)>
# endif 
class deque : protected _Deque_base<_Tp, _Alloc, __bufsiz> {
  typedef _Deque_base<_Tp, _Alloc, __bufsiz> _Base;
  typedef deque<_Tp, _Alloc, __bufsiz> _Self;
public:                         // Basic types
  typedef _Tp value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

  typedef typename _Base::allocator_type allocator_type;

public:                         // Iterators
  typedef typename _Base::iterator       iterator;
  typedef typename _Base::const_iterator const_iterator;

#if defined ( __STL_CLASS_PARTIAL_SPECIALIZATION ) && \
! defined (__STL_PARTIAL_SPECIALIZATION_BUG)
  typedef __STLPORT_STD::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef __STLPORT_STD::reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
# if defined (__STL_MSVC50_COMPATIBILITY)
    typedef __STLPORT_STD::reverse_iterator<const_iterator, value_type, const_reference, 
    const value_type*, difference_type>  const_reverse_iterator;
    typedef __STLPORT_STD::reverse_iterator<iterator, value_type, reference, pointer, 
        difference_type> reverse_iterator; 
# else
  typedef __STLPORT_STD::reverse_iterator<const_iterator, value_type, const_reference, 
                           difference_type>  
          const_reverse_iterator;
  typedef __STLPORT_STD::reverse_iterator<iterator, value_type, reference, difference_type>
          reverse_iterator; 
# endif /* __STL_MSVC50_COMPATIBILITY */
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */

protected:                      // Internal typedefs
  typedef pointer* _Map_pointer;

  typedef _Buf_size_traits < _Tp, __bufsiz > __buf_traits;

protected:
#if defined( __STL_HAS_NAMESPACES )
  __STL_USING_BASE_MEMBER _Deque_base<_Tp, _Alloc, __bufsiz>::_M_initialize_map;
  __STL_USING_BASE_MEMBER _Deque_base<_Tp, _Alloc, __bufsiz>::_M_create_nodes;
# ifndef __STL_DEBUG
  __STL_USING_BASE_MEMBER _Deque_base<_Tp, _Alloc, __bufsiz>::_M_destroy_nodes;
# endif
  __STL_USING_BASE_MEMBER _Deque_base<_Tp, _Alloc, __bufsiz>::_M_map;
  __STL_USING_BASE_MEMBER _Deque_base<_Tp, _Alloc, __bufsiz>::_M_map_size;
  __STL_USING_BASE_MEMBER _Deque_base<_Tp, _Alloc, __bufsiz>::_M_start;
  __STL_USING_BASE_MEMBER _Deque_base<_Tp, _Alloc, __bufsiz>::_M_finish;
#endif /* __STL_HAS_NAMESPACES */
# if defined (__STL_DEBUG)
protected:
  __owned_list _M_iter_list;
  void _Init_bounds() {
    _M_orphan_start();
    _M_orphan_finish();
  }
  void _Invalidate_iterator(const iterator& __it) { 
    __invalidate_iterator(&_M_iter_list,__it);
  }
  void _Invalidate_all() {
      _M_iter_list._Invalidate_all();
  }
  void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) {
    _Base::_M_destroy_nodes(__nstart, __nfinish);
    // to simplify unwind handling
      _M_finish._M_unsafe= false;
      _M_start._M_unsafe = false;
  }
  void _M_orphan_start() {
    _M_iter_list._Orphan(_M_start);
    _M_start._M_unsafe = false;
  }
  void _M_orphan_finish() {
    _M_iter_list._Orphan(_M_finish);
    _M_finish._M_unsafe= false;
  }
# endif
public:                         // Basic accessors
  iterator begin() { return _M_start; }
  iterator end() { return _M_finish; }
  const_iterator begin() const { return *(const const_iterator*)&_M_start; }
  const_iterator end() const { return *(const const_iterator*)&_M_finish; }

  reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
  reverse_iterator rend() { return reverse_iterator(_M_start); }
  const_reverse_iterator rbegin() const 
    { return const_reverse_iterator(_M_finish); }
  const_reverse_iterator rend() const 
    { return const_reverse_iterator(_M_start); }

  reference operator[](size_type __n)
    { return _M_start[difference_type(__n)]; }
  const_reference operator[](size_type __n) const 
    { return _M_start[difference_type(__n)]; }

#ifdef __STL_THROW_RANGE_ERRORS
  void _M_range_check(size_type __n) const {
    if (__n >= this->size())
      __stl_throw_range_error("deque");
  }

  reference at(size_type __n)
    { _M_range_check(__n); return (*this)[__n]; }
  const_reference at(size_type __n) const
    { _M_range_check(__n); return (*this)[__n]; }
#endif /* __STL_THROW_RANGE_ERRORS */

  reference front() { return *_M_start; }
  reference back() {
    iterator __tmp = _M_finish;
    --__tmp;
    return *__tmp;
  }
  const_reference front() const { return *_M_start; }
  const_reference back() const {
    const_iterator __tmp = _M_finish;
    --__tmp;
    return *__tmp;
  }

  size_type size() const { return _M_finish - _M_start; }
  size_type max_size() const { return size_type(-1); }
  bool empty() const { return _M_finish == _M_start; }

public:                         // Constructor, destructor.
  explicit deque(const allocator_type& __a = __STL_ALLOC_INSTANCE(allocator_type)) 
    : _Deque_base<_Tp, _Alloc, __bufsiz>(__a, 0) {
    __stl_debug_do(_M_iter_list._Safe_init(&_M_start));
    __stl_debug_do(_Init_bounds());
}
  deque(const _Self& __x) : 
    _Deque_base<_Tp, _Alloc, __bufsiz>(__x.get_allocator(), __x.size()) 
    { 
      __stl_debug_do(_M_iter_list._Safe_init(&_M_start));
      __stl_debug_do(_Init_bounds());
      uninitialized_copy(__x.begin(), __x.end(), _M_start); 
    }

  deque(size_type __n, const value_type& __value,
        const allocator_type& __a = __STL_ALLOC_INSTANCE(allocator_type)) : 
    _Deque_base<_Tp, _Alloc, __bufsiz>(__a, __n)
    { _M_fill_initialize(__value); }
  // int,long variants may be needed 
  explicit deque(size_type __n) : _Deque_base<_Tp, _Alloc, __bufsiz>(allocator_type(), __n)
    { _M_fill_initialize(value_type()); }

#ifdef __STL_MEMBER_TEMPLATES

  // Check whether it's an integral type.  If so, it's not an iterator.
  template <class _InputIterator>
  deque(_InputIterator __first, _InputIterator __last,
        const allocator_type& __a = __STL_ALLOC_INSTANCE(allocator_type)) : 
    _Deque_base<_Tp, _Alloc, __bufsiz>(__a) {
    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    _M_initialize_dispatch(__first, __last, _Integral());
  }

  template <class _Integer>
  void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
    _M_initialize_map(__n);
    _M_fill_initialize(__x);
  }

  template <class _InputIter>
  void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
                              __false_type) {
    _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
  }

#else /* __STL_MEMBER_TEMPLATES */

  deque(const value_type* __first, const value_type* __last,
        const allocator_type& __a = __STL_ALLOC_INSTANCE(allocator_type)) 
    : _Deque_base<_Tp, _Alloc, __bufsiz>(__a, __last - __first)
    { 
      __stl_debug_do(_M_iter_list._Safe_init(&_M_start));
      __stl_debug_do(_Init_bounds());
      uninitialized_copy(__first, __last, _M_start); 
    }
  deque(const_iterator __first, const_iterator __last,
        const allocator_type& __a = __STL_ALLOC_INSTANCE(allocator_type)) 
    : _Deque_base<_Tp, _Alloc, __bufsiz>(__a, __last - __first)
    { 
      __stl_debug_do(_M_iter_list._Safe_init(&_M_start));
      __stl_debug_do(_Init_bounds());
      uninitialized_copy(__first, __last, _M_start); 
    }

#endif /* __STL_MEMBER_TEMPLATES */

  ~deque() { 
    destroy(_M_start, _M_finish); 
  }

  _Self& operator= (const _Self& __x);

  void swap(_Self& __x) {
    __STLPORT_STD::swap(_M_start, __x._M_start);
    __STLPORT_STD::swap(_M_finish, __x._M_finish);
    __STLPORT_STD::swap(_M_map, __x._M_map);
    __STLPORT_STD::swap(_M_map_size, __x._M_map_size);
    __stl_debug_do(_M_iter_list._Swap_owners(__x._M_iter_list));
  }

public: 
  // assign(), a generalized assignment member function.  Two
  // versions: one that takes a count, and one that takes a range.
  // The range version is a member template, so we dispatch on whether
  // or not the type is an integer.

  void _M_fill_assign(size_type __n, const _Tp& __val) {
    if (__n > size()) {
      fill(begin(), end(), __val);
      insert(end(), __n - size(), __val);
    }
    else {
      erase(begin() + __n, end());
      fill(begin(), end(), __val);
    }
  }

  void assign(size_type __n, const _Tp& __val) {
    _M_fill_assign(__n, __val);
  }

#ifdef __STL_MEMBER_TEMPLATES

  template <class _InputIterator>
  void assign(_InputIterator __first, _InputIterator __last) {
    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    _M_assign_dispatch(__first, __last, _Integral());
  }

private:                        // helper functions for assign() 

  template <class _Integer>
  void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
    { _M_fill_assign((size_type) __n, (_Tp) __val); }

  template <class _InputIterator>
  void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
                          __false_type) {
    _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first));
  }

  template <class _InputIter>
  void _M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) {
    iterator __cur = begin();
    for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
      *__cur = *__first;
    if (__first == __last)
      erase(__cur, end());
    else
      insert(end(), __first, __last);
  }

  template <class _ForwardIterator>
  void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
                     forward_iterator_tag) {
    size_type __len = 0;
    distance(__first, __last, __len);
    if (__len > size()) {
      _ForwardIterator __mid = __first;
      advance(__mid, size());
      copy(__first, __mid, begin());
      insert(end(), __mid, __last);
    }
    else
      erase(copy(__first, __last, begin()), end());
  }

#endif /* __STL_MEMBER_TEMPLATES */

public:                         // push_* and pop_*
  
  void push_back(const value_type& __t) {
    if (_M_finish._M_cur != _M_finish._M_last - 1) {
      construct(_M_finish._M_cur, __t);
      ++_M_finish._M_cur;
    }
    else
      _M_push_back_aux(__t);
    __stl_debug_do(_Invalidate_all());
  }

  void push_back() {
    if (_M_finish._M_cur != _M_finish._M_last - 1) {
      construct(_M_finish._M_cur);
      ++_M_finish._M_cur;
    }
    else
      _M_push_back_aux();
    __stl_debug_do(_Invalidate_all());
  }

  void push_front(const value_type& __t) {
    if (_M_start._M_cur != _M_start._M_first) {
      construct(_M_start._M_cur - 1, __t);
      --_M_start._M_cur;
    }
    else
      _M_push_front_aux(__t);
    __stl_debug_do(_Invalidate_all());
  }

  void push_front() {
    if (_M_start._M_cur != _M_start._M_first) {
      construct(_M_start._M_cur - 1);
      --_M_start._M_cur;
    }
    else
      _M_push_front_aux();
    __stl_debug_do(_Invalidate_all());
  }


  void pop_back() {
    __stl_debug_do(_Invalidate_iterator(_M_finish));
    if (_M_finish._M_cur != _M_finish._M_first) {
      --_M_finish._M_cur;
      destroy(_M_finish._M_cur);
    }
    else
      _M_pop_back_aux();
  }

  void pop_front() {
    __stl_debug_do(_Invalidate_iterator(_M_start));        
    if (_M_start._M_cur != _M_start._M_last - 1) {
      destroy(_M_start._M_cur);
      ++_M_start._M_cur;
    }
    else 
      _M_pop_front_aux();
  }

public:                         // Insert

  iterator insert(iterator __position, const value_type& __x) {
    __stl_debug_check(__check_if_owner(&_M_iter_list, __position));
    if (__position._M_cur == _M_start._M_cur) {
      push_front(__x);
      return _M_start;
    }
    else if (__position._M_cur == _M_finish._M_cur) {
      push_back(__x);
      iterator __tmp = _M_finish;
      --__tmp;
      return __tmp;
    }
    else {
      return _M_insert_aux(__position, __x);
    }
  }

  iterator insert(iterator __position)
    { return insert(__position, value_type()); }

  void insert(iterator __pos, size_type __n, const value_type& __x) {
    _M_fill_insert(__pos, __n, __x);
  }

  void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);

#ifdef __STL_MEMBER_TEMPLATES  

  // Check whether it's an integral type.  If so, it's not an iterator.
  template <class _InputIterator>
  void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    _M_insert_dispatch(__pos, __first, __last, _Integral());
  }

  template <class _Integer>
  void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
                          __true_type) {
    _M_fill_insert(__pos, (size_type) __n, (value_type) __x);
  }

  template <class _InputIterator>
  void _M_insert_dispatch(iterator __pos,