SGISTL源码阅读十五 deque容器中

SGISTL源码阅读十五 deque容器中

前言

我们已经学习了deque的数据结构和它的迭代器，接下来我们继续学习它的构造及内存申请等内容。

---

深入源码

deque的构造函数

• 默认构造函数

/* 指针数组不申请空间
 * 并且first和finish迭代器也调用默认构造函数
 */
public:
  deque()
    : start(), finish(), map(0), map_size(0)
  {
    create_map_and_nodes(0);
  }

• 拷贝构造函数

  /* 分配了空间之后
   * 将x中的元素拷贝过去
   */
  deque(const deque& x)
    : start(), finish(), map(0), map_size(0)
  {
    //申请指针数组map的大小及线性空间（缓冲区buffer）
    create_map_and_nodes(x.size());
    __STL_TRY {
      uninitialized_copy(x.begin(), x.end(), start);
    }
    __STL_UNWIND(destroy_map_and_nodes());
  }

• 初始化n个值为value的元素
  根据不同的情况设计了不同的重载版本，它们都调用了fill_initialize函数

  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关键字已经见到过几次了，用途是防止隐式转换

  explicit deque(size_type n)
    : start(), finish(), map(0), map_size(0)
  {
    fill_initialize(n, value_type());
  }

• 迭代器范围构造
  同样根据不同的情况有多个不同的重载版本

#ifdef __STL_MEMBER_TEMPLATES
  template <class InputIterator>
  deque(InputIterator first, InputIterator last)
    : start(), finish(), map(0), map_size(0)
  {
    //range_initialize根据迭代器的类型选择最优的初始化方式
    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

申请指针数组map的大小及线性空间（缓冲区buffer）

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) {
  /* 计算结点个数
   * buffer_size()返回每段线性空间能容量元素的个数
   * num_elements代表需要申请的元素的个数
   * num_nodes代表需要申请的结点个数
   */
  size_type num_nodes = num_elements / buffer_size() + 1;
  /* map至少有8个结点,最多num_nodes + 2
   * 之所以要设计成num_nodes + 2
   * 是为了当插入元素分别到尾部和首部时有一定的扩展性,而不用一插入元素就分配空间
   */
  map_size = max(initial_map_size(), num_nodes + 2);
  //申请空间
  map = map_allocator::allocate(map_size);
  map_pointer nstart = map + (map_size - num_nodes) / 2;
  map_pointer nfinish = nstart + num_nodes - 1;
  map_pointer cur;
  __STL_TRY {
    /* 申请一整段线性空间
     * allocate_node的原型如下
     * return data_allocator::allocate(buffer_size();
     */
    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迭代器
  start.set_node(nstart);
  finish.set_node(nfinish);
  start.cur = start.first;
  finish.cur = finish.first + num_elements % buffer_size();
}

deque的初始化操作

fill_initialize

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::fill_initialize(size_type n,
                                               const value_type& value) {
  //创建map和nodes
  create_map_and_nodes(n);
  map_pointer cur;
  __STL_TRY {
    //初始化每一个node节点
    //初始化未初始化的值为value
    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 */
}

range_initialize

在进行构造的时候传入的迭代器也有可能是别的类型的迭代器，不一定是random_access_iterator
以下range_initialize根据不同的情况写了不同的重载版本

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;
  //计算出[first, last)范围内的节点个数
  distance(first, last, n);
  //申请空间
  create_map_and_nodes(n);
  __STL_TRY {
    //拷贝
    uninitialized_copy(first, last, start);
  }
  //失败则直接销毁
  __STL_UNWIND(destroy_map_and_nodes());
}

deque的析构和内存释放

析构函数

  ~deque() {
    destroy(start, finish);
    destroy_map_and_nodes();
  }

destroy_map_and_nodes()

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);
}

总结

我们学习了deque的构造，析构等。
我们可以看出deque为了维护它独特的数据结构付出了很多代价，很多的操作都变得异常艰难和复杂，但是只要理解到它的数据结构这些都不难理解。接下来我们将继续学习deque的一些相关操作，要看懂这些代码的前提是我们必须深刻地理解deque的数据结构。