利用C++模擬實現(xiàn)STL容器:list
一、list的介紹
列表是一種順序容器，它允許在序列中的任何位置執(zhí)行常量時間插入和刪除操作，并允許在兩個方向上進行迭代。
它的底層是一個帶頭雙向循環(huán)鏈表。附一篇博主用C語言寫的帶頭雙向循環(huán)鏈表：【數(shù)據(jù)結(jié)構(gòu)】帶頭雙向循環(huán)鏈表的實現(xiàn)
二、list的排序
list不能用算法庫的sort進行排序。算法庫中的sort的底層是一個快排，需滿足三數(shù)取中，需要傳入隨機訪問迭代器，所以list并不適用。
當然list中提供了一個自己的sort，它的底層是一個歸并排序。但是這個sort比vector使用算法庫的sort還慢，甚至比list的數(shù)據(jù)先push_back到vector到再用算法庫的sort還要慢。
三、迭代器
1、list的迭代器失效問題
insert，迭代器不失效
earse失效
2、迭代器的功能分類
1、單向迭代器：只能++，不能--。例如單鏈表，哈希表；
2、雙向迭代器：既能++也能--。例如雙向鏈表；
3、隨機訪問迭代器：能++--，也能+和-。例如vector和string。
迭代器是內(nèi)嵌類型（內(nèi)部類或定義在類里）
3、list迭代器的模擬實現(xiàn)
普通迭代器
迭代器的實現(xiàn)需要支持解引用（為了取數(shù)據(jù)），支持++--。
博主模擬實現(xiàn)string和vector時，直接將原生指針typedef成迭代器，是因為數(shù)組的結(jié)構(gòu)正好滿足迭代器的行為（注：string和vector可以用原生指針實現(xiàn)，但是vs中采用自定義類型封裝的方式實現(xiàn)），但是list中的節(jié)點地址是不連續(xù)的，不能使用原生指針，需要使用類進行封裝+運算符重載實現(xiàn)。
//用類封裝迭代器
template <class T>
struct __list_iterator
{
typedef list_node<T> node;
//用節(jié)點的指針進行構(gòu)造
__list_iterator(node* p)
:_pnode(p)
{}
//迭代器運算符的重載
T& operator*()
{
return _pnode->_data;
}
__list_iterator<T>& operator++()//返回值不要寫成node* operator++()，因為迭代器++肯定返回迭代器啊，你返回節(jié)點指針類型不對
{
//return _pnode->_next;
_pnode=_pnode->_next;
return *this;//返回的是迭代器
}
bool operator!=(const __list_iterator<T>& it)
{
return _pnode != it._pnode;
}
public:
node* _pnode;//封裝一個節(jié)點的指針
};
const迭代器
const迭代器的錯誤寫法：
typedef __list_iterator<T> iterator; const list<T>::iterator it=lt.begin();
因為typedef后，const修飾的是迭代器it，只能調(diào)用operator*(),調(diào)不了operator++()。（重載operator++()為const operator++()也不行,因為const版本++還是改變不了）
正確寫法：想實現(xiàn)const迭代器，不能在同一個類里面動腦筋，需要再寫一個const版本迭代器的類。
//用類封裝const迭代器
template <class T>
struct __list_const_iterator
{
typedef list_node<T> node;
//用節(jié)點的指針進行構(gòu)造
__list_const_iterator(node* p)
:_pnode(p)
{}
//迭代器運算符的重載
const T& operator*()const
{
return _pnode->_data;
}
__list_const_iterator<T>& operator++()//返回值不要寫成node*，因為迭代器++肯定返回迭代器啊，你返回節(jié)點指針類型不對
{
//return _pnode->_next;//返回類型錯誤的
_pnode = _pnode->_next;
return *this;//返回的是迭代器
}
__list_const_iterator<T>& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
bool operator!=(const __list_const_iterator<T>& it)const
{
return _pnode != it._pnode;
}
public:
node* _pnode;//封裝一個節(jié)點的指針
};
typedef __list_const_iterator<T> const_iterator;當然，這樣寫__list_iterator和__list_const_iterator這兩個類會出現(xiàn)代碼重復。STL庫中是通過類模板多給一個參數(shù)來實現(xiàn)，這樣，同一份類模板就可以生成兩種不同的類型的迭代器（以下為仿STL庫的模擬實現(xiàn)）：
//用類封裝普通/const迭代器
template <class T,class Ref>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T,Ref> Self;
//用節(jié)點的指針進行構(gòu)造
__list_iterator(node* p)
:_pnode(p)
{}
//迭代器運算符的重載
Ref operator*()
{
return _pnode->_data;
}
Self& operator++()//返回值不要寫成node*，因為迭代器++肯定返回迭代器啊，你返回節(jié)點指針類型不對
{
//return _pnode->_next;//返回類型錯誤的
_pnode=_pnode->_next;
return *this;//返回的是迭代器
}
Self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
bool operator!=(const Self& it)
{
return _pnode != it._pnode;
}
public:
node* _pnode;//封裝一個節(jié)點的指針
};
typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;4、迭代器價值
1、封裝底層實現(xiàn)，不暴露底層實現(xiàn)的細節(jié)；
2、多種容器提供統(tǒng)一的訪問方式，降低使用成本；
C語言沒有運算符重載和引用等語法，是實現(xiàn)不了迭代器的。
5、迭代器operator->的重載
迭代器的用法就是模擬指針的行為，如果現(xiàn)在有一個指向結(jié)構(gòu)的指針，那么就需要用到->來解引用。
//*的重載：返回節(jié)點的數(shù)據(jù)
Ref operator*()
{
return _pnode->_data;
}
//->的重載：返回數(shù)據(jù)的指針
T* operator->()
{
return &_pnode->_data;
}
但是operator->使用T*做返回值類型，這樣無論是普通迭代器和const迭代器都能修改，所以operator->的返回值類型應該改為泛型：
template <class T, class Ref,class Ptr>
Ptr operator->()
{
return &_pnode->_data;
}
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
四、模擬實現(xiàn)時遇到的困惑及注意點
1、調(diào)用拷貝構(gòu)造時，鏈表內(nèi)節(jié)點數(shù)據(jù)為什么已經(jīng)是深拷貝了？
2、類名和類型的區(qū)別
普通類：類名等于類型
類模板：類名不等價于類型，例如list類模板類名是list,類型list<int>等。
所以我們平常寫函數(shù)形參和返回值時，總會帶上形參和返回值的類型：
// 賦值運算符重載寫法2(賦值運算符重載都可以這么干)
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
但是C++在類模板里面可以用類名代替類型：
// 賦值運算符重載寫法2(賦值運算符重載都可以這么干)
list& operator=(list lt)
{
swap(lt);
return *this;
}
建議寫代碼的時候嚴格區(qū)分類型和類名，讓自己和別人能夠看的很明白。（了解下C++有這種坑語法即可）
五、vector和list的優(yōu)缺點
vector和list像左右手一樣，是互補關系，缺一不可。vector的優(yōu)點正是list的缺點，list的優(yōu)點也是vector的缺點，實際選用容器時，按照需求擇優(yōu)選用。
1、vector
vector的優(yōu)點（結(jié)構(gòu)厲害）：
1、支持下標的隨機訪問；
2、尾插尾刪效率高（當然擴容的那一次尾插尾刪會較慢）；
3、CPU高速緩存命中高（數(shù)據(jù)從緩存加載至CPU中，會加載連續(xù)的一段數(shù)據(jù)，vector因為結(jié)構(gòu)連續(xù)，高速緩存命中高）。
vector的缺點：
1、非尾插尾刪效率低；
2、擴容有消耗，并存在一定的空間浪費。
vector迭代器失效問題：
insert/erase均失效。（如果string的insert和erase形參是迭代器，那么也會失效，但是大部分接口是下標傳參，不考慮失效問題，只有幾個接口是迭代器傳參，需要注意迭代器失效問題）
2、list
list的優(yōu)點：
1、按需申請釋放，無需擴容；
2、任意位置插入刪除時間O(1)；（這里說的是插入刪除，不要加上查找的時間）
list的缺點：
1、不支持下標的隨機訪問；
2、CPU高速緩存命中率低；
3、每一個節(jié)點除了存儲數(shù)據(jù)外，還需要額外存儲兩個指針。
list迭代器失效問題：
insert不失效，erase失效。
六、模擬實現(xiàn)list整體代碼
#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <vector>
using std::cout;
using std::endl;
namespace jly
{
//鏈表節(jié)點的類
template <class T>
struct list_node
{
list_node(const T& x = T())//給一個缺省值，變成默認構(gòu)造函數(shù)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
list_node* _next;
list_node* _prev;
T _data;
};
//用類封裝普通/const迭代器
template <class T, class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T, Ref,Ptr> Self;
//用節(jié)點的指針進行構(gòu)造
__list_iterator(node* p)
:_pnode(p)
{}
//迭代器運算符的重載
Ref operator*()
{
return _pnode->_data;
}
Ptr operator->()
{
return &_pnode->_data;
}
Self& operator++()//返回值不要寫成node*，因為迭代器++肯定返回迭代器啊，你返回節(jié)點指針類型不對
{
//return _pnode->_next;//返回類型錯誤的
_pnode = _pnode->_next;
return *this;//返回的是迭代器
}
Self operator++(int)//后置++
{
_pnode = _pnode->_next;
return Self(_pnode->_next);
}
Self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
Self operator--(int)//后置--
{
_pnode = _pnode->_prev;
return Self(_pnode->_prev);
}
bool operator!=(const Self& it)const
{
return _pnode != it._pnode;
}
bool operator==(const Self& it)const
{
return _pnode == it._pnode;
}
public:
node* _pnode;//封裝一個節(jié)點的指針
};
//用類封裝const迭代器
//template <class T>
//struct __list_const_iterator
//{
// typedef list_node<T> node;
// //用節(jié)點的指針進行構(gòu)造
// __list_const_iterator(node* p)
// :_pnode(p)
// {}
// //迭代器運算符的重載
// const T& operator*()const
// {
// return _pnode->_data;
// }
// __list_const_iterator<T>& operator++()//返回值不要寫成node*，因為迭代器++肯定返回迭代器啊，你返回節(jié)點指針類型不對
// {
// //return _pnode->_next;//返回類型錯誤的
// _pnode = _pnode->_next;
// return *this;//返回的是迭代器
// }
// __list_const_iterator<T>& operator--()
// {
// _pnode = _pnode->_prev;
// return *this;
// }
// bool operator!=(const __list_const_iterator<T>& it)const
// {
// return _pnode != it._pnode;
// }
//public:
// node* _pnode;//封裝一個節(jié)點的指針
//};
//鏈表類（控制哨兵位）
template <class T>
class list
{
public:
typedef list_node<T> node;
typedef __list_iterator<T, T&,T*> iterator;
typedef __list_iterator<T, const T&,const T*> const_iterator;
//typedef __list_const_iterator<T> const_iterator;
//構(gòu)造函數(shù)
void empty_initialize()//用于初始化哨兵位
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_initialize();
}
template <class InputIterator>
list(InputIterator first, InputIterator last)//迭代器區(qū)間構(gòu)造
{
empty_initialize();
while (first != last)
{
push_back(*first);
++first;
}
}
//析構(gòu)函數(shù)
~list()
{
clear();
delete _head;
_head = nullptr;
}
//拷貝構(gòu)造
list(const list<T>& lt)
{
先初始化*this
//empty_initialize();
//for (const auto& e : lt)//取lt的數(shù)據(jù)給e
//{
// push_back(e);
//}
//工具人寫法
list<T> tmp(lt.begin(),lt.end());
empty_initialize();
swap(tmp);
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);//交換頭指針
std::swap(_size,lt._size);
}
賦值運算符重載寫法1
//list<T>& operator=(const list<T>& lt)
//{
// //防止自己給自己賦值
// if (this != <)
// {
// clear();
// for (const auto& e : lt)
// {
// push_back(e);
// }
// }
// return *this;
//}
// 賦值運算符重載寫法2(賦值運算符重載都可以這么干)
list<T>& operator=(list<T> lt)
{
swap(lt);//直接交換
return *this;
}
//插入刪除
void push_back(const T& x)
{
/*node* newNode = new node(x);
node* tail = _head->_prev;
newNode->_prev = tail;
newNode->_next = _head;
tail->_next = newNode;
_head->_prev = newNode;*/
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& x)//頭插
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
node* newNode = new node(x);
node* prev = pos._pnode->_prev;
node* cur = pos._pnode;
newNode->_prev = prev;
newNode->_next = cur;
prev->_next = newNode;
cur->_prev = newNode;
//return iterator(newNode);
pos._pnode = newNode;
++_size;
return pos;
}
iterator erase(iterator pos)
{
assert(!empty());
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
prev->_next = next;
next->_prev = prev;
delete pos._pnode;
--_size;
//return iterator(next);
pos._pnode = next;
return pos;
}
//鏈表小接口
bool empty()const
{
return _head->_next == _head;
}
void clear()
{
/*assert(!empty);
node* cur = _head->_next;
while (cur != _head)
{
node* next = cur->_next;
delete cur;
cur = next;
}*/
iterator it = begin();
while (it != end())
{
it = erase(it);//erase返回刪除元素的下一個
}
}
size_t size()const
{
return _size;
}
//普通begin(),end()迭代器
iterator begin()
{
//return iterator(_head->_next);
return __list_iterator<T, T&,T*>(_head->_next);
}
iterator end()
{
return __list_iterator<T, T&,T*>(_head);
}
//const begin(),end()迭代器
const_iterator begin()const
{
//return const_iterator(_head->_next);
return __list_iterator<T, const T&,const T*>(_head->_next);
}
const_iterator end()const
{
return __list_iterator<T, const T&,const T*>(_head);
}
private:
node* _head;//哨兵位
size_t _size;//用于統(tǒng)計節(jié)點個數(shù)，空間換時間
//不加這個私有變量，統(tǒng)計節(jié)點個數(shù)時間O(N),有這個私有變量，時間O(1),但是每個節(jié)點的體積變大
};
//測試函數(shù)
struct Pos
{
int _row;
int _col;
Pos(int row = 0, int col = 0)
:_row(row)
, _col(col)
{}
};
void test()
{
list<Pos> i;
i.push_back(Pos(1, 2));
i.push_back(Pos(2, 5));
i.push_back(Pos(4, 3));
list<Pos>::iterator it = i.begin();
while (it != i.end())
{
cout << (&( * it))->_row;//*it取數(shù)據(jù)，再取地址、解引用得到_row,多此一舉
cout << it->_row;//同第三種寫法，編譯器為了可讀性，省略了一個->
cout << it.operator->()->_row;//it.operator->()是顯示調(diào)用，->_row是解引用得到_row
it++;
}
}
void test1()
{
list<std::vector<int>> i;
std::vector<int> v1(1, 2);
std::vector<int> v2(2, 4);
std::vector<int> v3(3, 5);
i.push_back(v1);
i.push_back(v2);
i.push_back(v3);
list<std::vector<int>> m(i);
i = m;
cout << m.size();
}
}到此這篇關于利用C++模擬實現(xiàn)STL容器:list的文章就介紹到這了,更多相關C++ STL容器list內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
紅黑樹它一種特殊的二叉查找樹,這意味著它滿足二叉查找樹的特征,但是也有許多自己的特性,這篇文章主要給大家介紹了關于C++實現(xiàn)紅黑樹的相關資料,需要的朋友可以參考下2021-11-11
關于C++使用std::chrono獲取當前秒級/毫秒級/微秒級/納秒級時間戳問題
這篇文章主要介紹了C++使用std::chrono獲取當前秒級/毫秒級/微秒級/納秒級時間戳,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-07-07
這篇文章主要給大家介紹了關于C++11中多線程編程-std::async的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11
關于C++STL string類的介紹及模擬實現(xiàn)
這篇文章主要介紹了關于C++STL string類的介紹及模擬實現(xiàn)的相關資料,需要的朋友可以參考下面具體的文章內(nèi)容2021-09-09
在本篇文章里小編給大家分享了關于c++編程學習的技巧以及知識點總結(jié)，需要的朋友們學習下。2019-03-03
C語言數(shù)據(jù)結(jié)構(gòu)之線索二叉樹及其遍歷
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)之線索二叉樹及其遍歷的相關資料,為了加快查找節(jié)點的前驅(qū)和后繼。對二叉樹的線索化就是對二叉樹進行一次遍歷，在遍歷的過程中檢測節(jié)點的左右指針是否為空，如果是空，則將他們改為指向前驅(qū)和后繼節(jié)點的線索，需要的朋友可以參考下2017-08-08
這篇文章主要為大家介紹了ffmpeg?在?win平臺下的編譯以及集成詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步早日升職加薪2023-05-05
下面小編就為大家?guī)硪黄獪\談在函數(shù)中返回動態(tài)的內(nèi)存。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
C++實現(xiàn)LeetCode(131.拆分回文串)
這篇文章主要介紹了C++實現(xiàn)LeetCode(131.拆分回文串),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
linux c 查找使用庫的cflags與libs的方法詳解
本篇文章是對在linux中使用c語言查找使用庫的cflags與libs的方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05