在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 閱讀(1840)
評論(0) 編輯 收藏 引用 所屬分類:
STL