list模擬實現(xiàn)代碼：
namespace djx
{
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
list_node(const T& x = T())
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};
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* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin()const
{
return _head->_next;
}
const_iterator end()const
{
return _head;
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(const list<T>& lt)
{
empty_init();
for (auto e : lt)
{
push_back(e);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
_size++;
return newnode;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
delete cur;
prev->_next = next;
next->_prev = prev;
_size--;
return next;
}
size_t size()
{
return _size;
}
private:
Node* _head;
size_t _size;
};
}源碼中的list實現(xiàn)為帶頭雙向鏈表
?文章來源地址http://www.zghlxwxcb.cn/news/detail-679593.html
list類的對象有兩個成員：指向頭結(jié)點的指針_head，統(tǒng)計數(shù)據(jù)個數(shù)的_size
在模擬實現(xiàn)list之前，需要先模擬實現(xiàn)結(jié)點類，迭代器類
結(jié)點類：三個成員，_data _prev _next，實現(xiàn)成struct（也是類，不過與class不同的是，它的成員都是公開的，都可以在類外訪問），因為這三個成員，在迭代器類中都要使用訪問，設it是迭代器，*it就會返回結(jié)點中值(_data)的引用，it++（要訪問結(jié)點中的_next) ， it--（要訪問結(jié)點中的_prev)
template<class T>
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
list_node(const T& x = T())//x是匿名對象的引用，const延長了匿名對象的生命周期，x銷毀，匿名對象才銷毀，匿名對象會調(diào)用它的構(gòu)造函數(shù)，完成初始化
:_data(x)
,_prev(nullptr)
,_next(nullptr)
{}
};要寫構(gòu)造函數(shù)：list類中的push_back插入數(shù)據(jù)時，需要new一個結(jié)點，并傳數(shù)值
? ? ? ? ? ? ? ? ? ? ? ? ?調(diào)用構(gòu)造函數(shù)時，若是直接使用編譯器生成的默認構(gòu)造函數(shù)，則無法傳參
構(gòu)造函數(shù)的參數(shù)設計成缺省參數(shù)：有傳實參過來就使用此值，沒有傳參過來就用匿名對象去拷貝構(gòu)造_data，使用匿名對象去拷貝構(gòu)造_data的情形：list類中的無參構(gòu)造函數(shù)-->讓list中的成員變量_head指向一個new出來的頭結(jié)點，頭結(jié)點中不存儲任何有效數(shù)據(jù)，故而new時無需傳參
迭代器類：一個成員 _node（結(jié)點的指針）
設計成struct：在list類中設計insert和erase時，傳參給它們的是iterator迭代器，我們要使用迭代器中的成員變量（結(jié)點的指針）即要訪問迭代器中的成員，那么設計成struct會比設計成class類方便不少
list的迭代器與vector,string類不同，在模擬實現(xiàn)vector和string的迭代器時，它們可以用原生指針來實現(xiàn)，因為完美契合原生指針的行為，但是模擬實現(xiàn)list的迭代器時，它必須設計成一個類，是對原生指針的封裝，原因：
若是list的迭代器就用原生指針來實現(xiàn)，那么*it（it是一個迭代器）得到的不是數(shù)據(jù)，而是結(jié)點
it++ 不能走向下一個數(shù)據(jù)，故而需要對原生指針進行封裝，讓*it得到數(shù)據(jù)，it++，走向下一個數(shù)據(jù)
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* node)//要寫帶參的構(gòu)造，因為在list類中實現(xiàn)begin()時，返回值的類型是迭代器，但是我們返回的可以是結(jié)點的指針，單參數(shù)的構(gòu)造函數(shù)支持隱式類型轉(zhuǎn)換，也可以是迭代器，但是此迭代器中的成員變量（結(jié)點的指針）需要和第一個結(jié)點的指針一樣
:_node(node)
{}
Ref operator*()//Ref可以是T&（普通迭代器） const T& （const迭代器）
{
return _node->_data;
}
Ptr operator->()Ptr可以是T* (普通迭代器） const T* (const迭代器）
{
return &_node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)//后置++
{
self tmp(*this);
_node = _node->_next;
return tmp;//返回迭代器++之前的值
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)//后置--
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
bool operator==(const self& s)
{
return _node == s._node;
}
};迭代器有非const對象調(diào)用的，也有const對象調(diào)用的，二者的區(qū)別僅僅是能否修改的問題，*迭代器返回的是數(shù)據(jù)的引用，const對象調(diào)用的迭代器返回的也是數(shù)據(jù)的引用，但是const修飾的
迭代器-> 返回的是數(shù)據(jù)的地址，const對象調(diào)用的迭代器返回的是const修飾的數(shù)據(jù)地址
(迭代器可以看作是模擬原生指針的行為，若是數(shù)據(jù)為自定義類型，那么迭代器->就可以訪問到自定義類型對象中的成員，實際上看成是原生指針的迭代器->?無法做到，但是對原生指針封裝而出現(xiàn)的迭代器可以做到，只要迭代器->返回的是數(shù)據(jù)的指針，那么有了自定義類型對象指針，不就可以訪問它里面的成員了嗎）
綜上來看，我們只需要寫一份迭代器類的模板，根據(jù)實例化參數(shù)的不同，生成不同的迭代器
迭代器需要三個模板參數(shù)：T（迭代器類中的成員變量是結(jié)點的指針，結(jié)點實例化需要）
模板參數(shù) Ref? : 迭代器類中重載*運算符所用，重載*運算符的函數(shù)要返回數(shù)據(jù)的引用，而若是const對象的迭代器解引用，就要用const去修飾返回值
模板參數(shù)Ptr ：迭代器類中重載->運算符所用，重載->運算符的函數(shù)返回數(shù)據(jù)的指針，而若是const對象的迭代器->，也要用const去修飾返回值
那么在list類中，設計普通迭代器，const對象調(diào)用的迭代器時，就可以用迭代器類的模板，實例化參數(shù)不同就會是完全不同的類型，普通迭代器用迭代器類的模板實例化，傳參 T? ?T&? ?T*
const對象調(diào)用的迭代器用迭代器類的模板實例化，傳參 T? const T&? ?const T*
構(gòu)造函數(shù)：
1 無參的構(gòu)造
? ? 讓list對象中的成員變量_head指向一個頭指針（雙向循環(huán)）
? ? 參照源碼list的實現(xiàn)：
?
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
2 拷貝構(gòu)造（深拷貝）
list(const list<T>& lt)
{
empty_init();
for (auto e : lt)
{
push_back(e);
}
}析構(gòu)函數(shù)：
~list()
{
clear();
delete _head;//釋放頭結(jié)點
_head = nullptr;
}
void clear()//清除數(shù)據(jù)
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}賦值重載：
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)///lt是實參的深拷貝，lt銷毀會釋放掉原本由*this申請的空間
{
swap(lt);//交換*this和lt
return *this;
}迭代器：
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin()const
{
return _head->_next;
}
const_iterator end()const
{
return _head;
}測試1：
void test1()
{
djx::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
djx::list<int>:: iterator it = lt.begin();
while (it != lt.end())
{
*it += 20;
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
測試2：
void test2()
{
djx::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
djx::list<int> lt1(lt);//拷貝構(gòu)造
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
djx::list<int> lt2;
lt2.push_back(100);
lt2.push_back(200);
lt2.push_back(300);
lt2.push_back(400);
lt2.push_back(500);
lt1 = lt2;//賦值重載
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
}
?
?
插入：
?1 push_back
void push_back(const T& x)
{
insert(end(), x);
}2 push_front
void push_front(const T& x)
{
insert(begin(), x);
}3 insert
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;//當前節(jié)點的指針
Node* newnode = new Node(x);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
_size++;
return newnode;//單參數(shù)的構(gòu)造函數(shù)支持隱式類型轉(zhuǎn)換
//或者寫成：iterator(newnode)
}刪除：
1 pop_back
void pop_back()
{
erase(--end());
}2 pop_front
void pop_front()
{
erase(begin());
}3 erase
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
delete cur;
prev->_next = next;
next->_prev = prev;
_size--;
return next;//返回下一個數(shù)據(jù)的地址
}測試3：
struct AA
{
AA(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{}
int _a1;
int _a2;
};
void test3()
{
djx::list<AA> lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
djx::list<AA>::iterator it = lt.begin();
while (it != lt.end())
{
//cout << (*it)._a1 << " "<<(*it)._a2<<endl;
cout << it->_a1 << " " << it->_a2 << endl;
it++;
}
cout << endl;
}
題外：
?設計一個打印函數(shù)，打印任意list對象
template<typename T>//不可以用class
void print_list(const djx:: list<T>& lt)
{
//list<T>未實例化的類模板，編譯器不能去它里面去找
//編譯器就無法list<T>::const_iterator是內(nèi)嵌類型，還是靜態(tài)成員變量
//前面加一個typename就是告訴編譯器，這里是一個類型，等list<T>實例化，再去類里面找
typename djx::list<T>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}打印任意容器
template<typename Container>
void print_container(const Container& con)
{
typename Container::const_iterator it = con.begin();
while (it != con.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}測試4：
void test4()
{
djx::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
print_list(lt);
}
測試5：
void test5()
{
djx::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
print_container(lt);
djx::list<string> lt1;
lt1.push_back("1111111111111");
lt1.push_back("1111111111111");
lt1.push_back("1111111111111");
lt1.push_back("1111111111111");
lt1.push_back("1111111111111");
//print_list(lt1);
print_container(lt1);
vector<string> v;
v.push_back("222222222222222222222");
v.push_back("222222222222222222222");
v.push_back("222222222222222222222");
v.push_back("222222222222222222222");
print_container(v);
}?
文章來源：http://www.zghlxwxcb.cn/news/detail-679593.html
?
到了這里，關于C++ list模擬實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C++]:12:模擬實現(xiàn)list](https://imgs.yssmx.com/Uploads/2024/01/814378-1.png)
