C++初階（list容器+模擬實現）
2022-11-22 06:01:43
list介紹
list的本質是一個帶頭的雙向迴圈連結串列。
連結串列是一種物理儲存單元上非連續、非順序的儲存結構，資料元素的邏輯順序是通過連結串列中的指標連結次序實現的。連結串列由一系列結點（連結串列中每一個元素稱為結點）組成，結點可以在執行時動態生成。每個結點包括兩個部分：一個是儲存資料元素的資料域，另 一個是儲存下一個結點地址的指標域。
相較於vector的連續線性空間，list就顯得負責許多，它的好處是每次插入或者刪除一個元素，就只設定或者釋放一個元素的空間。因此，list對於空間的運用有絕對的精準， 一點也不浪費。而且，對於任何位置的元素插入或元素的移除，list永遠是常數時間。
List和vector是兩個最常被使用的容器。 List容器是一個雙向連結串列。
- 採用動態儲存分配，不會造成記憶體浪費和溢位
- 連結串列執行插入和刪除操作十分方便，修改指標即可，不需要移動大量元素
- 連結串列靈活，但是空間和時間額外耗費較大
- list有一個重要的性質，插入和刪除操作都不會造成原有的list迭代器失效
概述
list容器
- 資料結構：雙向迴圈連結串列
- 迭代器：雙向迭代器
- 常用API
- 構造
- 資料元素的插入和刪除
- 容器大小操作
- 賦值操作
- 資料的存取
- 反轉和排序
- 動態儲存分配（連結串列的插入和刪除）
- 注意：list容器不能使用常用的sort，只能使用自己的sort
- list容器插入和刪除很方便，但是不支援任意位置的隨機存取
list常見的介面
list的建構函式
list<T> lstT;//list採用採用模板類實現,物件的預設構造形式
list(beg,end);//建構函式將[beg, end)區間中的元素拷貝給本身
list(n,elem);//建構函式將n個elem拷貝給本身
list(const list &lst);//拷貝建構函式
void test()
{
list<int> lt1;// 無參構造
list<int> lt2(10, 5);// 用n個val構造一個list物件
list<int> lt3(lt2);// 拷貝構造
list<int> lt4(lt2.begin(), lt2.end());// 用一段區間的元素構造list
}
list中的迭代器
- begin + end： 獲取第一個資料位置的iterator/const_iterator， 獲取最後一個資料的下一個位置的iterator/const_iterator(最後一個資料的下一個位置就是第一個資料的位置)
- rbegin + rend： 獲取最後一個資料位置的reverse_iterator，獲取第一個資料前一個位置的reverse_iterator（第一個資料的前一個位置就是最後一個資料的位置）
- list容器是一個雙向的迴圈連結串列
list的迭代器遍歷
1.迭代器遍歷正向遍歷
void test01()
{
list<int> lt;
//尾插
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
//頭插
lt.push_front(0);
lt.push_front(-1);
lt.push_front(-2);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
2.範圍for
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
3.迭代器反向遍歷
list<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
}
輸出結果如下：
list的增刪改查
assign(beg, end);//將[beg, end)區間中的資料拷貝賦值給本身
assign(n, elem);//將n個elem拷貝賦值給本身
push_back(elem);//在容器尾部加入一個元素
pop_back();//刪除容器中最後一個元素
push_front(elem);//在容器開頭插入一個元素
pop_front();//從容器開頭移除第一個元素
insert(pos,elem);//在pos位置插elem元素的拷貝，返回新資料的位置
insert(pos,n,elem);//在pos位置插入n個elem資料，無返回值
insert(pos,beg,end);//在pos位置插入[beg,end)區間的資料，無返回值
clear();//移除容器的所有資料
erase(beg,end);//刪除[beg,end)區間的資料，返回下一個資料的位置
erase(pos);//刪除pos位置的資料，返回下一個資料的位置
remove(elem);//刪除容器中所有與elem值匹配的元素
swap(lst);//將lst與本身的元素互換
list<int> mylist;
mylist.push_back(19);
mylist.push_back(29);
mylist.push_back(39);
mylist.push_back(49);
mylist.push_back(59);
mylist.push_front(100);
mylist.push_front(200);
mylist.push_front(300);
mylist.push_front(400);
vector<int> v;
v.push_back(1000);
v.push_back(2000);
v.push_back(3000);
mylist.insert(mylist.begin(), v.begin(), v.end());
printList(mylist);
mylist.remove(300);
//刪除大於300的資料
mylist.remove_if(myfunc);
list的大小和頭尾元素的讀取
size();//返回容器中元素的個數
empty();//判斷容器是否為空
resize(num);//重新指定容器的長度為num，若容器變長，則以預設值填充新位置。如果容器變短，則末尾超出容器長度的元素被刪除
resize(num, elem);//重新指定容器的長度為num，若容器變長，則以值填充新位置。如果容器變短，則末尾超出容器長度的元素被刪除
list迭代器失效
迭代器失效即迭代器所指向的節點的無效，即該節點被刪除了。因為list的底層結構為帶頭結點的雙向迴圈連結串列，因此在list中進行插入時是不會導致list的迭代器失效的，只有在刪除時才會失效，並且失效的只是指向被刪除節點的迭代器，其他迭代器不會受到影響。
第一種情況：插入
list<int> mylist;
mylist.push_back(19);
mylist.push_back(29);
mylist.push_back(39);
mylist.push_back(49);
mylist.push_back(59);
list<int>::iterator it = mylist.begin();
mylist.insert(it,3);
執行結果沒有問題，不會報錯
第二種情況：刪除
list<int> mylist;
mylist.push_back(19);
mylist.push_back(29);
mylist.push_back(39);
mylist.push_back(49);
mylist.push_back(59);
list<int>::iterator it = mylist.begin();
while( it! = mylist.end())
{
mylist.erase(it);
++it;
}
總結：插入資料不會導致迭代器失效，刪除資料會導致迭代器失效。相比vector容器，vector容器插入資料是會導致迭代器失效，因為vector涉及增容問題，而list卻不存在增容問題，所以迭代器指向的位置是有效的。刪除資料會導致迭代器指向的位置是無效的，所以迭代器會失效。
解決方法：和vector一樣，對迭代器進行賦值
list<int> mylist;
mylist.push_back(19);
mylist.push_back(29);
mylist.push_back(39);
mylist.push_back(49);
mylist.push_back(59);
list<int>::iterator it = mylist.begin();
while( it! = mylist.end())
{
it = mylist.erase(it);//erase()返回值是指向被刪元素的下一元素的指標(也就是迭代器)
}
list模擬實現
list整體框架
list是由節點組成，所以定義一個節點的類，然後list的類中成員只需要一個頭結點的指標即可。
template<class T>
struct __list_node
{
__list_node<T>* _prev;
__list_node<T>* _next;
T _data;
__list_node(const T& x = T())
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
template<class T>
class list
{
typedef __list_node<T> Node;
public:
private:
Node* _head;
};
list的建構函式
建構函式要做的任務就是開一個頭結點，所以我們可以封裝出一個具體的函數來實現建立頭結點的這個過程
建立頭結點：
void CreatHead()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
建構函式的實現：
list()
{
CreatHead();
}
list迭代器的實現
list相比vector的迭代器而言，不再是一個簡單的指標，它相對而言更復雜一些，list的迭代器為了實現一些簡單的功能，我們把它封裝成了一個類。看下面原始碼實現：
我們自己來模擬實現一下簡單的。
迭代器的小框架（裡面有一個成員變數——節點指標）
struct __list_iterator
{
typedef __list_node<T> Node;
__list_iterator(Node* node = nullptr)
:_node(node)
{}
Node* _node;
}
由於迭代器分普通迭代器和const 迭代器，為了不造成程式碼冗餘，我們設計出來三個模板引數，根據傳入的模板引數確定是那種迭代器。
// __list_iterator<T, T&, T*> -> 普通迭代器
// __list_iterator<T, const T&, const T*> -> const迭代器
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 = nullptr)
:_node(node)
{}
__list_iterator(const Self& l)
:_node(l._node)
{}
// *it T&
Ref operator*()
{
return _node->_data;
}
// it-> T*
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
//_node = _node->_next;
++(*this);
return tmp;
}
Self operator--(int)
{
Self tmp(*this);
//_node = _node->_prev;
--(*this);
return tmp;
}
Self operator+(int count)
{
Self tmp(*this);
while (count--)
{
++tmp;
}
return tmp;
}
Self operator-(int count)
{
Self tmp(*this);
while (count--)
{
--tmp;
}
return tmp;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
};
我們還要在list裡面做這樣一個操作（堆兩種迭代器進行重新命名，方便我們認識）：
typedef list_iterator<T, T&, T*> iterator;// 普通迭代器
typedef list_iterator<T, const T&, const T*> const_iterator;// const迭代器
list內部begin()和end()的實現（普通迭代器呼叫前兩個，const迭代器呼叫後兩個）
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
list的增刪查改的實現
void push_back(const T& x)
{
Node* newnode = new Node(x);
Node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
void pop_back()
{
assert(head != head->_next);
Node* tail = head->_prev;
Node* prevTail = tail->_prev;
delete tail;
tail = prevTail;
tail->_next = head;
head->_prev = tail;
}
void push_front(const T& x)
{
Node* newnode = new Node(x);
Node* firstNode = head->_next;
head->_next = newnode;
newnode->_prev = head;
newnode->_next = firstNode;
firstNode->_prev = newnode;
}
void pop_front()
{
assert(head->_next != head);
Node* firstNode = head->_next;
Node* secondNode = firstNode->_next;
delete firstNode;
firstNode = nullptr;
head->_next = secondNode;
secondNode->_prev = head;
}
void insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
}
iterator erase(iterator pos)
{
assert(head->_next != head);
assert(pos != end());
Node* node = pos._node;
Node* prev = node->_prev;
Node* next = node->_next;
delete node;
node = nullptr;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}
T front()
{
assert(head->_next != head);
return head->_next->data;
}
T back()
{
assert(head->_next != head);
return head->_prev->data;
}
list中的解構函式和clear
1.clear 通過迭代器遍歷，一個一個的刪除節點
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
2.解構函式 可以先呼叫clear函數清理空間，然後再delete掉頭結點
~list()
{
clear();
delete head;
head = nullptr;
}
拷貝構造和operator=賦值過載
1.拷貝構造
list(const list<T>& lt)
{
CreatHead();
/*const_iterator it = lt.begin();
while (it != lt.end())
{
push_back(*it);
++it;
}*/
for (auto e : lt)
push_back(e);
}
2.operator= 直接利用swap和形參交換，形參會自己呼叫解構函式清理空間
list<T>& operator=(list<T> lt)
{
if (this != <)// 防止自己給自己賦值
{
swap(lt);
}
return *this;
}
swap函數實現如下：
void swap(list<T>& lt)
{
::swap(head, lt.head);
}