Listing 2: deque::iterator circa 1998

#define _DEQUEMAPSIZ    8    /* at least 5 */
#define _DEQUESIZ (4096 < sizeof (_Ty) ? 1 : 4096 / sizeof (_Ty))

        // TEMPLATE CLASS deque
template<class _Ty, class _A = allocator<_Ty> >
    class deque {
public:
// typedefs omitted

        // CLASS iterator
    class iterator : public _Ranit<_Ty, difference_type> {
    public:
        friend class deque<_Ty, _A>;
        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 && ++_Next == _Last
                && _Map[1] != 0)
                {_First = *++_Map;
                _Last = _First + _DEQUESIZ;
                _Next = _First; }
            return (*this); }
        iterator operator++(int)
            {iterator _Tmp = *this;
            ++*this;
            return (_Tmp); }
        iterator& operator--()
            {if (_Next != _First)
                --_Next;
            else if (_Map[-1] != 0)
                {_First = *--_Map;
                _Last = _First + _DEQUESIZ;
                _Next = _Last - 1; }
            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;
        };