C++标准库中的list设计
urn *this;
}
/*后向++操作符*/
iterator operator++(int)
{
iterator *old = *this;
++(*this);
return old;
}
protected:
/*基于节点的迭代器构造函数*/
iterator(Node *p):const_iterator(p)
{}
friend class List
List(const List &rhs)
{
/*创建哨兵节点*/
init();
/*复制数据*/
*this = rhs;
}
const List & operator=(const List &rhs)
{
if(this == &rhs)
return *this;
/*清除原有的信息*/
clear();
/*添加新的对象*/
for(const_iterator itr = rhs.begin(); itr != rhs.end(); ++ itr)
push_back(*itr);
return *this;
}
/*得到迭代器，实质上就是得到节点指针*/
iterator begin()
{
/*iterator()是构造函数*/
return iterator(head->next);
}
const_iterator begin()const
{
return const_iterator(head->next);
}
iterator end()
{
return iterator(tail);
}
const_iterator end()const
{
return const_iterator(tail);
}
int size()const
{
return theSize;
}
bool empty()const
{
return size() == 0;
}
void clear()
{
while( !empty())
pop_front();
}
/*得到第一个元素*/
Object & front()
{
/*采用了迭代器begin()*/
return *begin();
}
const Object &front()const
{
return *begin();
}
Object &back()
{
/*end()指向最后一个对象的下一个地址，因此需要--*/
return *--end();
}
const Object &back()const
{
return *--end();
}
/***********************************************
*从头插入新的节点，这时候的begin已经不再是begin
*因此插入操作会导致迭代器出错
***********************************************/
void push_front(const Object &x)
{
insert(begin(), x);
}
/*从后插入新的节点，这时候会将end后移*/
void push_back(const Object &x)
{
insert(end(), x);
}
/*从头弹出一个对象*/
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
/*插入对象，参数是迭代器和数据*/
iterator insert(iterator itr, const Object &x)
{
/*得到当前迭代器的指针*/
Node *p = itr.current;
theSize ++;
/*
*Node *np = Node(x,p->prev,p);
this means that np->prev = p->prev,
and np->next = p;
update the p->prev and p->prev->next;
*p->prev->next = np;
*p->prev = np;
*/
return iterator(p->prev=p->prev->next= new Node(x,p->prev, p));
}
/*删除迭代器处的对象,因此删除也会导致迭代器破坏*/
iterator erase(iterator itr)
{
/*得到当前迭代器的指针*/
Node *p = itr.current;
/*得到新的迭代器，并初始化*/
iterator retVal(p->next);
/*更新链表的链接关系*/
p->prev->next = p->next;
p->next->prev = p->prev;
/*删除对象*/
delete p;
/*使得对象数减少*/
theSize --;
/*返回新的迭代器*/
return retVal;
}
/*删除迭代器指向的对象*/
iterator erase(iterator start, iterator end)
{
/*for中不使用++itr的原因是erase之后
*就是下一个迭代器，因此不需要++操作*/
for(iterator itr = start; itr != end; )
{
/*该操作会导致迭代器更新到下一个*/
itr = erase(itr);
}
return itr;
}
private:
/*链表中的数据成员*/
int theSize;
Node *head;
Node *tail;
/*初始化函数*/
void init()
{
theSize = 0;
/*create two sentinel node*/
/*构建两个哨兵节点，也就是两个并不算在结构体中的对象*/
head = new Node;
tail = new Node;
/*绑定起来*/
head->next= tail;
tail->prev =head;
}
};
}
#endif
C++标准库list设 相关文章：
- Windows CE 进程、线程和内存管理(11-09)
- RedHatLinux新手入门教程(5)(11-12)
- uClinux介绍(11-09)
- openwebmailV1.60安装教学(11-12)
- Linux嵌入式系统开发平台选型探讨(11-09)
- Windows CE 进程、线程和内存管理(二)(11-09)