[C++]Deque with iterator實現細節

一、deque的中控器

deque是連續空間(至少邏輯上看來如此)，連續線性空間總令我們聯想到array或vector。array無法成長，vector雖可成長，卻只能向尾端成長，而且其所謂的成長原是個假象，事實上是(1)另覓更大空間;(2)將原數據復制過去;(3)釋放原空間三部曲。如果不是vector每次配置新空間時都有留下一些余裕，其成長假象所帶來的代價將是相當高昂。

deque系由一段一段的定量連續空間構成。一旦有必要在deque的前端或尾端增加新空間，便配置一段定量連續空間，串接在整個deque的頭端或尾端。deque的最大任務，便是在這些分段的定量連續空間上，維護其整體連續的假象，並提供隨機存取的借口。避開了“重新配置、復制、釋放”的輪回，代價則是復雜的迭代器架構。

受到分段連續線性空間的字面影響，我們可能以為deque的實現復雜度和vector相比雖不中亦不遠矣，其實不然。主要因為，既是分段連續線性空間，就必須有中央控制，而為了維持整體連續的假象，數據結構的設計及迭代器前進後退等操作都頗為繁瑣。deque的實現代碼分量遠比vector或list都多得多。

deque采用一塊所謂的map(注意，不是STL的map容器)作為主控。這裡所謂map是一小塊連續空間，其中每個元素(此處稱為一個節點，node)都是指針，指向另一段(較大的)連續線性空間，稱為緩沖區。緩沖區才是deque的儲存空間主體。SGI STL 允許我們指定緩沖區大小，默認值0表示將使用512 bytes 緩沖區。

二、deque的迭代器

讓我們思考一下，deque的迭代器應該具備什麼結構，首先，它必須能夠指出分段連續空間(亦即緩沖區)在哪裡，其次它必須能夠判斷自己是否已經處於其所在緩沖區的邊緣，如果是，一旦前進或後退就必須跳躍至下一個或上一個緩沖區。為了能夠正確跳躍，deque必須隨時掌握管控中心(map)。所以在迭代器中需要定義：當前元素的指針，當前元素所在緩沖區的起始指針，當前元素所在緩沖區的尾指針，指向map中指向所在緩區地址的指針。

在進行迭代器的移動時，需要考慮跨緩沖區的情況。

重載前加(減)，在實現後加(減)時，調用重載的前加(減)。

重載+=,實現+時，直接調用+=,實現-=時，調用+=負數，實現-時，調用-=.

//當需要實現新的功能時，最好使用已經重載好的操作，即方便有安全。。。。

另外，deque在效率上來說是不夠vector好的，因此有時候在對deque進行sort的時候，需要先將元素移到vector再進行sort，然後移回來。

構造函數：根據緩沖區設置大小和元素個數，決定map的大小;給map分配空間，根據緩沖區的個數，分配緩沖區，默認指定一個緩沖區;

設置start和finish迭代器，滿足左閉右開的原則。

push_back:如果空間滿足，直接插入;不滿足，調用push_back_aux。

push_back_aux:先調用reverse_map_at_back,若符合某種條件，重換一個map;分配空間。

reserve_map_at_back:看看map有沒有滿，滿的話，調用reallocate_map。

reallocate_map:如果前端或後端pop過多，就會導致大量的空閒空間，如果是這種情況，則不用新分配空間，調整一下start的位置即可;

如果不夠，則需要重新申請空間。

pop：析構元素，如果是最後一塊還需要刪除空間。

erase：需要判斷，前面的元素少還是後面的元素少，移動較少的部分。

insert：判斷位置，如果為前端或後端直接調用push操作，否則，移動較少的一端。

deque的構造與內存管理：

由於deque的設計思想就是由一塊塊的緩存區連接起來的，因此它的內存管理會比較復雜。插入的時候要考慮是否要跳轉緩存區、是否要新建map節點(和vector一樣，其實是重新分配一塊空間給map，刪除原來空間)、插入後元素是前面元素向前移動還是後面元素向後面移動(誰小移動誰)。而在刪除元素的時候，考慮是將前面元素後移覆蓋需要移除元素的地方還是後面元素前移覆蓋(誰小移動誰)。移動完以後要析構冗余的元素，釋放冗余的緩存區。

//
//  Deque.h
//  deque
//
//  Created by 顏澤鑫 on 6/3/16.
//  Copyright ? 2016 顏澤鑫. All rights reserved.
//

/*
template   // template declaration.
class DequeIterator {
 public:
typedef DequeIterator              iterator;
typedef DequeIterator              const_iterator;
typedef random_access_iterator_tag iterator_category;
  // iterator tag.
typedef T                          value_type;
typedef T*                         pointer;
typedef T&                         reference;
typedef size_t                     size_type;
typedef ptrdiff_t                  difference_type;
typedef T**                        map_pointer;
typedef DequeIterator              self;

  T* cur;
  // pointer, pointing to the current element.
  T* first;
  // pointer, pointing to the first element in current buffer.
  T* last;
  // pointer, pointing to the last element in current buffer.
  map_pointer node;
  // pointer, pointing to the buffer.

 public:  // constructor
  DequeIterator(Tx x, map_pointer y);
  DequeIterator();
  DequeIterator(const iterator& x);

 public:
  // basic operation
  reference operator*() const;
  reference operator->() const;
  void set_node(map_pointer new_node);
  difference_type operator-(const self& x) const;

  // logic operation
  bool operator==(const self& x);
  bool operator!=(const self& x);
  bool operator<(const self& x);

  // random access
  self& operator++();
  self operator++(int);
  self& operator--();
  self operator--(int);
  self& operator+=(difference_type n);
  self& operator-=(difference_type n);
  self operator+(difference_type n) const;
  self operator-(difference_type n) const;
  reference operator[](differece_type n) const;
*/

#ifndef DequeIterator_
#define DequeIterator_
#include 
#define BUFFER_SIZE 10
using namespace std;
template 
class DequeIterator {
 public:
  typedef DequeIterator iterator;
  typedef DequeIterator const_iterator;
  typedef random_access_iterator_tag iterator_category;
  // iterator tag.
  typedef T value_type;
  typedef T* pointer;
  typedef T& reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef T** map_pointer;
  typedef DequeIterator self;

  T* cur;    // pointer, pointing to the current element.
  T* first;  // pointer, pointing to the first element in current buffer.
  T* last;   // pointer, pointing to the last element in current buffer.
  map_pointer node;  // pointer, pointing to the buffer.

  static size_t buffer_size() { return BUFFER_SIZE; }

  DequeIterator(T* x, map_pointer y)
      : cur(x), first(*y), last(*y + buffer_size()), node(y) {}
  DequeIterator() : cur(0), first(0), last(0), node(0) {}
  DequeIterator(const iterator& x)
      : cur(x.cur), first(x.first), last(x.last), node(x.node) {}

  // return *current;定義解引用操作
  reference operator*() const { return *cur; }
  // return current;定義箭頭操作符
  reference operator->() const { return cur; }
  // 判斷兩個迭代器是否相等
  bool operator==(const self& x) const { return cur == x.cur; }
  // 判斷兩個迭代器是否不相等
  bool operator!=(const self& x) const { return !(*this == x); }
  // 先比較map的node，在比較cur
  bool operator<(const self& x) const {
    return (node == x.node) ? (cur < x.cur) : (node < x.node);
  }
  // 將當前的迭代器設置為new_node,主要是設置node、first、last屬性的值
  void set_node(map_pointer new_node) {
    node = new_node;
    first = *new_node;
    last = first + BUFFER_SIZE;
  }

  difference_type operator-(const self& x) const {
    return difference_type(buffer_size()) * (node - x.node - 1) +
           (cur - first) + (x.last - x.cur);
  }
  // 定義前置自加,++p，返回引用,因為是return *this
  self& operator++() {
    ++cur;
    if (cur == last) {
      set_node(node + 1);
      cur = first;
    }
    return *this;
  }
  // 定義後置自加,p++，返回非引用，因為是return
  self operator++(int) {
    self temp = *this;
    ++*this;
    return temp;
  }
  // 定義前置自減，--p，返回引用
  self& operator--() {
    if (cur == first) {
      set_node(node - 1);
      cur = last;
    }
    --cur;
    return *this;
  }
  // 定義後置自減，p--，返回非引用
  self operator--(int) {
    self temp = *this;
    --*this;
    return temp;
  }
  //  將本迭代器自加n步，隨機訪問迭代器的屬性
  self& operator+=(difference_type n) {
    difference_type offset = n + (cur - first);
    if (offset >= 0 && offset < difference_type(buffer_size())) {
      cur += n;  // 目標位置在同一緩沖區內
    } else {     // 目標位置不在同一緩沖區內
      difference_type node_offset =
          offset > 0 ? offset / difference_type(buffer_size())
                     : -difference_type((-offset - 1) / buffer_size()) - 1;
      // 切換至正確的節點（亦即緩沖區）
      set_node(node + node_offset);
      // 切換至正確的元素
      cur = first + (offset - node_offset * difference_type(buffer_size()));
    }
    return *this;
  }
  self& operator-=(difference_type n) { return * this += -n; }
  self operator+(difference_type n) const {
    self tmp = *this;
    // 這裡調用了operator +=()可以自動調整指針狀態
    return tmp += n;
  }
  self operator-(difference_type n) const {
    self tmp = *this;
    return tmp -= n;
  }
  reference operator[](difference_type n) const { return *(*this + n); }
  operator T*() { return (*this).cur; }
};
#endif /* DequeIterator */

/*
 #include 
 #define MAP_SIZE 20
 template 
 class deque {
 public:
 typedef T value_type;
 typedef value_type* pointer;
 typedef value_type& reference;
 typedef size_t size_type;
 typedef ptrdiff_t difference_type;
 typedef allocator d_allocator;
 typedef allocator m_allocator;
 typedef DequeIterator iterator;
 typedef pointer* map_pointer;
 m_allocator map_allocator;
 d_allocator data_allocator;

 protected:
 static size_type buffer_size();
 static size_type initial_map_size();
 size_type max_size() const;

 protected:  // memeory operation
 pointer allocate_node();
 void deallocate_node(pointer n);
 void create_map_and_nodes(size_type num_elements);
 void reallocate_map(size_type nodes_to_add, bool add_at_front);
 void destroy_map_and_nodes();
 void reserve_map_at_back(size_type nodes_to_add = 1);
 void reserve_map_at_front(size_type nodes_to_add = 1);

 protected:
 iterator start;
 iterator finish;
 map_pointer map;
 size_type map_size;

 public:
 deque();
 ~deque();

 iterator begin();
 iterator end();
 reference front();
 reference back();
 reference operator[](size_type n);
 size_type size() const;
 bool empty() const;

 public:
 // elements operation
 void push_back(const value_type& value);
 void push_back_aux(const value_type& value);
 void push_front(const value_type& value);
 void push_front_aux(const value_type& value);
 void pop_back();
 void pop_front();
 void pop_back_aux();
 void pop_front_aux();

 void insert(iterator pos, const value_type& value = value_type());
 void insert_aux(iterator pos, const value_type& value);
 iterator erase(iterator pos);
 iterator erase(iterator first, iterator last);
 clear();
 };
 */

#ifndef Deque
#define Deque
#include 
#define MAP_SIZE 20  // we set the size of map is 20
template 
class deque {
 public:
  typedef T value_type;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef allocator d_allocator;
  typedef allocator m_allocator;
  typedef DequeIterator iterator;
  typedef pointer* map_pointer;
  m_allocator map_allocator;
  d_allocator data_allocator;

 protected:
  static size_type buffer_size() { return size_t(BUFFER_SIZE); }
  static size_type initial_map_size() { return 8; }
  size_type max_size() const { return size_type(-1); }

  // 內存分配和回收的相關函數
  // 為node分配空間
  pointer allocate_node() { return data_allocator.allocate(buffer_size()); }
  // 為node回收空間
  void deallocate_node(pointer n) {
    data_allocator.deallocate(n, buffer_size());
  }
  // 創造map和節點node
  void create_map_and_nodes(size_type num_elements) {
    size_type num_nodes = num_elements / BUFFER_SIZE + 1;
    map_size = max(initial_map_size(), num_nodes + 2);
    // 開頭結尾各多增加一個，頭尾插入時更方便。
    map = map_allocator.allocate(map_size);
    // 在中間設置start和finish
    map_pointer nstart = map + (map_size - num_nodes) / 2;
    map_pointer nfinish = nstart + num_nodes - 1;
    for (map_pointer cur = nstart; cur <= nfinish; cur++) {
      *cur = allocate_node();
    }
    start.set_node(nstart);
    finish.set_node(nfinish);
    start.cur = start.first;
    finish.cur = finish.first + num_elements % BUFFER_SIZE;
  }
  void 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) {
      // 用於平衡頭尾的node
      new_nstart = map + (map_size - new_num_nodes) / 2 +
                   (add_at_front ? nodes_to_add : 0);
      if (new_nstart < start.node)
        copy(start.node, finish.node + 1, new_nstart);
      else
        copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
    } else {
      size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
      // 配置一塊空間，準備給新map使用。
      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);
      // 把原map 內容拷貝過來。
      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);
  }

 protected:
  iterator start;
  iterator finish;
  map_pointer map;
  size_type map_size;

 public:
  deque() : start(), finish(), map(0) { create_map_and_nodes(0); }

  ~deque() {
    for (map_pointer node = start.node; node <= finish.node; ++node) {
      // 釋放緩沖區內存
      delete *node;
    }
    destroy_map_and_nodes();
  }
  void destroy_map_and_nodes() { map_allocator.deallocate(map, map_size); }

  iterator begin() { return start; }
  iterator end() { return finish; }
  reference front() { return *start; }
  reference back() {
    iterator temp = finish;
    --temp;
    return *temp;
  }
  reference operator[](size_type n) { return start[difference_type(n)]; }
  size_type size() const { return finish - start; }
  bool empty() const { return finish == start; }

  void push_back(const value_type& t) {
    // 最後緩沖區尚有兩個（含）以上的元素備用空間
    if (finish.cur != finish.last - 1) {
      data_allocator.construct(finish.cur, t);  // 直接在備用空間上構造元素
      ++finish.cur;  // 調整最後緩沖區的使用狀態
    } else {
      // 容量已滿就要新申請內存了
      push_back_aux(t);
    }
  }
  void push_back_aux(const value_type& t) {
    value_type t_copy = t;
    reserve_map_at_back();
    *(finish.node + 1) = allocate_node();  // 配置一個新節點（緩沖區）
    map_allocator.construct(finish.cur, t_copy);  // 針對標的元素設值
    finish.set_node(finish.node + 1);  // 改變finish，令其指向新節點
    finish.cur = finish.first;         // 設定finish的狀態
  }
  void reserve_map_at_back(size_type nodes_to_add = 1) {
    if (nodes_to_add > map_size - (finish.node - map) - 1)
      // 如果 map 尾端的節點備用空間不足
      // 符合以上條件則必須重換一個map（配置更大的，拷貝原來的，釋放原來的）
      reallocate_map(nodes_to_add, false);
  }

  void push_front(const value_type& t) {
    if (start.cur != start.first)  // 第一緩沖區尚有備用空間
    {
      data_allocator.construct(start.cur - 1, t);  // 直接在備用空間上構造元素
      --start.cur;  // 調整第一緩沖區的使用狀態
    } else          // 第一緩沖區已無備用空間
      push_front_aux(t);
  }
  void push_front_aux(const value_type& t) {
    value_type t_copy = t;
    reserve_map_at_front();
    *(start.node - 1) = allocate_node();
    start.set_node(start.node - 1);  // 改變start，令其指向新節點
    start.cur = start.last - 1;      // 設定start的狀態
    data_allocator.construct(start.cur, t_copy);  // 針對標的元素設值
  }
  void reserve_map_at_front(size_type nodes_to_add = 1) {
    if (nodes_to_add > start.node - map)
      // 如果 map 前端的節點備用空間不足
      // 符合以上條件則必須重換一個map（配置更大的，拷貝原來的，釋放原來的）
      reallocate_map(nodes_to_add, true);
  }
  void pop_back() {
    if (!empty()) {
      if (finish.cur != finish.first)  // 最後緩沖區有一個（或更多）元素
      {
        --finish.cur;  // 調整指針，相當於排除了最後元素
        data_allocator.destroy(finish.cur);  // 將最後元素析構
      } else
        // 最後緩沖區沒有任何元素
        pop_back_aux();  // 這裡將進行緩沖區的釋放工作
    }
  }
  void pop_back_aux() {
    deallocate_node(finish.first);     // 釋放最後一個緩沖區
    finish.set_node(finish.node - 1);  // 調整finish狀態，使指向
    finish.cur = finish.last - 1;  // 上一個緩沖區的最後一個元素
    data_allocator.destroy(finish.cur);  // 將該元素析構
  }
  void pop_front() {
    if (!empty()) {
      if (start.cur != start.last - 1)  // 第一緩沖區有兩個（或更多）元素
      {
        data_allocator.destroy(start.cur);  // 將第一元素析構
        ++start.cur;  //調整指針，相當於排除了第一元素
      } else
        // 第一緩沖區僅有一個元素
        pop_front_aux();  // 這裡將進行緩沖區的釋放工作
    }
  }
  void pop_front_aux() {
    data_allocator.destroy(
        start.cur);                  // 將第一個緩沖區的第一個（也是最後一個、唯一一個）元素析構
    deallocate_node(start.first);    // 釋放第一緩沖區
    start.set_node(start.node + 1);  // 調整start狀態，使指向
    start.cur = start.first;         // 下一個緩沖區的第一個元素
  }

  iterator insert(iterator position, const value_type& value = value_type()) {
    if (position == start) {
      push_front(value);
      return start;
    } else if (position == finish) {
      push_front(value);
      return finish;
    } else {
      return insert_aux(position, value);
    }
  }

  iterator erase(iterator pos) {
    iterator next = pos;
    ++next;
    // 清除點之前的元素個數
    difference_type index = pos - start;
    // 如果清除點之前的元素個數比較少, 哪部分少就移動哪部分
    if (index < (size() >> 1)) {
      // 就移動清除點之前的元素
      copy_backward(start, pos, next);
      pop_front();  // 移動完畢，最前一個元素冗余，去除之
    } else          // 如果清除點之後的元素個數比較少
    {
      copy(next, finish, pos);  // 就移動清除點之後的元素
      pop_back();  // 移動完畢，最後一個元素冗余，去除之
    }
    return start + index;
  }
  iterator erase(iterator first, iterator last) {
    if (first == start && last == finish)  // 如果清除區間是整個deque
    {
      clear();  // 直接調用clear()即可
      return finish;
    } else {
      difference_type n = last - first;              // 清除區間的長度
      difference_type elems_before = first - start;  // 清除區間前方的元素個數
      if (elems_before < (size() - n) / 2)  // 如果前方的元素個數比較少
      {
        copy_backward(start, first, last);  // 向後移動前方元素（覆蓋清除區間）
        iterator new_start = start + n;  // 標記deque的新起點
        destroy(start, new_start);  // 移動完畢，將冗余的元素析構
        // 以下將冗余的緩沖區釋放
        for (map_pointer cur = start.node; cur < new_start.node; ++cur)
          data_allocator.deallocate(*cur, buffer_size());
        start = new_start;  // 設定deque的新起點
      } else                // 如果清除區間後方的元素個數比較少
      {
        copy(last, finish, first);  // 向前移動後方元素（覆蓋清除區間）
        iterator new_finish = finish - n;  // 標記deque的新尾點
        destroy(new_finish, finish);  // 移動完畢，將冗余的元素析構
        // 以下將冗余的緩沖區釋放
        for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)
          data_allocator.deallocate(*cur, buffer_size());
        finish = new_finish;  // 設定deque的新尾點
      }
      return start + elems_before;
    }
  }
  iterator insert_aux(iterator pos, const value_type& x) {
    difference_type index = pos - start;  // 插入點之前的元素個數
    value_type x_copy = x;
    if (index < size() / 2)  // 如果插入點之前的元素個數比較少
    {
      push_front(front());  // 在最前端加入與第一元素同值的元素
      iterator front1 = start;  // 以下標示記號，然後進行元素移動
      ++front1;
      iterator front2 = front1;
      ++front2;
      pos = start + index;
      iterator pos1 = pos;
      ++pos1;
      copy(front2, pos1, front1);  // 元素移動
    } else                         // 插入點之後的元素個數比較少
    {
      push_back(back());  // 在最尾端加入與最後元素同值的元素
      iterator back1 = finish;  // 以下標示記號，然後進行元素移動
      --back1;
      iterator back2 = back1;
      --back2;
      pos = start + index;
      copy_backward(pos, back2, back1);  // 元素移動
    }
    *pos = x_copy;  // 在插入點上設定新值
    return pos;
  }
  void clear() {
    // 以下針對頭尾以外的每一個緩沖區
    for (map_pointer node = start.node + 1; node < finish.node; ++node) {
      // 將緩沖區內的所有元素析構
      for (int i = 0; i != buffer_size() + 1; i++) {
        data_allocator.destroy(*node + i);

      }
      // 釋放緩沖區內存
      data_allocator.deallocate(*node, buffer_size());
    }

    if (start.node != finish.node)  // 至少有頭尾兩個緩沖區
    {
      for (auto iter = start.cur; iter != start.last; iter++) {
        data_allocator.destroy(iter);
      }
      for (auto iter = finish.first; iter != finish.cur; iter++) {
        data_allocator.destroy(iter);
      }
      // 以下釋放尾緩沖區。注意：頭緩沖區保留
      data_allocator.deallocate(finish.first, buffer_size());
    } else                             // 只有一個緩沖區
      for (auto iter = start.cur; iter != finish.cur; iter++) {
        data_allocator.destroy(iter);  // 將此唯一緩沖區內的所有元素析構
      }
    // 注意：並不釋放緩沖區空間，這唯一的緩沖區將保留
    finish = start;  // 調整狀態
  }
};
#endif /* Deque_h */

測試文件：（gtest)

#include 
#include "gtest/gtest.h"
#include 
#include "Deque.h"
using namespace std;
deque deq_standard;
Deque::deque deq_test;

TEST(TestOperation, Test_push_back) {
  int n;
  cout << "input a random number" << endl;
  cin >> n;
  for (int i = 0; i != n; i++) {
    deq_standard.push_back(i);
    deq_test.push_back(i);
  }
  EXPECT_EQ(deq_standard, deq_test);
}
TEST(TestOperation, Test_push_front) {
  int n;
  cout << "input a random number" << endl;
  cin >> n;
  for (int i = 0; i != n; i++) {
    deq_standard.push_front(i);
    deq_test.push_front(i);
  }
  EXPECT_EQ(deq_standard, deq_test);
}

TEST(TestOperation, Test_insert) {
  deq_test.insert(deq_test.begin(), 3);
  deq_standard.insert(deq_standard.begin(), 3);
  deq_test.insert(deq_test.end(), 4);
  deq_standard.insert(deq_standard.end(), 4);
  Deque::deque::iterator iter_t = deq_test.begin();
  deque::iterator iter_s = deq_standard.begin();
  iter_t += 3;
  iter_s += 3;
  deq_test.insert(iter_t, 10);
  deq_standard.insert(iter_s, 10);
  EXPECT_EQ(deq_standard, deq_test);
}
TEST(TestOperation, Test_erase) {
  Deque::deque::iterator iter_t = deq_test.begin();
  deque::iterator iter_s = deq_standard.begin();
  iter_t += 6;
  iter_s += 6;
  deq_test.erase(iter_t);
  deq_standard.erase(iter_s);
  EXPECT_EQ(deq_standard, deq_test);
}
TEST(TestOperation, Test_clear) {
  deq_standard.clear();
  deq_test.clear();
  EXPECT_EQ(deq_standard, deq_test);
}
TEST(Test_all, test_all) {
  int m, n;
  cout << "input two random number" << endl;
  cin >> m >> n;
  for (int i = 0; i < m; i++) {
    deq_standard.push_front(i);
    deq_test.push_front(i);
  }

  EXPECT_EQ(deq_standard, deq_test);
  EXPECT_EQ(deq_standard.size(), deq_test.size());
  EXPECT_EQ(deq_standard[0], deq_test[0]);
  deque::iterator tmp1 = deq_standard.begin();
  deque::iterator tmp2 = tmp1;
  Deque::deque::iterator tmp1_t = deq_test.begin();
  Deque::deque::iterator tmp2_t = tmp1_t;

  tmp2 = tmp2 + 5;
  tmp2_t = tmp2_t + 5;
  EXPECT_EQ(*(tmp2++), *(tmp2_t++));

  ++tmp2;
  ++tmp2_t;
  EXPECT_EQ(*(tmp2++), *(tmp2_t++));

  tmp2 = tmp2 - 2;
  tmp2_t = tmp2_t - 2;
  EXPECT_EQ(*(tmp2++), *(tmp2_t++));
  tmp2 += 25;
  tmp2_t += 25;
  EXPECT_EQ(*(tmp2--), *(tmp2_t--));

  --tmp2;
  tmp2 -= 13;
  --tmp2_t;
  tmp2_t -= 13;

  EXPECT_EQ(*tmp2, *tmp2_t);
  EXPECT_EQ(tmp1[0], tmp1_t[0]);
  EXPECT_EQ(tmp1[8], tmp1_t[8]);
  EXPECT_EQ(tmp1[23], tmp1_t[23]);
  EXPECT_EQ(tmp2[-3], tmp2_t[-3]);
}

int main(int argc, char **argv) {
    printf("Running main() from gtest_main.cc\n");
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

測試

用valgrind測試內存和gtest進行單元測試。