溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關C++中如何實現list，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
list的優點：
list頭部、中間插入不再需要挪動數據，O(1)效率高
list插入數據是新增節點，不需要增容
list的缺點：
不支持隨機訪問,訪問某個元素效率O(N)
底層節點動態開辟，小節點容易造成內存碎片，空間利用率低，緩存利用率低。
我們先來看看官方文檔中對于list的描述
我們先大致了解一下list的遍歷
對于迭代器我們可以用while循環+begin（）end（）。同時還可以用迭代器區間。
當然迭代器區間的方式只適用于內存連續的結構比如數組stringvector等
它們的原生指針就可以當作迭代器來用。
其實范圍for和迭代器的底層是完全一樣的，我們只有寫好迭代器，才能用范圍for，而且這里的迭代器必須和庫里的命名一樣才可以用范圍for
我們再來了解一下有關算法函數中，我們最常用的函數
swap
find
sort
我們主要看看sort函數
sort函數在官方庫中是用快排寫的，其中快排的精髓就是三數取中的優化操作。
sort默認是排升序 如果想排降序需要使用functional文件中的greater()這個模板函數，我們以vector來舉例。
對于list，我們極度不推薦使用algorithm文件中的sort函數，上文提到了sort函數是使用的快速排序的手段進行排序的，而其關鍵在于三數取中這樣的操作，那么三數取中這樣的操作只有在內存連續的數據結構中才能操作，如果給你一個head，給你一個tail，你如果能找到中間的結點？很明顯是很復雜的。
我們這里list迭代器是不支持隨機訪問，他不是隨即迭代器。
而vector string這樣的迭代器是支持隨機訪問的，所以他們用快排很有優勢。
我們可以看到這三個函數的迭代器是不同的，它們是繼承關系，隨機的支持雙向，雙向支持單向，反過來就不行。
當然除了這幾種迭代器，還有輸入輸出迭代器，也叫可讀可寫迭代器，他們是最弱的迭代器，一個單向迭代器都可以支持可讀可寫的功能。也就是說，可讀可寫迭代器在繼承的最上端。所有人都包含了他倆。
但是雖然他們功能很弱，但他們在一些重要的特性上有至關重要的作用，那就是迭代器的萃取。這個和復雜，暫時不去管它們。
當我們使用迭代器遍歷的時候，我們需要知道的是，begin（）代表了第一個結點，end（）代表了頭結點。
這里再穿插一個小知識，我們再官方文檔中總能看到max_size這樣的變量，
它的意義是整形的最大值除以一個節點的大小，也就是得出的節點個數
無符號整形最大是2^32-1，也就是42億多，對于int類型的vector，就是42億除以4得到的值，對于list，就是42億除以三個指針的大小得到的值。
我們還知道再vector中，我們在insert的擴容插入，還有erase的刪除時，會導致迭代器失效的問題。那么對于list我們還要去關注迭代器失效的問題嗎？
我們再insert的時候，插入數據并不會影響到其他的數據的地址，只是影響鏈接的關系，所以不會引起迭代器失效
但是對于erase，當我們刪除對應的結點之后，他會變成野指針。所以我們erase的時候通常去接收它的返回值，也就是下一個結點的迭代器。
當然庫中還有一些我們不常用的函數
splice 接合函數，把一個list的數據轉移到另一個list
這里不是拷貝，是轉移。
還有remove，找到就刪，沒找到就沒什么反應。
unique 去重，這里又一個小小的bug，只有連續的重復數據才會刪除。
聰明的同學會反應過來，這里sort+unique可以解決這樣的問題。當然沒反應過來的同學也很聰明。
這里顯然還是那個問題，我們不建議堆鏈表進行排序，效率是很低的。
list的成員函數是用的歸并排序。為什么不用algorithm中的sort快排呢？原因我們上文已經解釋過了。
說了這么多，來看看代碼吧。
先來看看頭文件吧！
#pragma once
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
namespace LL
{
我們先寫結點類，這里用類模板，并且是用struct實現，默認內容是公開的,其他的類都可以調用
template<class T>
其中結點類中要有三個變量，一個存值，兩個指針
struct _list_node
{
T _val;
_list_node<T>* _next;
_list_node<T>* _prev;
結點類中除了要有三個變量，還需要有一個構造函數。當我們定義一個新結點的時候，進行構造函數初始化
我們這里的參數是一個缺省的val值 ，其中缺省參數給的是匿名構造函數。最好以const接收。
_list_node(const T& val = T())
:_val(val)
, _next(nullptr)
, _prev(nullptr)
{}
};
這里實現迭代器類。首先我們依舊是使用類模板 ，我們這里給三個模板參數，同時類還是用struct來實現
在迭代器類中，我們主要實現 1、構造 2、解引用操作 3、！= 和== 操作 3、前置++后置++ --操作
template<class T, class Ref, class Ptr> 這里三個模板參數是什么意思呢?當我們需要const迭代器和非const迭代器的時候我們可以根據第二個參數的不同來實例化出不同的迭代器，就不需要寫兩個迭代器了
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T,cosnt T&,const T*> const_iterator; 我們可以根據模板參數實例化出不同的迭代器。
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T, Ref, Ptr> self;
node* _pnode;
構造函數，把node傳進來，然后把值賦給我們內部創建的_pnode,總不能亂修改外部指針吧。
_list_iterator(node * node)
:_pnode(node)
{}
這里我們不需要實現拷貝構造、operator=、析構，直接用編譯器生成的，對于內置類型直接進行淺拷貝
我們發現淺拷貝指針對于list來說完全沒問題。
解引用，解引用我們返回值寫為Ref ，這樣可以根據const和非const，并且就是引用返回可讀可修改，如果ref為const，那就不可修改只可讀。
這里不需要傳入參數，我們直接進行調用，返回值當然為對應的val引用.
Ref operator * ()
{
return _pnode->_val;
}
同理的我們寫一下這個指針解引用，這里返回值依舊用模板參數，很方便啊。我們應該返回一個地址。
Ptr operator ->()
{
return &(_pnode->_val);
}
！= 和 == ，當我們使用迭代器的時候，需要比較兩個迭代器是否相等來進行循環條件判定，所以這是必要的。
我們這里返回值當然是bool，參數傳入我們的迭代器，比較迭代器內的節點是否相等。再加上const最好。
bool operator != (const self& s) const
{
return _pnode != s._pnode;
}
bool operator == (const self& s) const
{
return _pnode == s._pnode;
}
接著我們實現前置后置++--
前置 ++ it 我們返回值是 原迭代器
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
后置 ++ it ，我們需要進行傳參，第一個參數就是默認的this，第二個參數為0
it ++ --> it.operator ++(&it,0);我們可以缺省掉第二個參數，因為默認是從參數列表末尾開始匹配的。
當然返回值就不能返回引用了，因為這里我們要用臨時變量進行返回,我們先用傳入的it拷貝構造一個臨時迭代器。然后在進行++操作。
因為后置加加是先賦值再++所以我們先用臨時變量保存一下之前的迭代器，再給之前的迭代器++，最后再返回未修改的臨時迭代器。
self operator++(int)
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
};
接下來我們開始寫list類,當然也要用類模板來寫，里面要實現1、迭代器 2、構造 3、push_back 。我們這里的list是帶頭雙向循環列表
template <class T>
class list
{
我們先來實現一下迭代器,我們首先需要typedef 我們的迭代器 ，所以先實現迭代器。然后需要定義const和非const的beginend ,
這里需要記住end和begin要有非const和cosnt，因為無法同時滿足可修改和可讀。比如const迭代器調用只能掉const的end，非const的迭代器雖然可以調用const的end，但是導致權限縮小，無法修改內容。
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() //begin指頭結點后第一個結點，end指頭結點。
{
return iterator(_head->_next); //這里調用的是匿名構造然后直接返回。
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
構造函數，這里直接進行頭結點的創建（自己鏈自己）
list()
{
_head = new node(T()); 當然可以有這種寫法，我們用匿名構造一個頭結點，可以是各種類型。這里和上文中，結點的構造函數是一樣的，我們寫一個就好了。
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
push_back 我們傳入一個要插入的值，創建新節點進行鏈接的更新。
void push_back(const T& val)
{
node* newnode = new node(val); //這里因為我們在結點的構造函數中寫了模板參數類型匿名構造，可以傳任意類型。
node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
拷貝構造 1、創造新的頭結點，把傳入的list循環賦值給新的頭結點。
list(const list<T>& l)
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
const_iterator it = l.begin();
while (it != l.end())
{
push_back(*it);
++it;
}
}
insert，在指定位置插入元素，我們不用返回值，參數是pos迭代器和val
先給一個cur 存pos位置的結點，然后定義一個我們的prev，為了之后和新節點鏈接。2、創建新節點，更新鏈接就好了。
void insert(iterator pos, const T& val) //這里不需要用const 因為，const迭代器對應了constlist ，const list怎么會來插入數據呢？
{
node* cur = pos._pnode;
node* prev = cur->_prev;
node* newnode = new node(val);
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
cur->_prev = newnode;
}
erase ,返回下一個位置的迭代器，傳入一個pos
1、保存指向結點，并找到前后的兩節點 2、更新鏈接 刪除掉當前節點。3、返回迭代器。這里需要強轉，從指針轉成迭代器類型。
iterator erase(iterator pos)
{
node* cur = pos._pnode;
node* prev = cur->_prev;
node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return (iterator)next;
}
那我們在賦值運算符重載的時候需要先清理掉自身的結點，所以我們實現一下clear
clear 清空list中除了頭結點以外的所有結點。很好實現，我們循環erase就好了，erase返回下一個的迭代器，所以接收其返回值就好了。
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
賦值運算符重載，返回值是類型的引用 ，參數傳入list
1、首先判斷是否給自己賦值，否則我們刪除后會發生野指針的問題 2、條件成立我們先清除現在的一切，然后循環賦值。最后返回*this；
list<T>& operator = (list<T>& l)
{
if (this != &l)
{
clear ();
iterator it = l.begin();
while (it != l.end())
{
push_back(*it);
it++;
}
}
return *this;
}
析構：析構要做的就是析構一切，先clear，在delete 頭，并給頭賦空
~list()
{
clear();
delete _head;
_head = nullptr;
cout << "析構執行成功" << endl;
}
獲得第一個元素，返回一定是類型的引用,這里應該有兩個版本，否則當const對象調用的時候，會無法調用。這里返回也要返回const，否則你給人家偷偷擴大了權限。
T& front()
{
return _head->_next->_val;
}
const T& front() const
{
return _head->_next->_val;
}
獲得最后一個元素
T& back()
{
return _head->_prev->_val;
}
const T& back() const
{
return _head->_prev->_val;
}
交換兩個list,傳入list。我們只需要交換一下頭結點就可以了
void swap(list<T>& l)
{
::swap(_head, l._head);
}
void push_back_insert(const T& val)
{
insert(end(), val);
}
void push_front_insert(const T& val)
{
insert(begin(), val);
}
void pop_front_erase()
{
erase(begin());
}
void pop_back_erase()
{
erase(--end());
}
求結點個數循環計數
size_t size()
{
size_t count = 0;
auto it = begin();
while (it != end())
{
++it;
++count;
}
return count;
}
bool empty()
{
return begin() == end();
}
resize ,開辟n個空間并賦初始值，用匿名構造賦值。
1、計算舊結點個數，如果就空間比新的空間大，我們就刪除多余的空間2、否則就從新空間開始給其賦初值。
void resize(size_t newsize, T& val = T())
{
size_t oldsize = size();
if (oldsize > newsize)
{
for (int i = newsize; i < oldsize; i++)
{
pop_back_erase();
}
}
else
{
for (int i = oldsize; i < newsize; i++)
{
push_back_insert(val);
}
}
}
private:
node* _head;
};
}我們來測試一下我們的函數
#include "List.h"
//printlist 打印不需要返回什么，參數是一個模板參數類型的列表
template<class Con>
void PrintContainer(const Con& c)
{
Con::const_iterator it = c.begin();
while (it != c.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test_list1()
{
cout << "list1使用pushback插入數據的打印" << endl;
LL::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.push_back(5);
lt1.push_back(6);
PrintContainer(lt1);
//for (auto e : lt)
//{
// cout << e << " ";
//}
//cout << endl;
//LL::list<int>::iterator it = lt.begin();
//while (it != lt.end())
//{
// (*it)++;
// cout << *it << " ";
// ++it;
//}
//cout << endl;
cout << "拷貝構造list2的打印" << endl;
LL::list<int> lt2(lt1);
PrintContainer(lt2);
//cout << "在list2的2位置前insert一個0并打印" << endl;
//LL::list<int>::iterator pos = find(lt2.begin(), lt2.end(),2);
//lt2.insert(pos,0);
//PrintContainer(lt2);
//cout << "在list2的2位置前insert一個0并打印" << endl;
//lt2.erase(pos);
//PrintContainer(lt2);
cout << "用list2給list3賦值,并打印" << endl;
LL::list<int> lt3;
lt3 = lt2;
PrintContainer(lt3);
cout << "獲得list3的第一個元素和最后一個元素" << endl;
cout << lt3.front() <<" ";
cout << lt3.back() << endl;
cout << "整一個全是0的list4，并打印" << endl;
LL::list<int> lt4;
lt4.push_back(0);
lt4.push_back(0);
lt4.push_back(0);
lt4.push_back(0);
lt4.push_back(0);
lt4.push_back(0);
PrintContainer(lt4);
cout << "交換鏈表list1和list4、并打印" << endl;
lt1.swap(lt4);
PrintContainer(lt4);
cout << "頭刪list4" << endl;
lt4.pop_front_erase();
PrintContainer(lt4);
cout << "頭插list4" << endl;
lt4.push_front_insert(0);
PrintContainer(lt4);
cout << "尾刪list4" << endl;
lt4.pop_back_erase();
PrintContainer(lt4);
cout << "尾插list4" << endl;
lt4.push_back_insert(0);
PrintContainer(lt4);
cout << "list4的節點個數" << endl;
cout << lt4.size() << endl;
cout << "判斷是list1是否為空鏈表" << endl;
cout << lt1.empty() << endl;
cout << " " << endl;
cout << " " << endl;
cout << " " << endl;
cout << " " << endl;
cout << " " << endl;
cout << " " << endl;
}
int main()
{
test_list1();
return 0;
}
關于“C++中如何實現list”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
