Implementation of std::deque (obsolete)

Question

Warning: This implementation is obsolete, because it doesn't meet the standard. Specifically, while the standard guarantee any pointers and references to elements to remain valid after insertion or erasure at the front or the back element, this implementation doesn't. This issue will be discussed later.

In fact, entire deque header, though.

According to Wikipedia, common implementations of std::deque include:

1. Storing deque contents in a circular buffer, and only resizing when the buffer becomes full. This decreases the frequency of resizings.
2. Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.
3. Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.

But I had another idea: what if I join two std::vectors, facing opposite ways?

So I tried implementing this way:

#include <vector>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <utility>
#include <unordered_set>
#include <algorithm>
#include <type_traits>
namespace std {
    template <class T, class Allocator = allocator<T> > class deque;
    template <class T, class Allocator>
    bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
    template <class T, class Allocator>
    bool operator<(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
    template <class T, class Allocator>
    bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
    template <class T, class Allocator>
    bool operator>(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
    template <class T, class Allocator>
    bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
    template <class T, class Allocator>
    bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
    template <class T, class Allocator>
    void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);

    template <class T, class Allocator = allocator<T> >
    class deque {
    public:
        // types:
        typedef T value_type;
        typedef Allocator allocator_type;
        typedef value_type &reference;
        typedef const value_type &const_reference;
        class iterator;
        class const_iterator; 
        typedef unsigned size_type;
        typedef int difference_type;
        typedef typename allocator_traits<Allocator>::pointer pointer;
        typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
        typedef reverse_iterator<iterator> reverse_iterator;
        typedef reverse_iterator<const_iterator> const_reverse_iterator;

        // construct/copy/destroy:
        deque() : deque(Allocator()) {}
        explicit deque(const Allocator&);
        deque(size_type n, const T& value,const Allocator& = Allocator());
        explicit deque(size_type n, const Allocator & = Allocator());
        template <class InputIterator>
        deque(InputIterator first, InputIterator last,const Allocator& = Allocator());
        deque(const deque<T,Allocator>& x);
        deque(deque&&);
        deque(const deque&, const Allocator&);
        deque(deque&&, const Allocator&);
        deque(initializer_list<T>, const Allocator& = Allocator());

        ~deque();
        deque<T,Allocator>& operator=(const deque<T,Allocator>& x);
        deque<T,Allocator>& operator=(deque<T,Allocator>&& x);
        deque& operator=(initializer_list<T>);
        template <class InputIterator>
        void assign(InputIterator first, InputIterator last);
        void assign(size_type n, const T& t);
        void assign(initializer_list<T>);
        allocator_type get_allocator() const noexcept;

        // iterators:
        iterator begin() noexcept;
        const_iterator begin() const noexcept;
        iterator end() noexcept;
        const_iterator end() const noexcept;

        reverse_iterator rbegin() noexcept;
        const_reverse_iterator rbegin() const noexcept;
        reverse_iterator rend() noexcept;
        const_reverse_iterator rend() const noexcept;

        const_iterator cbegin() noexcept;
        const_iterator cend() noexcept;
        const_reverse_iterator crbegin() const noexcept;
        const_reverse_iterator crend() const noexcept;

        // capacity:
        size_type size() const noexcept;
        size_type max_size() const noexcept;
        void resize(size_type sz);
        void resize(size_type sz, const T& c);
        void shrink_to_fit();
        bool empty() const noexcept;

        // element access:
        reference operator[](size_type n);
        const_reference operator[](size_type n) const;
        reference at(size_type n);
        const_reference at(size_type n) const;
        reference front();
        const_reference front() const;
        reference back();
        const_reference back() const;

        // modifiers:
        template <class... Args> void emplace_front(Args&&... args);
        template <class... Args> void emplace_back(Args&&... args);
        template <class... Args> iterator emplace(const_iterator position, Args&&... args);
        void push_front(const T& x);
        void push_front(T&& x);
        void push_back(const T& x);
        void push_back(T&& x);

        iterator insert(const_iterator position, const T& x);
        iterator insert(const_iterator position, T&& x);
        iterator insert(const_iterator position, size_type n, const T& x);
        template <class InputIterator>
        iterator insert (const_iterator position, InputIterator first, InputIterator last);
        iterator insert(const_iterator position, initializer_list<T>);

        void pop_front();
        void pop_back();

        iterator erase(const_iterator position);
        iterator erase(const_iterator first, const_iterator last);
        void swap(deque<T,Allocator>&);
        void clear() noexcept;
    private:
        // The keys of implementation; negative facing forward, positive facing backward.
        std::vector<T, Allocator> negative;
        std::vector<T, Allocator> positive;
        void shift(const_iterator pos); // This shifts entire data, pos becomes new begin of positive.
        unordered_set<iterator *> iters{}; // This prevents iterators from being invalidated, in case shift is called.
        unordered_set<const_iterator *> citers{};
    };

    template <class T, class Allocator> class deque<T, Allocator>::iterator {
        friend deque<T, Allocator>;
    private:
        deque<T, Allocator> *bound; // This is the deque which the iterator is bound to.
        make_signed<deque<T, Allocator>::size_type> pos; // This is the position of the iterator. bound->positive.begin() == 0
        iterator(deque<T, Allocator> *target, int target_pos) : bound(target), pos(target_pos) {
            if (target != nullptr) target->iters.insert(const_cast<iterator *>(this));
        }
    public:
        iterator() : bound(nullptr), pos(0) {}
        iterator(const iterator &other) : bound(other.bound), pos(other.pos) {}
        iterator(iterator &&other) :  bound(other.bound), pos(other.pos) {}
        iterator &operator = (const iterator &other) {
            bound = other.bound;
            pos = other.pos;
        }
        iterator &operator = (iterator &&other) {
            bound = other.bound;
            pos = other.pos;
        }
        ~iterator() {
            if (bound != nullptr) bound->iters.erase(const_cast<iterator *>(this));
        }
        T &operator * () const {
            if (pos < 0) return bound->negative[~pos];
            else return bound->positive[pos];
        }
        iterator &operator ++ () {
            ++pos;
            return *this;
        }
        bool operator == (const iterator &other) const {
            return bound == other.bound && pos == other.pos;
        }
        bool operator != (const iterator &other) const {
            return !(*this == other);
        }
        typename vector<T, Allocator>::iterator operator -> () const {
             if (pos < 0) return bound->negative.begin() + ~pos;
             else return bound->positive.begin() + pos;
        }
        iterator operator ++ (int) {
            iterator other(*this);
            ++*this;
            return other;
        }
        iterator &operator -- () {
            --pos;
            return *this;
        }
        iterator operator -- (int) {
            iterator other(*this);
            --*this;
            return other;
        }
        iterator operator + (int n) const {
            return iterator(bound, pos + n);
        }
        iterator operator - (int n) const {
            return iterator(bound, pos - n);
        }
        iterator operator += (int n) {
            *this = *this + n;
            return *this;
        }
        iterator operator -= (int n) {
            *this = *this - n;
            return *this;
        }
        typename deque<T, Allocator>::difference_type operator - (const iterator &other) const {
            if (bound != other.bound) /* UNDEFINED BEHAVIOR */;
            return pos - other.pos;
        }
        T &operator [] (int n) const {
            return *(*this + n);
        }
        bool operator < (const iterator &other) const {
            return bound == other.bound && pos < other.pos;
        }
        bool operator > (const iterator &other) const {
            return bound == other.bound && pos > other.pos;
        }
        bool operator <= (const iterator &other) const {
            return bound == other.bound && pos <= other.pos;
        }
        bool operator >= (const iterator &other) const{
            return bound == other.bound && pos >= other.pos;
        }
        /*implicit*/ operator const_iterator() () {
            return const_iterator(bound, pos);
        }
    };
    template <class T, class Allocator> typename deque<T, Allocator>::iterator operator + (int n, const typename deque<T, Allocator>::iterator &a) {
        return a + n;
    }
    template <class T, class Allocator> class deque<T, Allocator>::const_iterator {
        friend deque<T, Allocator>;
        friend deque<T, Allocator>::iterator::operator const_iterator;
    private:
        deque<T, Allocator> *bound; // This is the deque which the iterator is bound to.
        make_signed<deque<T, Allocator>::size_type> pos; // This is the position of the iterator. bound->positive.begin() == 0
        const_iterator(deque<T, Allocator> *target, int target_pos) : bound(target), pos(target_pos) {
            if (target != nullptr) target->citers.insert(const_cast<const_iterator *>(this));
        }
    public:
        const_iterator() : bound(nullptr), pos(0) {}
        const_iterator(const const_iterator &other) : bound(other.bound), pos(other.pos) {}
        const_iterator(const_iterator &&other) :  bound(other.bound), pos(other.pos) {}
        const_iterator &operator = (const const_iterator &other) {
            bound = other.bound;
            pos = other.pos;
        }
        const_iterator &operator = (const_iterator &&other) {
            bound = other.bound;
            pos = other.pos;
        }
        ~const_iterator() {
            if (bound != nullptr) bound->citers.erase(const_cast<const_iterator *>(this));
        }
        const T &operator * () const {
            if (pos < 0) return bound->negative[~pos];
            else return bound->positive[pos];
        }  
        const_iterator &operator ++ () {
            ++pos;
            return *this;
        }
        bool operator == (const const_iterator &other) const {
            return bound == other.bound && pos == other.pos;
        }
        bool operator != (const const_iterator &other) const {
            return !(*this == other);
        }
        typename vector<T, Allocator>::const_iterator operator -> () const {
             if (pos < 0) return bound->negative.cbegin() + ~pos;
             else return bound->positive.cbegin() + pos;
        }
        const_iterator operator ++ (int) {
            const_iterator other(*this);
            ++*this;
            return other;
        }
        const_iterator &operator -- () {
            --pos;
            return *this;
        }
        const_iterator operator -- (int) {
            const_iterator other(*this);
            --*this;
            return other;
        }
        const_iterator operator + (int n) const {
            return const_iterator(bound, pos + n);
        }
        const_iterator operator - (int n) const {
            return const_iterator(bound, pos - n);
        }
        const_iterator operator += (int n) {
            *this = *this + n;
            return *this;
        }
        const_iterator operator -= (int n) {
            *this = *this - n;
            return *this;
        }
        typename deque<T, Allocator>::difference_type operator - (const const_iterator &other) const {
            if (bound != other.bound) /* UNDEFINED BEHAVIOR */;
            return pos - other.pos;
        }
        const T &operator [] (int n) const {
            return *(*this + n);
        }
        bool operator < (const const_iterator &other) const {
            return bound == other.bound && pos < other.pos;
        }
        bool operator > (const const_iterator &other) const {
            return bound == other.bound && pos > other.pos;
        }
        bool operator <= (const const_iterator &other) const {
            return bound == other.bound && pos <= other.pos;
        }
        bool operator >= (const const_iterator &other) const{
            return bound == other.bound && pos >= other.pos;
        }
    };
    template <class T, class Allocator>
    typename deque<T, Allocator>::const_iterator operator + (int n, const typename deque<T, Allocator>::const_iterator &a) {
        return a + n;
    }

    template <class T, class Allocator>
    deque<T, Allocator>::shift(const_iterator pos) { // This shifts entire data, pos becomes new begin of positive.
        if (pos.pos < 0) {
            positive.insert(positive.cbegin(), make_reverse_iterator(negative.begin() + ~pos.pos), negative.rend());
            negative.erase(negative.begin(), negative.begin() - pos.pos);
        }
        else
            negative.insert(negative.cbegin(), make_reverse_iterator(positive.begin() + pos.pos - 1), positive.rend());
            positive.erase(positive.begin(), positive.begin() + pos.pos);
        for (auto &i : iters) i->pos -= pos.pos;
        for (auto &i : citers) i->pos -= pos.pos;
    }
    template <class T, class Allocator>
    explicit deque<T, Allocator>::deque(const Allocator &alloc)
    : negative(alloc), positive(alloc) {}
    template <class T, class Allocator>
    deque<T, Allocator>::deque(size_type n, const T &value, const Allocator &alloc = Allocator())
    : negative(n >> 1, value, alloc), positive(n - (n >> 1), value, alloc) {}
    template <class T, class Allocator>
    explicit deque<T, Allocator>::deque(size_type n, const Allocator &alloc = Allocator())
    : negative(n >> 1, alloc), positive(n - (n >> 1), alloc) {}
    template <class T, class Allocator> template <class InputIterator>
    deque<T, Allocator>::deque(InputIterator first, InputIterator last, const Allocator &alloc = Allocator())
    : negative(first, first + (last - first >> 1), alloc), positive(first + (last - first >> 1), last, alloc) {}
    template <class T, class Allocator>
    deque<T, Allocator>::deque(const deque<T, Allocator>& x)
    : negative(x.negative), positive(x.positive) {}
    template <class T, class Allocator>
    deque<T, Allocator>::deque(const deque<T, Allocator>& x, Allocator &alloc)
    : negative(x.negative, alloc), positive(x.positive, alloc) {}
    template <class T, class Allocator>
    deque<T, Allocator>::deque(deque<T, Allocator> &&x)
    : negative(x.negative), positive(x.positive) {}
    template <class T, class Allocator>
    deque<T, Allocator>::deque(deque<T, Allocator> &&x, Allocator &alloc)
    : negative(x.negative, alloc), positive(x.positive, alloc) {}
    template <class T, class Allocator>
    deque<T, Allocator>::deque(initializer_list<T> init, const Allocator &alloc = Allocator())
    : negative(init.begin(), init.begin() + (init.end() - init.begin() >> 1), alloc), positive(init.begin() + (init.end() - init.begin() >> 1), init.end(), alloc) {}
    template <class T, class Allocator>
    deque<T, Allocator> &deque<T, Allocator>::operator = (const deque<T, Allocator> &x) {
        negative = x.negative;
        positive = x.positive;
        return *this;
    }
    template <class T, class Allocator>
    deque<T, Allocator> &deque<T, Allocator>::operator = (deque<T, Allocator> &&x) {
        negative = x.negative;
        positive = x.positive;
        return *this;
    }
    template <class T, class Allocator>
    deque<T, Allocator> &deque<T, Allocator>::operator = (initializer_list<T> init) {
        negative.assign(init.begin(), init.begin() + (init.end() - init.begin() >> 1));
        positive.assign(init.begin() + (init.end() - init.begin() >> 1), init.end());
    }
    template <class T, class Allocator>
    deque<T, Allocator> deque<T, Allocator>::~deque() {
        for (auto &i : iters) i->bound = nullptr;
        for (auto &i : citers) i->bound = nullptr;
    }
    template <class T, class Allocator> template <class InputIterator>
    void deque<T, Allocator>::assign(InputIterator first, InputIterator last) {
    negative.assign(first, first + (last - first >> 1));
    positive.assign(first + (last - first >> 1), last);
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::assign(size_type n, const T &t) {
        negative.assign(n >> 1, value);
        positive.assign(n - (n >> 1), value);
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::assign(initializer_list<T> init) {
        negative.assign(init.begin(), init.begin() + (init.end() - init.begin() >> 1));
        positive.assign(init.begin() + (init.end() - init.begin() >> 1), init.end());
    }
    template <class T, class Allocator>
    Allocator deque<T, Allocator>::get_allocator() const noexcept {
        return negative.get_allocator();
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::iterator deque<T, Allocator>::begin() noexcept {
        return iterator(this, ~negative.size());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::const_iterator deque<T, Allocator>::begin() const noexcept {
        return const_iterator(this, ~negative.size());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::iterator deque<T, Allocator>::end() noexcept {
        return iterator(this, positive.size());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::const_iterator deque<T, Allocator>::end() const noexcept {
        return const_iterator(this, positive.size());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::reverse_iterator deque<T, Allocator>::rbegin() noexcept {
        return make_reverse_iterator(begin());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::rbegin() const noexcept {
        return make_reverse_iterator(cbegin());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::reverse_iterator deque<T, Allocator>::rend() noexcept {
        return make_reverse_iterator(end());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::rend() const noexcept {
        return make_reverse_iterator(cend());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::const_iterator deque<T, Allocator>::cbegin() const noexcept {
        return const_iterator(this, ~negative.size());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::crbegin() const noexcept {
        return make_reverse_iterator(cbegin());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::const_iterator deque<T, Allocator>::cend() const noexcept {
        return const_iterator(this, positive.size());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::crend() const noexcept {
        return make_reverse_iterator(cend());
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::size_type deque<T, Allocator>::size() const noexcept {
        return negative.size() + positive.size();
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::size_type deque<T, Allocator>::max_size() const noexcept {
        return negative.max_size() + positive.size();
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::resize(size_type sz) {
        if (sz >= negative.size())
            positive.resize(sz - negative.size());
        else {
            shift(negative.crbegin() + sz);
            positive.clear();
        }
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::resize(size_type sz, const T &c) {
        if (sz >= negative.size())
            positive.resize(sz - negative.size(), c);
        else {
            shift(negative.crbegin() + sz);
            positive.clear();
        }
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::shrink_to_fit() {
        negative.shrink_to_fit();
        positive.shrink_to_fit();
    }
    template <class T, class Allocator>
    bool deque<T, Allocator>::empty() {
        return negative.empty() && positive.empty();
    }
    template <class T, class Allocator>
    T &deque<T, Allocator>::operator [] (size_type n) {
        if (n < negative.size()) return negative.rbegin()[n];
        else return positive[n - negative.size()];
    }
    template <class T, class Allocator>
    const T &deque<T, Allocator>::operator [] (size_type n) const {
        if (n < negative.size()) return negative.crbegin()[n];
        else return positive[n - negative.size()];
    }
    template <class T, class Allocator>
    T &deque<T, Allocator>::at(size_type n) {
        if (n < negative.size()) return negative.rbegin()[n];
        else return positive.at(n - negative.size());
    }
    template <class T, class Allocator>
    const T &deque<T, Allocator>::at(size_type n) const {
        if (n < negative.size()) return negative.crbegin()[n];
        else return positive.at(n - negative.size());
    }
    template <class T, class Allocator>
    T &deque<T, Allocator>::front() {
        if (negative.empty()) return positive.front();
        else return negative.back();
    }
    template <class T, class Allocator>
    const T &deque<T, Allocator>::front() const {
        if (negative.empty()) return positive.front();
        else return negative.back();
    }
    template <class T, class Allocator>
    T &deque<T, Allocator>::back() {
        if (positive.empty()) return negative.front();
        else return positive.back();
    }
    template <class T, class Allocator>
    const T &deque<T, Allocator>::back() const {
        if (positive.empty()) return negative.front();
        else return positive.back();
    }
    template <class T, class Allocator> template <class ...Args>
    void deque<T, Allocator>::emplace_front(Args &&...args) {
        negative.emplace(negative.rbegin(), args...);
    }
    template <class T, class Allocator> template <class ...Args>
    void deque<T, Allocator>::emplace_back(Args &&...args) {
        positive.emplace_back(args...);
    }
    template <class T, class Allocator> template <class ...Args>
    typename deque<T, Allocator>::iterator deque<T, Allocator>::emplace(const_iterator position, Args &&...args) {
        if (position.bound != this) /* UNDEFINED BEHAVIOR */;
        if (position.pos < 0) {
            typename vector<T, Allocator>::iterator iter(negative.emplace(negative.begin() - position.pos, args...));
            reverse(iter, iter + sizeof...(args))
            return iterator(this, position.pos - sizeof...(args));
        } else {
            positive.emplace(positive.begin() + position.pos, args...);
            return iterator(this, position.pos);
        }
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::push_front(const T &x) {
        negative.push_back(x);
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::push_front(T &&x) {
        negative.push_back(x);
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::push_back(const T &x) {
        positive.push_back(x);
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::push_front(T &&x) {
        negative.push_back(x);
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::iterator deque<T, Allocator>::insert(const_iterator position, const T &x) {
        if (position.bound != this) /* UNDEFINED BEHAVIOR */;
        if (position.pos < 0) {
            negative.insert(negative.cbegin() - position.pos, x);
            return iterator(this, position.pos - 1);
        } else {
            positive.insert(positive.begin() + position.pos, x);
            return iterator(this, position.pos);
        }
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::iterator deque<T, Allocator>::insert(const_iterator position, T &&x) {
        if (position.bound != this) /* UNDEFINED BEHAVIOR */;
        if (position.pos < 0) {
            negative.insert(negative.cbegin() - position.pos, x);
            return iterator(this, position.pos - 1);
        } else {
            positive.insert(positive.begin() + position.pos, x);
            return iterator(this, position.pos);
        }
    }
    template <class T, class Allocator> template <class InputIterator>
    typename deque<T, Allocator>::iterator deque<T, Allocator>::insert(const_iterator position, InputIterator first, InputIterator last) {
        if (position.bound != this) /* UNDEFINED BEHAVIOR */;
        if (position.pos < 0) {
            negative.insert(negative.cbegin() - position.pos, make_reverse_iterator(last) - 1, make_reverse_iterator(first) - 1);
            return iterator(this, position.pos - (last - first));
        } else {
            positive.insert(positive.cbegin() + position.pos, first, last);
            return iterator(this, position.pos);
        }
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::iterator deque<T, Allocator>::insert(const_iterator position, initializer_list<T> ilist) {
        if (position.bound != this) /* UNDEFINED BEHAVIOR */;
        if (position.pos < 0) {
            negative.insert(negative.cbegin() - position.pos, ilist.rbegin(), ilist.rend());
            return iterator(this, position.pos - ilist.size());
        } else {
            positive.insert(positive.cbegin() + position.pos, ilist);
            return iterator(this, position.pos);
        }
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::pop_front() {
        if (negative.empty()) shift(const_iterator(this, (static_cast<vector<T, Allocator>::difference_type>(positive.size()) >> 1) + 1));
        negative.pop_back();
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::pop_back() {
        if (positive.empty()) shift(const_iterator(this, ~(static_cast<vector<T, Allocator>::difference_type>(negative.size()) >> 1));
        negative.pop_back();
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::iterator deque<T, Allocator>::erase(const_iterator position) {
        if (position.bound != this) /* UNDEFINED BEHAVIOR */;
        if (position.pos < 0) { 
            negative.erase(negative.cbegin() + ~position.pos);
            return iterator(this, position.pos - 1);
        } else {
            positive.erase(positive.cbegin() + position.pos);
            return iterator(this, position.pos);
        }
    }
    template <class T, class Allocator>
    typename deque<T, Allocator>::iterator deque<T, Allocator>::erase(const_iterator first, const_iterator last) {
        if (first.bound != this || last.bound != this) /* UNDEFINED BEHAVIOR */;
        if (first.pos < 0) {
            if (last.pos <= 0) {
                negative.erase(negative.cbegin() - last.pos, negative.cbegin() - first.pos);
                return iterator(this, last.pos);
            } else {
                negative.erase(negative.cbegin(), negative.cbegin() - first.pos);
                positive.erase(positive.cbegin(), positive.cbegin() + last.pos);
                return iterator(this, 0);
        } else {
            positive.erase(positive.cbegin() + first.pos, positive.cbegin() + last.pos);
            return iterator(this, first.pos);
        }
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::swap(deque<T, Allocator> &other) {
        swap(*this, other);
    }
    template <class T, class Allocator>
    void deque<T, Allocator>::clear() {
        negative.clear();
        positive.clear();
    }
    template <class T, class Allocator>
    bool operator == (const deque<T, Allocator> &x, const deque<T, Allocator> &y) {
        if (x.size() != y.size()) return false;
        else return mismatch(x.begin(), y.begin(), x.end()).first == x.end();
    }
    template <class T, class Allocator>
    bool operator == (const deque<T, Allocator> &x, const deque<T, Allocator> &y) {
        return !(x == y);
    }
    template <class T, class Allocator>
    bool operator < (const deque<T, Allocator> &x, const deque<T, Allocator> &y) {
        return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
    }
    template <class T, class Allocator>
    bool operator > (const deque<T, Allocator> &x, const deque<T, Allocator> &y) {
        return y < x;
    }
    template <class T, class Allocator>
    bool operator <= (const deque<T, Allocator> &x, const deque<T, Allocator> &y) {
        return !(y < x);
    }
    template <class T, class Allocator>
    bool operator >= (const deque<T, Allocator> &x, const deque<T, Allocator> &y) {
        return !(x < y);
    }
    template <class T, class Allocator>
    void swap(deque<T, Allocator> &x, deque<T, Allocator> &y) {
        deque<T, Allocator> temp(std::move(x));
        x = std::move(y);
        y = std::move(temp);
    }
}

I have just one question: does this implementation perform better than the common implementations described above?

Answer 1

You've independently discovered how to implement a (double-ended) queue using two stacks. See for example How to implement a queue using two stacks? or google that phrase for lots of hits.

If you've implemented them efficiently, each of the implementations you mentioned should be equally efficient: amortized constant time for insertions and deletions. The details really depend on exactly what workload you're expecting to handle: lots of push_fronts followed by lots of pop_backs? lots of push_fronts followed by lots of pop_fronts? alternating push_fronts and pop_backs? alternating push_fronts and pop_fronts? etc.

As for the efficiency of your C++ implementation, I have a few comments, but they're mostly minor. Basically it looks very thorough, and matches the Standard's style very well.

---

template <class T, class Allocator> class deque<T, Allocator>::iterator

Look into the SCARY iterator pattern. You should be able to do something like

template<class T> class deque_iterator { ... };

template<class T, class Allocator> class deque {
    using iterator = deque_iterator<T>;
};

so that deque<int> and deque<int, CustomAllocator> don't need to instantiate two different iterator classes. This will improve compile times, and more importantly improve binary sizes (which translates into "programs that require less RAM" and "programs that fit into icache better").

---

iterator(const iterator &other) : bound(other.bound), pos(other.pos) {}

This and all your special member functions (constructors and assignment operators) for iterator and const_iterator can be =default'ed (and therefore should be, just in case they're used in a situation where trivial construction/assignment gives a performance benefit).

---

typename vector<T, Allocator>::iterator operator -> () const

Why not T *operator->() const?

---

template <class T, class Allocator>
deque<T, Allocator> &deque<T, Allocator>::operator = (deque<T, Allocator> &&x) {
    negative = x.negative;
    positive = x.positive;
    return *this;
}

You're not getting move semantics here. This function should be =default'ed anyway; but if you're not going to =default it, then you ought to be doing

negative = std::move(x.negative);
positive = std::move(x.positive);

so that the vector contents are moved rather than copied.

---

In particular, because of your inefficient move-assignment operator, your swap operation is neither efficient nor noexcept:

template <class T, class Allocator>
void swap(deque<T, Allocator> &x, deque<T, Allocator> &y) {
    deque<T, Allocator> temp(std::move(x));
    x = std::move(y);
    y = std::move(temp);
}

You should instead implement non-member swap as

template <class T, class Allocator>
void swap(deque<T, Allocator> &x, deque<T, Allocator> &y) noexcept {
    x.swap(y);
}

and then implement the member function swap as

template <class T, class Allocator>
void deque<T, Allocator>::swap(deque<T, Allocator> &other) noexcept {
    positive.swap(other.positive);
    negative.swap(other.negative);
}