stl_deque.h

//
//  stl_deque.h
//  mini-stl
//
//  Created by cz-mac on 2022/1/1.
//

#ifndef stl_deque_h
#define stl_deque_h

#include "allocator.h"
#include "deque_iterator.h"
#include "uninitialized.h"

namespace MiniSTL {

template <class T, class Alloc = simpleAlloc<T>>
class deque {
public:  // alias declarations
    typedef T value_type;
    typedef T *  pointer;
    typedef T& reference;
    typedef const T& const_reference ;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef __deque_iterator<T, T &, T *> iterator;
    typedef MiniSTL::__reverse_iterator<iterator> reverse_iterator;
    typedef __deque_iterator<T, const T &, const T *> const_iterator;
    typedef MiniSTL::__reverse_iterator<const_iterator> const_reverse_iterator;

private:  // internal alias declarations
    typedef pointer * map_pointer;
    typedef simpleAlloc<value_type> node_allocator;
    typedef simpleAlloc<pointer> map_allocator;

private:              // data member
    iterator start;   // 第一个节点
    iterator finish;  // 最后一个节点
    map_pointer map;  // 指向节点的指针
    size_type map_size;

private:  // aux_interface for node
    value_type *allocate_node() {
        return node_allocator::allocate(__deque_buf_size(sizeof(value_type)));
    }
    void deallocate_node(value_type *p) {
        node_allocator::deallocate(p, __deque_buf_size(sizeof(value_type)));
    }
    void create_nodes(map_pointer, map_pointer);
    void destroy_nodes(map_pointer, map_pointer);

private:  // aux_interface for map
    void initialize_map(size_type);
    void deallocate_map(map_pointer p, size_type n) {
        map_allocator::deallocate(p, n);
    }
    void reallocate_map(size_type, bool);
    void reserve_map_at_front(size_type nodes_to_add = 1);
    void reserve_map_at_back(size_type nodes_to_add = 1);
    iterator reserve_elements_at_front(size_type);
    iterator reserve_elements_at_back(size_type);
    void new_elements_at_front(size_type);
    void new_elements_at_back(size_type);

private:  // aux_interface for ctor
    size_type initial_map_size() const noexcept { return 8U; }
    size_type buffer_size() const noexcept { return iterator::buffer_size(); }
    void fill_initialize(const value_type &);
    template <class Integer>
    void initialize_dispatch(Integer n, Integer val, _true_type) {
        initialize_map(static_cast<size_type>(n));
        fill_initialize(static_cast<value_type>(val));
    }
    template <class InputIterator>
    void initialize_dispatch(InputIterator first, InputIterator last,
                             _false_type) {
        range_initialize(first, last, iterator_category_t<InputIterator>());
    }
    template <class InputIterator>
    void range_initialize(InputIterator first, InputIterator last,
                          input_iterator_tag);
    template <class ForwardIterator>
    void range_initialize(ForwardIterator first, ForwardIterator last,
                          forward_iterator_tag);

public:  // ctor && dtor
    deque() : start(), finish(), map(nullptr), map_size(0) {
        initialize_map(0);
    }
    explicit deque(size_type n) : start(), finish(), map(nullptr), map_size(0) {
        initialize_map(n);
        fill_initialize(value_type());
    }
    deque(size_type n, const value_type &val)
        : start(), finish(), map(nullptr), map_size(0) {
        initialize_map(n);
        fill_initialize(val);
    }
    template <class InputIterator>
    deque(InputIterator first, InputIterator last) {
        initialize_dispatch(first, last, _is_integer_t<InputIterator>());
    }
    deque(std::initializer_list<value_type> ils) {
        range_initialize(ils.begin(), ils.end(), random_access_iterator_tag());
    }
    ~deque();

public:  // copy operations
    deque(const deque &rhs) {
        initialize_map(rhs.size());
        MiniSTL::uninitialized_copy(rhs.begin(), rhs.end(), start);
    }
    deque &operator=(const deque &);

public:  // move operations
    deque(deque &&);
    deque &operator=(deque &&) noexcept;

public:  // getter
    const_iterator begin() const noexcept { return start; }
    const_iterator end() const noexcept { return finish; }
    const_iterator cbegin() const noexcept { return start; }
    const_iterator cend() const noexcept { return finish; }
    const_reverse_iterator crbegin() const noexcept {
        return const_reverse_iterator(finish);
    }
    const_reverse_iterator crend() const noexcept {
        return const_reverse_iterator(start);
    }
    const_reference operator[](size_type n) const noexcept {
        return start[static_cast<difference_type>(n)];
    }
    const_reference front() const noexcept { return *start; }
    const_reference back() const noexcept { return *(finish - 1); }
    size_type size() const noexcept { return finish - start; }
    bool empty() const noexcept { return finish == start; }

public:  // setter
    iterator begin() noexcept { return start; }
    iterator end() noexcept { return finish; }
    reverse_iterator rbegin() noexcept { return reverse_iterator(finish); }
    reverse_iterator rend() noexcept { return reverse_iterator(start); }
    reference operator[](size_type n) {
        return start[static_cast<difference_type>(n)];
    }
    reference front() noexcept { return *start; }
    reference back() noexcept { return *(finish - 1); }

private:  // aux_interface for push && pop
    void push_back_aux(const value_type &);
    void push_front_aux(const value_type &);
    void pop_back_aux();
    void pop_front_aux();

public:  // push && pop
    void push_back(const value_type &);
    void push_front(const value_type &);
    void pop_back();
    void pop_front();

private:  // aux_interface for assign
    void fill_assign(size_type, const value_type &);
    template <class Integer>
    void assign_dispatch(Integer n, Integer val, _true_type) {
        fill_assign(static_cast<size_type>(n), static_cast<value_type>(val));
    }
    template <class InputIterator>
    void assign_dispatch(InputIterator first, InputIterator last, _false_type) {
        assign_aux(first, last, iterator_category_t<InputIterator>());
    }
    template <class InputIterator>
    void assign_aux(InputIterator, InputIterator, input_iterator_tag);
    template <class ForwardIterator>
    void assign_aux(ForwardIterator, ForwardIterator, forward_iterator_tag);

public:  // assign
    void assign(size_type n, const value_type &val) { fill_assign(n, val); }
    void assign(std::initializer_list<value_type> ils) {
        assign(ils.begin(), ils.end());
    }
    template <class InputIterator>
    void assign(InputIterator first, InputIterator last) {
        assign_dispatch(first, last, _is_integer_t<InputIterator>());
    }
    deque &operator=(std::initializer_list<value_type> ils) {
        assign(ils.begin(), ils.end());
        return *this;
    }

private:  // aux_interface for insert
    void fill_insert(iterator, size_type, const value_type &);
    template <class Integer>
    void insert_dispatch(iterator pos, Integer n, Integer val, _true_type) {
        fill_insert(pos, static_cast<size_type>(n),
                    static_cast<value_type>(val));
    }
    template <class InputIterator>
    void insert_dispatch(iterator pos, InputIterator first, InputIterator last,
                         _false_type) {
        range_insert_aux(pos, first, last,
                         iterator_category_t<InputIterator>());
    }
    template <class InputIterator>
    void range_insert_aux(iterator, InputIterator, InputIterator,
                          input_iterator_tag);
    template <class ForwardIterator>
    void range_insert_aux(iterator, ForwardIterator, ForwardIterator,
                          forward_iterator_tag);
    iterator insert_aux(iterator, const value_type &);
    void insert_aux(iterator, size_type, const value_type &);
    template <class ForwardIterator>
    void insert_aux(iterator, ForwardIterator, ForwardIterator, size_type);

public:  // insert
    iterator insert(iterator, const value_type &);
    iterator insert(iterator pos) { return insert(pos, value_type()); }
    void insert(iterator pos, size_type n, const value_type &val) {
        fill_insert(pos, n, val);
    }
    template <class InputIterator>
    void insert(iterator pos, InputIterator first, InputIterator last) {
        insert_dispatch(pos, first, last, _is_integer_t<InputIterator>());
    }

public:  // erase
    iterator erase(iterator);
    iterator erase(iterator, iterator);
    void clear();

public:  // resize
    void resize(size_type, const value_type &);
    void resize(size_type new_size) { resize(new_size, value_type()); }

public:  // swap
    void swap(deque &rhs) noexcept;
};

template <class T, class Alloc>
void deque<T, Alloc>::create_nodes(map_pointer nstart, map_pointer nfinish) {
    map_pointer cur;
    try {
        // 为每一个节点配置空间
        for (cur = nstart; cur <= nfinish; ++cur) *cur = allocate_node();
    } catch (std::exception &) {
        destroy_nodes(nstart, cur);
        throw;
    }
}

template <class T, class Alloc>
void deque<T, Alloc>::destroy_nodes(map_pointer nstart, map_pointer nfinish) {
    for (map_pointer n = nstart; n < nfinish; ++n) deallocate_node(*n);
}

template <class T, class Alloc>
void deque<T, Alloc>::initialize_map(size_type n) {
    // 所需节点数（整除则多配置一个）
    size_type num_nodes = n / buffer_size() + 1;
    // 一个map至少管理8个节点，至多管理num_nodes+2个
    map_size = MiniSTL::max(initial_map_size(), num_nodes + 2);
    map = map_allocator::allocate(map_size);
    // 令nstart与nfinish指向map所拥有的全部node的中部,以便日后扩充头尾
    map_pointer nstart = map + (map_size - num_nodes) / 2;
    map_pointer nfinish = nstart + num_nodes;
    try {
        create_nodes(nstart, nfinish);
    } catch (std::exception &) {
        deallocate_map(map, map_size);
        map = nullptr;
        map_size = 0;
        throw;
    }
    start.set_node(nstart);
    finish.set_node(nfinish - 1);
    start.cur = start.first;
    finish.cur =
        finish.first +
        n % buffer_size();  // 若n%buffer_size==0,会多配置一个节点，此时cur指向该节点头部
}

template <class T, class Alloc>
void deque<T, Alloc>::fill_initialize(const value_type &val) {
    map_pointer cur;
    try {
        // 为每个缓冲区设定初值
        for (cur = start.node; cur < finish.node; ++cur)
            MiniSTL::uninitialized_fill(*cur, *cur + buffer_size(), val);
        // 最后一个缓冲区只设定至需要处
        MiniSTL::uninitialized_fill(finish.first, finish.cur, val);
    } catch (std::exception &) {
        destroy(start, iterator(*cur, cur));
        throw;
    }
}

template <class T, class Alloc>
template <class InputIterator>
void deque<T, Alloc>::range_initialize(InputIterator first, InputIterator last,
                                       input_iterator_tag) {
    initialize_map(0);
    try {
        for (; first != last; ++first) push_back(*first);
    } catch (std::exception &) {
        clear();
        throw;
    }
}

template <class T, class Alloc>
template <class ForwardIterator>
void deque<T, Alloc>::range_initialize(ForwardIterator first,
                                       ForwardIterator last,
                                       forward_iterator_tag) {
    size_type n = MiniSTL::distance(first, last);
    initialize_map(n);

    map_pointer cur_node;
    try {
        for (cur_node = start.node; cur_node < finish.node; ++cur_node) {
            ForwardIterator mid = first;
            MiniSTL::advance(mid, buffer_size());
            MiniSTL::uninitialized_copy(first, last, *cur_node);
            first = mid;
        }
        MiniSTL::uninitialized_copy(first, last, finish.first);
    } catch (std::exception &) {
        destroy(start, iterator(*cur_node, cur_node));
        throw;
    }
}

template <class T, class Alloc>
inline void deque<T, Alloc>::reallocate_map(size_type nodes_to_add,
                                            bool add_at_front) {
    size_type old_num_nodes = finish.node - start.node + 1;
    size_type new_num_nodes = old_num_nodes + nodes_to_add;

    map_pointer new_nstart;
    if (map_size > 2 * new_num_nodes) {
        // 某一端出现失衡，因此释放存储区完成重新中央分配，
        // 规定新的nstart，若添加在前端则向后多移动n个单位
        new_nstart = map + (map_size - new_num_nodes) / 2 +
                     (add_at_front ? nodes_to_add : 0);
        if (new_nstart < start.node)  // 整体前移
            MiniSTL::copy(start.node, finish.node + 1, new_nstart);
        else  // 整体后移
            MiniSTL::copy_backward(start.node, finish.node + 1,
                                   new_nstart + old_num_nodes);
    } else {
        size_type new_map_size =
            map_size + MiniSTL::max(map_size, nodes_to_add) + 2;
        // 分配新空间
        map_pointer new_map = map_allocator::allocate(new_map_size);
        new_nstart = new_map + (new_map_size - new_num_nodes) / 2 +
                     (add_at_front ? nodes_to_add : 0);
        // 拷贝原有内容
        MiniSTL::copy(start.node, finish.node + 1, new_nstart);
        // 释放原map
        map_allocator::deallocate(map, map_size);
        // 重新设定map
        map = new_map;
        map_size = new_map_size;
    }

    //设定start与finish
    start.set_node(new_nstart);
    finish.set_node(new_nstart + old_num_nodes -
                    1);  // 注意并非new_num,接下来的设定转交其他函数处理
}

template <class T, class Alloc>
inline deque<T, Alloc> &deque<T, Alloc>::operator=(const deque &rhs) {
    const size_type len = size();
    if (&rhs != this) {
        if (len >= rhs.size())
            erase(MiniSTL::copy(rhs.begin(), rhs.end(), start), finish);
        else {
            const_iterator mid =
                rhs.begin() + static_cast<difference_type>(len);
            MiniSTL::copy(rhs.begin(), mid, start);
            insert(finish, mid, rhs.end());
        }
    }
    return *this;
}

template <class T, class Alloc>
inline void deque<T, Alloc>::reserve_map_at_back(size_type nodes_to_add) {
    // map_size-(finish.node-map+1) == 后端剩余node个数
    if (nodes_to_add + 1 > map_size - (finish.node - map))
        reallocate_map(nodes_to_add, false);
}

template <class T, class Alloc>
inline void deque<T, Alloc>::reserve_map_at_front(size_type nodes_to_add) {
    // start.node-map==前端剩余node个数
    if (nodes_to_add > static_cast<size_type>(start.node - map))
        reallocate_map(nodes_to_add, true);
}

template <class T, class Alloc>
inline typename deque<T, Alloc>::iterator
deque<T, Alloc>::reserve_elements_at_front(size_type n) {
    size_type vacancies = start.cur - start.first;
    if (n > vacancies) new_elements_at_front(n - vacancies);
    return start - static_cast<difference_type>(n);
}

template <class T, class Alloc>
inline typename deque<T, Alloc>::iterator
deque<T, Alloc>::reserve_elements_at_back(size_type n) {
    size_type vacancies = finish.last - finish.cur - 1;
    if (n > vacancies) new_elements_at_back(n - vacancies);
    return finish + static_cast<difference_type>(n);
}

template <class T, class Alloc>
void deque<T, Alloc>::new_elements_at_front(size_type new_elems) {
    size_type new_nodes = (new_elems + buffer_size() - 1) / buffer_size();
    reserve_map_at_front(new_nodes);
    size_type i;
    try {
        for (i = 1; i <= new_nodes; ++i) *(start.node - i) = allocate_node();
    } catch (std::exception &) {
        for (size_type j = 1; j < i; ++j) deallocate_node(*(start.node - j));
        throw;
    }
}

template <class T, class Alloc>
void deque<T, Alloc>::new_elements_at_back(size_type new_elems) {
    size_type new_nodes = (new_elems + buffer_size() - 1) / buffer_size();
    reserve_map_at_back(new_nodes);
    size_type i;
    try {
        for (i = 1; i <= new_nodes; ++i) *(finish.node + i) = allocate_node();
    } catch (std::exception &) {
        for (size_type j = 1; j < i; ++j) deallocate_node(*(finish.node + j));
        throw;
    }
}

template <class T, class Alloc>
inline void deque<T, Alloc>::push_back_aux(const value_type &value) {
    value_type value_copy = value;
    reserve_map_at_back();                 // 若符合条件则重新更换map
    *(finish.node + 1) = allocate_node();  // 配置新节点
    try {
        construct(finish.cur, value_copy);
        finish.set_node(finish.node + 1);
        finish.cur = finish.first;  // 更新finish.cur为当前first
    } catch (std::exception &) {
        deallocate_node(*(finish.node + 1));
        throw;
    }
}

template <class T, class Alloc>
inline void deque<T, Alloc>::push_front_aux(const value_type &value) {
    value_type value_copy = value;
    reserve_map_at_front();               // 若符合条件则重新更换map
    *(start.node - 1) = allocate_node();  // 配置新节点
    try {
        start.set_node(start.node - 1);
        start.cur = start.last - 1;
        construct(start.cur, value);
    } catch (std::exception &) {
        ++start;
        deallocate_node(*(start.node - 1));
        throw;
    }
}

template <class T, class Alloc>
inline void deque<T, Alloc>::pop_back_aux() {
    node_allocator::deallocate(finish.first);
    finish.set_node(finish.node - 1);
    finish.cur = finish.last - 1;
    destroy(finish.cur);
}

template <class T, class Alloc>
inline void deque<T, Alloc>::pop_front_aux() {
    destroy(start.cur);
    node_allocator::deallocate(start.first);
    start.set_node(finish.node + 1);
    start.cur = start.first;
}

template <class T, class Alloc>
typename deque<T, Alloc>::iterator deque<T, Alloc>::insert_aux(
    iterator pos, const value_type &val) {
    difference_type index = pos - start;  // 插入点之前的元素个数
    value_type value_copy = val;
    if (static_cast<size_type>(index) < size() / 2) {  // 前移
        // 插图见书
        push_front(front());  // 最前端加入哨兵以作标识，注意此时start发生了改变
        iterator front1 = start;
        ++front1;  // 复制后自增效率较高
        iterator front2 = front1;
        ++front2;
        pos = start + index;
        iterator pos1 = pos;
        ++pos1;
        MiniSTL::copy(front2, pos1, front1);  // 移动元素
    } else {
        // 过程类似于上
        push_back(back());
        iterator back1 = finish;
        --back1;
        iterator back2 = back1;
        --back2;
        pos = start + index;
        MiniSTL::copy_backward(pos, back2, back1);
    }
    *pos = value_copy;
    return pos;
}

template <class T, class Alloc>
void deque<T, Alloc>::fill_insert(iterator pos, size_type n,
                                  const value_type &val) {
    if (pos.cur == start.cur) {
        iterator new_start = reserve_elements_at_front(n);
        try {
            MiniSTL::uninitialized_fill(new_start, start, val);
            start = new_start;
        } catch (std::exception &) {
            destroy_nodes(new_start.node, start.node);
        }
    } else if (pos.cur == finish.cur) {
        iterator new_finish = reserve_elements_at_back(n);
        try {
            MiniSTL::uninitialized_fill(finish, new_finish, val);
            finish = new_finish;
        } catch (std::exception &) {
            destroy_nodes(finish.node + 1, new_finish.node + 1);
        }
    } else
        insert_aux(pos, n, val);
}

template <class T, class Alloc>
void deque<T, Alloc>::insert_aux(iterator pos, size_type n,
                                 const value_type &val) {
    const difference_type elems_before = pos - start;
    size_type length = size();
    value_type value_copy = val;
    if (elems_before < static_cast<difference_type>(length / 2)) {
        iterator new_start = reserve_elements_at_front(n);
        iterator old_start = start;
        pos = start + elems_before;
        try {
            if (elems_before >= static_cast<difference_type>(n)) {
                iterator start_n = start + static_cast<difference_type>(n);
                MiniSTL::uninitialized_copy(start, start_n, new_start);
                start = new_start;
                MiniSTL::copy(start_n, pos, old_start);
                MiniSTL::fill(pos - static_cast<difference_type>(n), pos,
                              value_copy);
            } else {
                MiniSTL::uninitialized_copy_fill(start, pos, new_start, start,
                                                 value_copy);  // extensions
                start = new_start;
                MiniSTL::fill(old_start, pos, val);
            }
        } catch (std::exception &) {
            destroy_nodes(new_start.node, start.node);
            throw;
        }
    } else {
        iterator new_finish = reserve_elements_at_back(n);
        iterator old_finish = finish;
        const difference_type elems_after =
            static_cast<difference_type>(length) - elems_before;
        pos = finish - elems_after;
        try {
            if (elems_after >= static_cast<difference_type>(n)) {
                iterator finish_n = finish - static_cast<difference_type>(n);
                MiniSTL::uninitialized_copy(finish_n, finish, finish);
                finish = new_finish;
                MiniSTL::copy_backward(pos, finish_n, old_finish);
                MiniSTL::fill(pos, pos + static_cast<difference_type>(n),
                              value_copy);
            } else {
                MiniSTL::uninitialized_fill_copy(
                    finish, pos + static_cast<difference_type>(n), value_copy,
                    pos,
                    finish);  // extensions
                finish = new_finish;
                MiniSTL::fill(pos, old_finish, value_copy);
            }
        } catch (std::exception &) {
            destroy_nodes(finish.node + 1, new_finish.node + 1);
            throw;
        }
    }
}

template <class T, class Alloc>
template <class ForwardIterator>
void deque<T, Alloc>::insert_aux(iterator pos, ForwardIterator first,
                                 ForwardIterator last, size_type n) {
    const difference_type elems_before = pos - start;
    size_type length = size();
    if (elems_before < static_cast<difference_type>(length / 2)) {
        iterator new_start = reserve_elements_at_front(n);
        iterator old_start = start;
        pos = start + elems_before;
        try {
            if (elems_before >= static_cast<difference_type>(n)) {
                iterator start_n = start + static_cast<difference_type>(n);
                MiniSTL::uninitialized_copy(start, start_n, new_start);
                start = new_start;
                MiniSTL::copy(start_n, pos, old_start);
                MiniSTL::copy(first, last,
                              pos - static_cast<difference_type>(n));
            } else {
                ForwardIterator mid = first;
                MiniSTL::advance(
                    mid, static_cast<difference_type>(n) - elems_before);
                MiniSTL::uninitialized_copy_copy(start, pos, first, mid,
                                                 new_start);  // extensions
                start = new_start;
                MiniSTL::copy(mid, last, old_start);
            }
        } catch (std::exception &) {
            destroy_nodes(new_start.node, start.node);
            throw;
        }
    } else {
        iterator new_finish = reserve_elements_at_back(n);
        iterator old_finish = finish;
        const difference_type elems_after =
            static_cast<difference_type>(length) - elems_before;
        pos = finish - elems_after;
        try {
            if (elems_after >= static_cast<difference_type>(n)) {
                iterator finish_n = finish - static_cast<difference_type>(n);
                MiniSTL::uninitialized_copy(finish_n, finish, finish);
                finish = new_finish;
                MiniSTL::copy_backward(pos, finish_n, old_finish);
                MiniSTL::copy(first, last, pos);
            } else {
                ForwardIterator mid = first;
                MiniSTL::advance(mid, elems_after);
                MiniSTL::uninitialized_copy_copy(mid, last, pos, finish,
                                                 finish);  // extensions
                finish = new_finish;
                MiniSTL::copy(first, mid, pos);
            }
        } catch (std::exception &) {
            destroy_nodes(finish.node + 1, new_finish.node + 1);
            throw;
        }
    }
}

template <class T, class Alloc>
template <class InputIterator>
void deque<T, Alloc>::range_insert_aux(iterator pos, InputIterator first,
                                       InputIterator last, input_iterator_tag) {
    MiniSTL::copy(first, last, inserter(*this, pos));  // 插入迭代器
}

template <class T, class Alloc>
template <class ForwardIterator>
void deque<T, Alloc>::range_insert_aux(iterator pos, ForwardIterator first,
                                       ForwardIterator last,
                                       forward_iterator_tag) {
    size_type n = MiniSTL::distance(first, last);
    if (pos.cur == start.cur) {
        iterator new_start = reserve_elements_at_front(n);
        try {
            MiniSTL::uninitialized_copy(first, last, new_start);
            start = new_start;
        } catch (std::exception &) {
            destroy_nodes(new_start.node, start.node);
            throw;
        }
    } else if (pos.cur == finish.cur) {
        iterator new_finish = reserve_elements_at_back(n);
        try {
            MiniSTL::uninitialized_copy(first, last, finish);
            finish = new_finish;
        } catch (std::exception &) {
            destroy_nodes(finish.node + 1, new_finish.node + 1);
            throw;
        }
    } else
        insert_aux(pos, first, last, n);
}

template <class T, class Alloc>
inline deque<T, Alloc>::deque(deque &&rhs) {
    initialize_map(0);
    if (rhs.map) {
        swap(rhs);
    }
}

template <class T, class Alloc>
deque<T, Alloc> &deque<T, Alloc>::operator=(deque &&rhs) noexcept {
    clear();
    swap(rhs);
    return *this;
}

template <class T, class Alloc>
inline deque<T, Alloc>::~deque() {
    destroy(start, finish);
    if (map) {
        destroy_nodes(start.node,
                      finish.node + 1);  // 也需要destroy finish.node
        deallocate_map(map, map_size);
    }
}

template <class T, class Alloc>
inline void deque<T, Alloc>::push_back(const value_type &value) {
    // finish的cur指向最后一个元素的下一个位置，因此if语句表征至少还有一个备用空间
    if (finish.cur != finish.last - 1) {
        construct(finish.cur, value);
        ++finish.cur;
    } else
        // 最终缓冲区已无或仅剩一个空间（我认为必然为仅剩一个空间的状态）
        push_back_aux(value);
}

template <class T, class Alloc>
inline void deque<T, Alloc>::push_front(const value_type &value) {
    if (start.cur != start.first) {
        construct(start.cur - 1, value);
        --start.cur;
    } else
        push_front_aux(value);
}

template <class T, class Alloc>
inline void deque<T, Alloc>::pop_back() {
    if (finish.cur != finish.first) {
        // 缓冲区至少存在一个元素
        --finish.cur;
        destroy(finish.cur);
    } else
        pop_back_aux();
}

template <class T, class Alloc>
inline void deque<T, Alloc>::pop_front() {
    if (start.cur != start.last - 1) {
        destroy(start.cur);
        ++start.cur;
    } else
        pop_front_aux();
}

template <class T, class Alloc>
inline void deque<T, Alloc>::clear() {
    // 清空所有node，保留唯一缓冲区（需要注意的是尽管map可能存有更多节点，但有[start,finish]占据内存
    for (map_pointer node = start.node + 1; node < finish.node;
         ++node) {                              //内部均存有元素
        destroy(*node, *node + buffer_size());  //析构所有元素
        node_allocator::deallocate(*node, buffer_size());
    }
    if (start.node != finish.node) {  // 存在头尾两个缓冲区
        // 析构其中所有元素
        destroy(start.cur, start.last);
        destroy(finish.first, finish.cur);
        // 保存头部，释放尾部
        node_allocator::deallocate(finish.first, buffer_size());
    } else
        destroy(start.cur, finish.cur);  // 利用finish.cur标记末尾
    finish = start;
}

template <class T, class Alloc>
typename deque<T, Alloc>::iterator deque<T, Alloc>::erase(iterator pos) {
    iterator next = pos + 1;
    difference_type index = pos - start;  // 清除点前的元素个数
    if (index < size() / 2) {             // 后移开销较低
        MiniSTL::copy_backward(start, pos, pos);
        pop_front();
    } else {
        MiniSTL::copy(next, finish, pos);
        pop_back();
    }
    return start + index;
}

template <class T, class Alloc>
typename deque<T, Alloc>::iterator deque<T, Alloc>::erase(iterator first,
                                                          iterator last) {
    if (first == start && last == finish) {
        clear();
        return finish;
    } else {
        difference_type n = last - first;              // 清除区间长度
        difference_type elems_before = first - start;  // 前方元素个数
        if (elems_before < (size() - n) / 2) {         // 后移开销较低
            MiniSTL::copy_backward(start, first, last);
            iterator new_start = start + n;  // 标记新起点
            destroy(start, new_start);       // 析构多余元素
            // 释放多余缓冲区
            for (map_pointer cur = start.node; cur < new_start.node; ++cur)
                node_allocator::deallocate(*cur, buffer_size());
            start = new_start;
        } else {  // 前移开销较低
            MiniSTL::copy(last, finish, first);
            iterator new_finish = finish - n;  // 标记末尾
            destroy(new_finish, finish);
            // 释放多余缓冲区
            for (map_pointer cur = new_finish.node + 1; cur <= finish.node;
                 ++cur)
                node_allocator::deallocate(*cur, buffer_size());
            finish = new_finish;
        }
        return start + elems_before;
    }
}

template <class T, class Alloc>
typename deque<T, Alloc>::iterator deque<T, Alloc>::insert(
    iterator pos, const value_type &value) {
    if (pos.cur == start.cur) {
        push_front(value);
        return start;
    } else if (pos.cur == finish.cur) {
        push_back(value);
        iterator temp = finish - 1;
        return temp;
    } else
        return insert_aux(pos, value);
}

template <class T, class Alloc>
void deque<T, Alloc>::fill_assign(size_type n, const value_type &val) {
    if (n > size()) {
        MiniSTL::fill(begin(), end(), val);
        insert(end(), n - size(), val);
    } else {
        erase(begin() + n, end());
        MiniSTL::fill(begin(), end(), val);
    }
}

template <class T, class Alloc>
template <class InputIterator>
void deque<T, Alloc>::assign_aux(InputIterator first, InputIterator last,
                                 input_iterator_tag) {
    iterator cur = start;
    for (; first != last && cur != finish; ++cur, ++first) *cur = *first;
    if (first == last)
        erase(cur, finish);
    else
        insert(cur, first, last);
}

template <class T, class Alloc>
template <class ForwardIterator>
void deque<T, Alloc>::assign_aux(ForwardIterator first, ForwardIterator last,
                                 forward_iterator_tag) {
    size_type len = MiniSTL::distance(first, last);
    if (len > size()) {
        ForwardIterator mid = first;
        MiniSTL::advance(mid, size());
        MiniSTL::copy(first, mid, start);
        insert(end(), mid, last);
    } else
        erase(MiniSTL::copy(first, last, start), finish);
}

template <class T, class Alloc>
void deque<T, Alloc>::resize(size_type new_size, const value_type &val) {
    const size_type len = size();
    if (new_size < len)
        erase(start + new_size, finish);
    else
        insert(finish, new_size - len, val);
}

template <class T, class Alloc>
void deque<T, Alloc>::swap(deque &rhs) noexcept {
    MiniSTL::swap(start, rhs.start);
    MiniSTL::swap(finish, rhs.finish);
    MiniSTL::swap(map, rhs.map);
    MiniSTL::swap(map_size, rhs.map_size);
}

template <class T, class Alloc>
inline bool operator==(const deque<T, Alloc> &lhs, const deque<T, Alloc> &rhs) {
    return lhs.size() == rhs.size() &&
           MiniSTL::equal(lhs.begin(), lhs.end(), rhs.begin());
}

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

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

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

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

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

template <class T, class Alloc>
inline void swap(const deque<T, Alloc> &lhs, const deque<T, Alloc> &rhs) {
    lhs.swap(rhs);
}

}  // namespace MiniSTL
#endif /* stl_deque_h */