首页 > 代码库 > STL源码剖析(list)
STL源码剖析(list)
SGI STL中list是使用环状双向链表实现的。它的结点结构定义如下：
1 template <class T> 2 struct __list_node { 3 typedef void* void_pointer; 4 void_pointer next; 5 void_pointer prev; 6 T data; 7 };
list定义了属于自己的迭代器，并重载了operator*(用于取结点的data成员)、operator+(用于取next结点)等等。
1 template<class T, class Ref, class Ptr> 2 struct __list_iterator { 3 // 定义相应型别 4 typedef __list_iterator<T, T&, T*> iterator; 5 typedef __list_iterator<T, Ref, Ptr> self; 6 7 typedef bidirectional_iterator_tag iterator_category; 8 typedef T value_type; 9 typedef Ptr pointer; 10 typedef Ref reference; 11 typedef __list_node<T>* link_type; 12 typedef size_t size_type; 13 typedef ptrdiff_t difference_type; 14 15 // 拥有一个指向对应结点的指针 16 link_type node; 17 18 // 构造函数 19 __list_iterator() {} 20 __list_iterator(link_type x) : node(x) {} 21 __list_iterator(const iterator& x) : node(x.node) {} 22 23 // 重载了iterator必须的操作符 24 reference operator*() const { return (*node).data; } 25 pointer operator->() const { return &(operator*()); } 26 self& operator++() { 27 node = (link_type)((*node).next); 28 return *this; 29 } 30 self& operator--() { 31 node = (link_type)((*node).prev); 32 return *this; 33 } 34 // ... 35 };
list的定义比较简单，而且环状双向链表的操作并不用过多的考虑边界条件。
list创建的时候会创建一个空白的结点，并用其node成员指向它，下面是list的基本定义：
1 template <class T, class Alloc = alloc> 2 class list { 3 protected: 4 typedef void* void_pointer; 5 typedef __list_node<T> list_node; 6 typedef simple_alloc<list_node, Alloc> list_node_allocator; 7 public: 8 typedef T value_type; 9 typedef value_type* pointer; 10 typedef value_type& reference; 11 typedef list_node* link_type; 12 typedef size_t size_type; 13 typedef ptrdiff_t difference_type; 14 public: 15 // 定义迭代器类型 16 typedef __list_iterator<T, T&, T*> iterator; 17 protected: 18 link_type node; // 空白结点 链表尾结点 19 // ... 20 };
下面是list的示意图
根据示意图我们很容易理解list的构造：
1 template <class T, class Alloc = alloc> 2 class list { 3 public: 4 // ... 5 // 可以从图中直观的看出来 6 iterator begin() { return (link_type)((*node).next); } 7 iterator end() { return node; } 8 9 // 默认构造函数 10 list() { empty_initialize(); } 11 protected: 12 // 为结点分配内存 13 link_type get_node() { return list_node_allocator::allocate(); } 14 // 回收内存 15 void put_node(link_type p) { list_node_allocator::deallocate(p); } 16 // 构造node 17 link_type create_node(const T& x) { 18 link_type p = get_node(); 19 construct(&p->data, x); 20 return p; 21 } 22 // 销毁node 23 void destroy_node(link_type p) { 24 destroy(&p->data); 25 put_node(p); 26 } 27 // 初始化 28 void empty_initialize() { 29 node = get_node(); 30 node->next = node; 31 node->prev = node; 32 } 33 // ... 34 };
list成员函数的实现其实就是对环状双向链表的操作。
首先是insert、erase、transfer的实现，关于插入删除大部分都调用这三个函数，实际上就是改变结点pre跟next指针的指向。
1 iterator insert(iterator position, const T& x) { 2 link_type tmp = create_node(x); 3 // 改变四个指针的指向 实际就是双向链表元素的插入 4 tmp->next = position.node; 5 tmp->prev = position.node->prev; 6 (link_type(position.node->prev))->next = tmp; 7 position.node->prev = tmp; 8 return tmp; 9 } 10 11 iterator erase(iterator position) { 12 // 改变四个指针的指向 实际就是双向链表的元素删除 13 link_type next_node = link_type(position.node->next); 14 link_type prev_node = link_type(position.node->prev); 15 prev_node->next = next_node; 16 next_node->prev = prev_node; 17 destroy_node(position.node); 18 return iterator(next_node); 19 } 20 21 // 将[first, last)插入到position位置(可以是同一个链表) 22 void transfer(iterator position, iterator first, iterator last) { 23 if (position != last) { 24 // 实际上也是改变双向链表结点指针的指向 具体操作看下图 25 (*(link_type((*last.node).prev))).next = position.node; 26 (*(link_type((*first.node).prev))).next = last.node; 27 (*(link_type((*position.node).prev))).next = first.node; 28 link_type tmp = link_type((*position.node).prev); 29 (*position.node).prev = (*last.node).prev; 30 (*last.node).prev = (*first.node).prev; 31 (*first.node).prev = tmp; 32 } 33 }
有了上面3个函数，list对外的接口实现就非常简单了
1 void push_front(const T& x) { insert(begin(), x); } 2 void push_back(const T& x) { insert(end(), x); } 3 void pop_front() { erase(begin()); } 4 void pop_back() { 5 iterator tmp = end(); 6 erase(--tmp); 7 } 8 9 // splice有很多重载版本 10 void splice(iterator position, list&, iterator first, iterator last) { 11 if (first != last) 12 transfer(position, first, last); 13 } 14 15 // merge函数实现跟归并排序中合并的操作类似 16 template <class T, class Alloc> 17 void list<T, Alloc>::merge(list<T, Alloc>& x) { ... } 18 19 // reserse函数每次都调用transfer将结点插入到begin()之前 20 template <class T, class Alloc> 21 void list<T, Alloc>::reverse() { 22 if (node->next == node || link_type(node->next)->next == node) return; 23 iterator first = begin(); 24 ++first; 25 while (first != end()) { 26 iterator old = first; 27 ++first; 28 transfer(begin(), old, first); 29 } 30 } 31 32 // list必须使用自己的sort()成员函数 因为STL算法中的sort()只接受RamdonAccessIterator 33 // 该函数采用的是quick sort 34 template <class T, class Alloc> 35 void list<T, Alloc>::sort() { ... }
STL源码剖析(list)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。