在STL中list是以双向链表的方式来存储的，应此使用给定的下标值来找到对应的节点所需的时间复杂度为O(n)，相比vector直接使用原生指针会慢一些。
因为是双向链表的关系，那么必然有一种结构来表示链表中的节点。
template <typename T>
struct __list_node
{
__list_node<T>* prev;
__list_node<T>* next;
T data;
__list_node() : prev(NULL), next(NULL)
{
}
__list_node(const T& x) : prev(NULL), next(NULL), data(x)
{
}
};
然后我们定义出其iterator和const_iterator的结构
template <typename T>
struct __list_iterator
{
typedef __list_iterator<T> iterator;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
typedef const T* const_pointer;
typedef const T& const_reference;
typedef __list_node<T>* link_type;
typedef void* void_pointer;
link_type node;
__list_iterator(link_type x) : node(x)
{
}
__list_iterator(const __list_const_iterator<T>& x) : node(x.node)
{
}
__list_iterator() : node(NULL)
{
}
inline iterator& operator++()
{
node = ((link_type)node)->next;
return *this;
}
inline iterator operator++(int)
{
iterator tmp = *this;
++*this;
return tmp;
}
inline iterator& operator--()
{
node = ((link_type)node)->prev;
return *this;
}
inline iterator operator--(int)
{
iterator tmp = *this;
--*this;
return tmp;
}
inline reference operator*()const
{
return node->data;
}
inline bool operator==(const iterator& x)const
{
return node == x.node;
}
inline bool operator!=(const iterator& x)const
{
return node != x.node;
}
};
由于const_iterator与iterator的结构类似，这里不再贴出。其中重载了++与--运算符，实际上就是节点的前后移动。
然后看一下list的定义
template <typename T>
class list
{
}
让我们来看看list中的别名
public:
typedef T value_type;
typedef T* pointer;
typedef __list_iterator<T> iterator;
typedef __list_const_iterator<T> const_iterator;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef reverse_iterator<const_iterator, value_type, size_type, difference_type> const_reverse_iterator;
typedef reverse_iterator<iterator, value_type, size_type, difference_type> reverse_iterator;
下面是其内部的成员变量
protected:
typedef __list_node<T>* link_type;
typedef list<T> self;
typedef allocator<__list_node<T> > Node_Alloc;
link_type node;
size_type length;
在STL中从begin到end总是以一个前闭后开的形式来表示的，应此我们给出一个node节点来表示end所指位置，而node节点的前驱则是这个list的起始节点，而length则存储了这个list的元素数量。
下面来看看list中最基本的构造函数和析构函数
list() : length(0)
{
node = Node_Alloc::allocate();
node->next = node;
node->prev = node;
}
~list()
{
clear();
Node_Alloc::deallocate(node);
}
在list对象构造之初，首先构造出node节点，使其的前驱和后继都指向其本身，应此通过begin和end拿出的迭代器为同一个。在list对象析构时，首先将这个list清空，然后将构造出的node节点释放掉。
然后是其begin和end方法，用来获取第一个元素和最后一个元素的后一个元素的迭代器
inline iterator begin()
{
return node->next;
}
inline const_iterator begin()const
{
return node->next;
}
inline iterator end()
{
return node;
}
inline const_iterator end()const
{
return node;
}
front和back分别被用来获取第一个元素和最后一个元素
inline reference front()
{
return *begin();
}
inline const_reference front()const
{
return *begin();
}
inline reference back()
{
return *end();
}
inline const_reference back()const
{
return *end();
}
empty、size分别被用来判别容器是否为空、获取容器内元素的个数
inline bool empty()const
{
return length == 0;
}
inline size_type size()const
{
return length;
}
list与vector不同的是list是双向的，应此它允许从头尾两个方向来插入和删除元素
inline void push_front(const T& x)
{
insert(begin(), x);
}
inline void push_back(const T& x)
{
insert(end(), x);
}
inline void pop_front()
{
erase(begin());
}
inline void pop_back()
{
erase(--end());
}
然后我们来看一下push的本质，insert函数
iterator insert(const iterator& position, const T& x)
{
if(!inRange(position)) throw "out of range";
link_type tmp = Node_Alloc::allocate();
construct(tmp, x);
tmp->prev = position.node->prev;
tmp->next = position.node;
position.node->prev->next = tmp;
position.node->prev = tmp;
++length;
return tmp;
}
这里首先会检查这个迭代器是否属于这个list，然后构造出一个新节点，并把它插入到这个迭代器的前面，最后将节点数+1。
然后是其删除节点函数erase
void erase(const iterator& position)
{
if(!inRange(position)) throw "out of range";
position.node->prev->next = position.node->next;
position.node->next->prev = position.node->prev;
destruct(&position.node->data, has_destruct(position.node->data));
Node_Alloc::deallocate(position.node);
--length;
}
这里同样会检查这个迭代器是否属于这个list，然后将这个节点移除，最后析构并释放内存空间。
最后让我们来看一下list中重载的运算符
self& operator=(const self& x)
{
if(this == &x) return *this;
iterator first1 = begin();
iterator last1 = end();
const_iterator first2 = x.begin();
const_iterator last2 = x.end();
while (first1 != last1 && first2 != last2) *first1++ = *first2++;
if (first2 == last2) erase(first1, last1);
else insert(last1, first2, last2);
return *this;
}
reference operator[](size_type n)
{
if(n < 0 || n >= length) throw "out of range";
link_type current = NULL;
if(n < length / 2)
{
current = node->next;
for(size_type i = 0; i < n; i++, current = current->next);
}
else
{
n = length - n - 1;
current = node->prev;
for(size_type i = 0; i < n; i++, current = current->prev);
}
return current->data;
}
inline value_type at(size_type n)
{
return operator[](n);
}
因为其内部使用的是双向链表，应此通过指定下标来获取这个元素是可分别从两头进行移动指针。
至此，list的讲解已完成，完整代码请到
http://qlanguage.codeplex.com下载
posted on 2012-08-09 21:17
lwch 阅读(1821)
评论(0) 编辑 收藏 引用 所属分类:
STL