目錄
1.const修飾的迭代器的實現
方法1:分成兩個類
完整代碼
方法2:STL庫的寫法
2.STL庫的第三個模版參數T*的解釋
->->的簡寫語法?
3.其他成員函數
insert
erase
push_back、push_front、pop_front、pop_back
size
clear
析構函數~list()
拷貝構造函數(★)
私有函數empty_initialize
swap
operator=
4.提交到leetcode題上測試成員函數的正確性
代碼
提交結果
承接CD46.【C++ Dev】list的模擬實現(1)文章
1.const修飾的迭代器的實現
回顧const修飾的迭代器的要求:1.自己可以修改 2.指向的數據不能修改
方法1:分成兩個類
const修飾的迭代器和非const修飾的迭代器分成兩個類,寫兩份代碼,這兩份代碼僅僅是operator*的返回的參數不同
//const修飾的迭代器
const T& operator*()
{return node->data;
}//非const修飾的迭代器
T& operator*()
{return node->data;
}注意:const修飾的迭代器中的operator*不能寫成T& operator*() const,這個const修飾的是this指針指向的對象node不能被修改(在CD22.【C++ Dev】類和對象(13) 流提取運算符的重載和const成員文章講過),不是指node->data不能修改
完整代碼
#pragma once
namespace mystl
{template<class T>struct __list_node{typedef __list_node<T>* link_type;__list_node(const T& x = T()):next(nullptr), prev(nullptr), data(x){}link_type next;link_type prev;T data;};template<class T>struct __list_iterator{typedef __list_node<T>* link_type;typedef __list_iterator<T> iterator;__list_iterator(link_type x):node(x){}iterator& operator++(){node = node->next;return *this;}iterator operator++(int){iterator tmp(*this);node = node->next;return tmp;}iterator& operator--(){node = node->prev;return *this;}iterator operator--(int){iterator tmp(*this);node = node->prev;return tmp;}bool operator!=(const iterator& x) const{return node != x.node;}bool operator==(const iterator& x) const{return node == x.node;}T& operator*(){return node->data;}link_type node;};template<class T>struct __list_const_iterator{typedef __list_node<T>* link_type;typedef __list_const_iterator<T> const_iterator;__list_const_iterator(link_type x):node(x){}const_iterator& operator++(){node = node->next;return *this;}const_iterator operator++(int){const_iterator tmp(*this);node = node->next;return tmp;}const_iterator& operator--(){node = node->prev;return *this;}const_iterator operator--(int){const_iterator tmp(*this);node = node->prev;return tmp;}bool operator!=(const const_iterator& x) const{return node != x.node;}bool operator==(const const_iterator& x) const{return node == x.node;}const T& operator*(){return node->data;}link_type node;};template<class T>class list{typedef __list_node<T> list_node;typedef __list_node<T>* link_type;public:typedef __list_iterator<T> iterator;typedef __list_const_iterator<T> const_iterator;list(){node = new list_node;node->next = node;node->prev = node;}void push_back(const T& x){link_type tmp = new list_node(x);//先找尾link_type tail = node->prev;tail->next = tmp;tmp->prev = tail;tmp->next = node;node->prev = tmp;}iterator begin(){//返回哨兵位的下一個節點return node->next;}iterator end(){//返回哨兵位return node;}const_iterator begin() const{//返回哨兵位的下一個節點return node->next;}const_iterator end() const{//返回哨兵位return node;}private:link_type node;};
}測試代碼:
#include <iostream>
#include "list.h"
void print_list(const mystl::list<int>& ls)//權限縮小
{mystl::list<int>::const_iterator it = ls.begin();while (it != ls.end()){std::cout << *it << " ";it++;}}
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);print_list(ls);return 0;
}運行結果:
方法2:STL庫的寫法
STL的源碼:__list_iterator迭代器類有3個模版參數:T、Ref、Ptr
template<class T, class Ref, class Ptr>
struct __list_iterator {typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef __list_iterator<T, Ref, Ptr> self;//......typedef Ref reference;//......reference operator*() const { return (*node).data; }
}
operator*的返回類型為reference,而reference為Ref,Ref是__list_iterator類的第二個模版參數
這樣可以為Ref指定:T&或者const T&,這樣可以簡寫const修飾和非const修飾的迭代器,沒有必要寫兩份代碼
之前返回類型為iterator要改成__list_iterator<T, Ref>,可以重定義為self?
其實是讓編譯器來代替我們寫iterator和const_iterator這兩個類
template<class T,class Ref>
struct __list_iterator
{typedef __list_node<T>* link_type;typedef __list_iterator<T,T&> iterator;typedef __list_iterator<T,const T&> const_iterator;typedef __list_iterator<T, Ref> self;typedef Ref reference;__list_iterator(link_type x):node(x){}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& x) const{return node != x.node;}bool operator==(const self& x) const{return node == x.node;}reference operator*(){return node->data;}link_type node;
};繼續測試之前的代碼,運行結果:
2.STL庫的第三個模版參數T*的解釋
上方代碼實現的__list_iterator只有2個模版參數,但是STL庫卻有3個模板參數:
template<class T, class Ref, class Ptr>
struct __list_iterator
{//......
}看看Ptr出現在什么函數中:
STL庫將Ptr重定義為pointer:?
typedef Ptr pointer;那就找pointer還出現在哪里:
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */發現:pointer是operator->的返回類型,原因:
迭代器的任務是模擬指針,而結構體指針是可以用operator->來訪問其指向對象的成員,那迭代器也要有operator->操作符
?那自制的operator->可以這樣寫:
template<class T,class Ref,class Ptr>
struct __list_iterator
{typedef __list_node<T>* link_type;typedef __list_iterator<T,T&,T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;typedef __list_iterator<T, Ref,Ptr> self;typedef Ref reference;typedef Ptr pointer;//......reference operator*(){return node->data;}pointer operator->(){return &(node->data);}link_type node;
};
當然也可以復用operator*,寫成:
pointer operator->()
{return &(operator*());
}測試代碼:
#include <iostream>
#include "list.h"
class Myclass
{
public:Myclass(const int val1=0, const char val2='\0'):_val1(val1), _val2(val2){}int _val1;char _val2;
};int main()
{mystl::list<Myclass> ls;ls.push_back(Myclass(1,'a'));ls.push_back(Myclass(2, 'b'));ls.push_back(Myclass(3, 'c'));mystl::list<Myclass>::iterator it = ls.begin();while (it != ls.end()){std::cout << it->_val1 << " " << it->_val2 << std::endl;std::cout << (*it)._val1 << " " << (*it)._val2 << std::endl;it++;}return 0;
}運行結果:
發現it->_val1和(*it)._val1的效果是等價的
->->的簡寫語法?
注意到operator->()返回的是Myclass*,嚴謹來說Myclass*是不能訪問_val1和_val2的,應該寫成
std::cout << it->->_val1 << " " << it->->_val2 << std::endl;但編譯器在編譯時自動加上了第二個->,C++標準只允許寫一個->,提高運算符重載的可讀性?
3.其他成員函數
insert
和STL保持一致:
這里只實現第一個:?
先生成新節點,再在pos前插入:
iterator insert(iterator pos,const T& val)
{link_type newnode = new list_node(val);newnode->prev = pos.node->prev;newnode->next = pos.node;pos.node->prev->next = newnode;pos.node->prev = newnode;return newnode;
}測試代碼:
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);auto new_it1=ls.insert(++ls.begin(), 4);//在2的前面插入4for (auto a : ls)std::cout << a << " ";return 0;
}運行結果:
erase
和STL保持一致:
這里只實現第一個:?
注意:erase不能刪哨兵位,因此先斷言
erase函數在刪除元素時,會?使當前迭代器失效?n并返回指向?下一個元素?的迭代器,因此不能返回void
iterator erase(iterator pos)
{assert(pos != end());iterator ret = pos.node->next;pos.node->prev->next = pos.node->next;pos.node->next->prev = pos.node->prev;delete pos.node;return ret;
}測試代碼:
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);ls.erase(++ls.begin());//刪除2for (auto a : ls)std::cout << a << " ";return 0;
}運行結果:
push_back、push_front、pop_front、pop_back
可以復用insert和erase的代碼
void push_back(const T& x)
{insert(end(), x);
}void push_front(const T& x)
{insert(begin(), x);
}
void pop_front()
{erase(begin());
}
void pop_back()
{erase(--end());
}?測試代碼:
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);ls.push_back(4);ls.pop_back();ls.pop_front();ls.push_back(5);ls.push_front(6);for (auto a : ls)std::cout << a << " ";return 0;
}運行結果:
size
STL庫的實現:
size_type size() const {size_type result = 0;distance(begin(), end(), result);return result;
}distance是算法庫<algorithm>中的函數,用于計算兩個迭代器之間的距離,并將結果存儲到result中,這里我們實現的簡單一些:
void distance(const_iterator begin, const_iterator end, size_type& result) const
{const_iterator it = begin;while (it != end){it++;result++;}
}
size_type size() const
{size_type result = 0;distance(begin(), end(), result);return result;
}測試代碼:
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);ls.push_back(4);std::cout << ls.size();return 0;
}(當然這樣遍歷一遍是有缺點的,比較耗時,可以為list類引入第二個成員變量size來存儲鏈表的長度,這里省略不寫)?
運行結果:
clear
和STL保持一致:
刪除多余節點,只保留哨兵位
void clear()
{iterator it = begin();while (it != end())it=erase(it);//應對迭代器失效,接收返回值
}測試代碼:
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);for (auto a : ls)std::cout << a << " ";ls.clear();ls.push_back(4);ls.push_back(5);ls.push_back(6);for (auto b : ls)std::cout << b << " ";return 0;
}運行結果:
析構函數~list()
先調用clear(),再將node釋放,最后置為空指針
~list()
{clear();delete node;node = nullptr;
}拷貝構造函數(★)
注意是深拷貝,淺拷貝會出問題(在CD44.【C++ Dev】vector模擬實現(3)文章的深拷貝問題解決提到過)
方法:通過遍歷的方式一個個拷貝
//const修飾,防止權限放大
list(const list<T>& ls)//必須是引用,這個&如果不寫,會無限調用拷貝構造函數
{//準備哨兵位node = new list_node;node->next = node;node->prev = node;//添加節點for (auto& a : ls)//使用引用,節省時間{push_back(a);}
}測試代碼:
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);mystl::list<int> ls_copy(ls);for (auto a : ls_copy)std::cout << a<<" ";return 0;
}運行結果:
?
私有函數empty_initialize
兩種構造函數的部分代碼有些冗余
可以封裝成一個私有函數empty_initialize(),當然庫里面也是這樣實現的:
swap
和STL保持一致:
注:上面swap的參數:list& x的list是類名,不是類型,卻也可以做參數,C++的語法支持這樣做,但不建議這樣寫,代碼不直觀
交換鏈表其實是交換頭節點
void swap(list<T>& ls)//寫成void swap(list& ls)也可以
{std::swap(node, ls.node);
}測試代碼:
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls1; ls1.push_back(1); ls1.push_back(2); ls1.push_back(3);mystl::list<int> ls2; ls2.push_back(4); ls2.push_back(5); ls2.push_back(6);std::cout << "ls1:";for (auto a : ls1) std::cout << a << " ";std::cout << std::endl << "ls2:";for (auto b : ls2) std::cout << b << " ";ls1.swap(ls2);std::cout << std::endl << "ls1:";for (auto a : ls1) std::cout << a<<" ";std::cout << std::endl << "ls2:";for (auto b : ls2) std::cout << b<<" ";return 0;
}運行結果:
operator=
使用CD40.【C++ Dev】string類的模擬實現(4)(operator=、拷貝構造函數的現代寫法、寫時拷貝的簡單了解)文章提到的現代寫法:1.operator=的參數需要調用拷貝構造 2.調用swap
list<T>& operator=(list<T> tmp)//寫成list& operator=(list tmp)也可以
{swap(tmp);return *this;
}測試代碼:
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls1; ls1.push_back(1); ls1.push_back(2); ls1.push_back(3);mystl::list<int> ls2 = ls1;std::cout << "ls2:";for (auto a : ls2) std::cout << a << " ";return 0;
}4.提交到leetcode題上測試成員函數的正確性
題:https://leetcode.cn/problems/design-linked-list/
你可以選擇使用單鏈表或者雙鏈表，設計并實現自己的鏈表。
單鏈表中的節點應該具備兩個屬性：
val和next。val是當前節點的值，next是指向下一個節點的指針/引用。如果是雙向鏈表，則還需要屬性?
prev?以指示鏈表中的上一個節點。假設鏈表中的所有節點下標從 0 開始。實現
MyLinkedList類：
MyLinkedList()初始化MyLinkedList對象。int get(int index)獲取鏈表中下標為index的節點的值。如果下標無效，則返回-1。void addAtHead(int val)將一個值為val的節點插入到鏈表中第一個元素之前。在插入完成后，新節點會成為鏈表的第一個節點。void addAtTail(int val)將一個值為val的節點追加到鏈表中作為鏈表的最后一個元素。void addAtIndex(int index, int val)將一個值為val的節點插入到鏈表中下標為index的節點之前。如果index等于鏈表的長度，那么該節點會被追加到鏈表的末尾。如果index比長度更大，該節點將 不會插入 到鏈表中。void deleteAtIndex(int index)如果下標有效，則刪除鏈表中下標為index的節點。示例：
輸入 ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] 輸出 [null, null, null, null, 2, null, 3]解釋 MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 鏈表變為 1->2->3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 現在，鏈表變為 1->3 myLinkedList.get(1); // 返回 3提示：
0 <= index, val <= 1000- 請不要使用內置的 LinkedList 庫。
- 調用
get、addAtHead、addAtTail、addAtIndex和deleteAtIndex的次數不超過2000。
代碼
namespace mystl
{template<class T>struct __list_node{typedef __list_node<T>* link_type;__list_node(const T& x = T()):next(nullptr), prev(nullptr), data(x){}link_type next;link_type prev;T data;};template<class T,class Ref,class Ptr>struct __list_iterator{typedef __list_node<T>* link_type;typedef __list_iterator<T,T&,T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;typedef __list_iterator<T, Ref,Ptr> self;typedef Ref reference;typedef Ptr pointer;__list_iterator(link_type x):node(x){}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& x) const{return node != x.node;}bool operator==(const self& x) const{return node == x.node;}reference operator*(){return node->data;}pointer operator->(){return &(node->data);}link_type node;};template<class T>class list{typedef __list_node<T> list_node;typedef __list_node<T>* link_type;typedef size_t size_type;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;list(){empty_initialize();}list(const list<T>& ls){empty_initialize();for (auto& a : ls){push_back(a);}}void push_back(const T& x){insert(end(), x);}iterator begin(){return node->next;}iterator end(){//返回哨兵位return node;}const_iterator begin() const{return node->next;}const_iterator end() const{return node;}iterator insert(iterator pos,const T& val){link_type newnode = new list_node(val);newnode->prev = pos.node->prev;newnode->next = pos.node;pos.node->prev->next = newnode;pos.node->prev = newnode;return newnode;}iterator erase(iterator pos){assert(pos != end());iterator ret = pos.node->next;pos.node->prev->next = pos.node->next;pos.node->next->prev = pos.node->prev;delete pos.node;return ret;}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void distance(const_iterator begin, const_iterator end, size_type& result) const{const_iterator it = begin;while (it != end){it++;result++;}}size_type size() const {size_type result = 0;distance(begin(), end(), result);return result;}void clear(){iterator it = begin();while (it != end())it=erase(it);}void swap(list<T>& ls){std::swap(node, ls.node);}list<T>& operator=(list<T> tmp){swap(tmp);return *this;}~list(){clear();delete node;node = nullptr;}private:void empty_initialize(){node = new list_node;node->next = node;node->prev = node;}link_type node;};
}class MyLinkedList {
public:MyLinkedList() {}mystl::list<int>::iterator getiterator(int index){mystl::list<int>::iterator it=ls.begin();while(index--)it++;return it;}int get(int index) {if (index<ls.size())return getiterator(index).node->data; return -1; }void addAtHead(int val) {ls.push_front(val);}void addAtTail(int val) {ls.push_back(val);}void addAtIndex(int index, int val) {if (index<=ls.size())//取等是尾插ls.insert(getiterator(index),val);}void deleteAtIndex(int index) {if (index<ls.size())ls.erase(getiterator(index));}mystl::list<int> ls;
};提交結果
