C++標(biāo)準(zhǔn)庫(kù)中的list設(shè)計(jì)

在數(shù)據(jù)結(jié)構(gòu)中鏈表是比較基本的類(lèi)型，在C++中鏈表是基于模板的類(lèi)，因此在實(shí)際的使用過(guò)程中需要涉及到實(shí)際的類(lèi)型。

#include

list lint;

在C++中關(guān)于list的接口比較豐富，主要是關(guān)于大小，數(shù)據(jù)的插入、刪除等。但是在C++中引入了迭代器的概念，這個(gè)迭代器是關(guān)于關(guān)于容器中比較重要的一部分，因?yàn)檫@種迭代器使得算法等問(wèn)題與容器獨(dú)立開(kāi)來(lái)，迭代器實(shí)質(zhì)上還是指針，準(zhǔn)確的將是一個(gè)封裝了指針的類(lèi)。

迭代器類(lèi)的創(chuàng)建應(yīng)該包含下面的操作，首先應(yīng)該支持的操作符至少包括如下（operator*()，operator++()，operator++(int)，operator==()， operator!=()）,當(dāng)然也會(huì)存在const_iterator這樣的常迭代器，也就是只允許訪問(wèn)，不能修改對(duì)象的迭代器，當(dāng)然存在迭代器的構(gòu)造函數(shù)、復(fù)制控制函數(shù)，這些函數(shù)都是必須要存在的，因?yàn)樵O(shè)計(jì)到了指針的操作問(wèn)題，構(gòu)造函數(shù)應(yīng)該存在參數(shù)是鏈表節(jié)點(diǎn)指針的定義，只有存在這個(gè)定義才能間接的訪問(wèn)節(jié)點(diǎn)對(duì)象。
當(dāng)然在類(lèi)中至少存在返回迭代器的begin()和end()函數(shù)，這兩個(gè)函數(shù)返回的迭代器分別指向鏈表的開(kāi)始和鏈表結(jié)束的下一個(gè)地址，這是迭代器中經(jīng)常容易理解錯(cuò)誤的地方。

在C++中通常創(chuàng)建const_iterator類(lèi)，然后iterator直接繼承const_iterator。

下面說(shuō)說(shuō)list類(lèi)設(shè)計(jì)的基本思路：
首先、創(chuàng)建鏈表節(jié)點(diǎn)對(duì)象，實(shí)質(zhì)上是完成對(duì)傳遞進(jìn)來(lái)的類(lèi)型的封裝操作，同時(shí)構(gòu)成一個(gè)雙向鏈表的基本要素（prev、next指針）。節(jié)點(diǎn)肯定要存在構(gòu)造函數(shù)，而且是直接初始化三個(gè)成員變量。
其次、創(chuàng)建迭代器類(lèi)，實(shí)質(zhì)上就是封裝一個(gè)節(jié)點(diǎn)指針，通過(guò)節(jié)點(diǎn)指針實(shí)現(xiàn)操作，至少要實(shí)現(xiàn)的操作符已說(shuō)明。這兩個(gè)類(lèi)都要設(shè)置List為友元類(lèi)，因?yàn)檫@樣才能用List直接操作迭代器的相關(guān)操作。
最后、依靠上面的迭代器類(lèi)和節(jié)點(diǎn)類(lèi)，創(chuàng)建一個(gè)List類(lèi)，該類(lèi)中主要完成一些基本操作。其中需要注意的就是迭代器的操作，比如刪除元素和插入元素以后迭代器的變化問(wèn)題等。

需要注意的是在List中采用了哨兵節(jié)點(diǎn)，這個(gè)哨兵節(jié)點(diǎn)并不算實(shí)際的操作對(duì)象，也就是為了保證肯定有目標(biāo)所指向，存在一個(gè)head對(duì)象，這個(gè)對(duì)象的next就是實(shí)際的數(shù)據(jù)，而tail是迭代器所能到達(dá)的最后一個(gè)對(duì)象，但是這個(gè)對(duì)象并不是合理的區(qū)域，實(shí)際上end()實(shí)際上就是指向了tail節(jié)點(diǎn)，這兩個(gè)節(jié)點(diǎn)head和tail就是哨兵節(jié)點(diǎn)。具體的參看代碼。

實(shí)現(xiàn)的基本形式如下：

#ifndef __MYLIST_H_H_
#define __MYLIST_H_H_

#include

namespace myspace
{

template
class List
{
private:
/*封裝對(duì)象，形成鏈表節(jié)點(diǎn)*/
struct Node
{
Object data;
struct Node *prev;
struct Node *next;

/*節(jié)點(diǎn)構(gòu)造函數(shù)*/
Node(const Object &d = Object(), Node *p = NULL, Node *n = NULL)
:data(d), prev(p),next(n){}
};

public:
/*創(chuàng)建一個(gè)常量迭代器類(lèi)，這是容器設(shè)計(jì)的關(guān)鍵*/
class const_iterator
{
public:
const_iterator():current(NULL)
{}

/*重載迭代器的值*/
const Object & operator*()const
{
return retrieve();
}
/*重載前向++操作符*/
const_iterator & operator++ ()
{
current = current->next;

return *this;
}
/*重載后向++操作符，因?yàn)槭且粋€(gè)局部對(duì)象不能返回引用*/
const_iterator operator++(int)
{
const_iterator old = *this;
++(*this);

return old;
}
/*判斷迭代器是否相同，實(shí)質(zhì)上就是判斷指向的節(jié)點(diǎn)是否相同*/
bool operator==(const const_iterator &rhs) const
{
return current == rhs.current;
}
/*調(diào)用==操作符*/
bool operator!=(const const_iterator &rhs)const
{
return (!(*this == rhs));
}
protected:
/*迭代器實(shí)質(zhì)就是一個(gè)節(jié)點(diǎn)指針*/
Node *current;

/*獲得鏈表中的內(nèi)容*/
Object & retrieve() const
{
return current->data;
}

/*基于指針參數(shù)的迭代器構(gòu)造函數(shù)，保證只有List使用*/
const_iterator(Node *p):current (p)
{}

/*友元類(lèi)，可以調(diào)用迭代器的私有成員*/
friend class List