sgi stl 的list实际上是一个双向环形链表
下面是代码
#ifndef C_LIST_H
#define C_LIST_H
#include "cconstruct.h"
#include "cvector.h"
template <class T>
struct list_node {
typedef list_node<T>* point;
point prev;
point next;
T data;
};
template <class T, class Ref, class Ptr>
struct list_iterator {
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t distance_type;
typedef T value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef list_node<T>* link_type;//指向list_node的指针，所谓list_iterator也指向list_node的指针
link_type node;
list_iterator(){}
list_iterator(link_type x):node(x) {}
list_iterator(iterator& x):node(x.node) {}
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;}//list_iterator表示指针，*point 表示取得这个指针所指之物,指向的不是list_node而是data
pointer operator->() const { return &(operator*()); }
//++i
self& operator++() {
node = node->next;
return *this;
}
//i++
self operator++(int) {
self tmp = *this;
++(*this);
return tmp;
}
//--i
self& operator--() {
node = node->prev;
return *this;
}
//i--
self operator--(int) {
self tmp = *this;
--(*this);
return tmp;
}
};
template <class T, class Alloc = alloc>
class clist {
protected:
typedef T vale_type;
typedef T* pointer;
typedef T& reference;
typedef list_node<T> list_node;
typedef list_node* link_type;
typedef simple_alloc<list_node, Alloc> list_node_allocator;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
public:
iterator begin() { return node->next; }
const_iterator begin() const{ return node->next; }
iterator end() {return node;}
const_iterator end() const{ return node; }
bool empty() const { return node->next == node; }
size_t size() const{
size_t len = 0;
const_iterator it;
for (it = begin(); it != end(); ++it)
++len;
return len;
}
reference front() { return *begin(); }
reference back() { return *(--end()); }
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();
construct(&p->data, x);
return p;
}
void destroy_node(link_type p) {
destroy(&p->data);
put_node(p);
}
void empty_initialize() {
node = get_node();
node->next = node;
node->prev = node;
}
public:
clist() { empty_initialize(); }
~clist() {
clear();
destroy_node(node);
}
iterator insert(iterator position, const T& x) {
link_type tmp = create_node(x);
tmp->next = position.node;
tmp->prev = position.node->prev;
position.node->prev->next = tmp;
position.node->prev = tmp;
return tmp;
}
void push_back(const T& x) { insert(end(), x); }
void pop_back() {
erase(--end());
}
void pop_front() {
erase(begin());
}
void push_front(const T& x) { insert(begin(), x); }
iterator erase(iterator position) {
position.node->prev->next = position.node->next;
position.node->next->prev = position.node->prev;
destroy_node(position.node);
return position.node->next;
}
void clear() {
iterator currNode = begin();
while ( currNode != end()) {
destroy_node((currNode++).node);
}
node->next = node;
node->prev = node;
}
void remove(const T& x) {
iterator first = begin();
iterator last = end();
while (first != last) {
if (*first == x)
erase(first++);
else
++first;
}
}
//这个算法的思路很清晰
void 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;
}
}
void splice(iterator position, clist&, iterator i) {
iterator j = i;
++j;
if (j == position || i == position) return;
transfer(position, i, j);
}
//将[first, last) 放入position之前,[first, last) 可以和position在同一链表或不同链表，但是区间和position不能重叠
void transfer(iterator position, iterator first, iterator last) {
if (position != last) {
first.node->prev->next = last.node;
position.node->prev->next = first.node;
last.node->prev->next = position.node;
link_type tmp = position.node->prev;
position.node->prev = last.node->prev;
last.node->prev = first.node->prev;
first.node->prev = tmp;
}
}
void merge(clist<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);
}
void reverse() {
if (node->next == node || node->next->next == node) return;
iterator first = begin();
++first;
while(first != end()) {
iterator old = first;
++first;
transfer(begin(),old, first);
}
}
void swap(clist<T, Alloc>& x) {
std::swap(node, x.node);
}
void sort() {
if (node->next == node || node->next->next == node) return;
clist<T, Alloc> carry;
clist<T, Alloc> counter[64];
int fill = 0;
while ( !empty()) {
carry.splice(carry.begin(), *this, begin());//carry = 1;可以认为是carry每次都赋值为1，counter是一个大数，能够表示2^64进制的数。while的过程就是counter加1的过程
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]);
}
protected:
link_type node;//用此指针指向环状链表
};
#endif
其中比较难理解的list中快速排序的实现，其实更像是归并排序
就是用counter[64]表示一个进制为2^64的大数，同样，这个算法可以排序的最大结点数是2^64 - 1
while(i < fill && !counter[i].empty())
可以看做是一个加1操作，从低位开始进位