html论坛网站模板下载,青岛李沧建设局网站,如何做网站静态页面,做wordpress挣钱目录 本次所需实现的三个类一、结点类的模拟实现构造函数 二、迭代器类的模拟实现为什么有迭代器类迭代器类的模板参数说明构造函数运算符的重载- -运算符的重载和!运算符的重载*运算符的重载-运算符的重载引入模板第二个和第三个参数 三、list的模拟实现3.1 默认成员函数构… 目录 本次所需实现的三个类一、结点类的模拟实现构造函数 二、迭代器类的模拟实现为什么有迭代器类迭代器类的模板参数说明构造函数运算符的重载- -运算符的重载和!运算符的重载*运算符的重载-运算符的重载引入模板第二个和第三个参数 三、list的模拟实现3.1 默认成员函数构造函数拷贝构造函数赋值运算符重载函数析构函数 3.2 迭代器相关函数begin和end 3.3 访问容器相关函数front和back 3.4 插入、删除函数insert和erasepush_back和pop_backpush_front和pop_front 3.5 其他函数sizeclearemptyswap 总结 本次所需实现的三个类
一、结点类的模拟实现 list类是由结点类和迭代器类组成 我们经常说list在底层实现时就是一个链表更准确来说list实际上是一个带头双向循环链表。
因此我们若要实现list则首先需要实现一个结点类。而一个结点需要存储的信息有数据、前一个结点的地址、后一个结点的地址于是该结点类的成员变量也就出来了数据、前驱指针、后继指针。
而对于该结点类的成员函数来说我们只需实现一个构造函数即可。因为该结点类只需要根据数据来构造一个结点即可而结点的释放则由list的析构函数来完成。
构造函数
templateclass T //由于该list可能是任何类型则使用模板类
struct list_node //存放结点成员变量
{list_nodeT* _prev;list_nodeT* _next;T _val;list_node(const T val T()) //缺省值初始化T不一定是内置类型所以不能直接给0:_prev(nullptr), _next(nullptr), _val(val){}
};注意 若构造结点时没有传入数据则默认以list容器所存储类型的默认构造函数所构造出来的值为传入数据。
二、迭代器类的模拟实现
引入 list迭代器是一个自定义类型内部成员是结点指针内置类型我们本身想要的就是结点指针结点指针就可以做迭代器它不能像原生指针如vector、string一样地址是连续的而list地址不是因为底层结构的差异所以用一个类封装结点指针然后重载运算符后就可以像内置类型一样访问。 为什么有迭代器类
在学习string和vector时都没有说专门要实现一个迭代器类为什么实现list的时候就需要实现一个迭代器类呢
因为string和vector对象都将其数据存储在了一块连续的内存空间我们通过指针进行自增、自减以及解引用等操作就可以对相应位置的数据进行一系列操作因此string和vector当中的迭代器就是原生指针。 但是对于list来说其各节点在内存中位置可能不都是连续的大多情况下都是随机的我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作需找到下一个结点才能访问。 迭代器的意义是让使用者可以不必关心容器的底层实现可以用简单统一的方式对容器内的数据进行访问。
既然list的结点指针的行为不满足迭代器定义那么我们可以对这个结点指针进行封装对结点指针的各种运算符操作进行重载使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。比如使用list当中的迭代器进行自增操作时实际上执行了node node-next语句。 list迭代器类实际上就是对结点指针进行了封装对其各种运算符进行了重载使得结点指针的各种行为在使用者角度看起来和普通指针一样。 迭代器类的模板参数说明
list迭代器类的模板参数列表当中有三个模板参数
templateclass T, class Ref, class Ptr在list的模拟实现当中我们typedef重命名了两个迭代器类型普通迭代器和const迭代器。
typedef _list_iteratorT, T, T* iterator;
typedef _list_iteratorT, const T, const T* const_iterator;迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。
构造函数
迭代器类实际上就是对结点指针进行了封装其成员变量就只有一个那就是结点指针其构造函数直接根据所给结点指针构造一个迭代器对象。
Node* _node;__list_iterator(Node* node):_node(node)
{}运算符的重载
当然也分为前置和后置
self operator() //返回类型还是迭代器
{_node _node-_next; //下一个位置return *this;
}self operator(int)
{selfT 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;
}和!运算符的重载
当使用运算符比较两个迭代器时实际上想知道的是这两个迭代器是否是同一个位置的迭代器判断这两个迭代器当中的结点指针的指向是否相同即可。!运算符则相反。
//通过结点的指针比较两数据比较时end返回的数据具有常性要加const
bool operator!(const self it)
{return _node ! it._node;
}
bool operator(const self it)
{return _node it._node;
}*运算符的重载
使用解引用操作符时是想得到该位置的数据内容。因此直接返回当前结点指针所指结点的数据即可但是这里需要使用引用返回因为解引用后可能需要对数据进行修改。
Ref operator*() //出了作用域还在可以引用返回
{return _node-_val; //结点指针的数据
}-运算符的重载
有些情景下我们使用迭代器的时候可能会用到-运算符。
void test2()
{struct A{A(int a0,int b0):_a(a),_b(b){}int _a;int _b;};ling::listA lt;lt.push_back(A(1,1));lt.push_back(A(2,2));lt.push_back(A(3,3));lt.push_back(A(4,4));ling::listA::iterator it lt.begin();while (it ! lt.end()){//cout *it ; //遍历对象是自定义类型要重载流插入才可以打印//都能实现遍历//cout (*it)._a (*it)._b endl; cout it-_a it-_b endl;it;}cout endl;
}对于-运算符的重载我们直接返回结点当中所存储数据的地址即可
Ptr operator-()
{return _node-_val;
}引入模板第二个和第三个参数
如上例子
三、list的模拟实现
3.1 默认成员函数
list是一个带头双向循环链表在构造一个list对象时申请一个头结点并让其前驱指针和后继指针都指向自己 由于有时容易忘记写上显示实例化模板参数才构成类型
typedef list_nodeT node; //重命名一下构造函数
list() //初始化构成双链表
{_head new Node; //给头节点申请空间head-_prev head; //前后指针指向自己head-_next head;
}拷贝构造函数
拷贝构造函数就是根据所给list容器拷贝构造出一个对象。对于拷贝构造函数先申请一个头结点并让其前驱指针和后继指针都指向自己然后将所给容器当中的数据通过遍历的方式一个个尾插到新构造的容器后面。
//拷贝构造函数
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; //支持连续赋值
}析构函数
对象进行析构时首先调用clear函数清理容器当中的数据然后将头结点释放最后将头指针置空
//析构函数
~list()
{clear(); //清理容器delete _head; //释放头结点_head nullptr; //头指针置空
}3.2 迭代器相关函数
begin和end
begin函数返回的是第一个有效数据的迭代器end函数返回的是最后一个有效数据的下一个位置的迭代器。
list带头双向循环链表第一个有效数据的迭代器就是使用头结点的下一个结点的地址构造出来的迭代器最后一个有效数据的下一个位置的迭代器就是使用头结点的地址构造出来的迭代器。最后一个结点的下一个结点就是头结点
//单参数的构造函数支持隐式类型转换,两种写法都可以都是生成匿名对象
iterator begin()
{return _head-_next;//return iterator(_head-_next);
}
iterator end()
{return _head;//return iterator(_head);
}3.3 访问容器相关函数
front和back
分别用于获取第一个有效数据和最后一个有效数据因此实现front和back函数时直接返回第一个有效数据和最后一个有效数据的引用即可。
T front()
{return *begin(); //返回第一个有效数据的引用
}
T back()
{return *(--end()); //返回最后一个有效数据的引用
}//不可修改
const T front() const
{return *begin(); //返回第一个有效数据的const引用
}
const T back() const
{return *(--end()); //返回最后一个有效数据的const引用
}3.4 插入、删除函数
insert和erase
当然还是任意位置插入和删除由于会迭代器失效所以有返回值
//插入
iterator insert(iterator pos, const T x)
{Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;
}//删除
iterator erase(iterator 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 next;
}有了这对增删函数就可以复用在其它增删的函数身上了
push_back和pop_back
分别对应尾插、尾删
//尾插
void push_back(const T x)
{Node* tail _head-prev; //找到尾Node* newnode new Node(x); //调用结点的构造函数//更新尾结点tail-_next newnode;newnode-_prev tail;_head-_prev newnode;newnode-_next _head;//可直接复用insertinsert(end(),x);
}//尾删
void pop_back()
{erase(--end());
}push_front和pop_front
//头插
void push_front(const T x)
{insert(begin(), x);
}//头删
void pop_front()
{erase(begin());
}3.5 其他函数
size
获取当前容器当中的有效数据个数因为list是链表所以只能通过遍历的方式逐个统计有效数据的个数。
size_t size()
{size_t sz 0;iterator it begin();while (it ! end()){sz;it;}return sz;
}clear
用于清空容器通过遍历的方式逐个删除结点只保留头结点
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}empty
用于判断容器是否为空直接判断该容器的begin函数和end函数所返回的迭代器是否是同一个位置的迭代器即可。此时说明容器当中只有一个头结点
bool empty() const
{return begin() end(); //判断是否只有头结点
}swap
用于交换两个容器list容器当中存储的实际上就只有链表的头指针将这两个容器当中的头指针交换即可。
void swap(listT lt)
{std::swap(_head, lt._head); //交换两个容器当中的头指针即可
}总结
由于list类不一定只接收一个类型如内置类型int、double自定义类型所以三个类都使用了模板。 类名模板参数才构成类型容易忘记往往typedef重命名一下它们也更方便使用。
