文章目錄
前言
一、List源碼閱讀
二、List常用接口模擬實(shí)現(xiàn)
1.定義一個(gè)list節(jié)點(diǎn)
2.實(shí)現(xiàn)一個(gè)迭代器
2.2const迭代器
3.定義一個(gè)鏈表，以及實(shí)現(xiàn)鏈表的常用接口
三、List和Vector
總結(jié)
前言
本文中出現(xiàn)的模擬實(shí)現(xiàn)經(jīng)過本地vs測(cè)試無(wú)誤，文件已上傳gitee，地址:list: 模仿實(shí)現(xiàn)stl的list - Gitee.com
一、List源碼閱讀
首先我們閱讀源碼，閱讀源碼我按照如下方式：先找到單個(gè)節(jié)點(diǎn)的定義，再找到list里面的主要成員函數(shù)。
list_node鏈表節(jié)點(diǎn)的定義，如下：有三個(gè)成員，prev,next指針，數(shù)據(jù)域。
實(shí)現(xiàn)鏈表的接口：增刪改查，回想我們用C語(yǔ)言實(shí)現(xiàn)的順序表的時(shí)候，使用指針去實(shí)現(xiàn)。使用C++的時(shí)候，模擬實(shí)現(xiàn)string，也是使用迭代器。迭代器就是模擬指針的行為，但是鏈表直接使用指針++，不一定能訪問到下一個(gè)節(jié)點(diǎn)，所以我們要封裝一下原生指針--迭代器，去實(shí)現(xiàn)對(duì)list的訪問。
閱讀源碼，_list_iterator這個(gè)迭代器，有三個(gè)模板參數(shù)，猜測(cè)T應(yīng)該是類型，Ref是引用，Ptr是指針，為什么有三個(gè)模板參數(shù)？后續(xù)再分析。這個(gè)迭代器里實(shí)現(xiàn)了一個(gè)原生迭代器，一個(gè)const迭代器，const調(diào)用const對(duì)象，然后還有一個(gè)self，暫時(shí)不明白什么意思。繼續(xù)往下。
?閱讀到這里，重定義了一些參數(shù)。注意這里：
- typedef _list_node<T> * link_type;??
- link_type node;
- _list_iterator(link type x):node(x){}
和C語(yǔ)言一樣，這里定義了一個(gè)節(jié)點(diǎn)的指針，作為實(shí)現(xiàn)迭代器的最小單元
繼續(xù)往下閱讀，這里有一些運(yùn)算符重載的函數(shù)，比較節(jié)點(diǎn)是否相等，以及引用，注意這里引用的返回值使用了reference，上面看出來(lái)將Ref重定義成了reference，所以這里可以猜測(cè)，ref就是返回引用的值
?這里實(shí)現(xiàn)了運(yùn)算符重載函數(shù)，使用迭代器，去訪問前后的節(jié)點(diǎn)。注意這里的返回值是self，前面讀到self就是_list_iterator的一個(gè)模板參數(shù)。對(duì)比之前實(shí)現(xiàn)日期類的時(shí)候，日期類++,返回的就是一個(gè)日期類對(duì)象。這里使用迭代器進(jìn)行++,猜測(cè)這里返回的就是一個(gè)迭代器。
繼續(xù)查看迭代器的使用：在list的成員函數(shù)中，查看到begin：指向頭節(jié)點(diǎn)的下一個(gè)，end指向頭節(jié)點(diǎn)。rbegin指向頭節(jié)點(diǎn)，rend指向頭節(jié)點(diǎn)的下一個(gè)。
判斷鏈表是否為空：判斷頭節(jié)點(diǎn)的下一個(gè)是否指向頭節(jié)點(diǎn)
計(jì)算鏈表的size:根據(jù)begin,end去計(jì)算
?以及鏈表中最重要的插入insert,通過迭代器找到pos的位置，根據(jù)T去構(gòu)建一個(gè)Node，再進(jìn)行插入。頭插尾插都可以復(fù)用Insert。頭插頭刪的時(shí)候先保留現(xiàn)在的指針指向情況，再進(jìn)行修改，修改完了之后再刪除這個(gè)節(jié)點(diǎn)
?往下閱讀，到了list的主體部分，有兩個(gè)模板參數(shù)。alloc暫時(shí)不明白是什么
?這里實(shí)現(xiàn)了一種創(chuàng)建節(jié)點(diǎn)的成員函數(shù)，create_node：通過T類型的參數(shù)x創(chuàng)建一個(gè)節(jié)點(diǎn).
empty_initialize 空的初始化，只創(chuàng)建一個(gè)節(jié)點(diǎn)
二、List常用接口模擬實(shí)現(xiàn)
通過上面閱讀源碼，我們來(lái)模仿實(shí)現(xiàn)list的一些常用接口。
1.定義一個(gè)list節(jié)點(diǎn)
template<class T>
struct list_node
{
T _data;
list_node<T> * _next;
list_node<T> * _prev;
}2.實(shí)現(xiàn)一個(gè)迭代器
?迭代器要么就是原生指針，要么就是自定義類型對(duì)原生指針的封裝，模擬指針的行為。
list用一個(gè)節(jié)點(diǎn)的指針，去構(gòu)造一個(gè)迭代器
template<class T>
struct _list_iterator
{
typedef list_node<T> node;
typedef _list_iterator<T> self;
//定義一個(gè)指針，指向鏈表
node * _node;
//構(gòu)造函數(shù) 用一個(gè)節(jié)點(diǎn)指針去構(gòu)造迭代器
_list_iterator(node * n)
:_node(n)
{
}
//實(shí)現(xiàn)迭代器的功能
//指針++向后遍歷，就如日期類，返回的還是一個(gè)日期類對(duì)象;迭代器++,返回一個(gè)迭代器對(duì)象
self& operator++()
{
_node = _node->_next;
return *this;
}
self& operator++(int) //實(shí)現(xiàn)前置++
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self& operator++(int) //實(shí)現(xiàn)前置++
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
T& operator*()
{
return _ndoe->data;
}
bool operator == (const self& s)
{
return _node == s._node;
}
bool operator !=(const self &s)
{
return _node != s._node;
}
2.2const迭代器
假設(shè)我們傳了一個(gè)const對(duì)象，
- void print_list(const list<int><)。
- 對(duì)象的類型是一個(gè)const list<int> * ，調(diào)用不了普通迭代器,是一個(gè)經(jīng)典的權(quán)限放大，所以我們要對(duì)this加一個(gè)const。此時(shí)變成了const* _head,指針本身不能改變，但是指向的內(nèi)容可以改變。即我們還是可以對(duì)對(duì)象進(jìn)行改變。
- 在stl庫(kù)中，它使用const修飾*this,返回值也是一個(gè)const_iterator。但是，對(duì)于所有的成員函數(shù)都使用const修飾*this和返回值類型很冗余，所以我們這里增加了一個(gè)模板參數(shù)class Ref。
template<class T>
struct __list_const_iterator
{
typedef list_node<T> node;
typedef __list_const_iterator<T> self;
node* _node;
__list_const_iterator(node* n)
:_node(n)
{}
//保護(hù)返回的值不能被修改
const T& operator*()
{
return _node->_data;
}
//... 其他成員函數(shù)都相同
};
template<class T,class Ref, class Ptr>
struct _list_iterator
{
typedef list_node<T> node;
typedef _list_iterator<T,Ref,Ptr> self;
node * _node;
_list_iterator(node * n)
:_node(n)
{}
Ref operator*()
{
return _ndoe->data;
}
//注意這里 如果我定義了一個(gè)AA類型的鏈表，通過迭代器去訪問,指針類型為AA*
// 現(xiàn)在要訪問它的成員 可以這樣： *(it)._a1;
//也可以it->->a1 一個(gè)是運(yùn)算符重載調(diào)用，it是自定義類型，無(wú)法直接使用箭頭，it-> 就相當(dāng)于運(yùn)算符重載operator-> AA*
//一個(gè)是找成員
//這里為了增強(qiáng)可讀性 省略了一個(gè)箭頭 it->_a1;
Ptr operator->()
{
return &_node->data;
}
self& operator--()
{
}
//其余運(yùn)算符操作類似
}
template<class T>
class list
{
//注意這里模板參數(shù) 調(diào)用普通迭代器 T&傳給ref, 調(diào)用const迭代器 const T& 傳給ref
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T,const T&, const T*> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
const iterator begin()
{
return const_iterator(_head->_next);
}
//..其余類似
}3.定義一個(gè)鏈表，以及實(shí)現(xiàn)鏈表的常用接口
template<class T>
struct _list
{
typedef list_node<T> node;
typedef _list_iterator<T> iterator;
//list的成員
node* _head;
//list的構(gòu)造 初始只有一個(gè)頭節(jié)點(diǎn)
list()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
//list的一些成員函數(shù)
//通過迭代器定位begin和end
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
//通過迭代器對(duì)指定pos位置進(jìn)行增刪改查
void insert(iterator pos, const T& x)
{
node new_node = new node(x);
//iterator cur = pos;
//這里是要通過pos的指針，找到這個(gè)節(jié)點(diǎn) 對(duì)pos進(jìn)行解引用
node * cur = pos._node;
node * prev = cur->_prev;
prev->_next = new_node;
new_node->_prev = prev;
new_node->_next = cur;
cur->_prev = new_node;
}
void push_back()
{
insert(end(),x);
}
void push_front()
{
insert(begin(),x);
}
void erase(iterator pos)
{
assert(pos!=end());
node * cur = pos._node;
node* prev = cur->_prev;
node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
}
void pop_back()
{
erase(end());
}
void pop_front()
{
erase(begin());
}
//打印
void print_list(const list<T> & lt)
{
iterator it = lt.begin();
while(it != lt.end())
{
cout<<*it;
++it;
}
cout<<endl;
}
}三、List和Vector對(duì)比
vector與list都是stl中非常重要的序列容器，由于兩個(gè)容器的底層結(jié)構(gòu)不同，導(dǎo)致特性以及應(yīng)用場(chǎng)景不同文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-640049.html
| vector | list | |
| 底層結(jié)構(gòu) | 動(dòng)態(tài)順序表，一段連續(xù)的空間 | 帶頭節(jié)點(diǎn)的雙向循環(huán)鏈表 |
| 隨機(jī)訪問 | 支持隨機(jī)訪問，訪問某個(gè)元素效率O(1） | 不支持隨機(jī)訪問，訪問某個(gè)元素效率O(N) |
| 插入和刪除 | 在任意位置插入刪除元素效率較低，時(shí)間復(fù)雜度O(N),插入可能需要擴(kuò)容，開辟新空間，拷貝元素，釋放舊空間 | 任意位置插入和刪除效率高，不需要搬移元素。時(shí)間復(fù)雜度O(1) |
| 空間利用率 | 底層為連續(xù)空間，不容易造成內(nèi)存碎片，空間利用率高，緩存利用率高 | 底層節(jié)點(diǎn)動(dòng)態(tài)開辟，小節(jié)點(diǎn)容易造成內(nèi)存碎片，空間利用率低，緩存利用率低 |
| 迭代器 | 原生指針 | 對(duì)原生指針（節(jié)點(diǎn)指針）進(jìn)行封裝 |
| 迭代器失效 | 在插入元素時(shí)，要給所有的迭代器重新賦值，因?yàn)椴迦朐赜锌赡軐?dǎo)致擴(kuò)容，導(dǎo)致原來(lái)迭代器失效，刪除時(shí)，也可能失效。需要重新給迭代器賦值 | 插入元素不會(huì)導(dǎo)致迭代器失效，刪除元素時(shí)，只會(huì)導(dǎo)致當(dāng)前迭代器失效，因?yàn)槟莻€(gè)節(jié)點(diǎn)已經(jīng)被刪除。其他迭代器不受影響 |
| 使用場(chǎng)景 | 需要高效存儲(chǔ)，支持隨機(jī)訪問，不關(guān)心插入刪除效率 | 大量插入和刪除操作，不關(guān)心隨機(jī)訪問 |
總結(jié)
本文主要對(duì)stl源碼中l(wèi)ist內(nèi)容進(jìn)行閱讀，并模擬實(shí)現(xiàn)。技術(shù)有限，如有錯(cuò)誤請(qǐng)指正。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-640049.html
到了這里，關(guān)于C++入門之stl六大組件--List源碼深度剖析及模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
