新聞中心

EEPW首頁 > 嵌入式系統(tǒng) > 設(shè)計(jì)應(yīng)用 > C++標(biāo)準(zhǔn)庫中的list設(shè)計(jì)

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

作者: 時(shí)間:2016-12-01 來源:網(wǎng)絡(luò) 收藏
C++++中采用了大量的標(biāo)志模板庫(STL)實(shí)現(xiàn)程序的設(shè)計(jì),這種設(shè)計(jì)方式使得不同類型的對象都能通用,而不再是C語言中的通常對于不同的類型需要重新設(shè)計(jì)或者或者比較采用間接的指針操作。C++中的這種方式簡化了寫代碼的復(fù)雜度,但是增加了編譯器的復(fù)雜度和難度。


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

本文引用地址:http://m.butianyuan.cn/article/201612/324523.htm

#include

list lint;

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

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

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

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

需要注意的是在List中采用了哨兵節(jié)點(diǎn),這個(gè)哨兵節(jié)點(diǎn)并不算實(shí)際的操作對象,也就是為了保證肯定有目標(biāo)所指向,存在一個(gè)head對象,這個(gè)對象的next就是實(shí)際的數(shù)據(jù),而tail是迭代器所能到達(dá)的最后一個(gè)對象,但是這個(gè)對象并不是合理的區(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:
/*封裝對象,形成鏈表節(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è)常量迭代器類,這是容器設(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è)局部對象不能返回引用*/
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)
{}

/*友元類,可以調(diào)用迭代器的私有成員*/
friend class List;
};
/*一般迭代器,直接繼承const_iterator*/
class iterator : public const_iterator
{
public:
iterator():const_iterator()
{}

/*得到對象的值*/
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:
/*基于節(jié)點(diǎn)的迭代器構(gòu)造函數(shù)*/
iterator(Node *p):const_iterator(p)
{}

friend class List;
};
public:
List()
{
init();
}
~List()
{
clear();
deletehead;
delete tail;
}

List(const List &rhs)
{
/*創(chuàng)建哨兵節(jié)點(diǎn)*/
init();
/*復(fù)制數(shù)據(jù)*/
*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;
}

/*得到迭代器,實(shí)質(zhì)上就是得到節(jié)點(diǎn)指針*/
iterator begin()
{
/*iterator()是構(gòu)造函數(shù)*/
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();
}

/*得到第一個(gè)元素*/
Object & front()
{
/*采用了迭代器begin()*/
return *begin();
}
const Object &front()const
{
return *begin();
}

Object &back()
{
/*end()指向最后一個(gè)對象的下一個(gè)地址,因此需要--*/
return *--end();
}
const Object &back()const
{
return *--end();
}
/***********************************************
*從頭插入新的節(jié)點(diǎn),這時(shí)候的begin已經(jīng)不再是begin
*因此插入操作會(huì)導(dǎo)致迭代器出錯(cuò)
***********************************************/
void push_front(const Object &x)
{
insert(begin(), x);
}
/*從后插入新的節(jié)點(diǎn),這時(shí)候會(huì)將end后移*/
void push_back(const Object &x)
{
insert(end(), x);
}

/*從頭彈出一個(gè)對象*/
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}

/*插入對象,參數(shù)是迭代器和數(shù)據(jù)*/
iterator insert(iterator itr, const Object &x)
{
/*得到當(dāng)前迭代器的指針*/
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));
}

/*刪除迭代器處的對象,因此刪除也會(huì)導(dǎo)致迭代器破壞*/
iterator erase(iterator itr)
{
/*得到當(dāng)前迭代器的指針*/
Node *p = itr.current;
/*得到新的迭代器,并初始化*/
iterator retVal(p->next);
/*更新鏈表的鏈接關(guān)系*/
p->prev->next = p->next;
p->next->prev = p->prev;
/*刪除對象*/
delete p;
/*使得對象數(shù)減少*/
theSize --;
/*返回新的迭代器*/
return retVal;
}

/*刪除迭代器指向的對象*/
iterator erase(iterator start, iterator end)
{
/*for中不使用++itr的原因是erase之后
*就是下一個(gè)迭代器,因此不需要++操作*/
for(iterator itr = start; itr != end; )
{
/*該操作會(huì)導(dǎo)致迭代器更新到下一個(gè)*/
itr = erase(itr);
}
return itr;
}

private:
/*鏈表中的數(shù)據(jù)成員*/
int theSize;
Node *head;
Node *tail;
/*初始化函數(shù)*/
void init()
{
theSize = 0;
/*create two sentinel node*/
/*構(gòu)建兩個(gè)哨兵節(jié)點(diǎn),也就是兩個(gè)并不算在結(jié)構(gòu)體中的對象*/
head = new Node;
tail = new Node;
/*綁定起來*/
head->next= tail;
tail->prev =head;
}
};
}

#endif



評論


相關(guān)推薦

技術(shù)專區(qū)