STL源码剖析—序列式容器—list

list

-数据结构
（1）环装双向链表，只需要一个指针，可以完整表现整个链表
（2）只要刻意在环状链表的尾端加上一个空白节点，便可满足“前闭后开”区间。

• 空间分配
  （1）非连续存储空间，容量大小=元素个数；
  （2）每次配置一个节点的空间，当元素删除时，相应空间一并删除；

• 迭代器
  （1）因为节点不连续保存在存储空间，不可以使用普通指针做迭代器；
  （2）双向链表，双向迭代器；
  （3）插入操作和接合操作都不会造成原有的list迭代器失效，只有在删除元素时，“指向被删除元素”的那个迭代器失效，其他迭代器不受影响

• 插入
  分配一个节点，位于目前所指迭代器之前
  

• 删除
  删除元素，释放空间
  

• 优缺点
  优点：无预留空间。插入和删除在常数时间内完成
  缺点：不能进行随机存取。时间复杂度为O(N)。

• 外部接口

#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	std::list<int> iList;
	std::cout<<"size="<<iList.size()<<std::endl;//0
	
	iList.push_back(0);
	iList.push_back(1);
	iList.push_back(2);
	iList.push_back(3);
	iList.push_back(4);
	std::cout<<"size="<<iList.size()<<std::endl;//5
	std::list<int>::iterator it;
	for(it=iList.begin();it!=iList.end();++it) cout<<*it<<'';//01234
	it=find(iList.begin(),iList.end(),3);
	if(it!=0) iList.insert(it,99);
	cout<<*it<<endl;//3 迭代器依然指向3，是在3前面插入
	for(it=iList.begin();it!=iList.end();++it) cout<<*it<<'';//0129934
	it=find(iList.begin(),iList.end(),1);
	if(it!=0)       cout<<*(iList.erase(it))<<endl;//2
	
}

• 相关方法

// 申请一个节点
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);
}

// 无参构造函数
list() { empty_initialize(); }

void empty_initialize()
{
    node = get_node(); 
    node->next = node; 
    node->prev = node;
}

// 返回头结点
iterator begin() { return (link_type)((*node).next); }

// 放回尾节点
iterator end() { return node; }

// 判断链表是否为空
bool empty() const { return node->next == node; }

// 计算链表的大小
size_type size() const 
{
    size_type result = 0;
    distance(begin(), end(), result);
    return result;
}

// 返回头文件的数据
reference front() { return *begin(); }

// 返回尾节点的数据
reference back() { return *(--end()); }

// 尾部插入数据
void push_back(const T& x) { insert(end(), x); }

// 头部插入数据
void push_front(const T& x) {insert(begin(), x);}

// 删除头部节点
void pop_front() { erase(begin()); }

// 删除尾节点
void pop_back()
{
    iterator tmp = end();
    erase(--tmp);
}

// 在position前面插入一个节点，数据为x   先处理待插入的节点，再处理前后节点
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;
}

// 删除指定位置的节点
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);
}

// 清空链表
template <class T, class Alloc>
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->next = node;
    node->prev = node;
}

// 将数据为value的节点全部删除
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;
    }
}