SGI STL值List
文章目录
1.概述
List使用一个doubly linked list(双向对列)来保存元素,相较于Vector的线性空间,List就显的复杂的多,它的好处是每次插入或删除一个元素,就配置或释放一个元素空间。对于任何位置的元素的插入或删除,List永远是常数时间。
2.list的节点
list本身和list节点是不同的结构,需要分开设计。以下是STL list的节点(node)结构:
template <class T>
struct __list_node{
typedef void* void_pointer;
void_pointer prev;
void_pointer next;
T data;
}
3.list的迭代器
由于STL List是一个双向链表,迭代器必须具备前移、后移的能力,所以list提供的是Bidirectional Iterators
list 有一个重要的性质:插入操作(insert)和接合操作(splice)都不会造成原有list迭代器失效。这在vector是不成立的,因为vector的插入操作可能会造成空间的重新配置,导致原有迭代器的全部失效。甚至list的删除(erase)操作也只有“指向被删除元素”的那个迭代器失效,其他迭代器不收任何影响。
以下是list迭代器的设计:(只列出部分)
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 bidirectioanal_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref referrence;
typedef __list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node;
__list_iterator(link_type x):node(x);
__list_iterator(){}
__list_iterator(const iterator& x):node(x.node){}
self& operator++()
{
node=(link_type)((*node).next);
return *this;
}
self operator++(int)
{
self tmp=*this;
++*this;
return tmp;
}
self& operator--()
{
node=(link_type)((*node).prev);
return *this;
}
self operator--(int)
{
self tmp=*this;
--*this;
return tmp;
}
}
4.list的数据结构
SGI list 不仅是一个双向链表,而且还是一个环装双向链表。所以它只需要一个指针,便可以完整表现整个链表:
template <class T,class alloc=Alloc>
class list{
protected:
typedef list_node<T> node;
public:
typedef list_node* link_type;
protected:
link_type node;
}
iterator begin(){ return (link_type)((node*).next);} //return link_type,使用iterator(link_type)构造函数返回一个iterator;
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())}
5.list的构造与内存管理
list缺省使用alloc作为空间配置器,并据此另外定义了一个list_node_allocator.
template <class T,class Alloc=alloc>
class list{
protected:
typedef __list_node<T> list_node;
typedef simple_alloc<list_node,Alloc> list_node_allocator;
}
list_node_allocator(n)表示配置n个节点空间。以下四个函数分别用来配置、释放、构造、销毁一个节点:
protected:
//配置一个节点并传回
link_type get_node() {return list_node_allocator::allocate();}
//释放一个节点
void put_node(lingk_type p){ list_node_allocator::deallocate();}
//产生(配置并构造)一个节点,带有元素值
link_type create_node(const T& x){
link_type p=get_node();
construct(&p->data,x);
retrurn p;
}
//销毁(析构并释放)一个节点
void destroy_node(link_type p){
destory(&p->data);
put_data(p);
}
public:
list(){ empty_initialize(); }
protected:
void empty_initialize(){
node=get_node();
node_next=node;
node_prev=node;
}
void push_back(const T&) {insert(end(),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(psition.node->prev))->next=tmp;
postion.node->prev=tmp;
return tmp;
}
6.list的元素操作
void push_back(const T& x){insert(end(),x);}
void psuh_pront(const T& x){insert(begin(),x);}
//移除迭代器position所指节点
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);
}
//移除头结点
void pop_front() { erase(begin());}
//移除尾节点
void pop_back(){
iterator tmp=end();
erase(--tmp);
}
//清除所有节点(整个链表)
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(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==next) erase(first);
first=next;
}
}
//移除数值相同的连续元素
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;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论