好记性不如铅笔头

C && C++, C++ STL, 编程

C++ STL读书笔记:stl_list.h

备注:

本读书笔记基于侯捷先生的《STL源码剖析》,截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL,部分代码删除了头部的版权注释,但代码版权属于原作者。
小弟初看stl,很多代码都不是太懂,注释可能有很多错误,还请路过的各位大牛多多给予指导。
为了降低学习难度,作者这里换到了SGI-STL-2.91.57的源码来学习,代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】

stl_list.h:

部分代码如下,去掉了文件头部的注释。

//由于list在内存中的存储状态为双向链表式结构可知,每个节点都需要有指向其上一个和下一个的指针。
//因此这里需要专门定义一个结构体来描述节点
template <class T>
struct __list_node {
  typedef void* void_pointer;//定义类型,个人认为可以改为 typedef __list_node* void_pointer
  void_pointer next;//指向下一个__list_node
  void_pointer prev;//指向上一个__list_node
  T data;//list_node中的数据
};



//由于list为链表式结构,而且节点的类型并不是存储的数据类型,而是__list_node,
//因此在节点间进行上下移动的iterator也必须重新定义,以便支持节点上下移动,和读写内部存储的数据
template<class T, class Ref, class Ptr>
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;


  typedef bidirectional_iterator_tag iterator_category;
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef __list_node<T>* link_type;//定义link_type为list中的节点指针类型
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;


  link_type node;//interator中保存的它指向的节点的指针。


  __list_iterator(link_type x) : node(x) {}
  __list_iterator() {}
  __list_iterator(const iterator& x) : node(x.node) {}


//判断两个iterator是否相等,就是判断其指向的节点是否相同
  bool operator==(const self& x) const { return node == x.node; }
  bool operator!=(const self& x) const { return node != x.node; }


//对iterator进行解引用,就是想取得节点内部数据的引用,因此这里返回的是list_node中的data
  reference operator*() const { return (*node).data; }


//重写了指针运算符,返回的指针是节点内部的数据的指针
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */


//这里是前置++( ++x )
//对于iterator来说,++就是指向下一个指针,因此这里将iterator内部的node赋值为下一个__list_node
//然后返回本身
  self& operator++() { 
    node = (link_type)((*node).next);
    return *this;
  }
//这里是后置++( x++ )
//和前置++功能类似,不过由于前置后置的语法问题,这里需要返回原来的数据
  self operator++(int) { 
    self tmp = *this;
    ++*this;
    return tmp;
  }
//前置--( --x )
  self& operator--() { 
    node = (link_type)((*node).prev);
    return *this;
  }


//后置--( x-- )
  self operator--(int) { 
    self tmp = *this;
    --*this;
    return tmp;
  }
};


#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION


//list的iterator是可以双向移动的,因此这里特化为返回bidirectional_iterator_tag
template <class T, class Ref, class Ptr>
inline bidirectional_iterator_tag
iterator_category(const __list_iterator<T, Ref, Ptr>&) {
  return bidirectional_iterator_tag();
}


//list的的iterator的value_type和distance_type都返回0,其实表示iterator不支持这两个操作
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 */


template <class T, class Alloc = alloc>
class list {
protected:
  typedef void* void_pointer;
  typedef __list_node<T> list_node;
  
  //使用简单的new,delete来申请和释放内存,注意这里内存单元节点类型为list_node,而不是T
  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:
	//定义两种不同类型的iterator
  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 */


protected:
	//申请一块新的内存,类型为__list_node<T>
  link_type get_node() { return list_node_allocator::allocate(); }
	//释放一块已有的内存
  void put_node(link_type p) { list_node_allocator::deallocate(p); }


	//申请一块新的内存,并且用x来初始化它
  link_type create_node(const T& x) {
    link_type p = get_node();//申请内存,类型为__list_node<T>
    __STL_TRY {
      construct(&p->data, x);//对__list_node<T>中的data上调用构造函数
    }
    __STL_UNWIND(put_node(p));
    return p;//返回构造好的__list_node<T>
  }
  
  //销毁一个已有的__list_node<T>
  void destroy_node(link_type p) {
    destroy(&p->data);//先调用析构函数,搞定__list_node<T>内部的数据
    put_node(p);//释放掉这块内存
  }


protected:
	//初始化成一个空的list  node首尾均指向自己
  void empty_initialize() { 
    node = get_node();
    node->next = node;
    node->prev = node;
  }


	//初始化一个list,有n个节点,每个节点都初始化为value
  void fill_initialize(size_type n, const T& value) {
    empty_initialize();//先构造一个空的list
    __STL_TRY {
      insert(begin(), n, value);//然后在头部插入n个数据
    }
    __STL_UNWIND(clear(); put_node(node));
  }


#ifdef __STL_MEMBER_TEMPLATES
  template <class InputIterator>
  void range_initialize(InputIterator first, InputIterator last) {
    empty_initialize();
    __STL_TRY {
      insert(begin(), first, last);
    }
    __STL_UNWIND(clear(); put_node(node));
  }
#else  /* __STL_MEMBER_TEMPLATES */
  void range_initialize(const T* first, const T* last) {
    empty_initialize();
    __STL_TRY {
      insert(begin(), first, last);
    }
    __STL_UNWIND(clear(); put_node(node));
  }
  void range_initialize(const_iterator first, const_iterator last) {
    empty_initialize();
    __STL_TRY {
      insert(begin(), first, last);
    }
    __STL_UNWIND(clear(); put_node(node));
  }
#endif /* __STL_MEMBER_TEMPLATES */


protected:
	//list中的保存的唯一一个节点的指针,通过它可以访问整个list中的所有的节点。
	//而且node在list的节点操作中,均指向【最后】的那个节点的下一个节点【即空白节点,无有效数据】。
	//node的下一个节点指向list的第一个节点。
  link_type node;


public:
  list() { empty_initialize(); }//构造函数 


	//begin方法
	//由于node的下一个节点指向list的第一个节点,因此这里返回node的next,
	//由于node的next强转为link_type类型,而返回值为iterator,因此这里又会调用iterator的构造函数来构造一个iterator返回。
  iterator begin() { return (link_type)((*node).next); }
  const_iterator begin() const { return (link_type)((*node).next); }
 
//和begin类似,不过在返回时也构造了一个iterator 返回。注意这里的node是空白节点,无有效数据。
//因此它对应的iterator也是一个无效的位置,这个和vector是类似的。
  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());
  } 
  //node的下一个节点指向list的第一个节点。因此可以用它来判空
  bool empty() const { return node->next == node; }
  
  //获取list的节点的个数,这里获取到指向list的第一个和最后一个无效节点的iterator
  size_type size() const {
    size_type result = 0;
    distance(begin(), end(), result);
    return result;
  }
  
  //list的节点是动态申请的,因此数目没有最大值限制
  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()); }
  void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); }
  	
  	
//在指定位置插入一个数据  	
  iterator insert(iterator position, const T& x) {
//list为链表结构,插入很简单,只要修改下next和prev即可。
//先用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) { 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 push_front(const T& x) { insert(begin(), x); }
//在尾部差一个  
  void push_back(const T& x) { insert(end(), x); }


//删除指定位置的一个数据
  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;
//销毁这个iterator对应的节点
    destroy_node(position.node);
    return iterator(next_node);
  }
  iterator erase(iterator first, iterator last);
  void resize(size_type new_size, const T& x);
  void resize(size_type new_size) { resize(new_size, T()); }
  void clear();


  void pop_front() { erase(begin()); }
  void pop_back() { 
    iterator tmp = end();
    erase(--tmp);
  }
  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); }
  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(const list<T, Alloc>& x) {
    range_initialize(x.begin(), x.end());
  }
  //析构函数
  ~list() {
    clear();//先清理掉所有的有效的数据
    put_node(node);//然后将最后的那个空白节点销毁【 empty_initialize函数申请的 】
  }
  list<T, Alloc>& operator=(const list<T, Alloc>& x);


protected:
	//将【first,last)中的这部分链表插入到当前链表的position中。
  void transfer(iterator position, iterator first, iterator last) {
    if (position != last) {
      (*(link_type((*last.node).prev))).next = position.node;//注意开闭关系,last指向的节点是不插入的
      (*(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;
    }
  }


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);
  }
  void remove(const T& value);
  void unique();
  void merge(list& x);
  void reverse();
  void sort();


#ifdef __STL_MEMBER_TEMPLATES
  template <class Predicate> void remove_if(Predicate);
  template <class BinaryPredicate> void unique(BinaryPredicate);
  template <class StrictWeakOrdering> void merge(list&, StrictWeakOrdering);
  template <class StrictWeakOrdering> void sort(StrictWeakOrdering);
#endif /* __STL_MEMBER_TEMPLATES */


  friend bool operator== __STL_NULL_TMPL_ARGS (const list& x, const list& y);
};


//判断两个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());
}


#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER


template <class T, class Alloc>
inline void swap(list<T, Alloc>& x, list<T, Alloc>& y) {
  x.swap(y);
}


#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */


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


template <class T, class Alloc>
list<T,Alloc>::iterator list<T, Alloc>::erase(iterator first, iterator last) {
  while (first != last) erase(first++);
  return last;
}


template <class T, class Alloc>
//将list的大小重设置为new_size
//多出来的删掉,不够的用x来补齐。
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)
    ;
  //计算list的节点的个数,这里退出for循环有两个判断:
  //1:list的节点数目<new_size,那么会补全
  //2:在数list的节点数目时已经数到了new_size,没必要数下去了,后面的全部删掉。
  if (len == new_size)
    erase(i, end());
  else                          // i == end()
    insert(end(), new_size - len, x);
}


template <class T, class Alloc> 
//删除所有有效数据
void list<T, Alloc>::clear()
{
  link_type cur = (link_type) node->next;//获取第一个有效数据
  while (cur != node) {//如果要删除的节点==node空白节点,说明已经删除干净了
    link_type tmp = cur;
    cur = (link_type) cur->next;
    destroy_node(tmp);
  }
  node->next = node;
  node->prev = node;
}


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++;//这里直接调用T的赋值构造函数,注意iterator的解引用
    if (first2 == last2)//如果新的少,就把旧的删除
      erase(first1, last1);
    else
      insert(last1, first2, last2);//如果新的多,就把多出来的插进去
  }
  return *this;
}


template <class T, class Alloc>
//遍历整个list,删除指定的节点
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;
  }
}


template <class T, class Alloc>
//删除list中的连续相同数据的节点。
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;
  }
}


template <class T, class Alloc>
//将listX中的节点合并到本list中
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;
      transfer(first1, first2, ++next);
      first2 = next;
    }
    else
      ++first1;
  if (first2 != last2) transfer(last1, first2, last2);
}


template <class T, class Alloc>
//将list翻转过来
void list<T, Alloc>::reverse() {
  if (node->next == node || link_type(node->next)->next == node) return;
  iterator first = begin();
  ++first;
/*
翻转顺序
1 2 3 4
2 1 3 4
3 2 1 4
4 3 2 1
*/   
  while (first != end()) {
    iterator old = first;
    ++first;
    transfer(begin(), old, first);
  }
}    

//将list进行排序,应该是快速排序
template <class T, class Alloc>
void list<T, Alloc>::sort() {
  if (node->next == node || link_type(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.swap(counter[i++]);
    }
    carry.swap(counter[i]);         
    if (i == fill) ++fill;
  } 


  for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);
  swap(counter[fill-1]);
}


#ifdef __STL_MEMBER_TEMPLATES


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


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


template <class T, class Alloc> template <class StrictWeakOrdering>
void list<T, Alloc>::merge(list<T, Alloc>& x, StrictWeakOrdering comp) {
  iterator first1 = begin();
  iterator last1 = end();
  iterator first2 = x.begin();
  iterator last2 = x.end();
  while (first1 != last1 && first2 != last2)
    if (comp(*first2, *first1)) {
      iterator next = first2;
      transfer(first1, first2, ++next);
      first2 = next;
    }
    else
      ++first1;
  if (first2 != last2) transfer(last1, first2, last2);
}


template <class T, class Alloc> template <class StrictWeakOrdering>
void list<T, Alloc>::sort(StrictWeakOrdering comp) {
  if (node->next == node || link_type(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, comp);
      carry.swap(counter[i++]);
    }
    carry.swap(counter[i]);         
    if (i == fill) ++fill;
  } 


  for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1], comp);
  swap(counter[fill-1]);
}

 

发表评论

9 + 4 =

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据