C++標準庫中的list設計
加入技術交流群
在數據結構中鏈表是比較基本的類型，在C++中鏈表是基于模板的類，因此在實際的使用過程中需要涉及到實際的類型。
#include
list
在C++中關于list的接口比較豐富，主要是關于大小，數據的插入、刪除等。但是在C++中引入了迭代器的概念，這個迭代器是關于關于容器中比較重要的一部分，因為這種迭代器使得算法等問題與容器獨立開來，迭代器實質上還是指針，準確的將是一個封裝了指針的類。
迭代器類的創建應該包含下面的操作，首先應該支持的操作符至少包括如下（operator*()，operator++()，operator++(int)，operator==()， operator!=()）,當然也會存在const_iterator這樣的常迭代器，也就是只允許訪問，不能修改對象的迭代器，當然存在迭代器的構造函數、復制控制函數，這些函數都是必須要存在的，因為設計到了指針的操作問題，構造函數應該存在參數是鏈表節點指針的定義，只有存在這個定義才能間接的訪問節點對象。
當然在類中至少存在返回迭代器的begin()和end()函數，這兩個函數返回的迭代器分別指向鏈表的開始和鏈表結束的下一個地址，這是迭代器中經常容易理解錯誤的地方。
在C++中通常創建const_iterator類，然后iterator直接繼承const_iterator。
下面說說list類設計的基本思路：
首先、創建鏈表節點對象，實質上是完成對傳遞進來的類型的封裝操作，同時構成一個雙向鏈表的基本要素（prev、next指針）。節點肯定要存在構造函數，而且是直接初始化三個成員變量。
其次、創建迭代器類，實質上就是封裝一個節點指針，通過節點指針實現操作，至少要實現的操作符已說明。這兩個類都要設置List為友元類，因為這樣才能用List直接操作迭代器的相關操作。
最后、依靠上面的迭代器類和節點類，創建一個List類，該類中主要完成一些基本操作。其中需要注意的就是迭代器的操作，比如刪除元素和插入元素以后迭代器的變化問題等。
需要注意的是在List中采用了哨兵節點，這個哨兵節點并不算實際的操作對象，也就是為了保證肯定有目標所指向，存在一個head對象，這個對象的next就是實際的數據，而tail是迭代器所能到達的最后一個對象，但是這個對象并不是合理的區域，實際上end()實際上就是指向了tail節點，這兩個節點head和tail就是哨兵節點。具體的參看代碼。
實現的基本形式如下：
#ifndef __MYLIST_H_H_
#define __MYLIST_H_H_
#include
namespace myspace
{
template
class List
{
private:
/*封裝對象，形成鏈表節點*/
struct Node
{
Object data;
struct Node *prev;
struct Node *next;
/*節點構造函數*/
Node(const Object &d = Object(), Node *p = NULL, Node *n = NULL)
:data(d), prev(p),next(n){}
};
public:
/*創建一個常量迭代器類，這是容器設計的關鍵*/
class const_iterator
{
public:
const_iterator():current(NULL)
{}
/*重載迭代器的值*/
const Object & operator*()const
{
return retrieve();
}
/*重載前向++操作符*/
const_iterator & operator++ ()
{
current = current->next;
return *this;
}
/*重載后向++操作符，因為是一個局部對象不能返回引用*/
const_iterator operator++(int)
{
const_iterator old = *this;
++(*this);
return old;
}
/*判斷迭代器是否相同，實質上就是判斷指向的節點是否相同*/
bool operator==(const const_iterator &rhs) const
{
return current == rhs.current;
}
/*調用==操作符*/
bool operator!=(const const_iterator &rhs)const
{
return (!(*this == rhs));
}
protected:
/*迭代器實質就是一個節點指針*/
Node *current;
/*獲得鏈表中的內容*/
Object & retrieve() const
{
return current->data;
}
/*基于指針參數的迭代器構造函數，保證只有List使用*/
const_iterator(Node *p):current (p)
{}
/*友元類，可以調用迭代器的私有成員*/
friend class List
/*得到對象的值*/
Object &operator*()
{
return retrieve();
}
/*基于const的重載*/
const Object& operator*()const
{
return const_iterator::operator*();
}
/*前向++操作符*/
iterator &operator++()
{
current = current->next;
return *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
評論