list類和string與vector不一樣,list類的底層是通過雙向帶頭回圈鏈表
屬性定義
由于是帶頭的鏈表,為了方便使用我們定義兩個類,一個是單獨結點的類,一個是屬性只有頭結點,用于存放結點的List類,
//單獨結點類
template <class T>
struct ListNode
{
T _data; //結點資料
ListNode<T>* _next; //該結點的下一個結點
ListNode<T>* _prev; //該結點的上一個結點
//默認建構式
ListNode(const T& val = T())
:_data(val)
, _next(nullptr)
, _prev(nullptr)
{}
};
//只有頭結點存放結點的List類
template <class T>
class List
{
public:
typedef ListNode<T> Node;
private :
Node* _header;
};
建構式
建構式存在多種,但是每個建構式在構造前,都必須先構建它的基本結構,也就是保證該鏈表是一個雙向帶頭回圈鏈表

第一種:無參建構式
List()
:_header(new Node())
{
//確立回圈結構
_header->_next = _header->_prev = _header;
}
第二種:創建n個結點,值為val (利用到尾插,后面有實作)
List(int n, const T& val = T())
:_header(new Node())
{
_header->_next = _header->_prev = _header;
for (size_t i = 0; i < n; ++i)
{
//尾插
pushBack(val);
}
}
測驗用例:

第三種:通過迭代器構造list (利用到尾插,后面有實作)
使用新的迭代器的原因是使傳入的迭代器可以是任意型別的,如果使用List的迭代器,那么傳入的迭代器的型別只能和List的型別一樣,這里拿string舉例,創建一個char型別的List,但是傳入的迭代器并不是char型別的,可以是字符陣列的迭代器或者是string的迭代器,只要通過解參考是char型別就可以
通過傳進來的兩個迭代器,只要迭代器不相等,就將第一個迭代器的值進行尾插,再++,直到兩個迭代器相等
template<class inputIterator>
List(inputIterator first, inputIterator last)
:_header(new Node())
{
_header->_next = _header->_prev = _header;
while (first != last)
{
pushBack(*first);
++first;
}
}
測驗用例:

pushBack()
按照一定順序改變各結點的指向
- 最后一個節點的next等于新的結點
- 新的結點的prev等于最后一個節點
- 新的結點的next等于頭結點
- 頭結點的prev等于新的結點

void pushBack(const T& val)
{
Node* tail = _header->_prev;//最后一個節點
Node* newNode = new Node(val); //新結點
tail->_next = newNode;
newNode->_prev = tail;
newNode->_next = _header;
_header->_prev = newNode;
}
測驗用例:

clean()
clean()的實作其實就是銷毀鏈表,由于是帶頭的鏈表,我們不能和不帶頭的鏈表一樣,利用判空條件去結束銷毀,應該定義一個頭結點的下一個結點cur,先保存cur結點的下一個結點next,再釋放和置空cur,再更新cur為next,如此回圈,直到cur為頭結點
void clear()
{
if (_header != nullptr)
{
Node* cur = _header->_next;
while (cur != _header)
{
Node* next = cur->_next;
delete[] cur;
cur = nullptr;
cur = next;
}
}
}
解構式
先將頭結點之外的所有結點都洗掉掉,最后再單獨洗掉頭結點,可以復用clear函式
~List()
{
clear();
delete _header;
_header = nullptr;
}
size()
定義一個計數器,然后從頭結點的下一個結點開始遍歷,每遍歷一個節點計數器就+1,當遇到頭結點就結束遍歷,回傳計數器
size_t size()const
{
int sz = 0;
Node* cur = _header->_next;
while (cur != _header)
{
++sz;
cur = cur->_next;
}
return sz;
}
list迭代器的實作
list底層是一個鏈表,底層并不像vector一樣是通過原生態指標來實作的,如果是指標,對迭代器的++也就是地址的偏移,偏移量為list物件的大小,但是list底層是鏈表實作,也就是說在物理地址上并非是連續存盤的,只是在邏輯上是連續的,偏移就并非能偏移到指定的位置,所以list的迭代器不能通過指標來實作,可不可以是結點指標型別的呢?假設它是結點指標型別的迭代器,通過++操作也并非能指向下一個節點,通過*操作也只是獲得該結點,但是該結點的屬性有好幾個,并不能通過解參考來獲得該結點的資料,
我們可以歸納一下,通過迭代器的操作,我們鏈表底層的實際操作對應的應該是哪些操作
迭代器的解參考* ---- node->data
迭代器的++ ---- node->next
所以我們只能通過對結點的封裝才能實作該操作,也就是用自定義型別來封裝結點,但是自定義型別也并不支持解參考和++的操作,那我們就必須在類內多載運算子,實作我們實際的操作,操作我們封裝的結點,就是操作我們list中鏈表的結點,為了方便遍歷,我們再多載一個!=的實作.
template<class T>
struct ListIterator
{
//結點
typedef ListNode<T> Node;
typedef ListIterator<T> Self;
Node* _node;
//建構式
ListIterator(Node* node = nullptr)
: _node(node)
{}
//多載*,回傳的是該結點的資料
T& operator*()
{
return _node->_data;
}
//多載前置++,回傳的是該結點的下一個結點
Self& operator++()
{
_node = _node->_next;
return *this;
}
//兩個節點的地址不同,就是不相同的結點
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
在List類中,應該要提供begin()和end()函式,它們的回傳值應該就是本身的迭代器型別
typedef ListIterator<T> iterator;
iterator begin()
{
//封裝第一個結點
return iterator(_header->_next);
}
iterator end()
{
//封裝最后一個結點的下一個結點,也就是頭結點
return iterator(_header);
}
測驗結果:

接下來補全迭代器的基本操作
template<class T>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T> Self;
Node* _node;
ListIterator(Node* node = nullptr)
: _node(node)
{}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self tmp(_node);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(_node);
_node = _node->_prev;
return tmp;
}
T& operator*()
{
return _node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
以上的操作支持內置型別的基本操作,但是并不能滿足當結點存盤的內置型別的操作,當對物件解參考時,是回傳的結點的_data,但是這個_data是一個物件,也就并非能得到內置型別的值,*it得到的是物件,再通過.來獲得物件的屬性值,
struct A
{
int _a;
A(int a = 0)
:_a(a)
{}
};

但是該操作并不方便,通過解參考再獲取物件值,在STL庫中的迭代器可以直接通過->_a來獲取,迭代器是一個物件,怎么可以通過->來獲取自定義型別的屬性呢?我們就必須多載->來實作,就是it->獲得自定義型別物件的地址,再通過->就可以獲得自定義型別物件的指定的值it->->_a
只是在C++會進行優化,省略了其中的一個->,
一下是實作第一個->的代碼
//場景:T為自定義型別,且包含多個成員
//it->T*->指定成員
//it->指定成員 來訪問成員變數
T* operator->()
{
//回傳自定義型別物件的地址
return &(_node->_data);
}
測驗結果:

滿足了內置型別和自定義型別的迭代器,我們就可以使用范圍for來遍歷list,

我們已經能夠正常實作可讀可寫的迭代器了,現在我們來實作只能讀的迭代器const_iterator,我們能不能按照之前迭代器的實作,在迭代器前加const關鍵字呢?我們在迭代器類中添加const的介面,但是添加const后的成員函式是不能改變成員變數的值,而++操作就涉及到了成員變數的改變_node=_node->next
//const修飾后不能改變當前類的成員
Self& operator++() const
{
_node = _node ->next;//error
return *this;
}
這樣子的方法行不通,我們只能再創建一個自定義型別,專門處理只讀迭代器的操作,能通過迭代器獲取到物件的值只有兩個成員函式,一個是解參考*操作,一個是->操作,所以我們在新的類中將這兩個成員函式的回傳值設定為const就可以了,其他代碼不變,
template<class T>
struct ConstListIterator
{
typedef ListNode<T> Node;
typedef ConstListIterator<T> Self;
Node* _node;
ConstListIterator(Node* node = nullptr)
: _node(node)
{}
ConstListIterator(const Self& s)
: _node(s._node)
{}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self tmp(_node);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
//回傳值不能修改
const T& operator*()
{
return _node->_data;
}
//回傳值不能修改
const T* operator->()
{
return &(_node->_data);
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
List類中const迭代器代碼:
typedef ConstListIterator<T> const_iterator;
const_iterator cbegin() const
{
return const_iterator(_header->_next);
}
const_iterator cend() const
{
return const_iterator(_header);
}
測驗結果:


但是STL庫中實作并不是這樣子的,我們發現兩個迭代器型別只是類中兩個成員函式的回傳值不一樣而已,其他代碼邏輯都是一樣的,所以我們可以通過多加兩個模板型別來解決這個問題,讓他們成為一個類,只是型別有所差別,在原來的迭代器中將模板改為template<class T, class Ref, class Ptr> T為普通型別,Ref為參考型別,Ptr為指標型別,
//Self別名中的型別也要對應起來
typedef ListIterator<T, Ref, Ptr> Self;
//const T& operator*()
Ref operator*()
{
return _node->_data;
}
//const T* operator->()
Ptr operator->()
{
return &(_node->_data);
}
這時候在List中將只讀迭代器的泛型型別都修飾成const,此時就回傳的型別就都是帶有const的了,呼叫只讀迭代器,編譯器會通過型別推出該型別為只讀,不能修改
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
erase()
- 獲取pos迭代器的結點,保存該結點的下一個結點
next和上一個結點prev - 將這兩個結點收尾相接
- 釋放pos位置上的結點
- 回傳next結點封裝后的迭代器

iterator erase(iterator pos)
{
if (pos != end())
{
Node* next = pos._node->_next;
Node* prev = pos._node->_prev;
prev->_next = next;
next->_prev = prev;
delete[] pos._node;
return iterator(next);
}
return pos;
}
測驗結果:

insert()
- 創建一個值為v的結點
newNode - 獲取當前位置pos的前一個節點
prev - 最后首尾相連即可

void insert(iterator pos, const T& val)
{
Node* newNode = new Node(val);
Node* prev = pos._node->_prev;
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
}
pushFront()
第一個結點前插入新的結點
void pushFront(const T& val)
{
insert(begin(), val);
}
popBack()
洗掉最后一個節點,end()指向的是頭結點,–end()
void popBack()
{
erase(--end());
}
popFront()
刪掉第一個結點
void popFront()
{
erase(begin());
}
拷貝建構式
利用現代寫法,利用建構式創建一個臨時物件tmp,
List(List<T>& l)
:_header(new Node())
{
_header->_next = _header->_prev = _header;
List<T> tmp(l.begin(), l.end());
swap(tmp);
}
//交換兩個物件的頭結點
void swap(List<T>& l)
{
Node* tmp = l._header;
l._header = this->_header;
this->_header = tmp;
}
賦值運算子多載
利用了拷貝建構式創建新空間,然后再交換他們的頭結點,tmp離開函式就會自動釋放了
List<T>& operator=(List<T> tmp)
{
swap(tmp);
return *this;
}
運行結果:

整個List實作
template <class T>
struct ListNode
{
T _data;
ListNode<T>* _next;
ListNode<T>* _prev;
ListNode(const T& val = T())
:_data(val)
, _next(nullptr)
, _prev(nullptr)
{}
};
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Self;
Node* _node;
ListIterator(Node* node = nullptr)
: _node(node)
{}
ListIterator(const Self& s)
: _node(s._node)
{}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self tmp(_node);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
template <class T>
class List
{
public:
typedef ListNode<T> Node;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return iterator(_header->_next);
}
iterator end()
{
return iterator(_header);
}
const_iterator cbegin() const
{
return const_iterator(_header->_next);
}
const_iterator cend() const
{
return const_iterator(_header);
}
List()
:_header(new Node())
{
//回圈結構
_header->_next = _header->_prev = _header;
}
List(int n, const T& val = T())
:_header(new Node())
{
_header->_next = _header->_prev = _header;
for (size_t i = 0; i < n; ++i)
{
pushBack(val);
}
}
template<class inputIterator>
List(inputIterator first, inputIterator last)
:_header(new Node())
{
_header->_next = _header->_prev = _header;
while (first != last)
{
pushBack(*first);
++first;
}
}
List(List<T>& l)
:_header(new Node())
{
_header->_next = _header->_prev = _header;
List<T> tmp(l.begin(), l.end());
swap(tmp);
}
List<T>& operator=(List<T> tmp)
{
swap(tmp);
return *this;
}
void swap(List<T>& l)
{
Node* tmp = l._header;
l._header = this->_header;
this->_header = tmp;
}
void pushBack(const T& val)
{
/*Node* tail = _header->_prev;
Node* newNode = new Node(val);
tail->_next = newNode;
newNode->_prev = tail;
newNode->_next = _header;
_header->_prev = newNode;*/
insert(end(), val);
}
void pushFront(const T& val)
{
insert(begin(), val);
}
void popBack()
{
erase(--end());
}
void popFront()
{
erase(begin());
}
T& font()
{
return _header->_next->_data;
}
const T& font()const
{
return _header->_next->_data;
}
T& back()
{
return _header->_prev->_data;
}
const T& back()const
{
return _header->_prev->_data;
}
bool empty()const
{
return _header->_next == _header;
}
size_t size()const
{
int sz = 0;
Node* cur = _header->_next;
while (cur != _header)
{
++sz;
cur = cur->_next;
}
return sz;
}
iterator erase(iterator pos)
{
if (pos != end())
{
Node* next = pos._node->_next;
Node* prev = pos._node->_prev;
prev->_next = next;
next->_prev = prev;
delete[] pos._node;
return iterator(next);
}
return pos;
}
void insert(iterator pos, const T& val)
{
Node* newNode = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
}
void clear()
{
if (_header != nullptr)
{
Node* cur = _header->_next;
while (cur != _header)
{
Node* next = cur->_next;
delete[] cur;
cur = nullptr;
cur = next;
}
}
}
~List()
{
clear();
delete _header;
_header = nullptr;
}
private :
Node* _header;
};
轉載請註明出處,本文鏈接:https://www.uj5u.com/ruanti/274770.html
標籤:其他
