遂溪手机网站建设公司,网上房地产备案查询,wordpress淘宝客排名主题,江苏网站建设官网目录
1、list介绍
所要实现类及其成员函数接口总览
2、结点类的模拟实现
基本框架
构造函数
3、迭代器类的模拟实现
迭代器类存在的意义
3.1、正向迭代器
基本框架
默认成员函数
构造函数
运算符重载
--运算符重载
!运算符重载
运算符重载
*运算符重载
…目录
1、list介绍
所要实现类及其成员函数接口总览
2、结点类的模拟实现
基本框架
构造函数
3、迭代器类的模拟实现
迭代器类存在的意义
3.1、正向迭代器
基本框架
默认成员函数
构造函数
运算符重载
--运算符重载
!运算符重载
运算符重载
*运算符重载
-运算符重载
3.2、反向迭代器
4、list类的模拟实现
基本框架
4.1、默认成员函数
构造函数
拷贝构造函数
赋值运算符重载函数
析构函数
4.2、迭代器相关函数
begin和end
rbegin和rend
4.3、访问容器相关函数
front和back
4.4、增加的相关函数
insert
push_back尾插
push_front头插
4.5、删除的相关函数
erase
pop_back尾删
pop_front头删
4.6、其他函数
size
resize
clear
empty
empty_init空初始化
swap交换 1、list介绍 在STL的底层实现当中list其实就是一个带头双向循环链表 我们现在要模拟实现list要实现以下三个类 模拟实现结点类模拟实现迭代器的类模拟list主要功能的类第三个类的实现是基于前两个类。我们依次递进进行讲解。 所要实现类及其成员函数接口总览 namespace Fan
{//模拟实现list当中的结点类templateclass Tstruct _list_node{//成员函数_list_node(const T val T()); //构造函数//成员变量T _data; //数据域_list_nodeT* _next; //后驱指针_list_nodeT* _prev; //前驱指针}; //模拟实现list迭代器templateclass T,class Ref,class Ptrstruct _list_iterator{typedef _list_nodeT Node;typedef _list_iteratorT, Ref, Ptr self;_list_iterator(Node*node); //构造函数//各种运算符重载函数self operator();self operator--();self operator(int);self operator--(int);bool operator(const self s)const;bool operator!(const self s)const;Ref operator*();Ptr operator-();//成员变量Node* _node; //一个指向结点的指针};//模拟实现listtemplateclass Tclass list{public:typedef _list_nodeT Node;typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;//默认成员函数list();list(const listT lt);listT operator(const listT lt);~list();//迭代器相关函数iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;//访问容器相关函数T front();T back();const T front()const;const T back() const;//插入、删除函数void insert(iterator pos, const T x);iterator erase(iterator pos);void push_back(const T x);void pop_back();void push_front(const T x);void pop_front();//其它函数size_t size()const;void resize(size_t n, const T val T());void clear();bool empty()const;void swap(listT lt);private:Node* _head; //指向链表头结点的指针};
} 2、结点类的模拟实现
基本框架 因为list的本质为带头双向循环链表所以我们要确保其每个结点有以下成员 前驱指针后继指针data值存放数据//模拟实现list当中的结点类templateclass Tstruct _list_node{//成员变量T _data; //数据域_list_nodeT* _next; //后驱指针_list_nodeT* _prev; //前驱指针}; 构造函数 对于结点类的成员函数我们只需要实现一个构造函数即可。结点的释放则由list默认生成的析构函数来完成。 //构造函数
_list_node(const T valT()):_data(val),_next(nullptr),_prev(nullptr)
{} 3、迭代器类的模拟实现
迭代器类存在的意义 我们知道list是带头双向循环链表对于链表我们知道其内存空间并不是连续的是通过结点的指针顺次链接。而string和vector都是将数据存储在一块连续的内存空间我们可以通过指针进行自增、自减以及解引用等操作就可以对相应位置的数据进行一系列操作因此string和vector的迭代器都是原生指针。而对于list其各个结点在内存中的位置是随机的并不是连续的我们不能通过结点指针的自增、自减以及解引用等操作来修改对应结点数据。为了使得结点指针的各种行为和普通指针一样我们对结点指针进行封装对其各种运算符进行重载使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。 3.1、正向迭代器
基本框架 //模拟实现list迭代器
templateclass T,class Ref,class Ptr
struct _list_iterator
{typedef _list_nodeT Node;typedef _list_iteratorT, Ref, Ptr self;//成员变量Node* _node; //一个指向结点的指针
}; 注意我们这里迭代器类的模板参数里面包含了3个参数 templateclass T,class Ref,class Ptr 在后文list类的模拟实现中我对迭代器进行了两种typedef typedef _list_iteratorT, T, T* iterator;//普通迭代器
typedef _list_iteratorT, const T, const T* const_iterator;//const迭代器 根据这里的对应关系Ref对应的是引用类型Ptr对应的是*指针类型。当我们使用普通迭代器时编译器就会实例化出一个普通迭代器对象当我们使用const迭代器时编译器就会实例化出一个const迭代器对象。提高代码复用性。 默认成员函数 这里的默认成员函数我们只需要写构造函数。 析构函数—结点并不属于迭代器不需要迭代器释放拷贝构造—编译器默认生成的浅拷贝即可赋值重载—编译器默认生成的浅拷贝即可构造函数 我们这里通过结点的指针即可完成构造。 //构造函数
_list_iterator(Node* node):_node(node)
{} 运算符重载 运算符非为前置和后置 前置迭代器的返回值还是迭代器。对于结点指针的前置我们就应该先让结点指针指向后一个结点然后返回“自增”后的结点指针。 //前置
self operator()
{_node _node-_next; //直接让自己指向下一个结点即可实现return *this; //返回自增后的结点指针
} 后置为了和前置进行区分后置通常需要加上一个参数。此外后置是返回自增前的结点指针。 //后置
self operator(int) //加参数以便于区分前置
{self tmp(*this); //拷贝构造tmp_node _node-_next; //直接让自己指向下一个结点即可实现return tmp;
} --运算符重载 --运算符分为前置--和后置-- 前置--前置--是让结点指针指向上一个结点然后再返回“自减”后的结点指针即可。 //前置--
self operator--()
{_node _node-_prev; //让结点指针指向前一个结点return *this; //返回自减后的结点指针
} 后置--先记录当前结点指针的指向然后让结点指针指向前一个结点最后返回“自减”前的结点指针即可。 //后置--
self operator--(int) //加参数以便于区分前置--
{self tmp(*this); //拷贝构造tmp_node _node-_prev;return tmp;
} !运算符重载 这里的比较是两个迭代器的比较我们直接返回两个结点的位置是否不同即可。 //!运算符重载
bool operator!(const self it)
{return _node ! it._node; //返回两个结点指针的位置是否不同即可
} 运算符重载 我们直接返回两个结点指针是否相同即可。 //运算符重载
bool operator(const self it)
{return _node it._node; //返回两个结点指针是否相同
} *运算符重载 当我们使用解引用操作符时是想要得到该位置的数据内容。因此我们直接返回结点指针指向的_data即可。 //*运算符重载
Ref operator*() //结点出了作用域还在我们用引用返回
{return _node-_data; //返回结点指向的数据
} -运算符重载 假设出现此类情形我们链表中存储的不是内置类型而是自定义类型如下 struct AA
{AA(int a1 0, int a2 0):_a1(a1),_a2(a2){}int _a1;int _a2;
};
void test()
{Fan::listAA lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));lt.push_back(AA(4, 4));
} 对于内置类型和自定义类型成员的指针其访问方式是不同的 int* *it
AA* (*it). 或者 it- 这里我们应该重载一个-运算符。以便于访问自定义类型成员的指针的数据。 //-运算符重载
Ptr operator-()
{return (operator*()); //返回结点指针所指向的数据的地址//或者return _node-_data;
} 实现了-运算符重载后我们执行it-_a1编译器就将其转换成it.operator-()此时获得的是结点位置的地址即AA*这里应该还有一个箭头-才能获取数据也就是这样it.operator-()-_a1 编译器为了可读性将其进行优化处理如果不进行优化应该是it--a1,优化以后省略了一个箭头-。3.2、反向迭代器 反向迭代器是一种适配器模式(后面我们会讲到适配器)。相比于正向迭代器反向迭代器主要有以下三种变化。 反向迭代器里面的执行的操作是正向迭代器里面的--。反向迭代器里面的--执行的操作是正向迭代器里面的。反向迭代器里面的*解引用和-操作指向的是前一个数据。⭐反向迭代器是一种适配器模式。任何容器的迭代器封装适配一下都能够生成对应的反向迭代器。 ⭐反向迭代器里面的*解引用和-操作指向的是前一个数据。其目的主要是为了对称设计。在代码实现当中rbegin函数对应的是end函数rend函数对应的是begin函数。 代码如下 namespace Fan
{templateclass Iterator,class Ref,class Ptrstruct Reverse_iterator{Iterator _it;typedef Reverse_iteratorIterator, Ref, Ptr Self;//构造函数Reverse_iterator(Iterator it):_it(it){}//*运算符重载Ref operator*(){Iterator tmp _it;//返回上一个数据return *(--tmp);}//-运算符重载Ptr operator-(){//复用operator*,返回上一个数据return (operator*());}//运算符重载Self operator(){--_it;return *this;}Self operator(int){Iterator tmp _it;--_it;return tmp;}//--运算符重载Self operator--(){_it;return *this;}Self operator--(int){Iterator tmp _it;_it;return tmp;}//!运算符重载bool operator!(const Self s){return _it ! s._it;}//运算符重载bool operator(const Self s){return _it s._it;}};
} 4、list类的模拟实现
基本框架 在list类中的唯一一个成员变量即为先前的结点类构成的头结点指针 //模拟实现list
templateclass T
class list
{
public:typedef _list_nodeT Node;//正向迭代器typedef _list_iteratorT, T, T* iterator; //普通迭代器typedef _list_iteratorT, const T, const T* const_iterator; //const迭代器//反向迭代器typedef Reverse_iteratoriterator, T, T* reverse_iterator;typedef Reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;private:Node* _head; //指向链表头结点的指针
}; 4.1、默认成员函数
构造函数 无参构造list是一个带头双向循环链表在构造一个list对象时我们直接申请一个头结点并让其前驱指针和后继指针都指向自己即可。 //构造函数
list()
{_head new Node();//申请一个头结点_head-_next _head;//头结点的下一个结点指向自己构成循环_head-_prev _head;//头结点的上一个结点指向自己构成循环
} 传迭代器区间构造先进行初始化然后利用循环对迭代器区间的元素挨个尾插。 //传迭代器区间构造
template class InputIterator
list(InputIterator first, InputIterator last)
{empty_init();while (first ! last){push_back(*first);first;}
} 拷贝构造函数 假设我们要用lt1去拷贝构造lt2。 传统写法我们首先复用empty_init对头结点进行初始化接着遍历lt1的元素在遍历的过程中将lt1的元素尾插到lt2上即可。接着使用push_back自动开辟空间完成深拷贝。 //传统写法
list(const listT lt)
{//先初始化lt2empty_init();//遍历lt1把lt1的元素push_back到lt2里面for (auto e : lt){push_back(e); //自动开辟新空间完成深拷贝}
} 现代写法这里我们先初始化lt2然后把lt1引用传参传给lt传lt的迭代器区间构造tmp复用swap交换头结点指针即可完成深拷贝的现代写法。 //现代写法
list(const listT lt)
{//先进行初始化empty_init();listTtmp(lt.begin(), lt.end()); //用迭代器区间去构造tmpswap(tmp);
} 赋值运算符重载函数 对于赋值运算符的重载我们仍然提供两种写法 传统写法先调用clear函数将原容器清空然后再将lt当中的数据通过遍历的方式一个个尾插到清空后的容器当中即可。 //传统写法
listT operator(const listT lt)
{if (this ! lt) //避免自己给自己赋值{clear(); //清空容器for (const auto e : lt){push_back(e); //将容器lt当中的数据一个个尾插到链表后面}}return *this; //支持连续赋值
} 现代写法利用编译器机制故意不使用引用传参通过编译器自动调用list的拷贝构造函数构造出一个list对象lt然后调用swap函数将原容器与该list对象进行交换即可。 //现代写法
listT operator(listT lt) //编译器接收右值的时候自动调用其拷贝构造函数
{swap(lt); //交换这两个对象return *this; //支持连续赋值
} 析构函数 我们可以先复用clear函数把除了头结点的所有结点给删除掉最后delete头结点即可。 //析构函数
~list()
{clear();delete _head; //删去哨兵位头结点_head nullptr;
} 4.2、迭代器相关函数
begin和end begin的作用是返回第一个位置的结点的迭代器而第一个结点就是哨兵位头结点的下一个结点。因此我们直接返回_head的_next即可。end的作用是返回最后一个有效数据的下一个位置的迭代器对于list指的就是哨兵位头结点_head的位置。begin和end均分为普通对象调用和const对象调用因此我们要写两个版本。 普通对象调用//begin
iterator begin() //begin返回的就是第一个有效数据即头结点的下一个结点
{return iterator(_head-_next);//return _head-_next;
}//end
iterator end()
{return iterator(_head);//return _head;
} const对象调用//begin
const_iterator begin() const
{return const_iterator(_head-_next);//return _head-_next;
}
//end
const_iterator end() const
{return const_iterator(_head);//return _head; 也可以这样写
} rbegin和rend rbegin就是正向迭代器里的end()位置rend就是正向迭代器里的begin()位置。 rbegin和rend同样分为普通对象调用和const对象调用 普通对象调用 //rbegin()
reverse_iterator rbegin()
{return reverse_iterator(end());
}
//rend
reverse_iterator rend()
{return reverse_iterator(begin());
} const对象调用//const反向迭代器
const_reverse_iterator rbegin() const
{return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{return const_reverse_iterator(begin());
} 4.3、访问容器相关函数
front和back front和back函数分别用于获取第一个有效数据和最后一个有效数据因此在实现front和back函数时直接返回第一个有效数据和最后一个有效数据的引用即可。 普通对象调用//front
T front()
{return *begin(); //直接返回第一个有效数据的引用
}
T back()
{return *(--end()); //返回最后一个有效数据的引用
} const对象调用const T front() const
{return *begin(); //直接返回第一个有效数据的引用
}
const T back() const
{return *(--end()); //返回最后一个有效数据的引用
} 4.4、增加的相关函数
insert 实现insert首先创建一个新的结点存储插入的值接着取出插入位置pos处的结点指针保存在cur里面记录cur的上一个结点位置prev先衔接prev和newnode再链接newnode和cur即可最后返回新插入元素的迭代器位置。 list的insert不存在野指针失效的迭代器失效问题。//头插
void push_front(const T x)
{insert(begin(), x);
}
//insert插入pos位置之前
iterator insert(iterator pos, const T x)
{Node* newnode new Node(x);//创建新的结点Node* cur pos._node; //迭代器pos处的结点指针Node* prev cur-_prev;//prev newnode cur//链接prev和newnodeprev-_next newnode;newnode-_prev prev;//链接newnode和curnewnode-_next cur;cur-_prev newnode;//返回新插入元素的迭代器位置return iterator(newnode);
} push_back尾插 法一首先要创建一个新结点用来存储尾插的值接着找到尾结点。将尾结点和新结点前后链接并将头结点和新结点前后链接构成循环即可。 //尾插
void push_back(const T x)
{Node* tail _head-_prev; //找尾Node* newnode new Node(x); //创建一个新的结点//_head tail newnode//链接tail和newnodetail-_next newnode;newnode-_prev tail;//链接newnode和头结点_headnewnode-_next _head;_head-_prev newnode;
} 法二这里也可以直接复用insert函数当insert中的pos位置为哨兵位头结点的位置时实现的就是尾插。 //尾插
void push_back(const T x)
{//法二复用insertinsert(end(), x);
} push_front头插 直接复用insert函数当pos位置为begin()时获得的pos就是第一个有效结点数据即可满足头插。 //头插
void push_front(const T x)
{insert(begin(), x);
} 4.5、删除的相关函数
erase erase删除的是pos位置的结点。我们首先取出pos位置的结点指针cur记录cur上一个结点位置为prev再记录cur下一个结点位置为next链接prev和next最后delete释放掉cur的结点指针即可。返回删除元素后一个元素的迭代器位置。 //erase
iterator erase(iterator pos)
{assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;//prev cur next//链接prev和nextprev-_next next;next-_prev prev;//delete要删除的结点delete cur;//返回删除元素后一个元素的迭代器位置//return next;return iterator(next);
} pop_back尾删 直接复用erase即可当pos位置为--end()时pos就是最后一个结点的位置实现的就是尾删。 //尾删
void pop_back()
{erase(--end());
} pop_front头删 直接复用erase即可当pos位置为begin()时pos就是第一个有效数据实现的就是头删。 //头删
void pop_front()
{erase(begin());
} 4.6、其他函数
size size函数用于获取当前容器当中的有效数据个数因为list是链表所以我们只能通过遍历的方式逐个统计有效数据的个数。 //size
size_t size()const
{size_t sz 0; //统计有效数据个数const_iterator it begin(); //获取第一个有效数据的迭代器while (it ! end()) //通过遍历统计有效数据个数{sz;it;}return sz; //返回有效数据个数
} resize resize函数的规则 若当前容器的size小于所给n则尾插结点直到size等于n为止。若当前容器的size大于所给n则只保留前n个有效数据。当我们实现resize函数时我们不要直接调用size函数获取当前容器的有效数据个数因为当我们调用resize函数后就已经遍历了一次容器。如果结果是size大于n那么还需要遍历容器找到第n个有效结点并释放之后的结点。 这里实现resize的方法是设置一个变量len用于记录当前所遍历的数据个数然后开始遍历容器在遍历的过程中 当len大于或者是等于n时遍历结束此时说明该结点后的结点都应该被释放将之后的结点释放即可。遍历完容器此时说明容器当中的有效数据个数小于n则需要尾插结点直到容器当中的有效数据个数为n时停止尾插即可。void resize(size_t n, const T val T())
{iterator i begin(); //获取第一个有效数据的迭代器size_t len 0; //记录当前所遍历的数据个数while (len n i ! end()){len;i;}if (len n) //说明容器当中的有效数据个数大于或者是等于n{while (i ! end()) //只保留前n个有效数据{i erase(i); //接收下一个数据的迭代器}}else //说明容器当中的有效数据个数小于n{while (len n){push_back(val);len;}}
} clear clear函数用于清空容器我们通过遍历的方式逐个删除结点只保留头结点即可。 void clear()
{iterator it begin();while (it ! end()){it erase(it); //用it接收删除后的下一个结点的位置}
} empty empty函数用于判断容器是否为空我们直接判断该容器的begin函数和end函数所返回的迭代器是否是同一个位置的迭代器即可。(此时说明容器当中只有一个头结点) bool empty()const
{return begin() end(); //判断是否只有头结点
} empty_init空初始化 该函数的作用是哨兵位的头结点开出来再对其进行初始化。该函数是库里面的。 //空初始化 对头结点进行初始化
void empty_init()
{_head new Node();_head-_next _head;_head-_prev _head;
} swap交换 对于链表的swap我们直接交换头结点指针的指向即可完成。直接复用库函数的swap即可。 //swap交换函数
void swap(listT lt)
{std::swap(_head, lt._head);//交换头指针
}
