_deque.h

MONA是为数不多的C++语言编写的一个很小的操作系统

//  allocators.

template <class _Tp, class _Alloc>
class _Deque_base {
public:
  typedef _Tp value_type;
  _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
  typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type  allocator_type;
  typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type _Map_alloc_type;

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

  static size_t  _STLP_CALL buffer_size() { return (size_t)_Deque_iterator_base<_Tp>::__buffer_size; } 

  _Deque_base(const allocator_type& __a, size_t __num_elements)
    : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _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(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0), 
      _M_map_size(__a, (size_t)0) {
  }
  ~_Deque_base();    

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;
  _STLP_alloc_proxy<value_type**, value_type*, _Map_alloc_type>  _M_map;
  _STLP_alloc_proxy<size_t, value_type,  allocator_type>   _M_map_size;  
};


template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc> {
  typedef _Deque_base<_Tp, _Alloc> _Base;
  typedef deque<_Tp, _Alloc> _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 random_access_iterator_tag _Iterator_category;
  _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
  typedef typename _Base::allocator_type allocator_type;

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

  _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;

protected:                      // Internal typedefs
  typedef pointer* _Map_pointer;
  typedef typename  __type_traits<_Tp>::has_trivial_assignment_operator _TrivialAss;
  typedef typename  __type_traits<_Tp>::has_trivial_assignment_operator _IsPODType;

public:                         // Basic accessors
  iterator begin() { return this->_M_start; }
  iterator end() { return this->_M_finish; }
  const_iterator begin() const { return const_iterator(this->_M_start); }
  const_iterator end() const { return const_iterator(this->_M_finish); }

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

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

  void _M_range_check(size_type __n) const {
    if (__n >= this->size())
      __stl_throw_out_of_range("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]; }

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

  size_type size() const { return this->_M_finish - this->_M_start; }
  size_type max_size() const { return size_type(-1); }
  bool empty() const { return this->_M_finish == this->_M_start; }
  allocator_type get_allocator() const { return this->_M_map_size; }

public:                         // Constructor, destructor.
  explicit deque(const allocator_type& __a = allocator_type()) 
    : _Deque_base<_Tp, _Alloc>(__a, 0) {}

  deque(const _Self& __x) : 
    _Deque_base<_Tp, _Alloc>(__x.get_allocator(), __x.size()) { 
      __uninitialized_copy(__x.begin(), __x.end(), this->_M_start, _IsPODType()); 
  }

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

#ifdef _STLP_MEMBER_TEMPLATES

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

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

# ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
  // VC++ needs this
  template <class _InputIterator>
  deque(_InputIterator __first, _InputIterator __last) : 
    _Deque_base<_Tp, _Alloc>(allocator_type()) {
    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    _M_initialize_dispatch(__first, __last, _Integral());
  }
# endif

  // 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 _STLP_ALLOCATOR_TYPE_DFL) : 
    _Deque_base<_Tp, _Alloc>(__a) {
    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    _M_initialize_dispatch(__first, __last, _Integral());
  }

# else
  deque(const value_type* __first, const value_type* __last,
        const allocator_type& __a = allocator_type() ) 
    : _Deque_base<_Tp, _Alloc>(__a, __last - __first) { 
    __uninitialized_copy(__first, __last, this->_M_start, _IsPODType()); 
  }

  deque(const_iterator __first, const_iterator __last,
        const allocator_type& __a = allocator_type() ) 
    : _Deque_base<_Tp, _Alloc>(__a, __last - __first) { 
    __uninitialized_copy(__first, __last, this->_M_start, _IsPODType()); 
  }
#endif /* _STLP_MEMBER_TEMPLATES */

  ~deque() { 
    _STLP_STD::_Destroy(this->_M_start, this->_M_finish); 
  }

  _Self& operator= (const _Self& __x);

  void swap(_Self& __x) {
    _STLP_STD::swap(this->_M_start, __x._M_start);
    _STLP_STD::swap(this->_M_finish, __x._M_finish);
    _STLP_STD::swap(this->_M_map, __x._M_map);
    _STLP_STD::swap(this->_M_map_size, __x._M_map_size);
  }

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()) {
      _STLP_STD::fill(begin(), end(), __val);
      insert(end(), __n - size(), __val);
    }
    else {
      erase(begin() + __n, end());
      _STLP_STD::fill(begin(), end(), __val);
    }
  }

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

#ifdef _STLP_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, const __true_type&)
    { _M_fill_assign((size_type) __n, (_Tp) __val); }

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

  template <class _InputIter>
  void _M_assign_aux(_InputIter __first, _InputIter __last, const 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,
                     const 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());
  }

#endif /* _STLP_MEMBER_TEMPLATES */

public:                         // push_* and pop_*
  
  void push_back(const value_type& __t) {
    if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
      _Construct(this->_M_finish._M_cur, __t);
      ++this->_M_finish._M_cur;
    }
    else
      _M_push_back_aux_v(__t);
  }
  void push_front(const value_type& __t) {
    if (this->_M_start._M_cur != this->_M_start._M_first) {
      _Construct(this->_M_start._M_cur - 1, __t);
      --this->_M_start._M_cur;
    }
    else
      _M_push_front_aux_v(__t);
  }

# ifndef _STLP_NO_ANACHRONISMS
  void push_back() {
    if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
      _Construct(this->_M_finish._M_cur);
      ++this->_M_finish._M_cur;
    }
    else
      _M_push_back_aux();
  }
  void push_front() {
    if (this->_M_start._M_cur != this->_M_start._M_first) {
      _Construct(this->_M_start._M_cur - 1);
      --this->_M_start._M_cur;
    }
    else
      _M_push_front_aux();
  }
# endif

  void pop_back() {
    if (this->_M_finish._M_cur != this->_M_finish._M_first) {
      --this->_M_finish._M_cur;
      _STLP_STD::_Destroy(this->_M_finish._M_cur);
    }
    else
      _M_pop_back_aux();
  }

  void pop_front() {
    if (this->_M_start._M_cur != this->_M_start._M_last - 1) {
      _STLP_STD::_Destroy(this->_M_start._M_cur);
      ++this->_M_start._M_cur;
    }
    else 
      _M_pop_front_aux();
  }

public:                         // Insert

  iterator insert(iterator __position, const value_type& __x) {
    if (__position._M_cur == this->_M_start._M_cur) {
      push_front(__x);