Listing 1: Template class deque

   // TEMPLATE CLASS deque
#define DEQUEMAPSIZ 2
#define DEQUESIZ (4096 < sizeof (Ty) ? 1 : 4096 / sizeof (Ty))
  // TEMPLATE CLASS deque
///template<class Ty, class A = allocator<Ty> >
template<class Ty, class A> ///
 class deque {
public:
 typedef deque<Ty, A> Myt;
 typedef A allocator_type;
 typedef typename A::size_type size_type;
 typedef typename A::difference_type difference_type;
 typedef typename A::pointer Tptr;
 typedef typename A::const_pointer Ctptr;
/// typedef A::rebind<Tptr>::other::pointer Mapptr;
 typedef Tptr *Mapptr; ///
 typedef typename A::reference reference;
 typedef typename A::const_reference const_reference;
 typedef typename A::value_type value_type;
  // CLASS iterator
 class const_iterator;
 class iterator : public Ranit<Ty, difference_type,
  Tptr, reference> {
 public:
  friend class deque<Ty, A>;
  friend class const_iterator;
  iterator()
   : First(0), Last(0), Next(0), Map(0) {}
  iterator(Tptr P, Mapptr M)
   : First(*M), Last(*M + DEQUESIZ),
    Next(P), Map(M) {}
  reference operator*() const
   {return (*Next); }
///  Tptr operator->() const
///   {return (&**this); }
  iterator& operator++()
   {if (++Next == Last)
    {First = *++Map;
    Last = First + DEQUESIZ;
    Next = First; }
   return (*this); }
  iterator operator++(int)
   {iterator Tmp = *this;
   ++*this;
   return (Tmp); }
  iterator& operator--()
   {if (Next == First)
    {First = *--Map;
    Last = First + DEQUESIZ;
    Next = Last; }
   --Next;
   return (*this); }
  iterator operator--(int)
   {iterator Tmp = *this;
   --*this;
   return (Tmp); }
  iterator& operator+=(difference_type N)
   {Add(N);
   return (*this); }
  iterator& operator-=(difference_type N)
   {return (*this += -N); }
  iterator operator+(difference_type N) const
   {iterator Tmp = *this;
   return (Tmp += N); }
  iterator operator-(difference_type N) const
   {iterator Tmp = *this;
   return (Tmp -= N); }
  difference_type operator-(const iterator& X) const
   {return (Map == X.Map ? Next - X.Next
    : DEQUESIZ * (Map - X.Map - 1)
    + (Next - First) + (X.Last - X.Next)); }
  reference operator[](difference_type N) const
   {return (*(*this + N)); }
  bool operator==(const iterator& X) const
   {return (Next == X.Next); }
  bool operator!=(const iterator& X) const
   {return (!(*this == X)); }
  bool operator<(const iterator& X) const
   {return (Map < X.Map
    || Map == X.Map && Next < X.Next); }
  bool operator<=(const iterator& X) const
   {return (!(X < *this)); }
  bool operator>(const iterator& X) const
   {return (X < *this); }
  bool operator>=(const iterator& X) const
   {return (!(*this < X)); }
 protected:
  void Add(difference_type N)
   {difference_type Off = N + Next - First;
   difference_type Moff = (0 <= Off)
    ? Off / DEQUESIZ
    : -((DEQUESIZ - 1 - Off) / DEQUESIZ);
   if (Moff == 0)
 Next += N;
   else
    {Map += Moff;
    First = *Map;
    Last = First + DEQUESIZ;
    Next = First + (Off - Moff * DEQUESIZ); }}
  Tptr First, Last, Next;
  Mapptr Map;
  };
  // CLASS const_iterator
 class const_iterator : public Ranit<Ty, difference_type,
  Ctptr, const_reference> {
 public:
  friend class deque<Ty, A>;
  const_iterator()
   : First(0), Last(0), Next(0), Map(0) {}
  const_iterator(Tptr P, Mapptr M)
   : First(*M), Last(*M + DEQUESIZ),
    Next(P), Map(M) {}
  const_iterator(const iterator& X)
   : First(X.First), Last(X.Last),
    Next(X.Next), Map(X.Map) {}
  const_reference operator*() const
   {return (*Next); }
///  Ctptr operator->() const
///   {return (&**this); }
  const_iterator& operator++()
   {if (++Next == Last)
    {First = *++Map;
    Last = First + DEQUESIZ;
    Next = First; }
   return (*this); }
  const_iterator operator++(int)
   {const_iterator Tmp = *this;
   ++*this;
   return (Tmp); }
  const_iterator& operator--()
   {if (Next == First)
    {First = *--Map;
    Last = First + DEQUESIZ;
    Next = Last; }
   --Next;
   return (*this); }
  const_iterator operator--(int)
   {const_iterator Tmp = *this;
   --*this;
   return (Tmp); }
  const_iterator& operator+=(difference_type N)
   {Add(N);
   return (*this); }
  const_iterator& operator-=(difference_type N)
   {return (*this += -N); }
  const_iterator operator+(difference_type N) const
   {const_iterator Tmp = *this;
   return (Tmp += N); }
  const_iterator operator-(difference_type N) const
   {const_iterator Tmp = *this;
   return (Tmp -= N); }
  difference_type operator-(const const_iterator& X) const
   {return (Map == X.Map ? Next - X.Next
    : DEQUESIZ * (Map - X.Map - 1)
    + (Next - First) + (X.Last - X.Next)); }
  const_reference operator[](difference_type N) const
   {return (*(*this + N)); }
  bool operator==(const const_iterator& X) const
   {return (Next == X.Next); }
  bool operator!=(const const_iterator& X) const
   {return (!(*this == X)); }
  bool operator<(const const_iterator& X) const
   {return (Map < X.Map
    || Map == X.Map && Next < X.Next); }
  bool operator<=(const const_iterator& X) const
   {return (!(X < *this)); }
  bool operator>(const const_iterator& X) const
   {return (X < *this); }
  bool operator>=(const const_iterator& X) const
   {return (!(*this < X)); }
 protected:
  void Add(difference_type N)
   {difference_type Off = N + Next - First;
   difference_type Moff = (0 <= Off)
    ? Off / DEQUESIZ
    : -((DEQUESIZ - 1 - Off) / DEQUESIZ);
   if (Moff == 0)
    Next += N;
   else
    {Map += Moff;
    First = *Map;
    Last = First + DEQUESIZ;
    Next = First + (Off - Moff * DEQUESIZ); }}
  Tptr First, Last, Next;
  Mapptr Map;
  };
 typedef Revranit<const_iterator,
  value_type, difference_type, Ctptr, const_reference>
  const_reverse_iterator;
 typedef Revranit<iterator,
  value_type, difference_type, Tptr, reference>
  reverse_iterator;
 explicit deque()
  : allocator(),
///  Myal(),
   First(), Last(), Map(0), Mapsize(0), Size(0)
  {}
 explicit deque(const A& Al)
  : allocator(Al),
///  Myal(Al),
   First(), Last(), Map(0), Mapsize(0), Size(0)
  {}
 explicit deque(size_type N)
  : allocator(),
///  Myal(),
   First(), Last(), Map(0), Mapsize(0), Size(0)
  {insert(begin(), N, Ty()); }
 explicit deque(size_type N, const Ty& V)
  : allocator(),
///  Myal(),
   First(), Last(), Map(0), Mapsize(0), Size(0)
  {insert(begin(), N, V); }
 explicit deque(size_type N, const Ty& V, const A& Al)
  : allocator(Al),
///  Myal(Al),
   First(), Last(), Map(0), Mapsize(0), Size(0)
  {insert(begin(), N, V); }
 deque(const Myt& X)
  : allocator(X.allocator),
///  Myal(X.allocator),
   First(), Last(), Map(0), Mapsize(0), Size(0)
  {copy(X.begin(), X.end(), back_inserter(*this)); }
/// template<class It>
 typedef const_iterator It; ///
  deque(It F, It L)
  : allocator(),
///  Myal(),
   First(), Last(), Map(0), Mapsize(0), Size(0)
  {copy(F, L, back_inserter(*this)); }
/// template<class It>
  deque(It F, It L, const A& Al)
  : allocator(Al),
///  Myal(Al),
   First(), Last(), Map(0), Mapsize(0), Size(0)
  {copy(F, L, back_inserter(*this)); }
 ~deque()
  {while (!empty())
   pop_front(); }
 Myt& operator=(const Myt& X)
  {if (this != &X)
   {iterator S;
   if (X.size() <= size())
    {S = copy(X.begin(), X.end(), begin());
    erase(S, end()); }
   else
    {const_iterator Sx = X.begin() + size();
    S = copy(X.begin(), Sx, begin());
    copy(Sx, X.end(), inserter(*this, S)); }}
  return (*this); }
 iterator begin()
  {return (First); }
 const_iterator begin() const
  {return ((const_iterator)First); }
 iterator end()
  {return (Last); }
 const_iterator end() const
  {return ((const_iterator)Last); }
 reverse_iterator rbegin()
  {return (reverse_iterator(end())); }
 const_reverse_iterator rbegin() const
  {return (const_reverse_iterator(end())); }
 reverse_iterator rend()
  {return (reverse_iterator(begin())); }
 const_reverse_iterator rend() const
  {return (const_reverse_iterator(begin())); }
 void resize(size_type N)
  {resize(N, Ty()); }
 void resize(size_type N, Ty X)
  {if (size() < N)
   insert(end(), N - size(), X);
  else if (N < size())
   erase(begin() + N, end()); }
 size_type size() const
  {return (Size); }
 size_type max_size() const
  {return (allocator.max_size()); }
 bool empty() const
  {return (size() == 0); }
 A get_allocator() const
  {return (allocator); }
 const_reference at(size_type P) const
  {if (size() <= P)
   Xran();
  return (*(begin() + P)); }
 reference at(size_type P)
  {if (size() <= P)
   Xran();
  return (*(begin() + P)); }
 const_reference operator[](size_type P) const
  {return (*(begin() + P)); }
 reference operator[](size_type P)
  {return (*(begin() + P)); }
 reference front()
  {return (*begin()); }
 const_reference front() const
  {return (*begin()); }
 reference back()
  {return (*(end() - 1)); }
 const_reference back() const
  {return (*(end() - 1)); }
 void push_front(const Ty& X)
  {if (empty() || First.Next == First.First)
   Buyfront();
  allocator.construct(--First.Next, X);
  ++Size; }
 void pop_front()
  {allocator.destroy(First.Next++);
  --Size;
  if (empty() || First.Next == First.Last)
   Freefront(); }
 void push_back(const Ty& X)
  {if (empty() || Last.Next == Last.Last)
   Buyback();
  allocator.construct(Last.Next++, X);
  ++Size; }
 void pop_back()
  {allocator.destroy(--Last.Next);
  --Size;
  if (empty() || Last.Next == Last.First)
   Freeback(); }
/// template<class It>
 void assign(It F, It L)
  {erase(begin(), end());
  insert(begin(), F, L); }
/// template<class Pd, class U>
///  void assign(Pd N)
 typedef Ty U; ///
 void assign(size_type N) ///
  {erase(begin(), end());
  insert(begin(), N, U()); }
/// template<class Pd, class U>
///  void assign(Pd N, const U& X)
 void assign(size_type N, const Ty& X) ///
  {erase(begin(), end());
  insert(begin(), N, X); }
 iterator insert(iterator P)
  {return (insert(P, Ty())); }
 iterator insert(iterator P, const Ty& X)
  {if (P == begin())
   {push_front(X);
   return (begin()); }
  else if (P == end())
   {push_back(X);
   return (end() - 1); }
  else
   {iterator S;
   size_type Off = P - begin();
   if (Off < size() / 2)
    {push_front(front());
    S = begin() + Off;
    copy(begin() + 2, S + 1, begin() + 1); }
   else
    {push_back(back());
    S = begin() + Off;
    copy_backward(S, end() - 2, end() - 1); }
   *S = X;
   return (S); }}
 void insert(iterator P, size_type M, const Ty& X)
  {iterator S;
  size_type I;
  size_type Off = P - begin();
  size_type Rem = Size - Off;
  if (Off < Rem)
   if (Off < M)
    {for (I = M - Off; 0 < I; --I)
     push_front(X);
    for (I = Off; 0 < I; --I)
     push_front(begin()[M - 1]);
    S = begin() + M;
    fill(S, S + Off, X); }
   else
    {for (I = M; 0 < I; --I)
     push_front(begin()[M - 1]);
    S = begin() + M;
    copy(S + M, S + Off, S);
    fill(begin() + Off, S + Off, X); }
  else
   if (Rem < M)
    {for (I = M - Rem; 0 < I; --I)
     push_back(X);
    for (I = 0; I < Rem; ++I)
     push_back(begin()[Off + I]);
    S = begin() + Off;
    fill(S, S + Rem, X); }
   else
    {for (I = 0; I < M; ++I)
     push_back(begin()[Off + Rem - M + I]);
    S = begin() + Off;
    copy_backward(S, S + Rem - M, S + Rem);
    fill(S, S + M, X); }}
/// template<class It>
///  void insert(iterator P, It F, It L)
///  {insert(P, F, L, Iter_cat(F)); }
/// template<class It>
///  void insert(iterator P, It F, It L,
///   forward_iterator_tag)
///  {size_type Off = P - begin();
///  for (; F != L; ++F, ++Off)
///   insert(begin() + Off, *F); }
/// template<class It>
///  void insert(iterator P, It F, It L,
///   bidirectional_iterator_tag)
 void insert(iterator P, It F, It L) ///
  {size_type M = 0;
  Distance(F, L, M);
  size_type I;
  size_type Off = P - begin();
  size_type Rem = Size - Off;
  if (Off < Rem)
   if (Off < M)
    {It Qx = F;
    advance(Qx, M - Off);
    for (It Q = Qx; F != Q; )
     push_front(*--Q);
    for (I = Off; 0 < I; --I)
     push_front(begin()[M - 1]);
    copy(Qx, L, begin() + M); }
   else
    {for (I = M; 0 < I; --I)
     push_front(begin()[M - 1]);
    iterator S = begin() + M;
    copy(S + M, S + Off, S);
    copy(F, L, begin() + Off); }
  else
   if (Rem < M)
    {It Qx = F;
    advance(Qx, Rem);
    for (It Q = Qx; Q != L; ++Q)
     push_back(*Q);
    for (I = 0; I < Rem; ++I)
     push_back(begin()[Off + I]);
    copy(F, Qx, begin() + Off); }
   else
    {for (I = 0; I < M; ++I)
     push_back(begin()[Off + Rem - M + I]);
    iterator S = begin() + Off;
    copy_backward(S, S + Rem - M, S + Rem);
    copy(F, L, S); }}
 iterator erase(iterator P)
  {return (erase(P, P + 1)); }
 iterator erase(iterator F, iterator L)
  {size_type N = L - F;
  size_type M = F - begin();
  if (M < end() - L)
   {copy_backward(begin(), F, L);
   for (; 0 < N; --N)
    pop_front(); }
  else
   {copy(L, end(), F);
   for (; 0 < N; --N)
    pop_back(); }
  return (M == 0 ? begin() : begin() + M); }
 void clear()
  {erase(begin(), end()); }
 void swap(Myt& X)
  {if (allocator == X.allocator)
   {STD swap(First, X.First);
   STD swap(Last, X.Last);
   STD swap(Map, X.Map);
   STD swap(Mapsize, X.Mapsize);
   STD swap(Size, X.Size); }
  else
   {Myt Ts = *this; *this = X, X = Ts; }}
 friend void swap(Myt& X, Myt& Y) ///
  {X.swap(Y); } ///
protected:
 void Buyback()
  {Tptr P = allocator.allocate(DEQUESIZ, (void *)0);
  if (empty())
   {Mapsize = DEQUEMAPSIZ;
   size_type N = Mapsize / 2;
   Getmap();
   Setptr(Map + N, P);
   First = iterator(P + DEQUESIZ / 2, Map + N);
   Last = First; }
  else if (Last.Map < Map + (Mapsize - 1))
   {Setptr(++Last.Map, P);
   Last = iterator(P, Last.Map); }
  else
   {difference_type I = Last.Map - First.Map + 1;
   Mapptr M = Growmap(2 * I);
   Setptr(M + I, P);
   First = iterator(First.Next, M);
   Last = iterator(P, M + I); }}
 void Buyfront()
  {Tptr P = allocator.allocate(DEQUESIZ, (void *)0);
  if (empty())
   {Mapsize = DEQUEMAPSIZ;
   size_type N = Mapsize / 2;
   Getmap();
   Setptr(Map + N, P);
   First = iterator(P + (DEQUESIZ / 2 + 1),
    Map + N);
   Last = First; }
  else if (Map < First.Map)
   {Setptr(--First.Map, P);
   First = iterator(P + DEQUESIZ, First.Map); }
  else
   {difference_type I = Last.Map - First.Map + 1;
   Mapptr M = Growmap(2 * I);
   Setptr(--M, P);
   First = iterator(P + DEQUESIZ, M);
   Last = iterator(Last.Next, M + I); }}
 void Freeback()
  {Freeptr(Last.Map--);
  if (empty())
   {First = iterator();
   Last = First;
   Freemap(); }
  else
   Last = iterator(*Last.Map + DEQUESIZ,
    Last.Map); }
 void Freefront()
  {Freeptr(First.Map++);
  if (empty())
   {First = iterator();
   Last = First;
   Freemap(); }
  else
   First = iterator(*First.Map, First.Map); }
 void Xran() const
  {throw out_of_range("invalid deque<T> subscript"); }
/// void Freemap()
///  {Myal.deallocate(Map, Mapsize); }
/// void Freeptr(Mapptr M)
///  {allocator.deallocate(*M, DEQUESIZ);
///  Myal.destroy(M); }
/// void Getmap()
///  {Map = Myal.allocate(Mapsize, (void *)0); }
/// Mapptr Growmap(size_type Newsize)
///  {Mapptr M = Myal.allocate(Newsize, (void *)0);
///  uninitialized_copy(First.Map, Last.Map + 1,
///   M + Newsize / 4);
///  for (Mapptr Mt = First.Map;
///   Mt < Last.Map + 1; ++Mt)
///   Myal.destroy(Mt);
///  Myal.deallocate(Map, Mapsize);
///  Map = M;
///  Mapsize = Newsize;
///  return (M + Newsize / 4); }
/// void Setptr(Mapptr M, Tptr P)
///  {Myal.construct(M, P); }
/// A::rebind<Tptr>::other Myal;
 void Freemap() ///
  {allocator.deallocate(Map, Mapsize); } ///
 void Freeptr(Mapptr M) ///
  {allocator.deallocate(*M, DEQUESIZ); } ///
 void Getmap() ///
  {Map = (Mapptr)allocator.Charalloc( ///
   Mapsize * sizeof (Tptr)); } ///
 Mapptr Growmap(size_type Newsize) ///
  {Mapptr M = (Mapptr)allocator.Charalloc( ///
   Newsize * sizeof (Tptr)); ///
  copy(First.Map, Last.Map + 1, ///
   M + Newsize / 4); ///
  allocator.deallocate(Map, Mapsize); ///
  Map = M; ///
  Mapsize = Newsize; ///
  return (M + Newsize / 4); } ///
 void Setptr(Mapptr M, Tptr P) ///
  {*M = P; } ///
 A allocator;
 iterator First, Last;
 Mapptr Map;
 size_type Mapsize, Size;
 };
// End of File