建设银行国际互联网网站_设计网站公司多少钱_网络营销相关的岗位有哪些_seo模拟点击算法

1.list的大致框架结构

list是任意位置插入删除的容器，底层为带头双向循环链表

begin() 代表第一个结点，end()代表最后一个结点的下一个

List类基本框架以及无参构造：

template<class T>
class list
{typedef list_node<T> Node;
public:list(){_head = new Node;_head->_next =_head;_head->_prev =_head;}private:Node* _head;
}

2.节点类

节点类：

template<class T>
class list_node
{
public:T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T())//全缺省给匿名对象:_data(x),_next(nullptr),_prev(nullptr){}
};

3. 迭代器

list的迭代器底层不是简单的指针，所以我们不能像实现vector一样直接在类中定义迭代器和使用迭代器相关函数

重新写一个类的作用是将迭代器的++和- -等操作实现在此类中
因为list中的++实际上是node=node->next，list中的==符号判断的是node1->data和node2->data是否相同，如果迭代器和
list写在一个类中,实现此等操作会很麻烦

新写一个迭代器类来实现其功能：

template<class T>
struct __list_iterator
{typedef list_node<T> Node;typedef __list_iterator<T> iterator;//前加_代表内部的实现Node* _node;__list_iterator(Node* node):_node(node){}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& it)const//等于{return _node == it._node;}bool operator!=(const iterator& s)//不等于{return _node != s._node;}T& operator*()//解引用{return _node->_data;}T* operator->(){return &(operator*());}
}

4.list内各种功能的实现

1.push_back(正常实现)

	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;}

2.insert

	iterator insert(iterator pos,const T&x)//在pos位置前插入{Node* temp = pos._node;Node* prev = temp->_prev;Node* newnode = new node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = temp;temp->_prev = newnode;return iterator(newnode);//匿名对象}

3.begin()和end()

	iterator begin(){//iterator tmp(_head->_next);//return tmp;return iterator(_head->_next);//使用了匿名对象}iterator end(){//iterator tmp(_head);//return tmp;return iterator(_head);}

4.push_back和push_front(复用insert)

	void push_back(const T& x)//尾插{insert(end(), x);}

	void push_back(const T& x)//头插{insert(begin(), x);}

5.erase

	iterator erase(iterator pos)//删除pos位置{assert(pos != end());//头节点不可以删除node* cur = pos._node;node* prev = cur->_prev;node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}

6. pop_back与pop_front (复用erase)

	void pop_back()//尾删{erase(--end());}void pop_front()//头删{erase(begin());}

7.clear 清空数据

	void clear()//清空数据{//注意不要把head清掉iterator it = begin();while (it != end()){it = erase(it);//为了防止迭代器失效设置返回值//返回值为当前节点的下一个}}

8.swap

	void swap(list<T>& x){std::swap(_head, x._head);}

9.无参构造

	void emptyinit()//创建并初始化哨兵位的头节点,方便给构造和拷贝构造复用{_head = new Node;_head->_next = _head;_head->_prev = _head;}list()//无参构造{emptyinit();}

10.析构函数

	~list()//_head也要被删除掉{clear();delete _head;_head = nullptr;}

11.含参构造

	template<class InputIterator>//有参的构造list(InputIterator first, InputIterator last)//可以用vector的迭代器来构造,也可以用栈和队列的迭代器来构造,设计成一个模板{emptyinit();while (first != last){push_back(*first);first++;}}

12.拷贝构造

	list(const list<T>& lt)//完成深拷贝{emptyinit();//创建并初始化头节点list<T> tmp(lt.begin(), lt.end());//用lt的迭代器区间去构造一下swap(tmp);//swap(_head, tmp._head)}

5.const迭代器

T*指针的可读可写可由iterator迭代器模拟
const T*指针的只读不能由const iterator模拟，这样写导致迭代器本身不能修改

第一种方式：写一个新的类
我们需要单独实现一个新的类叫做const_iterator模拟const T*

template<class T>
struct __list_const_iterator
{typedef list_node<T> Node;typedef __list_const_iterator iterator;Node* _node;__list_const_iterator(Node* node):_node(node){}//......
}template<class T>
class list
{typedef list_node<T> Node;
public:typedef __list_iterator<T> iterator;typedef __list_const_iterator<T> const_iterator;//......
private:Node* _head;
}；

第二种方式：复用普通迭代器（不需要写两份类）

同一个类模板，实例化参数不同，就是完全不同的类型

改进后的迭代器 和 list类：

template<class T, class Ref, class Ptr>//T,T&,T*
struct __list_iterator//迭代器不需要析函数
{typedef list_node<T> node;typedef __list_iterator<T,T&,T*> iterator;Node* _node;__list_iterator(Node* node):_node(node){}typedef Ptr pointer;typedef Ref reference;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& it)const//等于{return _node == it._node;}bool operator!=(const iterator& s)const//不等于{return _node != s._node;}Ref operator*()//解引用{return _node->_data;}Ptr operator->(){return &(operator*());}
};template<class T>
class 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);}iterator begin(){return iterator(_head->_next);//使用了匿名对象}const_iterator end()const{return const_iterator(_head);}iterator end(){return iterator(_head);}//......
private:Node* _head;
};

6.完整代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;template<class T>
class list_node
{
public:T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T())//全缺省给匿名对象:_data(x),_next(nullptr),_prev(nullptr){}
};
template<class T, class Ref, class Ptr>//T,T&,T*
struct __list_iterator//迭代器不需要析函数
{typedef list_node<T> node;typedef __list_iterator<T,T&,T*> iterator;Node* _node;__list_iterator(Node* node):_node(node){}typedef Ptr pointer;typedef Ref reference;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& it)const//等于{return _node == it._node;}bool operator!=(const iterator& s)const//不等于{return _node != s._node;}Ref operator*()//解引用{return _node->_data;}Ptr operator->(){return &(operator*());}
};template<class T>
class 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);}iterator begin(){return iterator(_head->_next);//使用了匿名对象}const_iterator end()const{return const_iterator(_head);}iterator end(){return iterator(_head);}iterator insert(iterator pos,const T&x)//在pos位置前插入{Node* temp = pos._node;Node* prev = temp->_prev;Node* newnode = new node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = temp;temp->_prev = newnode;return iterator(newnode);//匿名对象}void push_back(const T& x)//尾插{insert(end(), x);}void push_back(const T& x)//头插{insert(begin(), x);}iterator erase(iterator pos)//删除pos位置{assert(pos != end());//头节点不可以删除node* cur = pos._node;node* prev = cur->_prev;node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}void pop_back()//尾删{erase(--end());}void pop_front()//头删{erase(begin());}void clear()//清空数据{//注意不要把head清掉iterator it = begin();while (it != end()){it = erase(it);//为了防止迭代器失效设置返回值//返回值为当前节点的下一个}}void swap(list<T>& x){std::swap(_head, x._head);}void emptyinit()//创建并初始化哨兵位的头节点,方便给构造和拷贝构造复用{_head = new Node;_head->_next = _head;_head->_prev = _head;}list()//无参构造{emptyinit();}~list()//_head也要被删除掉{clear();delete _head;_head = nullptr;}template<class InputIterator>//有参的构造list(InputIterator first, InputIterator last)//可以用vector的迭代器来构造,也可以用栈和队列的迭代器来构造,设计成一个模板{emptyinit();while (first != last){push_back(*first);first++;}}list(const list<T>& lt)//完成深拷贝{emptyinit();//创建并初始化头节点list<T> tmp(lt.begin(), lt.end());//用lt的迭代器区间去构造一下swap(tmp);//swap(_head, tmp._head)}
private:Node* _head;
};