stl_deque.h

#pragma once

#include "Allocator/subAllocation/allocator.h"
#include "Allocator/subAllocation/uninitialized.h"
#include "deque_iterator.h"

namespace MiniSTL {

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

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

 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_integral<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_integral<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_integral<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 &) {
    MiniSTL::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 &) {
    MiniSTL::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(start.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() {
  MiniSTL::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) {                                   //内部均存有元素
    MiniSTL::destroy(*node, *node + buffer_size());//析构所有元素
    node_allocator::deallocate(*node, buffer_size());
  }
  if (start.node != finish.node) {// 存在头尾两个缓冲区
    // 析构其中所有元素
    MiniSTL::destroy(start.cur, start.last);
    MiniSTL::destroy(finish.first, finish.cur);
    // 保存头部，释放尾部
    node_allocator::deallocate(finish.first, buffer_size());
  } else
    MiniSTL::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;    // 标记新起点
      MiniSTL::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;// 标记末尾
      MiniSTL::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(deque<T, Alloc> &lhs, deque<T, Alloc> &rhs) noexcept {
  lhs.swap(rhs);
}

}// namespace MiniSTL