List

前言:

之前分析了 vector 的实现, 可以发现vector 的缺点在于处理高频率的插入与删除时的效率很低, 由于其是采用整体移动的方式处理插入与删除, 时间复杂度最坏是 O(n) , 而 list 则在删除与插入上有着优秀的效率

list 是使用链表实现的, 其对于删除和插入的时间复杂度为 O(1), 有着极其优秀的效率, 但是在于随机访问方面时间复杂度则为 O(n) , list 将具体实现分为了几个部分, 并通过嵌套的方式进行调用, 所以list 的实现也很灵活. 同时, list 在插入和删除后迭代器不会失效

list 基本结构框架

list 将基本的框架分为 __list_node (链表节点), __list_iterator (访问迭代器)

__list_node 链表结构

template <class T>
struct __list_node {
  //前后指针
  typedef void* void_pointer;
  void_pointer next;
  void_pointer prev;
  //节点数据
  T data;
};

__list_iterator 结构

基本属性

struct __list_iterator {
  //定义迭代器类型
  typedef __list_iterator<T, T&, T*>             iterator; 
  typedef __list_iterator<T, const T&, const T*> const_iterator;
  typedef __list_iterator<T, Ref, Ptr>           self;

  //定义迭代器为 bidirectional_iterator_tag 类型
  typedef bidirectional_iterator_tag iterator_category;
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef __list_node<T>* link_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  ...
}

构造函数

struct __list_iterator {
    
    //内部使用一个 __list_node<T>* 作为记录 list 中的某个节点信息
    typedef __list_node<T>* link_type;
    link_type node;
    
	__list_iterator(link_type x) : node(x) {}
	__list_iterator() {}
	__list_iterator(const iterator& x) : node(x.node) {}
    ...
}

重载运算符

struct __list_iterator {
  ....  
  bool operator==(const self& x) const { return node == x.node; }
  bool operator!=(const self& x) const { return node != x.node; }
  //对 * 运算符重载, 模拟指针的取值
  reference operator*() const { return (*node).data; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR
  //对 -> 运算符进行重载
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  //该迭代器是一个双向迭代器, 支持++, -- 运算符, 又 list 底层实现是由
  self& operator++() { 
    node = (link_type)((*node).next);
    return *this;
  }
  self operator++(int) { 
    self tmp = *this;
    ++*this;
    return tmp;
  }
  self& operator--() { 
    node = (link_type)((*node).prev);
    return *this;
  }
  self operator--(int) { 
    self tmp = *this;
    --*this;
    return tmp;
  }
  ....
};

traits 编程

list 的 iterator 自己实现了 traits 编程, 其迭代器是bidirectional_iterator_tag类型, 并不是一个普通指针.

#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION

//返回 list 迭代器的类型
template <class T, class Ref, class Ptr>
inline bidirectional_iterator_tag
iterator_category(const __list_iterator<T, Ref, Ptr>&) {
  return bidirectional_iterator_tag();
}

// 返回 list 迭代器中的类型
template <class T, class Ref, class Ptr>
inline T*
value_type(const __list_iterator<T, Ref, Ptr>&) {
  return 0;
}

template <class T, class Ref, class Ptr>
inline ptrdiff_t*
distance_type(const __list_iterator<T, Ref, Ptr>&) {
  return 0;
}

#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */

list 结构

list 基础类型定义

template <class T, class Alloc = alloc>
class list {
protected:
  typedef void* void_pointer;
  //定义节点信息	
  typedef __list_node<T> list_node;
  //节点内存分配
  typedef simple_alloc<list_node, Alloc> list_node_allocator;
public:      
  // 定义嵌套类型
  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 list_node* link_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

public:
  //定义迭代器以及反向迭代器
  typedef __list_iterator<T, T&, T*>             iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;

#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_bidirectional_iterator<const_iterator, value_type,
  const_reference, difference_type>
  const_reverse_iterator;
  typedef reverse_bidirectional_iterator<iterator, value_type, reference,
  difference_type>
  reverse_iterator; 
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    ....
};

list 构造和析构函数的实现

构造函数依赖的方法

get_node 分配节点空间
put_node 释放节点空间
create_node 分配并创建节点空间
destroy_node 调用节点内部数据析构函数并释放该节点空间
empty_initialize 对 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);
  }

protected:
  void empty_initialize() { 
    node = get_node();
    node->next = node;
    node->prev = node;
  }
  ....
};

构造函数

list 构造函数从上到下依次为:

空构造函数
创建一个长度为 n, 值为 value 的链表
4 为 2 的重载版本
如果允许拥有成员模板, 则提供接收其他 InputIterator 迭代器的类型的数据范围并将该范围内数据创建 list
反之根据提供的两个 list 迭代器来创建这两个迭代器范围内数据的 list

template <class T, class Alloc = alloc>
class list {
    .....	
  list() { empty_initialize(); }
    
  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); }
#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(const list<T, Alloc>& x) {
    range_initialize(x.begin(), x.end());
  }
  ....
};

对于前四个版本的构造函数都调用了 fill_initialize 方法, 可以看出其本质是先创建头节点, 然后对元素进行 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() {
    // 删除初空节点以外的所有节点
  clear();
    // 删除空节点
  put_node(node);
}

基本属性获取

iterator begin() { return (link_type)((*node).next); } // 获取 list 中第一个元素的迭代器, 没有则返回头节点 (end)
//同上 只不过返回的是 常量迭代器
const_iterator begin() const { return (link_type)((*node).next); }
//返回头节点, 也即尾部 end
iterator end() { return node; }
const_iterator end() const { return node; }
//返回反向迭代器
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const { 
    return const_reverse_iterator(end()); 
}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { 
    return const_reverse_iterator(begin());
} 

//如果 begin == end 那么就为空
bool empty() const { return node->next == node; }
size_type size() const {
    size_type result = 0;
    distance(begin(), end(), result);
    return result;
}
//最大值就是 unsigned long long 因为指针最多可以记录到 unsigned long long 个数量的地址
size_type max_size() const { return size_type(-1); }
//返回第一个元素引用
reference front() { return *begin(); }
const_reference front() const { return *begin(); }
//返回最后一个元素引用
reference back() { return *(--end()); }
const_reference back() const { return *(--end()); }

交换函数

可以看出, 交换两个链表并不是全部交换两个链表内元素, 而是交换头指针

1	void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); }

list 操作

这里主要介绍 list 的 pop, push 以及一些插入删除等基本操作

push 和 pop 操作

list 是一个双向链表, 所以对于 push 操作是在头部插入, 而 pop 则是在尾部插入, push 操作都调用了 insert 方法, pop 操作都调用了 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 方法来实现的, 由于 list 是一个双向链表, 所以 单节点的 erase 方法的操作就是双向链表的操作, 示例如下

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

// 利用 删除范围内元素的 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相等
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());
}

赋值操作

list 在赋值时要考虑两个链表的大小关系

原链表大, 就删除多余元素
原链表小, 在复制完本身容量后再将剩余元素以插入的形式加入原链表

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 操作

重新修改 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());
  else              
     //用 x 补充多出的元素
    insert(end(), new_size - len, x);
}

unique 操作

unique 方法是将 list 内连续且重复的节点删除至只剩一个, 注意: unique 并不是将整个 list 进行去重, 而是相同的连续元素, 如果要对整个 list 进行去重, 就要先对 list 进行一个排序, 所以对于 unique 方法, 通常与 sort 方法一起使用

template <class T, class Alloc>
void list<T, Alloc>::unique() {
  iterator first = begin();
  iterator last = end();
  if (first == last) return;
  iterator next = first;
  while (++next != last) {
    if (*first == *next)
      erase(next);
    else
      first = next;
    next = first;
  }
}

insert 操作

list 提供了多种重载方式的 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);
}

注意:

插入操作是将元素插入到指定位置的前一个位置

sort 操作

由于链表的元素空间地址并不是连续的, 所以对于 list 的 sort 操作需要单独实现, 由于该 sort 的实现过于复杂, 我不太能良好的用语言去分析所以引用了别的大佬的文章

以下部分引用自传送门

在分析sort之前先来分析transfer, reverse, merge这几个会被调用的函数.

transfer函数

transfer函数功能是将一段链表插入到我们指定的位置之前. 该函数一定要理解, 后面分析的所有函数都是该基础上进行修改的.

transfer函数接受3个迭代器. 第一个迭代器表示链表要插入的位置, first到last最闭右开区间插入到position之前.

从if下面开始分析(这里我将源码的执行的先后顺序进行的部分调整, 下面我分析的都是调整顺序过后的代码. 当然我也会把源码顺序写下来, 以便参考)

为了避免待会解释起来太绕口, 这里先统一一下部分名字

last的前一个节点叫last_but_one
first的前一个节点叫zero

好, 现在我们开始分析transfer的每一步(最好在分析的时候在纸上画出两个链表一步步来画)

第一行. last_but_one的next指向插入的position节点
第二行. position的next指向last_but_one
第三行. 临时变量tmp保存position的前一个节点
第四行. first的prev指向tmp
第五行. position的前一个节点的next指向first节点
第六行. zero的next指向last节点
第七行. last的prev指向zero

template <class T, class Alloc = alloc>
class list 
{
    ...
protected:
    void transfer(iterator position, iterator first, iterator last) 
    {
      if (position != last) 
      {
          (*(link_type((*last.node).prev))).next = position.node;
          (*position.node).prev = (*last.node).prev;
          link_type tmp = link_type((*position.node).prev);
          (*first.node).prev = tmp;
          (*(link_type((*position.node).prev))).next = first.node; 
          (*(link_type((*first.node).prev))).next = last.node;
          (*last.node).prev = (*first.node).prev; 
      }
    }
    /*
    void transfer(iterator position, iterator first, iterator last) 
    {
      if (position != last) 
      {
        (*(link_type((*last.node).prev))).next = position.node;
        (*(link_type((*first.node).prev))).next = last.node;
        (*(link_type((*position.node).prev))).next = first.node;  
        link_type tmp = link_type((*position.node).prev);
        (*position.node).prev = (*last.node).prev;
        (*last.node).prev = (*first.node).prev; 
        (*first.node).prev = tmp;
      }
    }
    */
    ...
};

splice 将两个链表进行合并.

template <class T, class Alloc = alloc>
class list 
{
    ...
public:
    void splice(iterator position, list& x) {
      if (!x.empty()) 
        transfer(position, x.begin(), x.end());
    }
    void splice(iterator position, list&, iterator i) {
      iterator j = i;
      ++j;
      if (position == i || position == j) return;
      transfer(position, i, j);
    }
    void splice(iterator position, list&, iterator first, iterator last) {
      if (first != last) 
        transfer(position, first, last);
    }
    ...
};

merge函数

merge函数接受一个list参数.

merge函数是将传入的list链表x与原链表按从小到大合并到原链表中(前提是两个链表都是已经从小到大排序了). 这里merge的核心就是transfer函数.

template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x) {
  iterator first1 = begin();
  iterator last1 = end();
  iterator first2 = x.begin();
  iterator last2 = x.end();
  while (first1 != last1 && first2 != last2)
    if (*first2 < *first1) {
      iterator next = first2;
      // 将first2到first+1的左闭右开区间插入到first1的前面
      // 这就是将first2合并到first1链表中
      transfer(first1, first2, ++next);
      first2 = next;
    }
    else
      ++first1;
      // 如果链表x还有元素则全部插入到first1链表的尾部
  if (first2 != last2) transfer(last1, first2, last2);
}

reverse函数

reverse函数是实现将链表翻转的功能. 主要是list的迭代器基本不会改变的特点, 将每一个元素一个个插入到begin之前. 这里注意迭代器不会变, 但是begin会改变, 它始终指向第一个元素的地址.

template <class T, class Alloc>
void list<T, Alloc>::reverse() 
{
  if (node->next == node || link_type(node->next)->next == node) 
  	return;
  iterator first = begin();
  ++first;
  while (first != end()) {
    iterator old = first;
    ++first;
      // 将元素插入到begin()之前
    transfer(begin(), old, first);
  }
}

sort

list实现sort 功能本身就不容易, 当我分析了之后就对其表示佩服. 严格的说list排序的时间复杂度应为nlog(n), 其实现用了归并排序的思想, 将所有元素分成n分, 总共2^n个元素.

这个sort的分析 :

这里将每个重要的参数列出来解释其含义
1. fill : 当前可以处理的元素个数为2^fill个
2. counter[fill] : 可以容纳2^(fill+1)个元素
3. carry : 一个临时中转站, 每次将一元素插入到counter[i]链表中.

在处理的元素个数不足 2^fill 个时，在counter[i](0<i<fill)之前转移元素

具体是显示步骤是：

每次读一个数据到 carry中，并将carry的数据转移到 counter[0] 中
1. 当counter[0]中的数据个数少于2时，持续转移数据到counter[0]中
2. 当counter[0]的数据个数等于2时，将counter[0]中的数据转移到counter[1]…从counter[i]转移到counter[i+1],直到counter[fill]中数据个数达到2^(fill+1)个。
++fill, 重复步骤1

//list 不能使用sort函数，因为list的迭代器是bidirectional_iterator, 而sort
//sort函数要求random_access_iterator
template<class T,class Alloc>
void list<T,Alloc>::sort()
{
    //如果元素个数小于等于1，直接返回
    if(node->next==node||node->next->next==node)
    return ;
    list<T,Alloc> carry; //中转站
    list<T,Alloc> counter[64];
    int fill=0;
    while(!empty())
    {
        carry.splice(carry.begin(),*this,begin());  //每次取出一个元素
        int i=0;    
        while(i<fill&&!counter[i].empty())
        {
            counter[i].merge(carry);  //将carry中的元素合并到counter[i]中
            carry.swap(counter[i++]);  //交换之后counter[i-1]为空
        }
        carry.swap(counter[i]);
        if(i==fill) 
            ++fill;
    }
    // 将counter数组链表的所有节点按从小到大的顺序排列存储在counter[fill-1]的链表中
    for(int i=1;i<fill;++i)
    {
        counter[i].merge(counter[i-1]);
    }
    // 最后将couter与carry交换, 实现排序
    swap(counter[fill-1]);
}

sort用了一个数组链表用来存储2^i个元素, 当上一个元素存储满了之后继续往下一个链表存储, 最后将所有的链表进行merge归并(合并), 从而实现了链表的排序.

总结

本节我们分析了list最难的transfer和sort实现, 当然transfer函数是整个实现的核心. 我在将本节分析的函数在进行一个归纳.

transfer : 将两个段链表进行合并(两段可以是来自同一个链表, 但不交叉).
merge : 前提两个段链表都已经排好序. 将两段链表按从小到大的顺序进行合并, 主要是sort实现调用.
reverse : 调用transfer函数将元素一个个调整到begin之前, 实现链表的转置.
sort : 运用归并思想将链表分段排序.