从零开始的 STL 实现记录：Container-2.2

前言

相较于 vector 的连续线性空间，list 就显得复杂许多、它的好处是每次插人或删除一个元素，就配置或释放一个元素空间。因此，1ist 对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list 永远是常数时间。
———— 《STL源码剖析》侯捷

本篇博客将会分析 STL 中 list 的基本函数。值得注意的是，在原始的 MyTinySTL 仓库中，作者 list 部分的实现方式是有些怪异的，包括但不限于：使用了本该出现在 SGI-STL 的 slist 中的 base_ptr 与 node_ptr 来代表 list 的指针、没有实现 transfer 函数、sort 的实现也很繁杂；保险起见，下面的解析均以 SGI-STL 中的实现为准。

list 的构造函数

辅助函数

以下函数为实现构造函数的辅助函数，包括对于空间的分配与释放，节点的构造与析构等。

template <class T, class Alloc = alloc>
class list 
{
    ...
protected:
	// 分配一个元素大小的空间, 返回分配的地址
    link_type get_node() { return list_node_allocator::allocate(); }
    // 释放一个元素大小的内存
    void put_node(link_type p) { list_node_allocator::deallocate(p); }
	// 分配一个元素大小的空间并调用构造初始化内存
    link_type create_node(const T& x) 
    {
      link_type p = get_node();
      __STL_TRY {
        construct(&p->data, x);
      }
      __STL_UNWIND(put_node(p));
      return p;
    }
    // 调用析构并释放一个元素大小的空间
    void destroy_node(link_type p) {
      destroy(&p->data);
      put_node(p);
    }
    // 对节点初始化
    void empty_initialize() { 
      node = get_node();
      node->next = node;
      node->prev = node;
    }  
    ...
};

其中，比较特殊的是 empty_initialize() 这个函数，该函数构造了一个节点并将其地址赋予 node，也就是在上一节提到的可以遍历整个 list 的空节点。

构造函数

构造函数有多个重载，以实现直接构造 n 个节点并初始化一个值，支持传入迭代器进行范围初始化，
也支持接受一个 list 参数，同样进行范围初始化.

template <class T, class Alloc = alloc>
class list 
{
    ...
protected: 
    // 构造函数
    list() { empty_initialize(); }	// 默认构造函数, 分配一个空的node节点
    // 都调用同一个函数进行初始化
    list(size_type n, const T& value) { fill_initialize(n, value); }
    list(int n, const T& value) { fill_initialize(n, value); }
    list(long n, const T& value) { fill_initialize(n, value); }
    // 分配n个节点
    explicit list(size_type n) { fill_initialize(n, T()); }

#ifdef __STL_MEMBER_TEMPLATES
    // 接受两个迭代器进行范围的初始化
    template <class InputIterator>
      list(InputIterator first, InputIterator last) {
        range_initialize(first, last);
      }
#else /* __STL_MEMBER_TEMPLATES */
    // 接受两个迭代器进行范围的初始化
    list(const T* first, const T* last) { range_initialize(first, last); }
    list(const_iterator first, const_iterator last) {
      range_initialize(first, last);
    }
#endif /* __STL_MEMBER_TEMPLATES */
    // 接受一个list参数, 进行拷贝
    list(const list<T, Alloc>& x) {
      range_initialize(x.begin(), x.end());
    }
    list<T, Alloc>& operator=(const list<T, Alloc>& x);
    ...
};

构造函数内大都调用这个函数，可以看出来list在初始化的时候都会构造一个空的node节点，
然后对元素进行insert插入操作。

void fill_initialize(size_type n, const T& value) {
    empty_initialize();
    __STL_TRY {
    insert(begin(), n, value);
    }
    __STL_UNWIND(clear(); put_node(node));
}

list 操作

push和pop操作

由于 list 是一个双向环状链表，只要我们把边际条件处理好，那么，在头部或尾部插入元素（ push_front 和 push_back ），操作几乎是一样的，在头部或尾部移除元素（ pop_front 和 pop_back ），操作耶几乎是一样的，移除 ( erase ) 某个迭代器所指元素，只是进行一些指针移动操作而已，并不复杂。

template <class T, class Alloc = alloc>
class list 
{
    ...
    // 直接在头部或尾部插入
    void push_front(const T& x) { insert(begin(), x); }
    void push_back(const T& x) { insert(end(), x); }
    // 直接在头部或尾部删除
    void pop_front() { erase(begin()); }
    void pop_back() { 
      iterator tmp = end();
      erase(--tmp);
    }
    ...
};

删除操作

删除元素的操作大都是由erase函数来实现的, 其他的所有函数都是直接或间接调用erase. list是链表, 所以链表怎么实现删除, list就在怎么操作.

template <class T, class Alloc = alloc>
class list 
{
    ...
	iterator erase(iterator first, iterator last);
    void clear();   
    // 参数是一个迭代器
    // 修改该元素的前后指针指向再单独释放节点就行了
	iterator erase(iterator position) {
      link_type next_node = link_type(position.node->next);
      link_type prev_node = link_type(position.node->prev);
      prev_node->next = next_node;
      next_node->prev = prev_node;
      destroy_node(position.node);
      return iterator(next_node);
    }
    ...
};
// erase的重载, 删除两个迭代器之间的元素
template <class T, class Alloc>
list<T,Alloc>::iterator list<T, Alloc>::erase(iterator first, iterator last) 
{
    // 就是一次次调用erase进行删除
  	while (first != last) 
        erase(first++);
  	return last;
}
// remove调用erase链表清除
template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {
  iterator first = begin();
  iterator last = end();
  while (first != last) {
    iterator next = first;
    ++next;
    if (*first == value) erase(first);
    first = next;
  }
}

clear函数是删除除空节点以外的所有节点, 即只留下了最初创建的空节点.

// 删除除空节点以外的所有节点
template <class T, class Alloc> 
void list<T, Alloc>::clear()
{
  link_type cur = (link_type) node->next;
    // 除空节点都删除
  while (cur != node) {
    link_type tmp = cur;
    cur = (link_type) cur->next;
    destroy_node(tmp);
  }
  node->next = node;
  node->prev = node;
}

重载

list也提供了基本操作的重载, 所以我们使用list也很方便.

相等比较

// 判断两个list相等
template <class T, class Alloc>
inline bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y) 
{
  typedef typename list<T,Alloc>::link_type link_type;
  link_type e1 = x.node;
  link_type e2 = y.node;
  link_type n1 = (link_type) e1->next;
  link_type n2 = (link_type) e2->next;
    // 将两个链表执行一一的对比来分析是否相等. 
    // 这里不把元素个数进行一次比较, 主要获取个数时也要遍历整个数组, 所以就不将个数纳入比较
  for ( ; n1 != e1 && n2 != e2 ; n1 = (link_type) n1->next, n2 = (link_type) n2->next)
    if (n1->data != n2->data)
      return false;
  return n1 == e1 && n2 == e2;
}

小于比较

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

赋值操作

需要考虑两个链表的实际大小不一样时的操作.

1. 原链表大 : 复制完后要删除掉原链表多余的元素
2. 原链表小 : 复制完后要还要将x链表的剩余元素以插入的方式插入到原链表中

template <class T, class Alloc>
list<T, Alloc>& list<T, Alloc>::operator=(const list<T, Alloc>& x) {
  if (this != &x) {
    iterator first1 = begin();
    iterator last1 = end();
    const_iterator first2 = x.begin();
    const_iterator last2 = x.end();
    // 直到两个链表有一个空间用尽
    while (first1 != last1 && first2 != last2) 
    	*first1++ = *first2++;
    //	原链表大, 复制完后要删除掉原链表多余的元素
    if (first2 == last2)
      erase(first1, last1);
    //  原链表小, 复制完后要还要将x链表的剩余元素以插入的方式插入到原链表中
    else
      insert(last1, first2, last2);
  }
  return *this;
}

resize操作

resize重新修改list的大小

template <class T, class Alloc = alloc>
class list 
{
    ...
    resize(size_type new_size, const T& x);
	void resize(size_type new_size) { resize(new_size, T()); }
    ...
}; 
template <class T, class Alloc>
void list<T, Alloc>::resize(size_type new_size, const T& x)
{
  iterator i = begin();
  size_type len = 0;
  for ( ; i != end() && len < new_size; ++i, ++len)
    ;
  // 如果链表长度大于new_size的大小, 那就删除后面多余的节点
  if (len == new_size)
    erase(i, end());
    // i == end(), 扩大链表的节点
  else                          
    insert(end(), new_size - len, x);
}

unique操作

unique函数是将数值相同且连续的元素删除, 只保留一个副本. 记住, unique并不是删除所有的相同元素, 而是连续的相同元素, 如果要删除所有相同元素就要对list做一个排序在进行unique操作.

一般unique同sort一起用的. sort函数准备放在下一节来分析.

template <class T, class Alloc> template <class BinaryPredicate>
void list<T, Alloc>::unique(BinaryPredicate binary_pred) {
  iterator first = begin();
  iterator last = end();
  if (first == last) return;
  iterator next = first;
  // 删除连续相同的元素, 留一个副本
  while (++next != last) {
    if (binary_pred(*first, *next))
      erase(next);
    else
      first = next;
    next = first;
  }
}

insert操作

insert函数有很多的重载函数, 满足足够用户的各种插入方法了. 但是最核心的还是iterator insert(iterator position, const T& x), 每一个重载函数都是直接或间接的调用该函数.

insert是将元素插入到指定地址的前一个位置.

template <class T, class Alloc = alloc>
class list 
{
    ...
public:
    // 最基本的insert操作, 之插入一个元素
    iterator insert(iterator position, const T& x) 
    {
        // 将元素插入指定位置的前一个地址
      link_type tmp = create_node(x);
      tmp->next = position.node;
      tmp->prev = position.node->prev;
      (link_type(position.node->prev))->next = tmp;
      position.node->prev = tmp;
      return tmp;
    }
    
   // 以下重载函数都是调用iterator insert(iterator position, const T& x)函数
   iterator insert(iterator position) { return insert(position, T()); }
#ifdef __STL_MEMBER_TEMPLATES
    template <class InputIterator>
      void insert(iterator position, InputIterator first, InputIterator last);
#else /* __STL_MEMBER_TEMPLATES */
    void insert(iterator position, const T* first, const T* last);
    void insert(iterator position,
        const_iterator first, const_iterator last);
#endif /* __STL_MEMBER_TEMPLATES */
    void insert(iterator pos, size_type n, const T& x);
    void insert(iterator pos, int n, const T& x) {
      insert(pos, (size_type)n, x);
    }
    void insert(iterator pos, long n, const T& x) {
      insert(pos, (size_type)n, x);
    }
    void resize(size_type new_size, const T& x);
    ...
};

#ifdef __STL_MEMBER_TEMPLATES
template <class T, class Alloc> template <class InputIterator>
void list<T, Alloc>::insert(iterator position, InputIterator first, InputIterator last) 
{
  	for ( ; first != last; ++first)
    	insert(position, *first);
}
#else /* __STL_MEMBER_TEMPLATES */
template <class T, class Alloc>
void list<T, Alloc>::insert(iterator position, const T* first, const T* last) {
  for ( ; first != last; ++first)
    insert(position, *first);
}
template <class T, class Alloc>
void list<T, Alloc>::insert(iterator position,
    const_iterator first, const_iterator last) {
  for ( ; first != last; ++first)
    insert(position, *first);
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class T, class Alloc>
void list<T, Alloc>::insert(iterator position, size_type n, const T& x) {
  for ( ; n > 0; --n)
    insert(position, x);
}

总结

本节分析了list的构造、插入、删除，重载等操作，这些都是链表的基本操作，相信大家看的时候应该也没有什么问题，链表最复杂也是最精华的操作在于 transfer、merge 以及 sort，这些将放到下一节分析。
这里还是提醒一下:

1. 节点实际是以node空节点开始的
2. 插入操作是将元素插入到指定位置的前一个地址进行插入的.