list不是连续的线性空间，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。list的结点不保证在储存空间中连续存在，所以不能以普通指针作为迭代器。list迭代器必须有能力指向list的节点，并有能力进行正确的递增，递减，取值等操作。
list的节点结构
template<class T>
struct __list_node{
typedef void *void_pointer;
void_pointer prev; //型别是void*,其实可设为__list_node<T>*
void_pointer next;
T data;
}; //双向链表
根据list的特性，即双向链表可以进行前后移动，那么迭代器的类型是Bidirectional Iterators.
迭代器的设计
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_iterators_tag iterator_category;
typedef T value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef ptrdiff_t difference_type;
typedef __list_node<T>* link_type;
typedef size_t size_type;
link_type node; //迭代器的根，指向list的节点
//构造函数
__list_iterator(link_type x) : node(x) {}
__list_iterator(const iterator& x) : node(x.node) {}
__list_iterator() {}
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; //元素值
}
pointer operator->() const{
return &(operator*()); //元素地址
}
self& operator++() {
node = (link_type)((*node).next); //移动内部的根，指向下一个节点
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return *this;
}
self& operator--() {
node = (link_type)((*node).prev); //移动内部的根，指向上一个节点
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return *this;
}
}
List是一个环状双向链表。只需要一个指针，便可以完整表现整个链表。
template<class T, class Alloc = alloc>
class list{
protected:
typedef __list_node<T> list_node;
typedef simple_alloc<list_node, Alloc> list_node_allocator;
public:
typedef list_node* link_type;
//定义必须内嵌型别
typedef T value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
//定义迭代器
typedef list_iterator<value_type, reference, pointer> iterator;
typedef list_iterator<value_type, const_reference, const_pointer> const_iterator;
protected:
link_type node;
//节点的创建和删除
link_type get_node(){
return list_node_allocator::allocate();
}
void put_node(link_type p){
list_node_allocator::deallocate();
}
link_type create_node(const T &x){
link_type p = get_node();
construct(&p->data, x); //取出节点中存放元素的地址
return p;
}
void destory_node(link_type p){
destroy(&p->data);
put_node(p);
}
void empty_initialize(){ //初始化一个节点，不存放任何数值，充当尾节点
node = get_node();
node->next = node;
node->prev = node;
}
//把[first, 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;
}
}
public:
//容器基本操作
inline iterator begin() {
return (link_type)(*node).next;
}
inline const_iterator cbegin() const {
return (link_type)(*node).next;
}
inline iterator end() {
return node; //头节点不存储任何数据，它就是end节点
}
inline const_iterator cend() const {
return node;
}
inline bool empty() {
return node->next == node; //自己和自己连接，则list为空
}
inline size_type size() {
return (size_type)distance(begin(), end());//计算首尾两个迭代器之间的距离
}
//引用方式返回
inline reference front() {
return *begin();
}
inline reference back() {
return *(--end());
}
//默认构造函数
list() { empty_initialize(); }
//在相应的位置插入元素
iterator insert(iterator position, const T &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;
}
void push_front(const T &x){
insetr(begin(), x);
}
void push_back(const T &x){
insetr(end(), x);
}
iterator erase(iterator position){
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
next_node->prev = prev_node;
prev_node->next = next_node;
destory(position.node);
return iterator(next_node);
}
void pop_front(){
erase(begin());
}
void pop_back(){
erase(--end());
}
void clear(){
link_type cur = (link_type)node->next;
while(cur != node){ //最后一个节点
link_type tmp = cur;
cur = (link_type) cur->next;
destory(tmp);
}
node->next = node; //空链表
node->prev = node;
}
void remove(const T &value){
iterator first = begin();
iterator last = end();
while(first != last){
iterator next = first;
++next;
if(*first == value){
erase(first);
}
first = next;
}
}
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, 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);
}
}
//merge()将x合并到*this身上。两个list的内容都必须经过递增排序
void 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);
}
}
}
//将*this的内容重载
void 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);
}
}
//list不能使用STL算法sort(),因为STL算法只接受RandomAccessIterator
void 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(carr.begin(), *this, end());
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]);
}
};
