C++list的模拟实现
基本结构
首先明确一个问题，list是带头双向循环链表，既然是链表，那么我们就需要定义一个节点的结构体，然后既然是list的模拟实现，就需要定义一个list的类，根据带头双向循环链表的特点，还需要一个头节点，所以list的成员变量中必有一个头节点
下面是基本结构
namespace bit
{
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _Date;
ListNode(const T x=T())
{
_next=nullptr;
_prev=nullptr;
_Date=x;
}
};
template<class T>
calss list
{
public:
list()
{
_head=new Node;
_head->_next=_head;
_head->_prev=_head;
}
private:
typedef ListNode<T> Node;
Node* _head;
};
}上面有一个问题，上面的那个定义节点要用struct,而不用class,原因就是上面的节点里面的任何元素随时都需要访问， 而struct里面的是默认共有的，当然在这里你也可以用calss,只是需要把所有的元素置成公有的
push_back()
向节点的尾部添加一个节点，基本的思路就是找到尾节点，申请新的节点，然后将新的节点连接就行了
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;
}迭代器
今天的这个迭代器会有一点特别，以前在string,vector里面的模拟实现里面，定义一个迭代器都是都是直接typedef一个int*,或者一个char*,让后直接对迭代器进行++或者--，但是，今天的这个是链表，结构在物理上都不是连续的，如何进行++或者--操作，这是不行的，唯一的方法就是对定义一个迭代器的类，然后对++或者--进行操作符的重载
template<class T>
class ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T> self;
Node* _node;
public:
ListIterator(Node* node)
:_node(node)
{}
self&operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self temp(_node);
_node = _node->_next;
return temp;
}
self&operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self temp(_node);
_node = _node->_prev;
return temp;
}
bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
T& operator*()
{
return _node->_Date;
}
T* operator->()
{
return &(_node->_Date);
}
};这样就可以对链表进行遍历了，当然了，这里的的begin()和end()函数还没有实现，可以在下面完整代码的list里面去查看
上面代码还有一个问题，你迭代器里面去重载一个—>有什么用
主要是为下面的情况做准备的
上面又又同学问了，啊，->这个操作符得出不是pos的地址吗，你这个怎么好直接就能去的出pos里面的成员变量的，其实上面的写法和被注释掉的代码是一样的，这里编译器是为了增强代码的可读性和美观性才这样省略出这样的，
const迭代器
const迭代器和非const迭代器其实是相差不大的，有人可能认为，在iterator前面加上一个const让他变成const iterator不就成为const迭代器了吗，那你就大错特错了
const迭代器是什么？是迭代器里面指向的内容不能被修改，直接加const不久变成迭代器不能被修改了，这里其实代码和非const迭代器是差不多的，唯一有一个地方需要改的就是限制解引用的返回值，让他变成const
template<class T>
class ListConstIterator
{
typedef ListNode<T> Node;
typedef ListConstIterator<T> self;
Node* _node;
public:
ListConstIterator(Node* node)
:_node(node)
{}
self&operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self temp(_node);
_node = _node->_next;
return temp;
}
bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s) //记得参数里面加const，如果不加，会出现权限的放大问题
{
return _node != s._node;
}
const T& operator*() //加const
{
return _node->_Date;
}
const T* operator->() //加const
{
return &(_node->_Date);
}
};
两个迭代器合一块
两个迭代器写一块，那不是太麻烦了一点，能不能写一个模板？答案是可以的
只需要在模板参数里面添加两个参数
然后下面函数的返回值稍微改动一下
最后关键的一步来了
在list定义迭代器里面的时候给不同的模板参数就行了
析构函数
~list()
{
list<T>::iterator it = begin();
while (it != end())
{
it = erase(it);
}
delete _head;
_head = nullptr;
}拷贝构造和赋值重载
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list<T>& operator=(const list<T> l1)
{
empty_init(); //这里记着要初始化
swap(_head, l1._head);
return *this;
}上面的赋值运算符重载设计得很巧妙，首先明确的一个问题是要使用传值传参，后面直接交换两个_head的指向，因为传值传参会引发拷贝构造函数，后面把_head的指向给l1的拷贝构造了之后函数结束直接析构，这里就有点像让你干活，最后把你给杀了
list(const list<T>& l1)
{
empty_init();
for (const auto &e : l1)
{
push_back(e);
}
}这里记得拷贝构造函数需要使用深拷贝，如果你不写拷贝构造函数得话，编译器生成的默认构造函数默认的是浅拷贝，函数调用结束了之后会发生同一块空间析构两次的问题，导致程序崩溃
写代码时的一个易错点
这里写代码的时候老是出现下面的问题：函数匹配问题，这一般都是由于权限的放大缩小问题
还有就是写范围for的时候尽量写引用，因为范围for实际上时赋值给e,赋值的话会拷贝产生一个临时对象，如果auto是自定义类型的话，拷贝量太大了，效率比较低
常规函数
void erase(iterator pos) //迭代器失效，因为被释放了
{
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
pos._node = nullptr;
}
void insert(iterator&pos, T x) //迭代器没有失效
{
Node* newnode = new Node(x);
Node* prev = pos._node->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = pos._node;
pos._node->_prev = newnode;
}
void pop_back()
{
Node* cur = _head->_prev;
Node* prev = cur->_prev;
prev->_next = _head;
_head->_prev = prev;
delete cur;
}完整代码
#include<iostream>
using namespace std;
namespace bit
{
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _Date;
ListNode(const T date = T())
:_Date(date)
,_prev(nullptr)
,_next(nullptr)
{
}
};
template<class T,class ref,class ptr>
class ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T,ref,ptr> self;
public:
Node* _node;
public:
ListIterator(Node* node)
:_node(node)
{
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self temp(_node);
_node = _node->_next;
return temp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
ref&operator*()
{
return _node->_Date;
}
ptr operator->()
{
return &(_node->_Date);
}
};
/*template<class T>
class ListConstIterator
{
typedef ListNode<T> Node;
typedef ListConstIterator<T> self;
Node* _node;
public:
ListConstIterator(Node* node)
:_node(node)
{}
self&operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self temp(_node);
_node = _node->_next;
return temp;
}
bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s)
{
return _node != s._node;
}
const T& operator*()
{
return _node->_Date;
}
T* operator->()
{
return &(_node->_Date);
}
};*/
template<class T>
class list
{
public:
typedef ListIterator<T, T&,T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
//typedef ListConstIterator<T> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
iterator end()
{
return iterator(_head);
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list<T>& operator=(const list<T> l1)
{
empty_init();
swap(_head, l1._head);
return *this;
}
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;
}
iterator erase(iterator pos)
{
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
pos._node = nullptr;
return iterator(next);
}
list(const list<T>& l1)
{
empty_init();
for (const auto &e : l1)
{
push_back(e);
}
}
~list()
{
list<T>::iterator it = begin();
while (it != end())
{
it = erase(it);
}
delete _head;
_head = nullptr;
}
bool empty()
{
return _head->_next == _head;
}
void insert(iterator&pos, T x)
{
Node* newnode = new Node(x);
Node* prev = pos._node->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = pos._node;
pos._node->_prev = newnode;
}
void pop_back()
{
Node* cur = _head->_prev;
Node* prev = cur->_prev;
prev->_next = _head;
_head->_prev = prev;
delete cur;
}
private:
typedef ListNode<T> Node;
Node* _head;
};
void test01()
{
list<int> l1;
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);
l1.push_back(50);
l1.push_back(60);
list<int>::iterator it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
void func(const list<int>&s)
{
list<int>::const_iterator it = s.begin();
while (it != s.end())
{
//(*it)++;
cout << *it << " ";
it++;
}
}
void test02()
{
list<int> l1;
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);
func(l1);
}
struct pos
{
int _x;
int _y;
pos(int x=0,int y=0)
:_x(x)
,_y(y)
{}
};
void test03()
{
list<pos> p;
p.push_back(pos(1,2));
p.push_back(pos(3,4));
p.push_back(pos(5,6));
list<pos>::iterator it = p.begin();
//cout << it.operator->()->_x << " " << it.operator->()->_y << endl;
cout << it->_x << " " << it->_y << endl;
}
void test04()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
for (auto &e : l1)
{
cout << e << " ";
}
cout << endl;
list<int> l2 = l1;
for (auto& e : l2)
{
cout << e << " ";
}
cout << endl;
}
void test05()
{
list<int> l1;
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);
}
}