1. 序：
本文参考了侯捷的 《stl 源码分析》一书，出于兴趣，自行实现了简单的 list 容器。
学习了 stl 的 list 容器的源代码，确实能够提高写链表代码的能力。其中的 sort 函数，可谓是非常神奇。。。
2. 实现的细节
stl 的 list 容器采用了一个带有尾节点的环状双向链表。 如下图所示：
/**
* @file my_list.h
* @brief a simple list
*/
#ifndef my_list_h
#define my_list_h
#include
#include
#include
/**
* list node
*/
template
struct list_node
{
typedef list_node* pointer;
pointer prev;
pointer next;
t data;
};
/**
* list's iterator
* users can use it to iteratate over this list container
*/
template
struct list_iterator
{
typedef t value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef t* pointer;
typedef const t* const_pointer;
typedef t& reference;
typedef const t& const_reference;
typedef list_iterator iterator;
list_iterator(list_node *p = null) : node(p) {}
reference operator*() { return node->data; }
iterator& operator (){
node = node->next;
return *this;
}
iterator operator (int){
iterator tmp = *this;
*this;
return tmp;
}
iterator& operator--(){
node = node->prev;
return *this;
}
iterator operator--(int){
iterator tmp = *this;
--*this;
return tmp;
}
bool operator==(const iterator &rhs){
return node == rhs.node;
}
bool operator!=(const iterator &rhs){
return node != rhs.node; }
list_node *node;
};
/**
* a simple list container
*/
template
class mylist
{
public:
typedef t value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef list_iterator iterator;
typedef const list_iterator const_iterator;
typedef t& reference;
typedef const t& const_reference;
typedef list_node* link_type;
mylist();
mylist(size_type n, t value = t());
//template
//mylist(inputiterator first, inputiterator last);
// copy control
mylist(const mylist&);
mylist& operator=(const mylist&);
~mylist();
bool empty() const { return node->next == node;}
difference_type size() const;
iterator begin() {return iterator(node->next);}
iterator end() {return iterator(node);}
iterator begin() const {return iterator(node->next);}
iterator end() const {return iterator(node);}
iterator rbegin() {return iterator(node->prev);}
iterator rbegin() const {return iterator(node->prev);}
iterator insert(iterator position, const t& x);
void swap(mylist& );
void push_back(const t& x);
void pop_back() {
iterator tmp = end();
erase(--tmp);
}
void push_front(const t& x);
void pop_front() {erase(begin());}
void reverse();
void merge(mylist &);
void sort();
void remove(const t&x);
iterator erase(iterator position);
void clear();
void splice(iterator position, mylist& x) {
if(!x.empty()){
transfer(x.begin(), x.end());
}
}
void splice(iterator position, mylist&, iterator i){
iterator j = i;
j;
if (position == i || position == j) return;
transfer(position, i, j);
}
void splice(iterator position, mylist&, iterator first, iterator last) {
if(first != last){
transfer(position, first, last);
}
}
void print();
protected:
list_node *node;
static std::allocator > alloc;
link_type get_node(){
link_type p = alloc.allocate(1);
return p;
}
void put_node(link_type p){
alloc.deallocate(p, 1);
}
link_type create_node(const t& x){
link_type p = get_node();
new (&p->data) t(x);
return p;
}
void destroy_node(link_type p){
(&p->data)->~t();
put_node(p);
}
void empty_initialize(){
node = get_node();
node->prev = node;
node->next = node;
}
void transfer(iterator position, iterator first, iterator last);
};
template
std::allocator > mylist::alloc;
template
mylist::mylist()
{
empty_initialize();
}
template
mylist::mylist(size_type n, t value)
{
empty_initialize();
for(size_type i(0); i!=n; i)
insert(begin(), value);
}
template
void mylist::clear()
{
link_type p = node->next;
link_type next(null);
while(p != node){
next = p->next;
destroy_node(p);
p = next;
}
node->prev = node;
node->next = node;
}
template
mylist::~mylist()
{
clear();
destroy_node(node);
node = null;
}
//copy control
template
mylist::mylist(const mylist &rhs)
{
empty_initialize();
for(iterator it = rhs.begin(); it != rhs.end(); it)
insert(end(), *it);
}
template
mylist& mylist::operator=(const mylist &rhs)
{
clear();
for(iterator it = rhs.begin(); it != rhs.end(); it)
insert(end(), *it);
return *this;
}
template
typename mylist::difference_type mylist::size() const
{
difference_type len(0);
link_type p = node->next;
for(; p != node; p = p->next, len);
return len;
}
template
typename mylist::iterator mylist::insert(iterator position, const t& x)
{
link_type new_node = create_node(x);
new_node->next = position.node;
new_node->prev = position.node->prev;
position.node->prev->next = new_node;
position.node->prev = new_node;
return iterator(new_node);
}
template
inline void mylist::push_back(const t& x)
{
insert(end(), x);
}
template
inline void mylist::push_front(const t& x)
{
insert(begin(), x);
}
template
typename mylist::iterator mylist::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);
}
// remove all nodes equal to x
template
void mylist::remove(const t& x)
{
link_type prev_node(node);
link_type cur(node->next);
link_type next_node(null);
while(cur != node)
{
if(cur->data == x){
/* delete node */
next_node = cur->next;
prev_node->next = next_node;
next_node->prev = prev_node;
destroy_node(cur);
cur = next_node;
}
else{
prev_node = cur;
cur = cur->next;
}
}
}
/**
* move [first, last) ahead of position
* an auxillary function
*/
template
void mylist::transfer(iterator position, iterator first, iterator last)
{
if(position != last)
{
link_type first_node = first.node;
link_type rear_node = last.node->prev;
//separate [first, last) from their list
first_node->prev->next = last.node;
last.node->prev = first_node->prev;
//add [first, last)
first_node->prev = position.node->prev;
rear_node->next = position.node;
position.node->prev->next = first_node;
position.node->prev = rear_node;
}
}
template
void mylist::swap(mylist &rhs)
{
if(this->node != rhs.node){
link_type tmp = node;
node = rhs.node;
rhs.node = tmp;
}
}
template
void mylist::reverse()
{
/* length == 0 || length == 1*/
if(node->next == node || node->next->next == node)
return;
iterator first = begin(), old(null);
first;
while(first != end()){
old = first;
first;
transfer(begin(), old, first);
}
}
template
void mylist::merge(mylist &x)
{
iterator first1 = this->begin();
iterator last1 = this->end();
iterator first2 = x.begin();
iterator last2 = x.end();
// *this and x are sorted incrementally
while(first1 != last1 && first2 != last2)
{
if(*first2 < *first1) {
iterator next = first2;
transfer(first1, first2, next);
first2 = next;
}
else
first1;
}
if(first2 != last2) {
transfer(end(), first2, last2);
}
assert(x.empty());
}
template
void mylist::print()
{
iterator cur = begin();
while(cur != end())
{
std::cout << *cur << " ";
cur;
}
std::cout << std::endl;
}
/**
* interesting sort function for list
* std::sort is not fit for list
* which requires random iterator
*/
template
void mylist::sort()
{
/* length == 0 || length == 1*/
if(node->next == node || node->next->next == node)
return;
mylist carry;
mylist counter[64];
int fill = 0;
while(!empty())
{
/* carry get the first node */
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