牛股大转盘网站建设,做旅游景点网站的目的和意义,东莞网页设计培训班,谷歌账号注册网站打不开文章目录 list模拟实现的大致框架节点类的模拟实现迭代器类的模拟实现迭代器类存在的意义迭代器类的模板参数说明运算符的重载--运算符的重载#xff01;与运算符的重载*运算符的重载-运算符的重载 list的模拟实现默认成员函数迭代器相关函数元素修改相关函数front和backi… 文章目录 list模拟实现的大致框架节点类的模拟实现迭代器类的模拟实现迭代器类存在的意义迭代器类的模板参数说明运算符的重载--运算符的重载与运算符的重载*运算符的重载-运算符的重载 list的模拟实现默认成员函数迭代器相关函数元素修改相关函数front和backinserterasepush_back和pop_backpush_front和pop_front 其他函数sizeresizeclearswap list模拟实现的大致框架
#includeiostreamusing namespace std;namespace lhj
{templateclass T//单个节点//内部框架struct list_node{};//迭代器: 像指针一样的对象templateclass T,class Ref,class Ptr//使迭代器类型泛型化RefPtr是普通类型那么迭代器就是普通类型//RefPtr是const类型迭代器就是const类型struct __list_iterator{};templateclass Tclass list{public:typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT,const T,const T*const_iterator;//......private:typedef list_nodeT Node;//将单个节点的类型 重命名为Node 便于书写Node* _head;};
}节点类的模拟实现
templateclass T
//单个节点
//内部框架
struct list_node
{T _data;//指向节点的指针类型为节点的类型list_node* _next;list_node* _prev;list_node(const T xT())//构造函数初始化:_data(x),_next(nullptr),_prev(nullptr){}
};注意 若构造结点时未传入数据则默认以list容器所存储类型的默认构造函数所构造出来的值为传入数据。
迭代器类的模拟实现
迭代器类存在的意义 总结 list迭代器类实际上就是对结点指针进行了封装对其各种运算符进行了重载使得结点指针的各种行为看起来和普通指针一样。例如对结点指针自增就能指向下一个结点
迭代器类的模板参数说明
在list的模拟实现当中typedef了两个迭代器类型普通迭代器和const迭代器。
typedef _list_iteratorT, T, T* iterator;
typedef _list_iteratorT, const T, const T* const_iterator;迭代器类中
templateclass T,class Ref,class Ptr
//使迭代器类型泛型化RefPtr是普通类型那么迭代器就是普通类型
//RefPtr是const类型迭代器就是const类型若该迭代器类不设计三个模板参数那么就不能很好的区分普通迭代器和const迭代器。
迭代器类的模拟实现
templateclass T,class Ref,class Ptr
//使迭代器类型泛型化RefPtr是普通类型那么迭代器就是普通类型
//RefPtr是const类型迭代器就是const类型
struct __list_iterator
{typedef list_nodeT Node;typedef __list_iteratorT,Ref,Ptr iterator;Node* _node;//迭代器的本质就是指针故需要定义一个节点的指针//构造函数用一个节点的指针来初始化迭代器__list_iterator(Node* node):_node(node){}//迭代器不需要提供析构函数//_node为指针属于内置类型//同时不需要写拷贝构造函数//默认的浅拷贝就是迭代器所需要的
};运算符的重载
前置原本的作用是将数据自增然后返回自增后的数据。
先记录当前结点指针的指向然后让结点指针指向后一个结点最后返回“自增”前的结点指针
//前置
iterator operator(int)
{iterator tmp(*this);//记录当前结点指针的指向_node _node-_next; //让结点指针指向后一个结点return tmp;//返回自增前的结点指针
}后置则应该让结点指针指向后一个结点然后再返回“自增”后的结点指针
iterator operator()
{_node _node-_next;//让结点指针指向后一个结点return *this;//返回自增后的结点指针
}注意iterator是当前迭代器类实例化出来的一个对象类型
–运算符的重载
iterator operator--()
{_node _node-_prev;return *this;
}
//--it
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 it)const
{//迭代器之间的比较return _node it._node;
}*运算符的重载
对指针变量进行解引用是为了得到该变量的数据内容。故直接返回当前结点指针所指结点的数据但是这里需要使用引用返回因为解引用后可能需要对数据进行修改。
Ref operator*()
{return _node-_data;//返回结点指针所指结点的数据
}-运算符的重载
对于-运算符的重载直接返回结点当中所存储数据的地址即可。
Ptr operator-()
{return (operator*());//返回结点指针所指结点的数据的地址// (operator*()) - (_pnode-_val)
}list的模拟实现
默认成员函数
构造函数
构造一个某类型的空容器。
listint lt1; //构造int类型的空容器使用迭代器拷贝构造某一段内容。
string s(hello world);
listchar lt4(s.begin(),s.end()); //构造string对象某段区间的复制品构造函数的模拟实现
void empty_init()
{//初始化//头结点的_next,_prev都是指向自己_head new Node;_head-_next _head;_haed-_prev _head;list()
{//构造函数先新建一个节点作为头结点empty_init();//复用
}
//迭代器区间初始化
template class InputIterator
list(InputIterator first, InputIterator last)
{empty_init();//先要将头结点初始化while (first!last){push_back(*first);first;}
}拷贝构造函数
拷贝构造某类型容器的复制品。
listint lt3(lt2); //拷贝构造int类型的lt2容器的复制品拷贝构造函数的模拟实现
拷贝构造一个对象即需要先构造出一个头结点然后再用被拷贝对象的迭代器区间初始化一个中间对象然后再与拷贝对象交换
也可以在初始化出一个头结点后将所给容器当中的数据通过遍历的方式一个个尾插到新构造的容器后面
//方法一
list(const list lt)
{empty_init();//初始化函数listT tmp(lt.begin(), lt.end());swap(tmp);
}//方法二
list(const listT lt)
{_head new node; //申请一个头结点_head-_next _head; //头结点的后继指针指向自己_head-_prev _head; //头结点的前驱指针指向自己for (const auto e : lt){push_back(e); //将容器lt当中的数据一个个尾插到新构造的容器后面}
}赋值运算符重载函数
//传统写法
listT operator(const listT lt)
{if (this ! lt) //避免自己给自己赋值{clear(); //清空容器for (const auto e : lt){push_back(e); //将容器lt当中的数据一个个尾插到链表后面}}return *this; //支持连续赋值
}//现代写法
listT operator(listT lt) //编译器接收右值的时候自动调用其拷贝构造函数
{swap(lt); //交换这两个对象return *this; //支持连续赋值
}析构函数
~list()
{clear();delete _head;_head nullptr;
}迭代器相关函数
begin和end
list的底层为带头双向循环链表begin()为头结点的下一个结点的地址构造出来的迭代器end()为最后一个节点的下一个位置的迭代器最后一个结点的下一个结点就是头结点
iterator begin()
{//返回头结点的下一个结点的地址构造出来的迭代器return iterator(_head-_next);
}
iterator end()
{//返回使用头结点的地址构造出来的普通迭代器return iterator(_head);
}
const_iterator begin() const
{//返回头结点的下一个结点的地址构造出来的const迭代器return const_iterator(_head-_next);
}
const_iterator end() const
{//返回使用头结点的地址构造出来的const迭代器return const_iterator(_head);
}元素修改相关函数
front和back
front和back函数分别用于获取第一个有效数据和最后一个有效数据.
T front()
{return *begin(); //返回第一个有效数据的引用
}
T back()
{return *(--end()); //返回最后一个有效数据的引用
}
const T front() const
{return *begin(); //返回第一个有效数据的const引用
}
T back()
{return *(--end()); //返回最后一个有效数据的引用
}
const T back() const
{return *(--end()); //返回最后一个有效数据的const引用
}insert
list中的插入节点与数据结构中的插入节点一样。
iterator insert(iterator pos, const T x)
{assert(pos._pnode); //检测pos的合法性Node* cur pos._node;//迭代器pos处的结点指针Node* prev cur-_prev;//迭代器pos前一个位置的结点指针Node* newnode new Node(x)//根据所给数据x构造一个待插入结点//建立newnode与prev之间的双向关系 prev-_next newnode;newnode-_prev prev;//建立newnode与cur之间的双向关系 newnode-_next cur;cur-_prev newnode;return iterator(newnode);
}erase
iterator erase(iterator pos)
{assert(pos ! end());//检测pos的合法性assert(pos ! end()); //删除的结点不能是头结点 Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;//建立prev与next之间的双向关系prev-_next next;next-_prev prev;delete cur;//释放cur结点return iterator(next);//返回所给迭代器pos的下一个迭代器
}push_back和pop_back
push_back和pop_back函数分别用于list的尾插和尾删在已经实现了insert和erase函数的情况下我们可以通过复用函数来实现push_back和pop_back函数。
//尾插
void push_back(const T x)
{insert(end(), x); //在头结点前插入结点
}
//尾删
void pop_back()
{erase(--end()); //删除头结点的前一个结点
}push_front和pop_front
头插和头删的push_front和pop_front函数也可以复用insert和erase函数来实现。
//头插
void push_front(const T x)
{insert(begin(), x); //在第一个有效结点前插入结点
}
//头删
void pop_front()
{erase(begin()); //删除第一个有效结点
}其他函数
size
size函数用于获取当前容器当中的有效数据个数因为list是链表所以只能通过遍历的方式逐个统计有效数据的个数。
size_t size() const
{size_t sz 0; //统计有效数据个数const_iterator it begin(); //获取第一个有效数据的迭代器while (it ! end()) //通过遍历统计有效数据个数{sz;it;}return sz; //返回有效数据个数
}扩展 其实也可以给list多设置一个成员变量size用于记录当前容器内的有效数据个数。
resize
实现resize的方法设置一个变量len用于记录当前所遍历的数据个数然后开始遍历容器
在遍历过程中
当len大于或是等于n时遍历结束此时说明该结点后的结点都应该被释放将之后的结点释放即可。 当容器遍历完毕说明容器当中的有效数据个数小于n则需要尾插结点直到容器当中的有效数据个数为n时停止尾插即可。
void resize(size_t n, const T val T())
{iterator i begin(); //获取第一个有效数据的迭代器size_t len 0; //记录当前所遍历的数据个数while (len ni ! end()){len;i;}if (len n) //说明容器当中的有效数据个数大于或是等于n{while (i ! end()) //只保留前n个有效数据{i erase(i); //每次删除后接收下一个数据的迭代器}}else //说明容器当中的有效数据个数小于n{while (len n) //尾插数据为val的结点直到容器当中的有效数据个数为n{push_back(val);len;}}
}clear
void clear()
{//clear是清除头结点以外的所有节点//析构函数才是清除包括头结点的所有节点iterator it begin();while (it!end()){it erase(it);//erase会返回下一个位置的迭代器//故不需要it}
}swap
void swap(listT lt)
{::swap(_head, lt._head); //交换两个容器当中的头指针即可
}注意 在此处调用库当中的swap函数需要在swap之前加上“::”作用域限定符告诉编译器这里优先在全局范围寻找swap函数否则编译器会认为你调用的就是你正在实现的swap函数就近原则。
