deque 源码分析

前言:

deque 所提供的功能相较于其他顺序容器, 拥有较为强大的功能, 在实现上相对于 list , vector 更复杂, deque 的迭代器是属于 random_access_iterator_tag 类型, 在分析 vector 时, 可以发现, 在某些极端情况下, 由于 vector 采用连续的空间储存元素, 会出现头插入以及扩容时进行大量元素的复制, 导致复杂度很高, 且对于空间的要求也是相对较高的. deque 则是 相对连续的 即它将多个数组按照顺序排序, 这样即使每个数组的头地址并不是连续的, 但是并不影响元素是连续的, 这里的连续指的是逻辑上是连续, 而不是地址连续, deque 是一个双向开口的容器, 头尾插入和删除都是 O(1) 复杂度的, 空间也是可扩展的, 且扩展时不经常对已有的元素进行移动.

__deque_iterator迭代器结构

deque 的 iterator 和 vector 类似, 但是由于其结构为相对连续所以对于 iterator 的设计要比 vector 的 iterator 更为复杂

全局函数

用来计算每一个数组的大小

1
2
3
4
inline size_t __deque_buf_size(size_t n, size_t sz)
{
  return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}

类型定义

deque 的 iterator 是 random_access_iterator_tag 类型, 满足 traits 编程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
// 迭代器定义
  typedef __deque_iterator<T, T&, T*, BufSiz>             iterator;
  typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
  static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
template <class T, class Ref, class Ptr>
struct __deque_iterator {
  typedef __deque_iterator<T, T&, T*>             iterator;
  typedef __deque_iterator<T, const T&, const T*> const_iterator;
  static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); }
#endif
	// deque是random_access_iterator_tag类型
  typedef random_access_iterator_tag iterator_category;
  // 基本类型的定义, 满足traits编程
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  // node
  typedef T** map_pointer;
  map_pointer node;
	
  typedef __deque_iterator self;
  ...
};

满足 traits 编程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 满足traits编程
template <class T, class Ref, class Ptr, size_t BufSiz>
inline random_access_iterator_tag
iterator_category(const __deque_iterator<T, Ref, Ptr, BufSiz>&) {
  return random_access_iterator_tag();
}
template <class T, class Ref, class Ptr, size_t BufSiz>
inline T* value_type(const __deque_iterator<T, Ref, Ptr, BufSiz>&) {
  return 0;
}
template <class T, class Ref, class Ptr, size_t BufSiz>
inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref, Ptr, BufSiz>&) {
  return 0;
}

上文提到, 由于 deque 的连续性是使用数组进行拼接的, 所以需要一个指向指针的指针来记录每块数组的地址, 所以 iterator 就需要一个指向指针的指针来保证 iterator 在跨域数组的时候找到下(上)一顺序的数组

1
2
3
4
5
6
7
8
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
	...
	// node
  typedef T** map_pointer;
  map_pointer node;
  ...
};

同时还 iterator 中还设置了三个 T*指针 cur, first, last

  • cur: 当前指向的位置
  • first: 该数组中头的位置
  • last: 该数组中尾的位置
1
2
3
4
5
6
7
8
9
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
	...
  typedef T value_type;
  T* cur;
  T* first;
  T* last;
  ...
};

构造函数

1
2
3
4
5
6
7
8
9
10
11
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
	...
  	// 初始化cur指向当前数组位置, last指针数组的尾, node指向y
  	__deque_iterator(T* x, map_pointer y)  : cur(x), first(*y), last(*y + buffer_size()), node(y) {}
  	// 初始化为一个空的deque
  	__deque_iterator() : cur(0), first(0), last(0), node(0) {}
  	// 接受一个迭代器
  	__deque_iterator(const iterator& x) : cur(x.cur), first(x.first), last(x.last), node(x.node) {}
    ...
};

重载运算符

__deque_iterator 实现了基本运算符 在分析 __deque_iterator 的运算符之前先介绍一个基础函数 set_node

由于在 __deque_iterator 移动时可能会跨越数组, 所以需要重新设定指向数组指针的位置, set_node 则提供了更新指向将要前往的数组的头部位置的功能

1
2
3
4
5
6
7
8
9
10
11
12
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
	...
	void set_node(map_pointer new_node) 
	{
		// 让node指针另一个数组的头, 同时修改头和尾的地址
    	node = new_node;
    	first = *new_node;
    	last = first + difference_type(buffer_size());
  	}
  	...
};

重载++和–

要注意 __deque_iterator 在向前或者向后移动在跨越数组时会出现越界的情况, 需要进行判断, 如果跨越了数组就要重新设置 node 指向的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
	...  
 	// 这里需要判断是否达到当前数组的尾部
  self& operator++() {
    ++cur;
    // 达到了尾部就需要更新node的指向
    if (cur == last) {
      set_node(node + 1);
      cur = first;
    }
    return *this; 
  }
  // 同理, 需要判断是否到达数组的头. 到达就要更新node指向
  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--(int) {
    self tmp = *this;
    --*this;
    return tmp;
  }
  ...
};

重载+, -等

由于 __deque_iterator 是 random_access_iterator_tag 类型迭代器, 所以支持 +, - 运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
	...
	// 重载指针
  	reference operator*() const { return *cur; }
  	reference operator[](difference_type n) const { return *(*this + n); } // 这个会调用重载+运算符
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  	pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  	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;
  	}
  	// 以下都是调用+运算符
	difference_type operator-(const self& x) const 
	{
    	return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur);
  	}
  	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;
  	}
	// 
  	bool operator==(const self& x) const { return cur == x.cur; }
  	bool operator!=(const self& x) const { return !(*this == x); }
  	bool operator<(const self& x) const 
  	{
	    return (node == x.node) ? (cur < x.cur) : (node < x.node);
  	}
};

deque 结构

基本类型定义

deque 满足 traits 编程的嵌套定义类型.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:                         
    // 满足traits编程 可以利用 traits 来获取关于容器的基础信息
  typedef T value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

public:                        
   // 定义迭代器 
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
  typedef __deque_iterator<T, T&, T*, BufSiz>              iterator;
  typedef __deque_iterator<T, const T&, const T&, BufSiz>  const_iterator;
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
  typedef __deque_iterator<T, T&, T*>                      iterator;
  typedef __deque_iterator<T, const T&, const T*>          const_iterator;
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */

	// 反向迭代器
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  typedef reverse_iterator<const_iterator> const_reverse_iterator;
  typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  typedef reverse_iterator<const_iterator, value_type, const_reference, 
                           difference_type>  
          const_reverse_iterator;
  typedef reverse_iterator<iterator, value_type, reference, difference_type>
          reverse_iterator; 
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */

protected:                      // Internal typedefs
    // map, 指向指针的指针 用来记录数组的地址
  typedef pointer* map_pointer;
  typedef simple_alloc<value_type, Alloc> data_allocator;	// value_type类型的空间配置器
  typedef simple_alloc<pointer, Alloc> map_allocator;		// 指针类型的空间配置器
    ...
};

map_pointer 是一个 指向指针的指针 用来管理 deque 中数组的数据

构造和析构函数

构造函数 有多种重载函数, 接受许多类型的创建 deque 的方式, 不过可以发现绝大部分的构造函数都会调用 create_map_and_nodes 这个方法, 其就是构造函数的核心, 在下面将会进行分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public:                        
    // 默认构造函数
  deque() : start(), finish(), map(0), map_size(0)	
  {
    create_map_and_nodes(0);
  }
    // 接受一个deque
  deque(const deque& x) : start(), finish(), map(0), map_size(0)	
  {
    create_map_and_nodes(x.size());
    __STL_TRY {
      uninitialized_copy(x.begin(), x.end(), start);
    }
    __STL_UNWIND(destroy_map_and_nodes());
  }
    // 接受 n:初始化大小, value:初始化的值
  deque(size_type n, const value_type& value) : start(), finish(), map(0), map_size(0)
  {
    fill_initialize(n, value);
  }
  deque(int n, const value_type& value) : start(), finish(), map(0), map_size(0)
  {
    fill_initialize(n, value);
  } 
  deque(long n, const value_type& value) : start(), finish(), map(0), map_size(0)
  {
    fill_initialize(n, value);
  }
    // 接受 n:初始化大小
  explicit deque(size_type n) : start(), finish(), map(0), map_size(0)
  {
    fill_initialize(n, value_type());
  }
#ifdef __STL_MEMBER_TEMPLATES
    //利用两个 InputIterator 类型迭代器范围内的元素进行初始化
    // 前提是可以使用成员模板
  template <class InputIterator>
  deque(InputIterator first, InputIterator last) : start(), finish(), map(0), map_size(0)
  {
    range_initialize(first, last, iterator_category(first));
  }
#else /* __STL_MEMBER_TEMPLATES */
  deque(const value_type* first, const value_type* last) : start(), finish(), map(0), map_size(0)
  {
    create_map_and_nodes(last - first);
    __STL_TRY {
      uninitialized_copy(first, last, start);
    }
    __STL_UNWIND(destroy_map_and_nodes());
  }
    // 接受两个迭代器, 构造一个范围
  deque(const_iterator first, const_iterator last) : start(), finish(), map(0), map_size(0)
  {
    create_map_and_nodes(last - first);
    __STL_TRY {
      uninitialized_copy(first, last, start);
    }
    __STL_UNWIND(destroy_map_and_nodes());
  }

#endif /* __STL_MEMBER_TEMPLATES */
    ...
};

create_map_and_nodes 函数实现.

  1. 计算初始化时需要容纳多少元素

  2. 在默认开辟的空间和第一步中的空间取 max 保证 dqeue 在向前和向后扩展数组时都有空间

  3. 计算出初始时最前面数组和最后面数组的位置, 这里给两个位置前面预留的空间为 (map_size - num_nodes) / 2 保证了前后预留空间都相同

  4. 为已经确定的空间范围**(最前和最后两个数组之间)** 都分配一个 buffer_size 的数组

  5. 将 start 和 finish 中的 cur 指向所对应的数组, 并更新 first, lasr , 即将 start 和 finish 指向第一个元素和最后一个元素的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) 
{
    // 计算初始化类型参数的个数
  size_type num_nodes = num_elements / buffer_size() + 1;
	// 因为deque是头尾插入都是O(1), 就是deque在头和尾都留有空间方便头尾插入
    // 两者取最大的. num_nodes是保证前后都留有位置
  map_size = max(initial_map_size(), num_nodes + 2);
  map = map_allocator::allocate(map_size);	// 分配空间

    // 计算出数组的头前面留出来的位置保存并在nstart.
  map_pointer nstart = map + (map_size - num_nodes) / 2;
  map_pointer nfinish = nstart + num_nodes - 1;
    
  map_pointer cur;
  __STL_TRY 
  {
      // 为每一个a[cur]分配一个buffer_size的数组, 即这样就实现了二维数组即map
    for (cur = nstart; cur <= nfinish; ++cur)
      *cur = allocate_node();
  }
#     ifdef  __STL_USE_EXCEPTIONS 
  catch(...) {
    for (map_pointer n = nstart; n < cur; ++n)
      deallocate_node(*n);
    map_allocator::deallocate(map, map_size);
    throw;
  }
#     endif /* __STL_USE_EXCEPTIONS */
	// 修改start, finish, cur指针的位置
  start.set_node(nstart);
  finish.set_node(nfinish);
  start.cur = start.first;
  finish.cur = finish.first + num_elements % buffer_size();
}

range_initialize 函数

虽然 deque 的 iterator 是 random_access_iterator_tag 类型, 但是在执行构造函数时可能接收到的是 list 或其他容器的迭代器, 就会通过该方法来确定如何向 deque 内部添加元素

这种设计考虑了不同迭代器的差异, 迭代器要 向下兼容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <class T, class Alloc, size_t BufSize>
template <class InputIterator>
void deque<T, Alloc, BufSize>::range_initialize(InputIterator first,
                                                InputIterator last,
                                                input_iterator_tag) {
  create_map_and_nodes(0);
    // 一个个进行插入操作
  for ( ; first != last; ++first)
    push_back(*first);
}

template <class T, class Alloc, size_t BufSize>
template <class ForwardIterator>
void deque<T, Alloc, BufSize>::range_initialize(ForwardIterator first,
                                                ForwardIterator last,
                                                forward_iterator_tag) {
  size_type n = 0;
    // 计算距离, 申请空间. 失败则释放所有空间
  distance(first, last, n);
  create_map_and_nodes(n);
  __STL_TRY {
    uninitialized_copy(first, last, start);
  }
  __STL_UNWIND(destroy_map_and_nodes());
}

fill_initialize 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::fill_initialize(size_type n, const value_type& value) 
{
    // 申请空间
  create_map_and_nodes(n);
  map_pointer cur;
  __STL_TRY {
      //对每个空间进行初始化
    for (cur = start.node; cur < finish.node; ++cur)
      uninitialized_fill(*cur, *cur + buffer_size(), value);
      // 最后一个数组单独处理. 毕竟最后一个数组一般不是会全部填充满
    uninitialized_fill(finish.first, finish.cur, value);
  }
#ifdef __STL_USE_EXCEPTIONS
  catch(...) {
    for (map_pointer n = start.node; n < cur; ++n)
      destroy(*n, *n + buffer_size());
    destroy_map_and_nodes();
    throw;
  }
#       endif /* __STL_USE_EXCEPTIONS */
}

析构函数, 分步释放内存.

  • 释放开辟的各个数组内的元素
  • 释放记录数组地址的数组空间
1
2
3
4
5
6
7
8
9
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public: 
   ~deque() {
    destroy(start, finish);
    destroy_map_and_nodes();
  }
};

deque是一个”二维数组”并且每个数组之间并不连续, 所以需要一个数组一个数组的执行释放.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// This is only used as a cleanup function in catch clauses.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::destroy_map_and_nodes() {
// 便利所有的数组, 一个个析构
  for (map_pointer cur = start.node; cur <= finish.node; ++cur)
    deallocate_node(*cur);
    // 内存释放
  map_allocator::deallocate(map, map_size);
}
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public: 
  pointer allocate_node() { return data_allocator::allocate(buffer_size()); }
  void deallocate_node(pointer n) {
    data_allocator::deallocate(n, buffer_size());
  }
};

deque基本属性获取方法

deque 的 first 指向第一个元素的地址, finish 指向最后一个元素的后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
protected:                      // Internal typedefs
...
    // 获取缓冲区大小
  static size_type buffer_size() {
    return __deque_buf_size(BufSiz, sizeof(value_type));
  }
  static size_type initial_map_size() { return 8; }

protected:                      // Data members
  iterator start;	// 指向第一个元素的地址
  iterator finish;	// 指向最后一个元素的后一个地址, 即尾

  map_pointer map;		// 定义map, 指向指针的指针
  size_type map_size;	// map的实际大小
public:                         // Basic accessors
  iterator begin() { return start; }	// 获取头地址
  const_iterator begin() const { return start; }
  iterator end() { return finish; }		// 获取尾地址
  const_iterator end() const { return finish; }
	// 倒转后获取首尾地址.
  reverse_iterator rbegin() { return reverse_iterator(finish); }
  reverse_iterator rend() { return reverse_iterator(start); }
  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(finish);
  }
  const_reverse_iterator rend() const {
    return const_reverse_iterator(start);
  }

  // 获取第一个和最后一个元素的值
  reference front() { return *start; }
  reference back() {
    iterator tmp = finish;
    --tmp;
    return *tmp;
  }
  const_reference front() const { return *start; }
  const_reference back() const {
    const_iterator tmp = finish;
    --tmp;
    return *tmp;
  }
  size_type size() const { return finish - start;; } 	// 获取数组的大小
  size_type max_size() const { return size_type(-1); }	
  bool empty() const { return finish == start; }	// 判断deque是否为空
    
  reference operator[](size_type n) { return start[difference_type(n)]; }
  const_reference operator[](size_type n) const {
    return start[difference_type(n)];
  }
    ...
};

deque 的操作符重载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public:                         // Constructor, destructor.
    // 重载 = 
    // 原deque比赋值的大, 就必须清除多余的元素, 否则就需要将多余的元素进行插入
  deque& operator= (const deque& x) {
    const size_type len = size();
    if (&x != this) {
        // 清楚原deque的多余元素
      if (len >= x.size())
        erase(copy(x.begin(), x.end(), start), finish);
      else {
        const_iterator mid = x.begin() + difference_type(len);
        copy(x.begin(), mid, start);
        insert(finish, mid, x.end());
      }
    }
    return *this;
  }        

#ifdef __STL_NON_TYPE_TMPL_PARAM_BUG
public:
    // 重载==, !=, <
  bool operator==(const deque<T, Alloc, 0>& x) const {
    return size() == x.size() && equal(begin(), end(), x.begin());
  }
  bool operator!=(const deque<T, Alloc, 0>& x) const {
    return size() != x.size() || !equal(begin(), end(), x.begin());
  }
  bool operator<(const deque<T, Alloc, 0>& x) const {
    return lexicographical_compare(begin(), end(), x.begin(), x.end());
  }
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
	...
};

template <class T, class Alloc, size_t BufSiz>
bool operator==(const deque<T, Alloc, BufSiz>& x,
                const deque<T, Alloc, BufSiz>& y) {
  return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

template <class T, class Alloc, size_t BufSiz>
bool operator<(const deque<T, Alloc, BufSiz>& x,
               const deque<T, Alloc, BufSiz>& y) {
  return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

deque 的 元素操作

push, pop

由于 deque 都可以实现双向操作 所以其 push, pop 的操作都类似于 list 的 push 和 pop 操作, 但是由于 list 采用链表实现, 所以不会涉及到容器边界的判断, 而由于 deque 是利用不连续的数组来实现元素的存储, 所以在插入和弹出数据是需要对边界线进行判断

push 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public:                         
    // 对尾进行插入
    // 判断函数是否达到了数组尾部. 没有达到就直接进行插入
  void push_back(const value_type& t) {
    if (finish.cur != finish.last - 1) {
      construct(finish.cur, t);
      ++finish.cur;
    }
    else
      push_back_aux(t);
  }
    // 对头进行插入
    // 判断函数是否达到了数组头部. 没有达到就直接进行插入
  void push_front(const value_type& t) {
    if (start.cur != start.first) {
      construct(start.cur - 1, t);
      --start.cur;
    }
    else
      push_front_aux(t);
  }
    ...
};

如果在 push 操作中发现数组越界的情况, 就移动到相应的下一个数组进行 push 操作, 其是调用 push_front(back)_aux 方法来实现, 这个辅助方法会在后面进行介绍

push_front(back)_aux

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Called only if finish.cur == finish.last - 1.
// 到达了数组的尾部
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) {
  value_type t_copy = t;
  reserve_map_at_back();
  // 申请空间
  *(finish.node + 1) = allocate_node();
  __STL_TRY {
  	// 执行构造
    construct(finish.cur, t_copy);
    // 移动node, 指向下一个数组的头
    finish.set_node(finish.node + 1);
    finish.cur = finish.first;	// cur只指向当前数组的头
  }
  // 如果分配失败, 释放掉该内存
  __STL_UNWIND(deallocate_node(*(finish.node + 1)));
}

// Called only if start.cur == start.first.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) {
  value_type t_copy = t;
  reserve_map_at_front();
  // 申请空间
  *(start.node - 1) = allocate_node();
  __STL_TRY {
  	// 先要移动node, 让其指向上一个数组的尾部
    start.set_node(start.node - 1);
    // cur指向当前数组的尾部
    start.cur = start.last - 1;
    // 执行构造
    construct(start.cur, t_copy);
  }
#     ifdef __STL_USE_EXCEPTIONS
  catch(...) {
    start.set_node(start.node + 1);
    start.cur = start.first;
    deallocate_node(*(start.node - 1));
    throw;
  }
#     endif /* __STL_USE_EXCEPTIONS */
}

这里要注意, 由于在尾部插入的时候, 是判断的插入的位置是不是该数组的最后一个位置, 也即 finish 是指向的最后一个元素的后一个地址, 而 first 当前指向的位置是有元素的, 所以 push_back 是先执行构造再移动 node, push_front 则是先移动 node 再进行构造, 下面 pop 也是同理

pop 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public: 
    // 对尾部进行操作
    // 判断是否达到数组的头部. 没有到达就直接释放
    void pop_back() {
    if (finish.cur != finish.first) {
      --finish.cur;
      destroy(finish.cur);
    }
    else
      pop_back_aux();
  }
    // 对头部进行操作
    // 判断是否达到数组的尾部. 没有到达就直接释放
  void pop_front() {
    if (start.cur != start.last - 1) {
      destroy(start.cur);
      ++start.cur;
    }
    else 
      pop_front_aux();
  }
    ...
};

pop判断越界后执行 pop_xxx_aux 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Called only if finish.cur == finish.first.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>:: pop_back_aux() {
  deallocate_node(finish.first);	// 先调用析构函数
  finish.set_node(finish.node - 1);	// 再移动node
  finish.cur = finish.last - 1;		// 然后cur指向当前数组的最后位置
  destroy(finish.cur);				// 最后释放内存空间.
}

// Called only if start.cur == start.last - 1.  Note that if the deque
//  has at least one element (a necessary precondition for this member
//  function), and if start.cur == start.last, then the deque must have
//  at least two nodes.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::pop_front_aux() {
  destroy(start.cur);				// 先释放内存空间.
  deallocate_node(start.first);		// 再调用析构函数
  start.set_node(start.node + 1);	// 然后移动node
  start.cur = start.first;			// 最后cur指向当前数组的第一个位置
}

注意 这里 dellocate_node 函数是析构的数组空间

reserve_map_at一类函数. pop和push都先调用了reserve_map_at_XX函数, 这些函数
主要是为了判断前后空间是否足够.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
  public:
  void new_elements_at_front(size_type new_elements);
  void new_elements_at_back(size_type new_elements);

  void destroy_nodes_at_front(iterator before_start);
  void destroy_nodes_at_back(iterator after_finish);

protected:                      // Allocation of map and nodes
  // Makes sure the map has space for new nodes.  Does not actually
  //  add the nodes.  Can invalidate map pointers.  (And consequently, 
  //  deque iterators.)
	// 始终保证后面要有一个及以上的空数组大小
  void reserve_map_at_back (size_type nodes_to_add = 1) {
    if (nodes_to_add + 1 > map_size - (finish.node - map))
      reallocate_map(nodes_to_add, false);
  }
	// 始终保证前面要有一个及以上的空数组大小
  void reserve_map_at_front (size_type nodes_to_add = 1) {
    if (nodes_to_add > start.node - map)
      reallocate_map(nodes_to_add, true);
  }

  void reallocate_map(size_type nodes_to_add, bool add_at_front);
    ...
};

对于 reallocate_map 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::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;
    // map_size > 2 * new_num_nodes 发现deque空间还很充足就只是调整deque内部的元素就行了, 没必要重新开空间
    // 这种情况主要出现在一直往首或尾单方向插入元素, 导致首(尾)前面还有很多余留的空间, 这种情况就这样调整
  if (map_size > 2 * new_num_nodes) {
    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;
	// 分配空间. 重新定位start的位置
    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);
      // 拷贝原deque元素, 最后释放掉原内存空间
    copy(start.node, finish.node + 1, new_nstart);
    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);
}

其是在 deque 空间不足时使用, 来进行扩容

  1. deque 的空间足够使用 其内部移动 start, finish 来实现, 这种情况一般是前后剩余空间失衡所进行的移动
  2. deque 空间不足
    i. 申请更大的空间
    ii. 将所有元素拷贝到新的空间
    iii. 修改原 map 的 start 和 finish 指向
1
2
3
4
5
6
7
8
9
10
11
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::destroy_nodes_at_front(iterator before_start) {
  for (map_pointer n = before_start.node; n < start.node; ++n)
    deallocate_node(*n);
}

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::destroy_nodes_at_back(iterator after_finish) {
  for (map_pointer n = after_finish.node; n > finish.node; --n)
    deallocate_node(*n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public:  
  iterator reserve_elements_at_front(size_type n) {
      //查看最前面的数组剩余多少空间
    size_type vacancies = start.cur - start.first;
    if (n > vacancies) 
        //给多出元素数量在分配足够的数组
      new_elements_at_front(n - vacancies);
      //返回重新添加元素后的新的 start
    return start - difference_type(n);
  }

    //同上
  iterator 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 + difference_type(n);
  }
    ...
};
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::new_elements_at_front(size_type new_elements) {
    //计算至少需要多少数组
  size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
  reserve_map_at_front(new_nodes);
  size_type i;
  __STL_TRY {
      //初始化
    for (i = 1; i <= new_nodes; ++i)
      *(start.node - i) = allocate_node();
  }
# ifdef __STL_USE_EXCEPTIONS
  catch(...) {
    for (size_type j = 1; j < i; ++j)
      deallocate_node(*(start.node - j));      
    throw;
  }
#endif /* __STL_USE_EXCEPTIONS */
}

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::new_elements_at_back(size_type new_elements) {
  size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();
  reserve_map_at_back(new_nodes);
  size_type i;
  __STL_TRY {
    for (i = 1; i <= new_nodes; ++i)
      *(finish.node + i) = allocate_node();
  }
#ifdef __STL_USE_EXCEPTIONS
  catch(...) {
    for (size_type j = 1; j < i; ++j)
      deallocate_node(*(finish.node + j));      
    throw;
  }
#endif /* __STL_USE_EXCEPTIONS */
}

删除操作

之前考虑到 deque 在前后实现插入时为了保证时间复杂度为 O(1), 所以在前后预留了空间, 所以 push 和 `pop 都可以在前面的数组进行操作

对于 earse 由于 deque 是由数组构成的, 所以地址空间是 相对连续 的, 故在删除时也要像 vector 一样, 要移动大量元素, deque 为了保证效率尽可能的高, 采用了判断删除的位置是中间偏后还是中间偏前来进行移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public:                         // Erase
  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;
  }
	// 范围删除, 实际也是调用上面的erase函数.
  iterator erase(iterator first, iterator last);
  void clear(); 
    ...
};

erase(iterator first, iterator last)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template <class T, class Alloc, size_t BufSize>
deque<T, Alloc, BufSize>::iterator 
deque<T, Alloc, BufSize>::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) {
      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)
        data_allocator::deallocate(*cur, buffer_size());
      start = new_start;
    }
      // 删除的地方是中间偏后, 移动后面的元素
    else {
      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)
        data_allocator::deallocate(*cur, buffer_size());
      finish = new_finish;
    }
    return start + elems_before;
  }
}

clear 方法

删除所有元素, 一共有两步

  1. 从第二个数组一直到倒数第二个数组, 一次性全部删除, 因为中间的数组一定是满的
  2. 删除首尾两个数组元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::clear() {
	// 从第二个数组开始到倒数第二个数组一次性全部删除
	// 毕竟中间的数组肯定都是满的, 前后两个数组就不一定是填充满的.
  for (map_pointer node = start.node + 1; node < finish.node; ++node) {
    destroy(*node, *node + buffer_size());
    data_allocator::deallocate(*node, buffer_size());
  }
	// 删除前后两个数组的元素.
  if (start.node != finish.node) { // 防止重复释放元素
    destroy(start.cur, start.last);
    destroy(finish.first, finish.cur);
    data_allocator::deallocate(finish.first, buffer_size());
  }
  else
    destroy(start.cur, finish.cur);

  finish = start;
}

swap

deque的swap操作也只是交换了start, finish, map, 并没有交换所有的元素.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
        ...
    	void swap(deque& x)
        {
        	__STD::swap(start, x.start);
        	__STD::swap(finish, x.finish);
        	__STD::swap(map, x.map);
        	__STD::swap(map_size, x.map_size);
      	}
        ...
};
template <class T, class Alloc, size_t BufSiz>
inline void swap(deque<T, Alloc, BufSiz>& x, deque<T, Alloc, BufSiz>& y) {
  x.swap(y);
}

resize函数

resize函数. 重新将deque进行调整, 实现与list一样的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public: 
    void resize(size_type new_size) { resize(new_size, value_type()); }
    void resize(size_type new_size, const value_type& x) {
    const size_type len = size();
    // 元素大小大于了要修改的大小, 则释放掉超过的元素
    if (new_size < len) 
      erase(start + new_size, finish);
    // 元素不够, 就从end开始到要求的大小为止都初始化x
    else
      insert(finish, new_size - len, x);
  }
};

insert

insert 实现

先列出所有的重载方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
iterator insert(iterator position, const value_type& x);
iterator insert(iterator position) ;

// 调用相同的重载函数
void insert(iterator pos, size_type n, const value_type& x);
void insert(iterator pos, int n, const value_type& x);
void insert(iterator pos, long n, const value_type& x);

void insert(iterator pos, InputIterator first, InputIterator last);
void insert(iterator pos, const value_type* first, const value_type* last);
void insert(iterator pos, const_iterator first, const_iterator last);

void insert(iterator pos, InputIterator first, InputIterator last, input_iterator_tag);
void insert(iterator pos, ForwardIterator first, ForwardIterator last,forward_iterator_tag);

单点插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public:                         // Insert
  iterator insert(iterator position, const value_type& x) {
      // 如果只是在头尾插入, 直接调用push就行了.
    if (position.cur == start.cur) {
      push_front(x);
      return start;
    }
    else if (position.cur == finish.cur) {
      push_back(x);
      iterator tmp = finish;
      --tmp;
      return tmp;
    }
      // 随机插入
    else {
      return insert_aux(position, x);
    }
  }
};

单位置插入多个元素

**insert(iterator pos, size_type n, const value_type& x) ** 在指定的位置插入n个元素并初始化.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert(iterator pos, size_type n, const value_type& x) 
{
    // 同样判断是不是直接在头尾进行插入.
  if (pos.cur == start.cur) {
      // 判断还有没有足够的空间
    iterator new_start = reserve_elements_at_front(n);
    uninitialized_fill(new_start, start, x); // 范围初始化
    start = new_start;	// 修改start位置
  }
  else if (pos.cur == finish.cur) {
    iterator new_finish = reserve_elements_at_back(n);	// 判断还有没有足够的空间
    uninitialized_fill(finish, new_finish, x);	// 范围初始化
    finish = new_finish;	// 修改finish位置
  }	
    // 随机插入
  else 
    insert_aux(pos, n, x);
}
  void insert(iterator pos, int n, const value_type& x) {
    insert(pos, (size_type) n, x);
  }
  void insert(iterator pos, long n, const value_type& x) {
    insert(pos, (size_type) n, x);
  }

**void insert(iterator pos, InputIterator first, InputIterator last) **. 通过参数的类型选择最优, 高效率的插入方式.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last) 
{
    insert(pos, first, last, iterator_category(first));
}

// input_iterator_tag类型的迭代器
template <class T, class Alloc, size_t BufSize>
template <class InputIterator>
void deque<T, Alloc, BufSize>::insert(iterator pos,InputIterator first, InputIterator last,
input_iterator_tag) 
{
  copy(first, last, inserter(*this, pos));	// 直接调用copy函数
}

// forward_iterator_tag类型的迭代器
template <class T, class Alloc, size_t BufSize>
template <class ForwardIterator>
void deque<T, Alloc, BufSize>::insert(iterator pos,ForwardIterator first,ForwardIterator last,forward_iterator_tag) 
{
  size_type n = 0;
  distance(first, last, n); // 计算迭代器之间的距离
    // 同样, 首尾插入判断
  if (pos.cur == start.cur) {
    iterator new_start = reserve_elements_at_front(n);
    __STL_TRY {
      uninitialized_copy(first, last, new_start);
      start = new_start;
    }
    __STL_UNWIND(destroy_nodes_at_front(new_start));
  }
  else if (pos.cur == finish.cur) {
    iterator new_finish = reserve_elements_at_back(n);
    __STL_TRY {
      uninitialized_copy(first, last, finish);
      finish = new_finish;
    }
    __STL_UNWIND(destroy_nodes_at_back(new_finish));
  }
    // 随机插入
  else
    insert_aux(pos, first, last, n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert(iterator pos,const value_type* first,const value_type* last) 
{
  size_type n = last - first;
  if (pos.cur == start.cur) {
    iterator new_start = reserve_elements_at_front(n);
    __STL_TRY {
      uninitialized_copy(first, last, new_start);
      start = new_start;
    }
    __STL_UNWIND(destroy_nodes_at_front(new_start));
  }
  else if (pos.cur == finish.cur) {
    iterator new_finish = reserve_elements_at_back(n);
    __STL_TRY {
      uninitialized_copy(first, last, finish);
      finish = new_finish;
    }
    __STL_UNWIND(destroy_nodes_at_back(new_finish));
  }
  else
    insert_aux(pos, first, last, n);
}

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert(iterator pos,const_iterator first,const_iterator last)
{
  size_type n = last - first;
  if (pos.cur == start.cur) {
    iterator new_start = reserve_elements_at_front(n);
    __STL_TRY {
      uninitialized_copy(first, last, new_start);
      start = new_start;
    }
    __STL_UNWIND(destroy_nodes_at_front(new_start));
  }
  else if (pos.cur == finish.cur) {
    iterator new_finish = reserve_elements_at_back(n);
    __STL_TRY {
      uninitialized_copy(first, last, finish);
      finish = new_finish;
    }
    __STL_UNWIND(destroy_nodes_at_back(new_finish));
  }
  else
    insert_aux(pos, first, last, n);
}

insert_aux

上面的每一个方法, 基本都调用了 insert_aux 方法, 下面就介绍一下该方法

**insert_aux(iterator pos, const value_type& x) **

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template <class T, class Alloc, size_t BufSize>
typename deque<T, Alloc, BufSize>::iterator
deque<T, Alloc, BufSize>::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进行调整
    copy(front2, pos1, front1);
  }
    // 离尾近
  else {
    push_back(back());	// 将尾往前移动
      // 调整将要移动的距离
    iterator back1 = finish;
    --back1;
    iterator back2 = back1;
    --back2;
    pos = start + index;
      // 用copy进行调整
    copy_backward(pos, back2, back1);
  }
  *pos = x_copy;
  return pos;
}

**insert_aux(iterator pos, size_type n, const value_type& x) ** 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert_aux(iterator pos, size_type n, const value_type& x) 
{
  const difference_type elems_before = pos - start;
  size_type length = size();
  value_type x_copy = x;
    // 判断插入的位置离头还是尾比较近
    // 离头近
  if (elems_before < length / 2) {
    iterator new_start = reserve_elements_at_front(n);	// 新的内存空间
    iterator old_start = start;
      // 计算pos的新位置
    pos = start + elems_before;
    __STL_TRY {
        // 到头的距离大于插入的个数n
      if (elems_before >= difference_type(n)) {
          // 一部分一部分的进行调整
        iterator start_n = start + difference_type(n);
        uninitialized_copy(start, start_n, new_start);
        start = new_start;
        copy(start_n, pos, old_start);
        fill(pos - difference_type(n), pos, x_copy);
      }
        // 到头的距离不大于插入的个数n
      else {
        __uninitialized_copy_fill(start, pos, new_start, start, x_copy);
        start = new_start;
        fill(old_start, pos, x_copy);
      }
    }
    __STL_UNWIND(destroy_nodes_at_front(new_start));
  }
    // 离尾近. 执行都是一样的
  else {
    iterator new_finish = reserve_elements_at_back(n);
    iterator old_finish = finish;
    const difference_type elems_after = difference_type(length) - elems_before;
    pos = finish - elems_after;
    __STL_TRY {
      if (elems_after > difference_type(n)) {
        iterator finish_n = finish - difference_type(n);
        uninitialized_copy(finish_n, finish, finish);
        finish = new_finish;
        copy_backward(pos, finish_n, old_finish);
        fill(pos, pos + difference_type(n), x_copy);
      }
      else {
        __uninitialized_fill_copy(finish, pos + difference_type(n),
                                  x_copy,
                                  pos, finish);
        finish = new_finish;
        fill(pos, old_finish, x_copy);
      }
    }
    __STL_UNWIND(destroy_nodes_at_back(new_finish));
  }
}

剩余方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#ifdef __STL_MEMBER_TEMPLATES  
template <class T, class Alloc, size_t BufSize>
template <class ForwardIterator>
void deque<T, Alloc, BufSize>::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 < length / 2) {
    iterator new_start = reserve_elements_at_front(n);
    iterator old_start = start;
    pos = start + elems_before;
    __STL_TRY {
      if (elems_before >= difference_type(n)) {
        iterator start_n = start + difference_type(n); 
        uninitialized_copy(start, start_n, new_start);
        start = new_start;
        copy(start_n, pos, old_start);
        copy(first, last, pos - difference_type(n));
      }
      else {
        ForwardIterator mid = first;
        advance(mid, difference_type(n) - elems_before);
        __uninitialized_copy_copy(start, pos, first, mid, new_start);
        start = new_start;
        copy(mid, last, old_start);
      }
    }
    __STL_UNWIND(destroy_nodes_at_front(new_start));
  }
  else {
    iterator new_finish = reserve_elements_at_back(n);
    iterator old_finish = finish;
    const difference_type elems_after = difference_type(length) - elems_before;
    pos = finish - elems_after;
    __STL_TRY {
      if (elems_after > difference_type(n)) {
        iterator finish_n = finish - difference_type(n);
        uninitialized_copy(finish_n, finish, finish);
        finish = new_finish;
        copy_backward(pos, finish_n, old_finish);
        copy(first, last, pos);
      }
      else {
        ForwardIterator mid = first;
        advance(mid, elems_after);
        __uninitialized_copy_copy(mid, last, pos, finish, finish);
        finish = new_finish;
        copy(first, mid, pos);
      }
    }
    __STL_UNWIND(destroy_nodes_at_back(new_finish));
  }
}

#else /* __STL_MEMBER_TEMPLATES */

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert_aux(iterator pos,
                                          const value_type* first,
                                          const value_type* last,
                                          size_type n)
{
  const difference_type elems_before = pos - start;
  size_type length = size();
  if (elems_before < length / 2) {
    iterator new_start = reserve_elements_at_front(n);
    iterator old_start = start;
    pos = start + elems_before;
    __STL_TRY {
      if (elems_before >= difference_type(n)) {
        iterator start_n = start + difference_type(n);
        uninitialized_copy(start, start_n, new_start);
        start = new_start;
        copy(start_n, pos, old_start);
        copy(first, last, pos - difference_type(n));
      }
      else {
        const value_type* mid = first + (difference_type(n) - elems_before);
        __uninitialized_copy_copy(start, pos, first, mid, new_start);
        start = new_start;
        copy(mid, last, old_start);
      }
    }
    __STL_UNWIND(destroy_nodes_at_front(new_start));
  }
  else {
    iterator new_finish = reserve_elements_at_back(n);
    iterator old_finish = finish;
    const difference_type elems_after = difference_type(length) - elems_before;
    pos = finish - elems_after;
    __STL_TRY {
      if (elems_after > difference_type(n)) {
        iterator finish_n = finish - difference_type(n);
        uninitialized_copy(finish_n, finish, finish);
        finish = new_finish;
        copy_backward(pos, finish_n, old_finish);
        copy(first, last, pos);
      }
      else {
        const value_type* mid = first + elems_after;
        __uninitialized_copy_copy(mid, last, pos, finish, finish);
        finish = new_finish;
        copy(first, mid, pos);
      }
    }
    __STL_UNWIND(destroy_nodes_at_back(new_finish));
  }
}

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert_aux(iterator pos,
                                          const_iterator first,
                                          const_iterator last,
                                          size_type n)
{
  const difference_type elems_before = pos - start;
  size_type length = size();
  if (elems_before < length / 2) {
    iterator new_start = reserve_elements_at_front(n);
    iterator old_start = start;
    pos = start + elems_before;
    __STL_TRY {
      if (elems_before >= n) {
        iterator start_n = start + n;
        uninitialized_copy(start, start_n, new_start);
        start = new_start;
        copy(start_n, pos, old_start);
        copy(first, last, pos - difference_type(n));
      }
      else {
        const_iterator mid = first + (n - elems_before);
        __uninitialized_copy_copy(start, pos, first, mid, new_start);
        start = new_start;
        copy(mid, last, old_start);
      }
    }
    __STL_UNWIND(destroy_nodes_at_front(new_start));
  }
  else {
    iterator new_finish = reserve_elements_at_back(n);
    iterator old_finish = finish;
    const difference_type elems_after = length - elems_before;
    pos = finish - elems_after;
    __STL_TRY {
      if (elems_after > n) {
        iterator finish_n = finish - difference_type(n);
        uninitialized_copy(finish_n, finish, finish);
        finish = new_finish;
        copy_backward(pos, finish_n, old_finish);
        copy(first, last, pos);
      }
      else {
        const_iterator mid = first + elems_after;
        __uninitialized_copy_copy(mid, last, pos, finish, finish);
        finish = new_finish;
        copy(first, mid, pos);
      }
    }
    __STL_UNWIND(destroy_nodes_at_back(new_finish));
  }
}

总结:

为了渐少在增加或者删除元素时移动元素所带来的时间复杂度的提升, deque 的设计不可谓不复杂, 但是我认为, 其是为了支持更多的功能而采用如此复杂的设计. 不过其中一些操作在我看来是不需要进行深入了解的, 比如 earse 以及 insert 操作, 其原因在于对于 deque 的定义双端队列的元素出入顺序就只允许首尾进出, 所以对于deque 设计出的随机插入, 删除, 提取元素是不符合双端队列的定义, 而且绝大多数使用者都是按照双端队列的定义来进行使用的, 我暂时没有思考出 deque 提供如此复杂的设计和功能是出于什么目的, 不过以后在阅读了更多的优秀源码之后, 可能会得到答案, 到时会进行分析==(预定 <分析为何部分 **STL** 容器的设计复杂度远超过其定义> )==.

在后续实现自己 Tiny STL 时, 考虑使用 list 作为适配器来实现 deque的功能, 其实对于 stack 和 queue 使用list 来实现底层容器在时间复杂度上是相对优于标准库提供的deque, 对于绝大多数使用者, 本质上还是在使用其定义出的结构来使用此类容器, 所以并不会设计的如此复杂, 从而考虑尽可能降低时间复杂度