目錄
1.STL庫的list
2.模擬實現
節點結構體
list類
無參構造函數
尾插函數
迭代器★
begin()
operator++
前置++
后置++
operator--
前置--
后置--
operator!=
operator==
end()
operator*
const修飾的迭代器的設計
1.STL庫的list
模擬實現list之前,先看看STL庫里的list是怎么做的
STL v3.0版本代碼一覽:
先看鏈表的結構體和構造函數
結構體:
template <class T>
struct __list_node {typedef void* void_pointer;void_pointer next;//后指針void_pointer prev;//前指針T data;//數據域
};看到next和prev,顯然是雙向鏈表,復習雙向鏈表的參見:
96.【C語言】數據結構之雙向鏈表的初始化,尾插,打印和尾刪
97.【C語言】數據結構之雙向鏈表的頭插,頭刪,查找,中間插入,中間刪除和銷毀函數CC32.【C++ Cont】靜態實現雙向鏈表及STL庫的list
?構造函數:
list() { empty_initialize(); }//調用空鏈表的構造函數void empty_initialize() { node = get_node();//調用空間配置器node->next = node;node->prev = node;
}//......
protected:link_type node;2.模擬實現
定義節點結構體next和prev成員變量,不建議用void_pointer,因為void*需要強制類型轉換,比較麻煩
節點結構體
仿照STL:
namespace mystl
{template<class T>struct __list_node{typedef __list_node<T>* link_type;link_type next;link_type prev;T data;};//......
}
list類
框架:?
template<class T>
class list
{typedef __list_node<T> list_node;
public:
private:
};發現STL庫中的成員變量只有一個
node為__list_node<T>的指針,顯然是雙向鏈表的哨兵位,如下圖?
照葫蘆畫瓢寫:
template<class T>
class list
{typedef __list_node<T> list_node;typedef __list_node<T>* link_type;
public:
private:link_type node;
};無參構造函數
生成哨兵位,讓next和prev都指向自己
list()
{node = new list_node;node->next = node;node->prev = node;
}測試代碼:
#include "list.h"
int main()
{mystl::list<int> ls;return 0;
}下斷點到return 0,看看無參構造函數是否能正常工作
?可以正常工作
尾插函數
void push_back(const T& x)
{link_type tmp = new list_node;tmp->data = x;//先找尾link_type tail = node->prev;tail->next = tmp;tmp->prev = tail;tmp->next = node;node->prev = tmp;
}測試代碼:
#include "list.h"
using namespace std;
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);return 0;
}運行結果:
當然上面的代碼可以簡寫
link_type tmp = new list_node(x);new list_node(x)會自動調用list_node的構造函數,需要提前準備,將list_node構造函數寫在struct?list_node中即可
struct __list_node
{typedef __list_node<T>* link_type;__list_node(const T& x = T())//寫成缺省參數的形式:next(nullptr), prev(nullptr), data(x){}link_type next;link_type prev;T data;
};迭代器★
迭代器的本質:自定義類型的封裝
list迭代器不能像模擬vector一樣是指針,因為list不是連續區間,因此迭代器需要重新定義,能讓迭代器++能直接指向下一個節點
因此:vector<int>::iterator和list<int>::iterator從封裝上的格式上來看是一樣的,但底層的實現不一樣
即封裝自定義指針成對象,符合C++面向對象的思想
//it是迭代器,本質上都是調用類的成員函數
it.operator++();
it.operator++(0);
it.operator--();
it.operator--(0);
it.operator*();
it.operator!=(...);
it.operator==(...);
STL庫的解決方法:寫成結構體,存儲節點的指針
struct __list_iterator
{link_type node;
};?(省略了成員函數和typedef)
再自定義成iterator
typedef __list_iterator<T> iterator;?可以發現迭代器定義成了實例化的類
注意:__list_iterator定義成類時不要定義到list里面,嵌套類(可參見文章)是有限制的!
template<class T>
struct __list_iterator//是類
{typedef __list_node<T>* link_type;link_type node;
};?當然list類里面要定義迭代器,這樣利用訪問
begin()
寫在list類中,可以直接構造iterator對象返回
iterator begin()
{//返回哨兵位的下一個節點//或者寫成return node->next;使用隱式類型轉換return iterator(node->next);//構造對象返回
}當然node->next是自定義類型,需要手動在__list_iterator類中添加構造函數,這個很容易忘
struct __list_iterator
{typedef __list_node<T>* link_type;__list_iterator(link_type x){node = x;}link_type node;
};或者寫成初始化列表:
__list_iterator(link_type x):node(x)
{}測試代碼:
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);//::可以訪問typedef的或者訪問內部類mystl::list<int>::iterator it=ls.begin();return 0;
} 運行結果:
operator++
operator++是__list_iterator類的方法,不能寫在list類中,因為list類中沒有迭代器成員變量
前置++
返回++后的iterator
typedef __list_iterator<T> iterator;
iterator& operator++()
{node= node->next;return *this;
}后置++
返回++前的iterator
iterator operator++(int)
{iterator tmp(*this);node= node->next;return tmp;
}operator--
因為是雙向鏈表,所以可以向前和向后移動迭代器
前置--
返回--后的iterator
iterator& operator--()
{node = node->prev;return *this;
}后置--
返回--前的iterator
iterator& operator--(int)
{iterator tmp(*this);node = node->prev;return tmp;
}operator!=
注意兩個const修飾
const iterator& x防止權限放大,而且begin()和end()返回的是臨時對象具有常性
operator!=末尾的const是防止修改node
bool operator!=(const iterator& x) const
{return node != x.node;
}operator==
bool operator==(const iterator& x) const
{return node == x.node;
}end()
寫在list類中,由于是雙向鏈表,因此返回哨兵位即可
iterator end()
{//返回哨兵位return node;//隱式類型轉換,完整寫法:iterator(node)
}測試代碼:用迭代器遍歷
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);mystl::list<int>::iterator it=ls.begin();while (it != ls.end()){ std::cout << it.node->data << " ";++it;}return 0;
}運行結果:
operator*
雖然這里定義的迭代器是實例化的對象,但是迭代器任務是模擬指針行為,因此要有operator*
T& operator*()
{return node->data;
}?測試代碼
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);mystl::list<int>::iterator it = ls.begin();std::cout << *it;return 0;
}注:mystl::list<int>::iterator it = ls.begin();會自動調用默認的拷貝構造,由于__list_iterator的成員變量是自定義類型的指針,淺拷貝沒有問題,而且__list_iterator 不用寫析構函數,節點應該是list類釋放,迭代器只是借助節點訪問
運行結果:
const修飾的迭代器的設計
能這樣寫嗎?
typedef const __list_iterator<T> const_iterator;不可以,?const修飾的是?__list_iterator<T>這個類,類的成員函數不能被修改
一個簡明的例子說明:
class myclass
{
public:int* node;int data;
};int main()
{const myclass obj;obj.node++;
}obj.node++是不被允許的,被const修飾的對象的成員變量是不能被修改的
要明確: 無論是否有const修飾,雙向迭代器是要能用operator++和operator--進行修改來訪問的,但const修飾的迭代器指向的內容是不能被修改的,非const修飾的迭代器指向的內容能被修改
(有關const修飾的基礎問題參見38.【C語言】指針（重難點）（C)文章)
那const修飾的迭代器應該模擬類似const T* ptr的情況
在迭代器的成員函數中,只有operator*需要修改,其余都不變
下文將介紹兩種處理方法
)
