CD46.【C++ Dev】list的模拟实现(1)
目录
1.STL库的list
2.模拟实现
节点结构体
list类
无参构造函数
尾插函数
迭代器★
begin()
operator++
前置++
后置++
operator--
前置--
后置--
operator!=
operator==
end()
operator*
const修饰的迭代器的设计
1.STL库的list
模拟实现list之前,先看看STL库里的list是怎么做的
STL v3.0版本代码一览:
先看链表的结构体和构造函数
结构体:
template <class T>
struct __list_node {typedef void* void_pointer;void_pointer next;//后指针void_pointer prev;//前指针T data;//数据域
};看到next和prev,显然是双向链表,复习双向链表的参见:
96.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删
97.【C语言】数据结构之双向链表的头插,头删,查找,中间插入,中间删除和销毁函数CC32.【C++ Cont】静态实现双向链表及STL库的list
构造函数:
list() { empty_initialize(); }//调用空链表的构造函数void empty_initialize() { node = get_node();//调用空间配置器node->next = node;node->prev = node;
}//......
protected:link_type node;2.模拟实现
定义节点结构体next和prev成员变量,不建议用void_pointer,因为void*需要强制类型转换,比较麻烦
节点结构体
仿照STL:
namespace mystl
{template<class T>struct __list_node{typedef __list_node<T>* link_type;link_type next;link_type prev;T data;};//......
}
list类
框架:
template<class T>
class list
{typedef __list_node<T> list_node;
public:
private:
};发现STL库中的成员变量只有一个
node为__list_node<T>的指针,显然是双向链表的哨兵位,如下图
照葫芦画瓢写:
template<class T>
class list
{typedef __list_node<T> list_node;typedef __list_node<T>* link_type;
public:
private:link_type node;
};无参构造函数
生成哨兵位,让next和prev都指向自己
list()
{node = new list_node;node->next = node;node->prev = node;
}测试代码:
#include "list.h"
int main()
{mystl::list<int> ls;return 0;
}下断点到return 0,看看无参构造函数是否能正常工作
可以正常工作
尾插函数
void push_back(const T& x)
{link_type tmp = new list_node;tmp->data = x;//先找尾link_type tail = node->prev;tail->next = tmp;tmp->prev = tail;tmp->next = node;node->prev = tmp;
}测试代码:
#include "list.h"
using namespace std;
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);return 0;
}运行结果:
当然上面的代码可以简写
link_type tmp = new list_node(x);new list_node(x)会自动调用list_node的构造函数,需要提前准备,将list_node构造函数写在struct list_node中即可
struct __list_node
{typedef __list_node<T>* link_type;__list_node(const T& x = T())//写成缺省参数的形式:next(nullptr), prev(nullptr), data(x){}link_type next;link_type prev;T data;
};迭代器★
迭代器的本质:自定义类型的封装
list迭代器不能像模拟vector一样是指针,因为list不是连续区间,因此迭代器需要重新定义,能让迭代器++能直接指向下一个节点
即封装自定义指针成对象,符合C++面向对象的思想
//it是迭代器,本质上都是调用类的成员函数
it.operator++();
it.operator++(0);
it.operator--();
it.operator--(0);
it.operator*();
it.operator!=(...);
it.operator==(...);
STL库的解决方法:写成结构体,存储节点的指针
struct __list_iterator
{link_type node;
};(省略了成员函数和typedef)
再自定义成iterator
typedef __list_iterator<T> iterator;可以发现迭代器定义成了实例化的类
注意:__list_iterator定义成类时不要定义到list里面,嵌套类(可参见文章)是有限制的!
template<class T>
struct __list_iterator//是类
{typedef __list_node<T>* link_type;link_type node;
};当然list类里面要定义迭代器,这样利用访问
begin()
写在list类中,可以直接构造iterator对象返回
iterator begin()
{//返回哨兵位的下一个节点//或者写成return node->next;使用隐式类型转换return iterator(node->next);//构造对象返回
}当然node->next是自定义类型,需要手动在__list_iterator类中添加构造函数,这个很容易忘
struct __list_iterator
{typedef __list_node<T>* link_type;__list_iterator(link_type x){node = x;}link_type node;
};或者写成初始化列表:
__list_iterator(link_type x):node(x)
{}测试代码:
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);//::可以访问typedef的或者访问内部类mystl::list<int>::iterator it=ls.begin();return 0;
} 运行结果:
operator++
operator++是__list_iterator类的方法,不能写在list类中,因为list类中没有迭代器成员变量
前置++
返回++后的iterator
typedef __list_iterator<T> iterator;
iterator& operator++()
{node= node->next;return *this;
}后置++
返回++前的iterator
iterator operator++(int)
{iterator tmp(*this);node= node->next;return tmp;
}operator--
因为是双向链表,所以可以向前和向后移动迭代器
前置--
返回--后的iterator
iterator& operator--()
{node = node->prev;return *this;
}后置--
返回--前的iterator
iterator& operator--(int)
{iterator tmp(*this);node = node->prev;return tmp;
}operator!=
注意两个const修饰
const iterator& x防止权限放大,而且begin()和end()返回的是临时对象具有常性
operator!=末尾的const是防止修改node
bool operator!=(const iterator& x) const
{return node != x.node;
}operator==
bool operator==(const iterator& x) const
{return node == x.node;
}end()
写在list类中,由于是双向链表,因此返回哨兵位即可
iterator end()
{//返回哨兵位return node;//隐式类型转换,完整写法:iterator(node)
}测试代码:用迭代器遍历
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);mystl::list<int>::iterator it=ls.begin();while (it != ls.end()){ std::cout << it.node->data << " ";++it;}return 0;
}运行结果:
operator*
虽然这里定义的迭代器是实例化的对象,但是迭代器任务是模拟指针行为,因此要有operator*
T& operator*()
{return node->data;
}测试代码
#include <iostream>
#include "list.h"
int main()
{mystl::list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);mystl::list<int>::iterator it = ls.begin();std::cout << *it;return 0;
}注:mystl::list<int>::iterator it = ls.begin();会自动调用默认的拷贝构造,由于__list_iterator的成员变量是自定义类型的指针,浅拷贝没有问题,而且__list_iterator 不用写析构函数,节点应该是list类释放,迭代器只是借助节点访问
运行结果:
const修饰的迭代器的设计
能这样写吗?
typedef const __list_iterator<T> const_iterator;不可以, const修饰的是 __list_iterator<T>这个类,类的成员函数不能被修改
一个简明的例子说明:
class myclass
{
public:int* node;int data;
};int main()
{const myclass obj;obj.node++;
}obj.node++是不被允许的,被const修饰的对象的成员变量是不能被修改的
要明确: 无论是否有const修饰,双向迭代器是要能用operator++和operator--进行修改来访问的,但const修饰的迭代器指向的内容是不能被修改的,非const修饰的迭代器指向的内容能被修改
(有关const修饰的基础问题参见38.【C语言】指针（重难点）（C)文章)
那const修饰的迭代器应该模拟类似const T* ptr的情况
在迭代器的成员函数中,只有operator*需要修改,其余都不变
下文将介绍两种处理方法