双链表的迭代器类:
template<class T>
class iterator
{
public:
//向前迭代
typedef forward_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
//构造函数
iterator(chainNode<T> * theNode = NULL)
{
node = theNode;
}
//解引用操作符
T& operator*() const
{
return node->element;
}
T* operator->() const
{
return &node->element;
}
//迭代器加法操作
iterator& operator++()//前加
{
node = node->next;
return *this;
}
iterator operator++(int)//后加
{
iterator old = *this;
node = node->next;
return old;
}
//相等检验
bool operator != (const iterator right) const
{
return node != right.node;
}
bool operator == (const iterator right) const
{
return node == right.node;
}
protected:
chainNode<T>* node;
};
iterator begin()
{
return iterator(firstNode);
}
iterator end()
{
return irerator(NULL);
}
使用迭代器访问链表元素和get()方法访问元素,时间效率有很大的差别: get()函数:O(listSize²) 迭代器:O(listSize)