C++——模拟实现list

1.初步实现结点和链表

namespace jxy
{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 list//list的框架本质是封装+运算符重载{typedef list_node<T> Node;public:void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}private:Node* _head;size_t _size;
//不写_size变量的话，想获取size的大小，从头遍历链表，时间复杂度是O(N)};
}

2.push_back

namespace jxy
{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 list//list的框架本质是封装+运算符重载{typedef list_node<T> Node;public:void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}void push_back(const T& x){Node* tail = _head->_prev;Node* newnode = new Node(x);//调用构造函数tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}private:Node* _head;size_t _size;};
}

3.初步实现迭代器

将迭代器封装为类来实现其功能

namespace jxy
{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>struct __list_iterator//一般前加__就说明这是内部的实现{typedef list_node<T> Node;typedef __list_iterator<T> self;Node* _node;__list_iterator(Node* node):_node(node){}self& operator++()//不是连续的物理空间，++不能到下一个位置{_node = _node->_next;return *this;}T& operator*(){return _node->_data;}bool operator!=(const self& s){return (_node != s._node);}};template<class T>class list//list的框架本质是封装+运算符重载{typedef list_node<T> Node;public:typedef __list_iterator<T> iterator;iterator begin(){//return iterator(_head->_next);return _head->_next;}iterator end(){//return iterator(_head);return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}void push_back(const T& x){Node* tail = _head->_prev;Node* newnode = new Node(x);//调用构造函数tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}private:Node* _head;size_t _size;};void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);// 封装，屏蔽了底层差异和实现细节// 提供了统一的访问、修改和遍历方式list<int>::iterator it = lt.begin();while (it != lt.end()){*it += 10;//还可以修改cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}
}

4.插入和删除

namespace jxy
{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>struct __list_iterator//一般前加__就说明这是内部的实现{typedef list_node<T> Node;typedef __list_iterator<T> self;Node* _node;__list_iterator(Node* node):_node(node){}self& operator++()//不是连续的物理空间，++不能到下一个位置{_node = _node->_next;return *this;}T& operator*(){return _node->_data;}bool operator!=(const self& s){return (_node != s._node);}};template<class T>class list//list的框架本质是封装+运算符重载{typedef list_node<T> Node;public:typedef __list_iterator<T> iterator;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_front(){erase(begin());}void pop_back(){erase(--end());}//void insert(iterator pos,const T& x)//{//	Node* cur = pos._node;//	Node* newnode = new Node(x);//	Node* prev = cur->_prev;//	//prev  newnode  cur//	prev->_next = newnode;//	newnode->_prev = prev;//	newnode->_next = cur;//	cur->_prev = newnode;//	//理论上可以认为list的迭代器不存在失效问题//}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;//prev  newnode  curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);//指向新插入的元素}//void erase(iterator pos)//{//	Node* cur = pos._node;//	Node* prev = cur->_prev;//	Node* next = cur->_next;//	delete cur;//	prev->_next = next;//	next->_prev = prev;//}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;--_size;//erase后的迭代器会失效，所有最好把返回值类型改为iteratorreturn iterator(next);}size_t size(){return _size;}private:Node* _head;size_t _size;};}

5.拷贝构造和赋值

namespace jxy
{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>struct __list_iterator//一般前加__就说明这是内部的实现{typedef list_node<T> Node;typedef __list_iterator<T> self;Node* _node;__list_iterator(Node* node):_node(node){}self& operator++()//不是连续的物理空间，++不能到下一个位置{_node = _node->_next;return *this;}T& operator*(){return _node->_data;}bool operator!=(const self& s){return (_node != s._node);}};template<class T>class list//list的框架本质是封装+运算符重载{typedef list_node<T> Node;public:typedef __list_iterator<T> iterator;iterator begin(){//return iterator(_head->_next);return _head->_next;}iterator end(){//return iterator(_head);return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}~list(){clear();delete(_head);_head = nullptr;}//拷贝构造//list(const list<T>& lt)//这里是const迭代器list(list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}传统写法//list<int>& operator=(const list<int>& lt)//{//	if (this != &lt)//	{//		clear();//		for (auto e : lt)//		{//			push_back(e);//		}//	}//	return *this;//}void swap(list<int>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<int>& operator=(list<int> lt)//调用拷贝构造{swap(lt);return *this;}private:Node* _head;size_t _size;};}

6.完善迭代器

namespace jxy
{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>struct __list_iterator//一般前加__就说明这是内部的实现{typedef list_node<T> Node;typedef __list_iterator<T> self;Node* _node;__list_iterator(Node* node):_node(node){}self& operator++()//不是连续的物理空间，++不能到下一个位置{_node = _node->_next;return *this;}self& operator--(){_node = _node->_prev;return *this;}//自定义类型尽量使用前置++，后置++要返回++之前的值self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}T& operator*(){return _node->_data;}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:private:Node* _head;size_t _size;};}

7.补充：迭代器的->运算符重载

namespace jxy
{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>struct __list_iterator//一般前加__就说明这是内部的实现{typedef list_node<T> Node;typedef __list_iterator<T> self;Node* _node;__list_iterator(Node* node):_node(node){}self& operator++()//不是连续的物理空间，++不能到下一个位置{_node = _node->_next;return *this;}T& operator*(){return _node->_data;}bool operator!=(const self& s){return (_node != s._node);}T* operator->(){return &_node->_data;}};template<class T>class list{typedef list_node<T> Node;public:private:Node* _head;size_t _size;};struct AA{AA(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}int _a1;int _a2;};void test_list3(){//存一个自定义类型list<AA> lt;lt.push_back(AA(1, 2));lt.push_back(AA(2, 3));lt.push_back(AA(3, 4));list<AA>::iterator it = lt.begin();while (it != lt.end()){//cout << *it << " ";//*it的类型是AA，不支持流插入//一、让AA类支持流插入//二、打印公有成员变量//cout << (*it)._a1 << " " << (*it)._a2 << endl;//三、让AA类支持->//自定义类型不支持运算符，需要重载cout << it->_a1 << " " << it->_a2 << endl;cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;++it;//当数据存储自定义类型时，重载->}//解引用有三种方式：*、[]、->int* p = new int;*p = 1;AA* ptr = new AA;ptr->_a1=1;}}

8.const迭代器

namespace jxy
{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){}};//const迭代器模拟的是指向的内容不能改变，而不是本身不能改变//const迭代器本身可以++template<class T>struct __list_const_iterator//const迭代器是一个单独的类{typedef list_node<T> Node;typedef __list_const_iterator<T> self;Node* _node;__list_const_iterator(Node* node):_node(node){}self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prev;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}const T& operator*() //通过解引用才能修改数据{return _node->_data;//返回的是const别名，不能修改}const T* operator->(){return &_node->_data;}bool operator!=(const self& s){return (_node != s._node);}bool operator==(const self& s){return (_node == s._node);}};template<class T>class list//list的框架本质是封装+运算符重载{typedef list_node<T> Node;public:typedef __list_iterator<T> iterator;typedef __list_const_iterator<T> const_iterator;//单独去支持一个类型：const_iteratorconst_iterator begin() const{//return const_iterator(_head->_next);return _head->_next;}const_iterator end() const{//return const_iterator(_head);return _head;}private:Node* _head;size_t _size;};//测试const迭代器void print_list(const list<int>& lt)
//容器通常不支持流插入，所以要写个print函数{list<int>::const_iterator it = lt.begin();while (it != lt.end()){//*it = 100;//不可修改cout << *it << " ";it++;}cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);print_list(lt);}
}

9.改善为模板

当前代码的实现太过冗余，iterator类和const_iterator类的代码实现高度重合

namespace jxy
{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){}};//T  T&  T*
//T  const T&  const T*
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){}self& operator++()//不是连续的物理空间，++不能到下一个位置{_node = _node->_next;return *this;}self& operator--(){_node = _node->_prev;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*()//从泛型的角度来说，这里返回值类型是什么是不知道的{return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const self& s){return (_node != s._node);}bool operator==(const self& s){return (_node == s._node);}//所以迭代器到底如何实现，是根据容器的底层结构来决定的
};template<class T>
class list//list的框架本质是封装+运算符重载
{typedef list_node<T> Node;public:typedef __list_iterator<T,T&,T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;const_iterator begin() const{//return const_iterator(_head->_next);return _head->_next;}const_iterator end() const{//return const_iterator(_head);return _head;}iterator begin(){//return iterator(_head->_next);return _head->_next;}iterator end(){//return iterator(_head);return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}~list(){clear();delete(_head);_head = nullptr;}//拷贝构造list(const list<T>& lt)//这里是const迭代器{empty_init();for (auto e : lt){push_back(e);}}void swap(list<int>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<int>& operator=(list<int> lt)//调用拷贝构造{swap(lt);return *this;}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_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;//prev  newnode  curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);//指向新插入的元素}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;--_size;//erase后的迭代器会失效，所有最好把返回值类型改为iteratorreturn iterator(next);}size_t size(){return _size;}private:Node* _head;size_t _size;
};//测试const迭代器void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){//*it = 100;//不可修改cout << *it << " ";it++;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);print_list(lt);}
}

10.关于typename

namespace jxy
{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>void print_list(const list<T>& lt)//之前的print只支持int类型{list<T>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list4(){list<string> lt1;lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");//这里会不会涉及深层次的深拷贝问题？//之前的vector容器就涉及到了深层次的浅拷贝问题//它的主要原因是因为扩容时使用了memcpy//list不存在扩容的事情，也就不涉及这个问题print_list(lt1);}
}

但事实上，这样修改以后是编译不通过的。

 

这就涉及到另一个知识点，在日常使用中，模板命名时，使用class和使用typename是等价的

template<class T>	
template<typename T>

但此时的场景下，就要使用typename了。

namespace jxy
{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<typename T>void print_list(const list<T>& lt)//之前的print只支持int类型{typename list<T>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list4(){list<string> lt1;lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");print_list(lt1);}
}

typename list<T>::const_iterator it = lt.begin();
当模板是未实例化的类模板时，如list<T>
编译器不能去它里面查找，它里面带有许多不可确定的东西
编译器在编译阶段、没有实例化时，只会对这里进行初步的检查
所以编译器无法判断list<T>::const_iterator是内嵌类型，还是静态成员变量
所以这里要加上typename，凡是这种类模板中取类型都要加
前面加一个typename就是告诉编译器，这里是一个类型
要等list<T>实例化了，再去类里面去取
模板里面取东西都要加typename，使得编译器初步检查时先通过
然后实例化后，再去类中取这个类型，就知道它具体是什么了

11.再次改善为模板

namespace jxy
{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<typename T>void print_list(const list<T>& lt){typename list<T>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list4(){list<string> lt1;lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");print_list(lt1);vector<string> v;v.push_back("111111111111");v.push_back("111111111111");v.push_back("111111111111");v.push_back("111111111111");v.push_back("111111111111");print_list(v);//此时是打印不了的}
}

print_list是专门打印list的，想要打印vector，难道再去写一个逻辑高度重复的print函数吗?

namespace jxy
{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<typename Container>void print_container(const Container& con)//针对容器的打印{typename Container::const_iterator it = con.begin();while (it != con.end()){cout << *it << " ";it++;}cout << endl;}//模板实现了泛型编程，本质就是本来应该由我们做的事情交给了编译器void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);print_container(lt);list<string> lt1;lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");lt1.push_back("1111111111111111111111");print_container(lt1);vector<string> v;v.push_back("111111111111");v.push_back("111111111111");v.push_back("111111111111");v.push_back("111111111111");v.push_back("111111111111");print_container(v);}
}

12.总结：对比vector和list

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率O(1)，适合sort数据	不支持随机访问，访问某个元素效率O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，CPU高速缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针(节点指针)进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随 机访问