无锡网站制作的公司有哪些,罗山网站建设,户外网站模板,网站建没有前景本专栏内容为#xff1a;C学习专栏#xff0c;分为初阶和进阶两部分。 通过本专栏的深入学习#xff0c;你可以了解并掌握C。 #x1f493;博主csdn个人主页#xff1a;小小unicorn ⏩专栏分类#xff1a;C #x1f69a;代码仓库#xff1a;小小unicorn的代码仓库… 本专栏内容为C学习专栏分为初阶和进阶两部分。 通过本专栏的深入学习你可以了解并掌握C。 博主csdn个人主页小小unicorn ⏩专栏分类C 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 STL详解八 list的再认识初始化与定义节点迭代器实现构造解引用*基本框架搭建--后置与后置---const迭代器拓展拓展2 相关函数接口Inserterase:push_front与pop_fronrpush_back与pop_backsize:clear与析构拷贝构造赋值重载传统写法现代写法 对比vector与list list的再认识
在之前List的介绍与使用中我们知道list容器是一个带头双向循环链表那么我们在模拟实现中能不能先证明一下List是否是一个双向循环链表呢
我们参考一下stl中list的源码 我们看到在源码中list中有一个__list_node的节点我们将这个链表的节点定义打开发现定义两个指针nextprev.
再来看一下它的空初始化 通过观察源码中list的初始化确实是一个双向循环链表。
接下来。我们就来自己实现一下里面的接口函数。 注意在模拟实现中我们采取用与与源码中相同的命名风格。 为防止与库里面的list重复我们模拟实现将定义在自己的命名空间中。
初始化与定义节点
首先我们需要定义三个类并用摸版进行封装分别是listlist的节点以及迭代器
list节点
templateclass T
struct list_node
{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T xT()):_data(x),_next(nullptr),_prev(nullptr)
{}
};list:
templateclass T
class list
{typedef list_nodeT Node;
public://空初始化void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}//无参构造list(){empty_init();}void push_Back(const T x){Node* tail _head-_prev;Node* newnode new Node(x);tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;}
private:Node* _head;
};这里我们写的是无参构造以及实现了一个尾插接口 尾插双向链表实现已经再简单不过了 现在我们测试一下 现在还不能进行遍历因此我们自己要实现一个迭代器
迭代器实现
那么这个迭代器我们要作为怎么实现呢 我们可以先回顾一下在vector中我们实现迭代器就是实现原生指针。 在vector中给it解引用就可以访问到里面的数据但是链表不行因为链表中空间不是连续的。 那么应该怎么实现呢其实这个就和我们之前的日期类一样在日期类中我们用运算符重载与封装实现了对日期类的操作。而我们的迭代器也使这样实现的。
这里我们需要实现迭代器的*与操作 我们先看一下库里面的操作
构造
看一下库里面的操作 库里面用了一个节点的指针进行构造这是因为单参数的构造函数支持隐式类型转换。
所以我们的构造就可以这样写
__list_iterator(Node* node):_node(node)
{
}实现迭代器就是指针往后走的过程注意返回的是迭代器。我们可以将迭代器重命名一下
typedef __list_iteratorT self;实现代码
self operator()
{_node _node-_next;return *this;
}解引用*
返回节点里面的数据即可
T operator*()
{return _node-_data;
}两个迭代器进行比较实质两个指针比较。
//两个迭代器进行比较两个指针比较
bool operator!(const self s)
{return _node ! s._node;
}基本框架搭建
这样基本上迭代器的基本架子就完成了
typedef __list_iteratorT iterator;
iterator begin()
{return _head-_next;
}
iterator end()
{return _head;
}在list中定义一下迭代器。迭代器开始位置就是返回哨兵位头节点的下一个位置结束位置就是返回哨兵位的地址。
测试一下
void test_list1(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);listint::iterator it lt.begin();while (it ! lt.end()){//*it 20;cout *it ;it;}cout endl;
}测试结果 有了迭代器就有范围for
for (auto e : lt)
{cout e ;
}
cout endl;总结其实会发现就是在模拟指针但他的底层细节很大。所以迭代器体现了封装的强势之处。封装屏蔽底层差异和实现细节提供统一的访问修改遍历方式。这样我们就不用关注他的底层是什么.
举个例子 setint s;s.insert(1);s.insert(3);s.insert(2);s.insert(4);setint::iterator sit s.begin();while (sit ! s.end()){cout *sit ;sit;}cout endl;
}这里的set就是树我们也可以依然用这个迭代器进行遍历。
–
实现迭代器就是指针往前走的过程注意返回的是迭代器。
self operator--()
{_node _node-_prev;return *this;
}后置与后置–
//后置
self operator(int)
{self tmp(*this);_node _node-_next;return tmp;
}
//后置
self operator--(int)
{self tmp(*this);_node _node-_prev;return tmp;
}-
在讲-重载之前先看一下这个示例
struct AA
{AA(int a1 0, int a2 0):_a1(a1), _a2(a2){}int _a1;int _a2;
};
listAA lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));listAA::iterator it lt.begin();
while (it ! lt.end())
{cout *it endl;it;
}
cout endl;在这里就访问不了因为自定义类型不支持类型。
这里我们回顾一下之前的知识对与内置类型的指针我们可以采用*来进行解引用。对于自定义类型的指针我们要用-来进行解引用。
int* p new int;
*p 1;AA* ptr new AA;
ptr-_a1 1;实现-
T* operator-()
{return _node-_data;
}两个迭代器进行比较就是两个指针比较
bool operator(const self s)
{return _node s._node;
}const迭代器
在实现const迭代器之前首先要知道一点const迭代器是一个完全不一样的类所以不能将非const迭代器前加const就变成const迭代器。 因此我们可以list类中在定义一个const迭代器
typedef __list_const_iteratorT const_iterator;const_iterator begin() const
{return _head-_next;
}
const_iterator end() const
{return _head;
}在单独实现一个const迭代器的类
templateclass T
struct __list_const_iterator
{....
}const迭代器基本的功能与非const迭代器相似只有在解引用时不同
// *it 10
const T operator*()
{return _node-_data;
}// it-a1 10
const T* operator-()
{return _node-_data;
}测试一下
void print_list(const listint lt)
{listint::const_iterator it lt.begin();while (it ! lt.end()){//*it 10;cout *it ;it;}cout endl;for (auto e : lt){cout e ;}cout endl;
}void test_list4()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);print_list(lt);
}但是这样实现还是太冗余了因为非const和const只有返回值不同那么还有优化的空间吗 我们看一下库里面的实现: 库里面定义只定义了同一个类模版的迭代器只是这两个迭代器之间的摸版参数不同实例化的参数不同就是完全不一样的类型。也就是说把能靠模版实现的就写一份让编译器搞。
所以我们可以将我们的迭代器进行进一步优化
templateclass T
class list
{typedef list_nodeT Node;
public:typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT,const T,const T* const_iterator;....
}// T T T*
// T cosnt T const T*
templateclass T, class Ref, class Ptr
struct __list_iterator
{typedef list_nodeT Node;/*typedef __list_iteratorT self;*/typedef __list_iteratorT, Ref, Ptr self;Node* _node;...
}到这里我们的迭代器就全部实现完了。
拓展
在刚才的测试函数中有一个print_list函数但是这个测试函数里面的数据我们给定的是int,那我要是其他类型的呢这个函数又该如何修改呢 其实很简单我们加一个摸版参数即可
templatetypename T
void print_list(const listT lt)
{typename listT::const_iterator it lt.begin();while (it ! lt.end()){//*it 10;cout *it ;it;}cout endl;
}测试一下 注意这里我们没有用class这个摸版参数这是因为
list是一个未实例化的类模板编译器不能去他里面去找 编译器就无法确定list::const_iterator是内嵌类型还是静态成员变量 前面加一个typename就是告诉编译器这里是一个类型等list实例化后再去类里面去取
拓展2
如果要是将刚才的类在改造一下呢 比如 我要打印以下内容
vectorstring v;
v.push_back(222222222222222222222);
v.push_back(222222222222222222222);
v.push_back(222222222222222222222);
v.push_back(222222222222222222222);这个函数对于我们的printf_list就不适用了因为我们的print_list就只适用于链表。 这里我们就可以写一个容器container的打印函数
templatetypename Container
void print_Container(const Container con)
{typename Container::const_iterator it con.begin();while (it ! con.end()){cout *it ;it;}cout endl;
}测试结果 总结一下 摸版实现了泛型编程而泛型编程的本质就是本来我们干的活交给了编译器。
相关函数接口
有了迭代器的实现我们就可以实现一下链表的相关接口
Insert
Insert:在pos位置之前插入
iterator insert(iterator pos, const T x)
{Node* cur pos._node;Node* newnode new Node(x);Node* prev cur-_prev;// prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);
}Insert迭代器不会产生失效的问题因为没有扩容。
erase:
在指定位置删除
iterator erase(iterator pos)
{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;prev-_next next;next-_prev prev;--_size;return iterator(next);
}注意erase的迭代器会失效所以我们加个返回值。
实现了insert和erase后我们就可以服用来实现头插头删尾插尾删。
push_front与pop_fronr
具体实现
头插
//头插
void push_front(const T x)
{insert(begin(), x);
}头删
//头删
void pop_front()
{erase(begin());
}push_back与pop_back
具体实现
尾插
void push_back(const T x)
{insert(end(), x);
}尾删
//尾删
void pop_back()
{erase(--end());
}size:
为了方便计算大小我们还可以再实现一个函数
size_t size()
{return _size;
}clear与析构
clear清理空间我们可以采取迭代器访问的方式逐个将节点释放。
//清理空间
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}析构我们可以先清理空间在将头节点释放即可。
//析构
~list()
{clear();delete _head;_head nullptr;
}拷贝构造
我们可以采用范围for来进行拷贝构造
//拷贝构造
// lt2(lt1)
//list(const listT lt)
list(listT lt)
{empty_init();for (auto e : lt){push_back(e);}
}赋值重载
传统写法
listint operator(const listint lt)
{if (this ! lt){clear();for (auto e : lt){push_back(e);}}return *this;
}现代写法
void swap(listT lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}// lt3 lt1
listint operator(listint lt)
{swap(lt);return *this;
}对比vector与list
