list是一个环状双向链表,迭代器必须具备前移和后移的能力,所以提供的是Bidirectional Iterators。
list的节点结构如下:
template <class T> struct __list_node { typedef void* void_pointer; void_pointer next; void_pointer prev; T data; };
list会在最后加上一个空白节点,符合STL“前闭后开”区间
list内部的构造与析构
//配置一个节点 link_type get_node() { return list_node_allocator::allocate(); } // 释放指定结点, 不进行析构, 析构交给全局的destroy, 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指向它 node->next = node; //令node头尾指向自己,不设置元素值 node->prev = node; }
// 复制构造 list(const list<T, Alloc>& x) { range_initialize(x.begin(), x.end()); } ~list() { // 释放所有结点 // 使用全局函数distance()进行计算, 时间复杂度O(n) size_type size() const { size_type result = 0; distance(begin(), end(), result); return result; } clear(); // 释放头结点 put_node(node); }
list的很多初始化内部都是通过inset完成的
iterator insert(iterator position, const T& x) { link_type tmp = create_node(x); //产生节点,内容为x tmp->next = position.node; tmp->prev = position.node->prev; (link_type(position.node->prev))->next = tmp; position.node->prev = tmp; return tmp; }
list的元素操作:
push_front(),push_back() ,pop_front(),pop_back()
erase() 如下:
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); }
好几个函数内部也用transfer()
// 将[first, last)区间插入到position 之前 // 如果last == position, 则相当于链表不变化, 不进行操作 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; } }
clear()
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初始状态 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++; if (first2 == last2) erase(first1, last1); else insert(last1, first2, last2); } return *this; }
remove()
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; } }
unique():删除连续的相同元素,只留一个
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; } }
merge():合并两有序的链表,使合并后仍然有序
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; transfer(first1, first2, ++next); first2 = next; } else ++first1; if (first2 != last2) transfer(last1, first2, last2);}
reverse():使元素全部倒序
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; transfer(begin(), old, first); } }
sort():按升序排列。还记得前面说过了list的迭代器是Bidirectional Iterators。STL中有全局的sort(),但要求迭代器是RamdonAccessIterator,所以得为list设计一个单独使用的,这样效率更高。它是非递归版的快速排序算法。它空间复杂度是O(1)。counter是用于模拟函数调用栈的。关于这个函数比较难,有讲解:
stl中list的sort算法实现 - 绝迹·危言的专栏 - 博客频道 - CSDN.NET http://blog.csdn.net/qq276592716/article/details/7932483
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]); }