网站营销如何做,济南做网站得多少钱,跨境网站,企业展厅设计风格目录 节点
迭代器
整体框架
构造函数
empty_init
拷贝构造
赋值重载
析构函数
clear
insert
erase
push_back和push_front
pop_back和push_front
size
empty
Print_Container 节点
对于链表节点#xff0c;我们需要一个数据、一个前驱指针、一个后继指针来维护…目录 节点
迭代器
整体框架
构造函数
empty_init
拷贝构造
赋值重载
析构函数
clear
insert
erase
push_back和push_front
pop_back和push_front
size
empty
Print_Container 节点
对于链表节点我们需要一个数据、一个前驱指针、一个后继指针来维护并且将其封装成一个类。
templateclass T
struct list_node
{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T data T()):_data(data),_next(nullptr),_prev(nullptr){}
};
使用struct的原因是因为struct默认的域作用限定符是public方便后续使用不用走友元的那一套。
迭代器
我们知道迭代器提供访问容器的方法之前实现vector和string时迭代器用的就是数据类型的指针但是list不可以直接用。因为vector和string的数据在内存的存放都是连续的如果想找下一个数据的指针迭代器直接迭代器指针就可以了但是list的数据存放在内存不是连续的如果直接把指针当成迭代器迭代器是找不到下一个数据的迭代器。
所以综上所述我们应该用类对链表数据类型的指针封装成迭代器在类里重载操作符让其达到我们想要的效果。
当然我们实现的迭代器应该有两个版本普通版本和const版本。
//普通迭代器
templateclass T
struct list_iterator
{typedef list_nodeT Node;typedef list_iteratorT Self;Node* _node;list_iterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}//前置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 it) const{return _node ! it._node;}bool operator(const Self it) const{return _node it._node;}
};
//const迭代器
templateclass T
struct list_const_iterator
{typedef list_nodeT Node;typedef list_const_iteratorT Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T operator*(){return _node-_data;}const T* operator-(){return _node-_data;}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;}bool operator!(const Self it) const{return _node ! it._node;}bool operator(const Self it) const{return _node it._node;}
};
我们发现这两份代码除了重载*和-有所不同其余代码都是一样的所以我们可以增加两个模板参数将这两份代码合二为一。
templateclass T, class Ref, class Ptr
struct list_iterator
{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}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 it) const{return _node ! it._node;}bool operator(const Self it) const{return _node it._node;}
}; 增加Ref和Ptr模板参数让T*和T作为参数传入这就可以解决将两份代码合二为一。
整体框架
templateclass T
class list
{typedef list_nodeT Node;
public:/*typedef list_iteratorT iterator;typedef list_const_iteratorT const_iterator;*///将T和T*作为参数传入typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;iterator begin(){/*iterator it(_head-_next);return it;*///return iterator(_head-_next);//返回哨兵节点的下一个节点第一个有效节点//隐式类型转换return _head-_next;}iterator end(){//最后一个有效节点的下一位置也就是哨兵节点return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}//实现各种函数......private:Node* _head;size_t _size;
};
构造函数
empty_init
多种构造函数的代码都有重合所以把重合部分独立成一个函数。
void empty_init()
{//创造哨兵节点_head new Node();_head-_next _head;_head-_prev _head;_size 0;
}
普通构造
普通构造就是创造哨兵节点调用empty_init即可。
//普通构造
list()
{empty_init();
}
列表构造
C11的用法用法例子如下
listint lt1 { 1,2,3,4,5,6 }; 先创造一个哨兵节点然后将列表的元素尾插即可。
//列表构造
list(initializer_listT il)
{empty_init();for (auto e : il){push_back(e);}
}
关于列表initializer_listT的知识可以看以下连接。 介绍列表 拷贝构造
创建哨兵节点将链表元素尾插到待构造的链表就完成拷贝构造了。
//拷贝构造
list(const listT lt)
{empty_init();for (auto e : lt){push_back(e);}
}
赋值重载
与临时对象lt交换即可跟string、vector的实现类似。
void swap(listT lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}listT operator(listT lt)
{swap(lt);return *this;
}
析构函数
clear
清理除了哨兵节点以外的所有节点。
void clear()
{auto it begin();while (it ! end()){it erase(it);}
}
先将链表clear掉然后清理哨兵节点。
~list()
{clear();delete _head;_head nullptr;
}
insert
在pos迭代器位置前插入元素x插入后_size返回新插入元素的迭代器。
iterator insert(iterator pos, const T x)
{Node* cur pos._node; //pos是iterator类的对象访问里面的成员变量用pos._node不能用pos-_nodeNode* prev cur-_prev;Node* newnode new Node(x);newnode-_next cur;cur-_prev newnode;newnode-_prev prev;prev-_next newnode;_size;//隐式类型转换return newnode;
}
erase
删除pos位置的元素删除后_size--返回删除元素的下一元素的迭代器。
iterator erase(iterator pos)
{assert(pos ! end()); //不能删掉哨兵位的节点Node* prev pos._node-_prev;Node* next pos._node-_next;prev-_next next;next-_prev prev;delete pos._node; --_size;return next;
}
push_back和push_front
利用insert函数就可以实现尾插和头插。
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;_size;*/ insert(end(), x);
}void push_front(const T x)
{insert(begin(), x);
}
pop_back和push_front
利用erase函数实现尾删和头删。
void pop_back()
{erase(--end());
}void pop_front()
{erase(begin());
}
size
返回链表有效元素的个数.。
size_t size() const
{return _size;
}
empty
判断链表是否为空。
bool empty() const
{return _size 0;
}
Print_Container
打印容器的函数。
templateclass Container
void Print_Container(const Container con)
{//const对象要用const迭代器这里没实现的话会报错/*auto it con.begin();while (it ! con.end()){cout *it ;it;}*/for (auto e : con){cout e ;}cout endl;
} 拜拜下期再见
摸鱼ing✨
