deque.h

#ifndef MYTINYSTL_DEQUE_H
#define MYTINYSTL_DEQUE_H

// 这个头文件包含了一个模板类 deque
// deque: 双端队列

// notes:
//
// 异常保证：
// mystl::deque<T> 满足基本异常保证，部分函数无异常保证，并对以下等函数做强异常安全保证：
//   * emplace_front
//   * emplace_back
//   * emplace
//   * push_front
//   * push_back
//   * insert

#include <initializer_list>

#include "iterator.h"
#include "memory.h"
#include "util.h"
#include "exceptdef.h"

namespace mystl
{
#ifdef max
#pragma message("#undefing marco max")
#undef max
#endif // max

#ifdef min
#pragma message("#undefing marco min")
#undef min
#endif // min

// deque map 初始化的大小
#ifndef DEQUE_MAP_INIT_SIZE
#define DEQUE_MAP_INIT_SIZE 8
#endif

    template <class T>
    struct deque_buf_size
    {
        static constexpr size_t value = sizeof(T) < 256 ? 4096 / sizeof(T) : 16;
    };

    // deque 的迭代器设计
    template <class T, class Ref, class Ptr>
    struct deque_iterator : public iterator<random_access_iterator_tag, T>
    {
        typedef deque_iterator<T, T&, T*>             iterator;
        typedef deque_iterator<T, const T&, const T*> const_iterator;
        typedef deque_iterator                        self;

        typedef T            value_type;
        typedef Ptr          pointer;
        typedef Ref          reference;
        typedef size_t       size_type;
        typedef ptrdiff_t    difference_type;
        typedef T* value_pointer;
        typedef T** map_pointer;

        static const size_type buffer_size = deque_buf_size<T>::value;

        // 迭代器所含成员数据
        value_pointer cur;    // 指向所在缓冲区的当前元素
        value_pointer first;  // 指向所在缓冲区的头部
        value_pointer last;   // 指向所在缓冲区的尾部
        map_pointer   node;   // 缓冲区所在节点

        // 构造、复制、移动函数
        deque_iterator() noexcept
            :cur(nullptr), first(nullptr), last(nullptr), node(nullptr) {}

        deque_iterator(value_pointer v, map_pointer n)
            :cur(v), first(*n), last(*n + buffer_size), node(n) {}

        deque_iterator(const iterator& rhs)
            :cur(rhs.cur), first(rhs.first), last(rhs.last), node(rhs.node)
        {
        }
        deque_iterator(iterator&& rhs) noexcept
            :cur(rhs.cur), first(rhs.first), last(rhs.last), node(rhs.node)
        {
            rhs.cur = nullptr;
            rhs.first = nullptr;
            rhs.last = nullptr;
            rhs.node = nullptr;
        }

        deque_iterator(const const_iterator& rhs)
            :cur(rhs.cur), first(rhs.first), last(rhs.last), node(rhs.node)
        {
        }

        self& operator=(const iterator& rhs)
        {
            if (this != &rhs)
            {
                cur = rhs.cur;
                first = rhs.first;
                last = rhs.last;
                node = rhs.node;
            }
            return *this;
        }

        // 转到另一个缓冲区
        void set_node(map_pointer new_node)
        {
            node = new_node;
            first = *new_node;
            last = first + buffer_size;
        }

        // 重载运算符
        reference operator*()  const { return *cur; }
        pointer   operator->() const { return cur; }

        difference_type operator-(const self& x) const
        {
            return static_cast<difference_type>(buffer_size) * (node - x.node)
                + (cur - first) - (x.cur - x.first);
        }

        self& operator++()
        {
            ++cur;
            if (cur == last)
            { // 如果到达缓冲区的尾
                set_node(node + 1);
                cur = first;
            }
            return *this;
        }
        self operator++(int)
        {
            self tmp = *this;
            ++* this;
            return tmp;
        }

        self& operator--()
        {
            if (cur == first)
            { // 如果到达缓冲区的头
                set_node(node - 1);
                cur = last;
            }
            --cur;
            return *this;
        }
        self operator--(int)
        {
            self tmp = *this;
            --* this;
            return tmp;
        }

        self& operator+=(difference_type n)
        {
            const auto offset = n + (cur - first);
            if (offset >= 0 && offset < static_cast<difference_type>(buffer_size))
            { // 仍在当前缓冲区
                cur += n;
            }
            else
            { // 要跳到其他的缓冲区
                const auto node_offset = offset > 0
                    ? offset / static_cast<difference_type>(buffer_size)
                    : -static_cast<difference_type>((-offset - 1) / buffer_size) - 1;
                set_node(node + node_offset);
                cur = first + (offset - node_offset * static_cast<difference_type>(buffer_size));
            }
            return *this;
        }
        self operator+(difference_type n) const
        {
            self tmp = *this;
            return tmp += n;
        }
        self& operator-=(difference_type n)
        {
            return *this += -n;
        }
        self operator-(difference_type n) const
        {
            self tmp = *this;
            return tmp -= n;
        }

        reference operator[](difference_type n) const { return *(*this + n); }

        // 重载比较操作符
        bool operator==(const self& rhs) const { return cur == rhs.cur; }
        bool operator< (const self& rhs) const
        {
            return node == rhs.node ? (cur < rhs.cur) : (node < rhs.node);
        }
        bool operator!=(const self& rhs) const { return !(*this == rhs); }
        bool operator> (const self& rhs) const { return rhs < *this; }
        bool operator<=(const self& rhs) const { return !(rhs < *this); }
        bool operator>=(const self& rhs) const { return !(*this < rhs); }
    };

    // 模板类 deque
    // 模板参数代表数据类型
    template <class T>
    class deque
    {
    public:
        // deque 的型别定义
        typedef mystl::allocator<T>                      allocator_type;
        typedef mystl::allocator<T>                      data_allocator;
        typedef mystl::allocator<T*>                     map_allocator;

        typedef typename allocator_type::value_type      value_type;
        typedef typename allocator_type::pointer         pointer;
        typedef typename allocator_type::const_pointer   const_pointer;
        typedef typename allocator_type::reference       reference;
        typedef typename allocator_type::const_reference const_reference;
        typedef typename allocator_type::size_type       size_type;
        typedef typename allocator_type::difference_type difference_type;
        typedef pointer* map_pointer;
        typedef const_pointer* const_map_pointer;

        typedef deque_iterator<T, T&, T*>                iterator;
        typedef deque_iterator<T, const T&, const T*>    const_iterator;
        typedef mystl::reverse_iterator<iterator>        reverse_iterator;
        typedef mystl::reverse_iterator<const_iterator>  const_reverse_iterator;

        allocator_type get_allocator() { return allocator_type(); }

        static const size_type buffer_size = deque_buf_size<T>::value;

    private:
        // 用以下四个数据来表现一个 deque
        iterator       begin_;     // 指向第一个节点
        iterator       end_;       // 指向最后一个结点
        map_pointer    map_;       // 指向一块 map，map 中的每个元素都是一个指针，指向一个缓冲区
        size_type      map_size_;  // map 内指针的数目

    public:
        // 构造、复制、移动、析构函数

        deque()
        {
            fill_init(0, value_type());
        }

        explicit deque(size_type n)
        {
            fill_init(n, value_type());
        }

        deque(size_type n, const value_type& value)
        {
            fill_init(n, value);
        }

        template <class IIter, typename std::enable_if<
        mystl::is_input_iterator<IIter>::value, int>::type = 0>
        deque(IIter first, IIter last)
        {
            copy_init(first, last, iterator_category(first));
        }

        deque(std::initializer_list<value_type> ilist)
        {
            copy_init(ilist.begin(), ilist.end(), mystl::forward_iterator_tag());
        }

        deque(const deque& rhs)
        {
            copy_init(rhs.begin(), rhs.end(), mystl::forward_iterator_tag());
        }
        deque(deque&& rhs) noexcept
            :begin_(mystl::move(rhs.begin_)),
            end_(mystl::move(rhs.end_)),
            map_(rhs.map_),
            map_size_(rhs.map_size_)
        {
            rhs.map_ = nullptr;
            rhs.map_size_ = 0;
        }

        deque& operator=(const deque& rhs);
        deque& operator=(deque&& rhs);

        deque& operator=(std::initializer_list<value_type> ilist)
        {
            deque tmp(ilist);
            swap(tmp);
            return *this;
        }

        ~deque()
        {
            if (map_ != nullptr)
            {
                clear();
                data_allocator::deallocate(*begin_.node, buffer_size);
                *begin_.node = nullptr;
                map_allocator::deallocate(map_, map_size_);
                map_ = nullptr;
            }
        }

    public:
        // 迭代器相关操作

        iterator               begin()         noexcept
        {
            return begin_;
        }
        const_iterator         begin()   const noexcept
        {
            return begin_;
        }
        iterator               end()           noexcept
        {
            return end_;
        }
        const_iterator         end()     const noexcept
        {
            return end_;
        }

        reverse_iterator       rbegin()        noexcept
        {
            return reverse_iterator(end());
        }
        const_reverse_iterator rbegin()  const noexcept
        {
            return reverse_iterator(end());
        }
        reverse_iterator       rend()          noexcept
        {
            return reverse_iterator(begin());
        }
        const_reverse_iterator rend()    const noexcept
        {
            return reverse_iterator(begin());
        }

        const_iterator         cbegin()  const noexcept
        {
            return begin();
        }
        const_iterator         cend()    const noexcept
        {
            return end();
        }
        const_reverse_iterator crbegin() const noexcept
        {
            return rbegin();
        }
        const_reverse_iterator crend()   const noexcept
        {
            return rend();
        }

        // 容量相关操作

        bool      empty()    const noexcept { return begin() == end(); }
        size_type size()     const noexcept { return end_ - begin_; }
        size_type max_size() const noexcept { return static_cast<size_type>(-1); }
        void      resize(size_type new_size) { resize(new_size, value_type()); }
        void      resize(size_type new_size, const value_type& value);
        void      shrink_to_fit() noexcept;

        // 访问元素相关操作 
        reference       operator[](size_type n)
        {
            MYSTL_DEBUG(n < size());
            return begin_[n];
        }
        const_reference operator[](size_type n) const
        {
            MYSTL_DEBUG(n < size());
            return begin_[n];
        }

        reference       at(size_type n)
        {
            THROW_OUT_OF_RANGE_IF(!(n < size()), "deque<T>::at() subscript out of range");
            return (*this)[n];
        }
        const_reference at(size_type n) const
        {
            THROW_OUT_OF_RANGE_IF(!(n < size()), "deque<T>::at() subscript out of range");
            return (*this)[n];
        }

        reference       front()
        {
            MYSTL_DEBUG(!empty());
            return *begin();
        }
        const_reference front() const
        {
            MYSTL_DEBUG(!empty());
            return *begin();
        }
        reference       back()
        {
            MYSTL_DEBUG(!empty());
            return *(end() - 1);
        }
        const_reference back() const
        {
            MYSTL_DEBUG(!empty());
            return *(end() - 1);
        }

        // 修改容器相关操作

        // assign

        void     assign(size_type n, const value_type& value)
        {
            fill_assign(n, value);
        }

        template <class IIter, typename std::enable_if<
            mystl::is_input_iterator<IIter>::value, int>::type = 0>
            void     assign(IIter first, IIter last)
        {
            copy_assign(first, last, iterator_category(first));
        } 

        void     assign(std::initializer_list<value_type> ilist)
        {
            copy_assign(ilist.begin(), ilist.end(), mystl::forward_iterator_tag{});
        }

        // emplace_front / emplace_back / emplace

        template <class ...Args>
        void     emplace_front(Args&& ...args);
        template <class ...Args>
        void     emplace_back(Args&& ...args);
        template <class ...Args>
        iterator emplace(iterator pos, Args&& ...args);

        // push_front / push_back

        void     push_front(const value_type& value);
        void     push_back(const value_type& value);

        void     push_front(value_type&& value) { emplace_front(mystl::move(value)); }
        void     push_back(value_type&& value) { emplace_back(mystl::move(value)); }

        // pop_back / pop_front

        void     pop_front();
        void     pop_back();

        // insert

        iterator insert(iterator position, const value_type& value);
        iterator insert(iterator position, value_type&& value);
        void     insert(iterator position, size_type n, const value_type& value);
        template <class IIter, typename std::enable_if<
            mystl::is_input_iterator<IIter>::value, int>::type = 0>
            void     insert(iterator position, IIter first, IIter last)
        {
            insert_dispatch(position, first, last, iterator_category(first));
        }

        // erase /clear

        iterator erase(iterator position);
        iterator erase(iterator first, iterator last);
        void     clear();

        // swap

        void     swap(deque& rhs) noexcept;

    private:
        // helper functions

        // create node / destroy node
        map_pointer create_map(size_type size);
        void        create_buffer(map_pointer nstart, map_pointer nfinish);
        void        destroy_buffer(map_pointer nstart, map_pointer nfinish);

        // initialize
        void        map_init(size_type nelem);
        void        fill_init(size_type n, const value_type& value);
        template <class IIter>
        void        copy_init(IIter, IIter, input_iterator_tag);
        template <class FIter>
        void        copy_init(FIter, FIter, forward_iterator_tag);

        // assign
        void        fill_assign(size_type n, const value_type& value);
        template <class IIter>
        void        copy_assign(IIter first, IIter last, input_iterator_tag);
        template <class FIter>
        void        copy_assign(FIter first, FIter last, forward_iterator_tag);

        // insert
        template <class... Args>
        iterator    insert_aux(iterator position, Args&& ...args);
        void        fill_insert(iterator position, size_type n, const value_type& x);
        template <class FIter>
        void        copy_insert(iterator, FIter, FIter, size_type);
        template <class IIter>
        void        insert_dispatch(iterator, IIter, IIter, input_iterator_tag);
        template <class FIter>
        void        insert_dispatch(iterator, FIter, FIter, forward_iterator_tag);

        // reallocate
        void        require_capacity(size_type n, bool front);
        void        reallocate_map_at_front(size_type need);
        void        reallocate_map_at_back(size_type need);

    };
     
    /*****************************************************************************************/
    // 复制赋值运算符
    template <class T>
    deque<T>& deque<T>::operator=(const deque& rhs)
    {
        if (this != &rhs)
        {
            const auto len = size();
            if (len >= rhs.size())
            {
                erase(mystl::copy(rhs.begin_, rhs.end_, begin_), end_);
            }
            else
            {
                iterator mid = rhs.begin() + static_cast<difference_type>(len);
                mystl::copy(rhs.begin_, mid, begin_);
                insert(end_, mid, rhs.end_);
            }
        }
        return *this;
    }

    // 移动赋值运算符
    template <class T>
    deque<T>& deque<T>::operator=(deque&& rhs)
    {
        clear();
        begin_ = mystl::move(rhs.begin_);
        end_ = mystl::move(rhs.end_);
        map_ = rhs.map_;
        map_size_ = rhs.map_size_;
        rhs.map_ = nullptr;
        rhs.map_size_ = 0;
        return *this;
    }

    // 重置容器大小
    template <class T>
    void deque<T>::resize(size_type new_size, const value_type& value)
    {
        const auto len = size();
        if (new_size < len)
        {
            erase(begin_ + new_size, end_);
        }
        else
        {
            insert(end_, new_size - len, value);
        }
    }

    // 减小容器容量
    template <class T>
    void deque<T>::shrink_to_fit() noexcept
    {
        // 至少会留下头部缓冲区
        for (auto cur = map_; cur < begin_.node; ++cur)
        {
            data_allocator::deallocate(*cur, buffer_size);
            *cur = nullptr;
        }
        for (auto cur = end_.node + 1; cur < map_ + map_size_; ++cur)
        {
            data_allocator::deallocate(*cur, buffer_size);
            *cur = nullptr;
        }
    }

    // 在头部就地构建元素
    template <class T>
    template <class ...Args>
    void deque<T>::emplace_front(Args&& ...args)
    {
        if (begin_.cur != begin_.first)
        {
            data_allocator::construct(begin_.cur - 1, mystl::forward<Args>(args)...);
            --begin_.cur;
        }
        else
        {
            require_capacity(1, true);
            try
            {
                --begin_;
                data_allocator::construct(begin_.cur, mystl::forward<Args>(args)...);
            }
            catch (...)
            {
                ++begin_;
                throw;
            }
        }
    }

    // 在尾部就地构建元素
    template <class T>
    template <class ...Args>
    void deque<T>::emplace_back(Args&& ...args)
    {
        if (end_.cur != end_.last - 1)
        {
            data_allocator::construct(end_.cur, mystl::forward<Args>(args)...);
            ++end_.cur;
        }
        else
        {
            require_capacity(1, false);
            data_allocator::construct(end_.cur, mystl::forward<Args>(args)...);
            ++end_;
        }
    }

    // 在 pos 位置就地构建元素
    template <class T>
    template <class ...Args>
    typename deque<T>::iterator deque<T>::emplace(iterator pos, Args&& ...args)
    {
        if (pos.cur == begin_.cur)
        {
            emplace_front(mystl::forward<Args>(args)...);
            return begin_;
        }
        else if (pos.cur == end_.cur)
        {
            emplace_back(mystl::forward<Args>(args)...);
            return end_;
        }
        return insert_aux(pos, mystl::forward<Args>(args)...);
    }

    // 在头部插入元素
    template <class T>
    void deque<T>::push_front(const value_type& value)
    {
        if (begin_.cur != begin_.first)
        {
            data_allocator::construct(begin_.cur - 1, value);
            --begin_.cur;
        }
        else
        {
            require_capacity(1, true);
            try
            {
                --begin_;
                data_allocator::construct(begin_.cur, value);
            }
            catch (...)
            {
                ++begin_;
                throw;
            }
        }
    }

    // 在尾部插入元素
    template <class T>
    void deque<T>::push_back(const value_type& value)
    {
        if (end_.cur != end_.last - 1)
        {
            data_allocator::construct(end_.cur, value);
            ++end_.cur;
        }
        else
        {
            require_capacity(1, false);
            data_allocator::construct(end_.cur, value);
            ++end_;
        }
    }

    // 弹出头部元素
    template <class T>
    void deque<T>::pop_front()
    {
        MYSTL_DEBUG(!empty());
        if (begin_.cur != begin_.last - 1)
        {
            data_allocator::destroy(begin_.cur);
            ++begin_.cur;
        }
        else
        {
            data_allocator::destroy(begin_.cur);
            ++begin_;
            destroy_buffer(begin_.node - 1, begin_.node - 1);
        }
    }

    // 弹出尾部元素
    template <class T>
    void deque<T>::pop_back()
    {
        MYSTL_DEBUG(!empty());
        if (end_.cur != end_.first)
        {
            --end_.cur;
            data_allocator::destroy(end_.cur);
        }
        else
        {
            --end_;
            data_allocator::destroy(end_.cur);
            destroy_buffer(end_.node + 1, end_.node + 1);
        }
    }

    // 在 position 处插入元素
    template <class T>
    typename deque<T>::iterator
        deque<T>::insert(iterator position, const value_type& value)
    {
        if (position.cur == begin_.cur)
        {
            push_front(value);
            return begin_;
        }
        else if (position.cur == end_.cur)
        {
            push_back(value);
            auto tmp = end_;
            --tmp;
            return tmp;
        }
        else
        {
            return insert_aux(position, value);
        }
    }

    template <class T>
    typename deque<T>::iterator
        deque<T>::insert(iterator position, value_type&& value)
    {
        if (position.cur == begin_.cur)
        {
            emplace_front(mystl::move(value));
            return begin_;
        }
        else if (position.cur == end_.cur)
        {
            emplace_back(mystl::move(value));
            auto tmp = end_;
            --tmp;
            return tmp;
        }
        else
        {
            return insert_aux(position, mystl::move(value));
        }
    }

    // 在 position 位置插入 n 个元素
    template <class T>
    void deque<T>::insert(iterator position, size_type n, const value_type& value)
    {
        if (position.cur == begin_.cur)
        {
            require_capacity(n, true);
            auto new_begin = begin_ - n;
            mystl::uninitialized_fill_n(new_begin, n, value);
            begin_ = new_begin;
        }
        else if (position.cur == end_.cur)
        {
            require_capacity(n, false);
            auto new_end = end_ + n;
            mystl::uninitialized_fill_n(end_, n, value);
            end_ = new_end;
        }
        else
        {
            fill_insert(position, n, value);
        }
    }

    // 删除 position 处的元素
    template <class T>
    typename deque<T>::iterator
        deque<T>::erase(iterator position)
    {
        auto next = position;
        ++next;
        const size_type elems_before = position - begin_;
        if (elems_before < (size() / 2))
        {
            mystl::copy_backward(begin_, position, next);
            pop_front();
        }
        else
        {
            mystl::copy(next, end_, position);
            pop_back();
        }
        return begin_ + elems_before;
    }

    // 删除[first, last)上的元素
    template <class T>
    typename deque<T>::iterator
        deque<T>::erase(iterator first, iterator last)
    {
        if (first == begin_ && last == end_)
        {
            clear();
            return end_;
        }
        else
        {
            const size_type len = last - first;
            const size_type elems_before = first - begin_;
            if (elems_before < ((size() - len) / 2))
            {
                mystl::copy_backward(begin_, first, last);
                auto new_begin = begin_ + len;
                data_allocator::destroy(begin_.cur, new_begin.cur);
                begin_ = new_begin;
            }
            else
            {
                mystl::copy(last, end_, first);
                auto new_end = end_ - len;
                data_allocator::destroy(new_end.cur, end_.cur);
                end_ = new_end;
            }
            return begin_ + elems_before;
        }
    }

    // 清空 deque
    template <class T>
    void deque<T>::clear()
    {
        // clear 会保留头部的缓冲区
        for (map_pointer cur = begin_.node + 1; cur < end_.node; ++cur)
        {
            data_allocator::destroy(*cur, *cur + buffer_size);
        }
        if (begin_.node != end_.node)
        { // 有两个以上的缓冲区
            mystl::destroy(begin_.cur, begin_.last);
            mystl::destroy(end_.first, end_.cur);
        }
        else
        {
            mystl::destroy(begin_.cur, end_.cur);
        }
        shrink_to_fit();
        end_ = begin_;
    }

    // 交换两个 deque
    template <class T>
    void deque<T>::swap(deque& rhs) noexcept
    {
        if (this != &rhs)
        {
            mystl::swap(begin_, rhs.begin_);
            mystl::swap(end_, rhs.end_);
            mystl::swap(map_, rhs.map_);
            mystl::swap(map_size_, rhs.map_size_);
        }
    }

    /*****************************************************************************************/
    // helper function

    template <class T>
    typename deque<T>::map_pointer
        deque<T>::create_map(size_type size)
    {
        map_pointer mp = nullptr;
        mp = map_allocator::allocate(size);
        for (size_type i = 0; i < size; ++i)
            *(mp + i) = nullptr;
        return mp;
    }

    // create_buffer 函数
    template <class T>
    void deque<T>::
        create_buffer(map_pointer nstart, map_pointer nfinish)
    {
        map_pointer cur;
        try
        {
            for (cur = nstart; cur <= nfinish; ++cur)
            {
                *cur = data_allocator::allocate(buffer_size);
            }
        }
        catch (...)
        {
            while (cur != nstart)
            {
                --cur;
                data_allocator::deallocate(*cur, buffer_size);
                *cur = nullptr;
            }
            throw;
        }
    }

    // destroy_buffer 函数
    template <class T>
    void deque<T>::
        destroy_buffer(map_pointer nstart, map_pointer nfinish)
    {
        for (map_pointer n = nstart; n <= nfinish; ++n)
        {
            data_allocator::deallocate(*n, buffer_size);
            *n = nullptr;
        }
    }

    // map_init 函数
    template <class T>
    void deque<T>::
        map_init(size_type nElem)
    {
        const size_type nNode = nElem / buffer_size + 1;  // 需要分配的缓冲区个数
        map_size_ = mystl::max(static_cast<size_type>(DEQUE_MAP_INIT_SIZE), nNode + 2);
        try
        {
            map_ = create_map(map_size_);
        }
        catch (...)
        {
            map_ = nullptr;
            map_size_ = 0;
            throw;
        }

        // 让 nstart 和 nfinish 都指向 map_ 最中央的区域，方便向头尾扩充
        map_pointer nstart = map_ + (map_size_ - nNode) / 2;
        map_pointer nfinish = nstart + nNode - 1;
        try
        {
            create_buffer(nstart, nfinish);
        }
        catch (...)
        {
            map_allocator::deallocate(map_, map_size_);
            map_ = nullptr;
            map_size_ = 0;
            throw;
        }
        begin_.set_node(nstart);
        end_.set_node(nfinish);
        begin_.cur = begin_.first;
        end_.cur = end_.first + (nElem % buffer_size);
    }

    // fill_init 函数
    template <class T>
    void deque<T>::
        fill_init(size_type n, const value_type& value)
    {
        map_init(n);
        if (n != 0)
        {
            for (auto cur = begin_.node; cur < end_.node; ++cur)
            {
                mystl::uninitialized_fill(*cur, *cur + buffer_size, value);
            }
            mystl::uninitialized_fill(end_.first, end_.cur, value);
        }
    }

    // copy_init 函数
    template <class T>
    template <class IIter>
    void deque<T>::
    copy_init(IIter first, IIter last, input_iterator_tag)
    {
        const size_type n = mystl::distance(first, last);
        map_init(n);
        for (; first != last; ++first)
            emplace_back(*first);
    }

    template <class T>
    template <class FIter>
    void deque<T>::
        copy_init(FIter first, FIter last, forward_iterator_tag)
    {
        const size_type n = mystl::distance(first, last);
        map_init(n);
        for (auto cur = begin_.node; cur < end_.node; ++cur)
        {
            auto next = first;
            mystl::advance(next, buffer_size);
            mystl::uninitialized_copy(first, next, *cur);
            first = next;
        }
        mystl::uninitialized_copy(first, last, end_.first);
    }

    // fill_assign 函数
    template <class T>
    void deque<T>::
        fill_assign(size_type n, const value_type& value)
    {
        if (n > size())
        {
            mystl::fill(begin(), end(), value);
            insert(end(), n - size(), value);
        }
        else
        {
            erase(begin() + n, end());
            mystl::fill(begin(), end(), value);
        }
    }

    // copy_assign 函数
    template <class T>
    template <class IIter>
    void deque<T>::
        copy_assign(IIter first, IIter last, input_iterator_tag)
    {
        auto first1 = begin();
        auto last1 = end();
        for (; first != last && first1 != last1; ++first, ++first1)
        {
            *first1 = *first;
        }
        if (first1 != last1)
        {
            erase(first1, last1);
        }
        else
        {
            insert_dispatch(end_, first, last, input_iterator_tag{});
        }
    }

    template <class T>
    template <class FIter>
    void deque<T>::
        copy_assign(FIter first, FIter last, forward_iterator_tag)
    {
        const size_type len1 = size();
        const size_type len2 = mystl::distance(first, last);
        if (len1 < len2)
        {
            auto next = first;
            mystl::advance(next, len1);
            mystl::copy(first, next, begin_);
            insert_dispatch(end_, next, last, forward_iterator_tag{});
        }
        else
        {
            erase(mystl::copy(first, last, begin_), end_);
        }
    }

    // insert_aux 函数
    template <class T>
    template <class... Args>
    typename deque<T>::iterator
        deque<T>::
        insert_aux(iterator position, Args&& ...args)
    {
        const size_type elems_before = position - begin_;
        value_type value_copy = value_type(mystl::forward<Args>(args)...);
        if (elems_before < (size() / 2))
        { // 在前半段插入
            emplace_front(front());
            auto front1 = begin_;
            ++front1;
            auto front2 = front1;
            ++front2;
            position = begin_ + elems_before;
            auto pos = position;
            ++pos;
            mystl::copy(front2, pos, front1);
        }
        else
        { // 在后半段插入
            emplace_back(back());
            auto back1 = end_;
            --back1;
            auto back2 = back1;
            --back2;
            position = begin_ + elems_before;
            mystl::copy_backward(position, back2, back1);
        }
        *position = mystl::move(value_copy);
        return position;
    }

    // fill_insert 函数
    template <class T>
    void deque<T>::
        fill_insert(iterator position, size_type n, const value_type& value)
    {
        const size_type elems_before = position - begin_;
        const size_type len = size();
        auto value_copy = value;
        if (elems_before < (len / 2))
        {
            require_capacity(n, true);
            // 原来的迭代器可能会失效
            auto old_begin = begin_;
            auto new_begin = begin_ - n;
            position = begin_ + elems_before;
            try
            {
                if (elems_before >= n)
                {
                    auto begin_n = begin_ + n;
                    mystl::uninitialized_copy(begin_, begin_n, new_begin);
                    begin_ = new_begin;
                    mystl::copy(begin_n, position, old_begin);
                    mystl::fill(position - n, position, value_copy);
                }
                else
                {
                    mystl::uninitialized_fill(
                        mystl::uninitialized_copy(begin_, position, new_begin), begin_, value_copy);
                    begin_ = new_begin;
                    mystl::fill(old_begin, position, value_copy);
                }
            }
            catch (...)
            {
                if (new_begin.node != begin_.node)
                    destroy_buffer(new_begin.node, begin_.node - 1);
                throw;
            }
        }
        else
        {
            require_capacity(n, false);
            // 原来的迭代器可能会失效
            auto old_end = end_;
            auto new_end = end_ + n;
            const size_type elems_after = len - elems_before;
            position = end_ - elems_after;
            try
            {
                if (elems_after > n)
                {
                    auto end_n = end_ - n;
                    mystl::uninitialized_copy(end_n, end_, end_);
                    end_ = new_end;
                    mystl::copy_backward(position, end_n, old_end);
                    mystl::fill(position, position + n, value_copy);
                }
                else
                {
                    mystl::uninitialized_fill(end_, position + n, value_copy);
                    mystl::uninitialized_copy(position, end_, position + n);
                    end_ = new_end;
                    mystl::fill(position, old_end, value_copy);
                }
            }
            catch (...)
            {
                if (new_end.node != end_.node)
                    destroy_buffer(end_.node + 1, new_end.node);
                throw;
            }
        }
    }

    // copy_insert
    template <class T>
    template <class FIter>
    void deque<T>::
        copy_insert(iterator position, FIter first, FIter last, size_type n)
    {
        const size_type elems_before = position - begin_;
        auto len = size();
        if (elems_before < (len / 2))
        {
            require_capacity(n, true);
            // 原来的迭代器可能会失效
            auto old_begin = begin_;
            auto new_begin = begin_ - n;
            position = begin_ + elems_before;
            try
            {
                if (elems_before >= n)
                {
                    auto begin_n = begin_ + n;
                    mystl::uninitialized_copy(begin_, begin_n, new_begin);
                    begin_ = new_begin;
                    mystl::copy(begin_n, position, old_begin);
                    mystl::copy(first, last, position - n);
                }
                else
                {
                    auto mid = first;
                    mystl::advance(mid, n - elems_before);
                    mystl::uninitialized_copy(first, mid,
                        mystl::uninitialized_copy(begin_, position, new_begin));
                    begin_ = new_begin;
                    mystl::copy(mid, last, old_begin);
                }
            }
            catch (...)
            {
                if (new_begin.node != begin_.node)
                    destroy_buffer(new_begin.node, begin_.node - 1);
                throw;
            }
        }
        else
        {
            require_capacity(n, false);
            // 原来的迭代器可能会失效
            auto old_end = end_;
            auto new_end = end_ + n;
            const auto elems_after = len - elems_before;
            position = end_ - elems_after;
            try
            {
                if (elems_after > n)
                {
                    auto end_n = end_ - n;
                    mystl::uninitialized_copy(end_n, end_, end_);
                    end_ = new_end;
                    mystl::copy_backward(position, end_n, old_end);
                    mystl::copy(first, last, position);
                }
                else
                {
                    auto mid = first;
                    mystl::advance(mid, elems_after);
                    mystl::uninitialized_copy(position, end_,
                        mystl::uninitialized_copy(mid, last, end_));
                    end_ = new_end;
                    mystl::copy(first, mid, position);
                }
            }
            catch (...)
            {
                if (new_end.node != end_.node)
                    destroy_buffer(end_.node + 1, new_end.node);
                throw;
            }
        }
    }

    // insert_dispatch 函数
    template <class T>
    template <class IIter>
    void deque<T>::
        insert_dispatch(iterator position, IIter first, IIter last, input_iterator_tag)
    {
        if (last <= first)  return;
        const size_type n = mystl::distance(first, last);
        const size_type elems_before = position - begin_;
        if (elems_before < (size() / 2))
        {
            require_capacity(n, true);
        }
        else
        {
            require_capacity(n, false);
        }
        position = begin_ + elems_before;
        auto cur = --last;
        for (size_type i = 0; i < n; ++i, --cur)
        {
            insert(position, *cur);
        }
    }

    template <class T>
    template <class FIter>
    void deque<T>::
        insert_dispatch(iterator position, FIter first, FIter last, forward_iterator_tag)
    {
        if (last <= first)  return;
        const size_type n = mystl::distance(first, last);
        if (position.cur == begin_.cur)
        {
            require_capacity(n, true);
            auto new_begin = begin_ - n;
            try
            {
                mystl::uninitialized_copy(first, last, new_begin);
                begin_ = new_begin;
            }
            catch (...)
            {
                if (new_begin.node != begin_.node)
                    destroy_buffer(new_begin.node, begin_.node - 1);
                throw;
            }
        }
        else if (position.cur == end_.cur)
        {
            require_capacity(n, false);
            auto new_end = end_ + n;
            try
            {
                mystl::uninitialized_copy(first, last, end_);
                end_ = new_end;
            }
            catch (...)
            {
                if (new_end.node != end_.node)
                    destroy_buffer(end_.node + 1, new_end.node);
                throw;
            }
        }
        else
        {
            copy_insert(position, first, last, n);
        }
    }

    // require_capacity 函数
    template <class T>
    void deque<T>::require_capacity(size_type n, bool front)
    {
        if (front && (static_cast<size_type>(begin_.cur - begin_.first) < n))
        {
            const size_type need_buffer = (n - (begin_.cur - begin_.first)) / buffer_size + 1;
            if (need_buffer > static_cast<size_type>(begin_.node - map_))
            {
                reallocate_map_at_front(need_buffer);
                return;
            }
            create_buffer(begin_.node - need_buffer, begin_.node - 1);
        }
        else if (!front && (static_cast<size_type>(end_.last - end_.cur - 1) < n))
        {
            const size_type need_buffer = (n - (end_.last - end_.cur - 1)) / buffer_size + 1;
            if (need_buffer > static_cast<size_type>((map_ + map_size_) - end_.node - 1))
            {
                reallocate_map_at_back(need_buffer);
                return;
            }
            create_buffer(end_.node + 1, end_.node + need_buffer);
        }
    }

    // reallocate_map_at_front 函数
    template <class T>
    void deque<T>::reallocate_map_at_front(size_type need_buffer)
    {
        const size_type new_map_size = mystl::max(map_size_ << 1,
            map_size_ + need_buffer + DEQUE_MAP_INIT_SIZE);
        map_pointer new_map = create_map(new_map_size);
        const size_type old_buffer = end_.node - begin_.node + 1;
        const size_type new_buffer = old_buffer + need_buffer;

        // 另新的 map 中的指针指向原来的 buffer，并开辟新的 buffer
        auto begin = new_map + (new_map_size - new_buffer) / 2;
        auto mid = begin + need_buffer;
        auto end = mid + old_buffer;
        create_buffer(begin, mid - 1);
        for (auto begin1 = mid, begin2 = begin_.node; begin1 != end; ++begin1, ++begin2)
            *begin1 = *begin2;

        // 更新数据
        map_allocator::deallocate(map_, map_size_);
        map_ = new_map;
        map_size_ = new_map_size;
        begin_ = iterator(*mid + (begin_.cur - begin_.first), mid);
        end_ = iterator(*(end - 1) + (end_.cur - end_.first), end - 1);
    }

    // reallocate_map_at_back 函数
    template <class T>
    void deque<T>::reallocate_map_at_back(size_type need_buffer)
    {
        const size_type new_map_size = mystl::max(map_size_ << 1,
            map_size_ + need_buffer + DEQUE_MAP_INIT_SIZE);
        map_pointer new_map = create_map(new_map_size);
        const size_type old_buffer = end_.node - begin_.node + 1;
        const size_type new_buffer = old_buffer + need_buffer;

        // 另新的 map 中的指针指向原来的 buffer，并开辟新的 buffer
        auto begin = new_map + ((new_map_size - new_buffer) / 2);
        auto mid = begin + old_buffer;
        auto end = mid + need_buffer;
        for (auto begin1 = begin, begin2 = begin_.node; begin1 != mid; ++begin1, ++begin2)
            *begin1 = *begin2;
        create_buffer(mid, end - 1);

        // 更新数据
        map_allocator::deallocate(map_, map_size_);
        map_ = new_map;
        map_size_ = new_map_size;
        begin_ = iterator(*begin + (begin_.cur - begin_.first), begin);
        end_ = iterator(*(mid - 1) + (end_.cur - end_.first), mid - 1);
    }

    // 重载比较操作符
    template <class T>
    bool operator==(const deque<T>& lhs, const deque<T>& rhs)
    {
        return lhs.size() == rhs.size() &&
            mystl::equal(lhs.begin(), lhs.end(), rhs.begin());
    }

    template <class T>
    bool operator<(const deque<T>& lhs, const deque<T>& rhs)
    {
        return mystl::lexicographical_compare(
            lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
    }

    template <class T>
    bool operator!=(const deque<T>& lhs, const deque<T>& rhs)
    {
        return !(lhs == rhs);
    }

    template <class T>
    bool operator>(const deque<T>& lhs, const deque<T>& rhs)
    {
        return rhs < lhs;
    }

    template <class T>
    bool operator<=(const deque<T>& lhs, const deque<T>& rhs)
    {
        return !(rhs < lhs);
    }

    template <class T>
    bool operator>=(const deque<T>& lhs, const deque<T>& rhs)
    {
        return !(lhs < rhs);
    }

    // 重载 mystl 的 swap
    template <class T>
    void swap(deque<T>& lhs, deque<T>& rhs)
    {
        lhs.swap(rhs);
    }

}

#endif // !MYTINYSTL_DEQUE_H