网站建设自查及整改报告,网站编程图,阿里云做网站用哪个镜像,手机网站图片切换目录 一、认识list底层结构 二、list的构造类函数 三、迭代器 四、数据的访问 五、容量相关的函数 六、关于数据的增删查改操作 七、list和vector的比较
前言 要模拟实现list#xff0c;必须要熟悉list的底层结构以及其接口的含义#xff0c;在上一篇我们仔细讲解了list的…目录 一、认识list底层结构 二、list的构造类函数 三、迭代器 四、数据的访问 五、容量相关的函数 六、关于数据的增删查改操作 七、list和vector的比较
前言 要模拟实现list必须要熟悉list的底层结构以及其接口的含义在上一篇我们仔细讲解了list的常见接口的使用及其含义这篇我们就直接进入主题 一、list底层结构
list底层实现的是带头双向循环链表list底层实现需要三个类分别是链表的结点类链表的迭代器类链表本身
// List的节点类
templateclass T
struct ListNode
{ListNodeT* _prev;ListNodeT* _next;T _data;ListNode(const T dataT()):_prev(nullptr),_next(nullptr),_data(data){}
};//List的迭代器类
templateclass T,class Ref,class Ptr
struct ListIterator
{typedef ListNodeT Node;typedef ListIteratorT,Ref,Ptr Self;Node* _node;ListIterator(Node* node):_node(node){}Ref operator*();Ptr operator-();Self operator();Self operator(int);Self operator--();Self operator--(int);bool operator!(const Self l);bool operator(const Self l);
};//list类
templateclass T
class list
{typedef ListNodeT Node;Node* _head;//哨兵位的头节点size_t _size;//链表数据个数
public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T const_iterator;
}给大家讲一下这三个类的关联链表类是主类链表的结点用一个类封装起来构造起来更方便放在主类里面不方便且冗余由于链表的物理结构不连续所以不能像vector和string那样单纯的用原生指针来实现我们可以把结点类再次进行封装封装成迭代器让它能很好的指向链表的结点利用它的结构优势来重载运算符遍历这个链表 二、初始化list的构造函数
1、默认构造 list();
void empty_init()
{_head new Node;_head-_next _head;_head-_prev _head;_size 0;
}list()
{empty_init();//这里没有直接写默认构造而是通过empty_init来实现因为后面我们要多次用到这个函数来初始化哨兵位的头节点写在默认构造里面就不方便其他地方的调用了
}2、用n个val来构造链表 list(size_t n, const T val T());
list(size_t n, const T val T())
{empty_init();//要记得初始化哨兵位的头节点for (size_t i 0; i n; i){push_back(val);}_size n;
}3、迭代器区间构造 template class InputIterator list(InputIteratorfirst, InputIterator last);
list(InputIterator first, InputIterator last)
{empty_init();while (first ! last){push_back(*first);first;}
}特别注意 如果你写了迭代器区间构造就一定要重载上面的list(size_t n, const T val T())如果你不重载的话他会报一个错误 非法间接寻址博主我深受其害再重载一个这个函数list(int n, const T val T());就可以 其实就是改一个类型的事
为什么要重载一下
listint li(10,1);
你传的参数都是int类型两个类型是一样的而迭代器区间构造的类型是一样的最符合这就导致你没走你
想走的那个构造函数你想走的那个函数list(size_t n, const T val T())在这个案例中是size_t和int类型虽然
也可以走这个函数但是编译器觉得迭代器区间构造更好所以你得重载一个intint类型的这样编译器就会
走你重载的函数了4、拷贝构造 用来初始化一个正在创建的对象 list(const listT li);
list(const listT li)
{empty_init();for (auto e : li){push_back(e);}_size li._size;
}5、赋值构造 两个已经存在的对象一个赋值给另一个 listT operator(const listT li)
void swap(listT li)
{std::swap(_head, li._head);std::swap(_size, li._size);
}
//这里的赋值构造我用的是现代写法
listT operator(listT li)//这里的参数使用传值传参会调用拷贝构造
{swap(li);//直接让*this和临时对象li交换出了作用域li也就销毁了return *this;
}6、析构函数 ~list();
//clear只需要清除掉里面的数据就行也就是析构掉除哨兵位以外的结点
void clear()
{iterator it begin();while (it ! end()){it erase(it);}_size 0;
}
~list()
{clear();delete _head;_head nullptr;
}三、迭代器
讲到list迭代器这里我们先把迭代器类完善一下
//这里弄了三个模板参数好实例化生成iterator和const_iterator,因为他们两个基本上没什么区别只用区分好解引用后的返回值类型就好
templateclass T,class Ref,class Ptr//Ref表示引用,Ptr表示指针
struct ListIterator
{typedef ListNodeT Node;typedef ListIteratorT,Ref,Ptr Self;Node* _node;ListIterator(Node* node):_node(node){}//*itRef operator*(){return _node-_data;}//it-Ptr operator-(){return _node-_data;}//iSelf operator(){_node _node-_next;return *this;//返回的变量出了作用域不会被销毁用引用返回更合适}//iSelf operator(int){Self temp(*this);_node _node-_next;return temp;//返回的变量出了作用域会被销毁用传值返回更合适}Self operator--(){_node _node-_prev;return *this;}Self operator--(int){Self temp(*this);_node _node-_prev;return temp;}bool operator!(const Self s){return _node ! s._node;//这里是用迭代器的地址去比较}bool operator(const Self s){return _node s._node;}
};三个模板参数的主要意图
这个类里面的接口我们重点讲解一下这个Ptr operator-();如下图
iterator begin(); iterator end(); const_iterator begin(); const_iterator end(); begin表示链表的第一个结点第一个结点应该是哨兵位的下一个结点哨兵位是不存放任何东西的单纯作为头结点end表示最后一个结点的下一个位置list是一个带头双向循环链表所以最后一个结点的下一个位置就是_head迭代器遍历的区间[begin,end) 左闭右开区间这样就能遍历到所有结点
templateclass T
class list
{typedef ListNodeT Node;Node* _head;//哨兵位的头节点size_t _size;//链表数据个数
public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T const_iterator;iterator begin(){//return iterator(_head-_next);匿名对象return _head-_next;//单参数的构造函数隐式类型转换}iterator end(){return _head;}const_iterator begin(){return _head-_next;}const_iterator end(){return _head;}
}四、数据的访问
1、front 访问头结点 T front();
T front()
{return _head-_next-_data;
}const T front()const;
const T front() const
{return _head-_next-_data;
}2、back 访问尾节点 T back();
T back()
{return _head-_prev-_data;
}const T back()const;
const T back() const
{return _head-_prev-_data;
}五、容量相关的函数
size 有效数据个数 size_t size()const;
size_t size() const
{return _size;
}empty 判断是否为空 bool empty()const;
bool empty()
{return _size 0;
}六、关于数据的增删查改操作
push_back 尾插数据 void push_back(const T val) ;
void push_back(const T val)
{Node* newnode new Node(val);//为插入的数据new一个结点出来Node* tail _head-_prev;//先保存链表尾部的结点//处理好tail和newnode的指向tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;//将newnode更新成为新的尾节点_size;
}pop_back 尾删数据 void pop_back() ;
void pop_back()
{Node* tail _head-_prev;Node* prev tail-_prev;delete tail;prev-_next _head;_head-_prev prev;_size--;
}push_front 头插数据 void push_front(const T val);
void push_front(const T val)
{Node* newnode new Node(val);Node* next _head-_next;//_head newnode nextnewnode-_next next;next-_prev newnode;newnode-_prev _head;_head-_next newnode;_size;
}pop_front 头删数据 pop_front();
void pop_front()
{Node* del _head-_next;Node* next del-_next;delete del;_head-_next next;next-_prev _head;_size--;
}insert 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T val);
void insert(iterator pos, const T val)
{Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);//prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;}erase 删除pos位置的节点返回该节点的下一个位置 iterator erase(iterator pos);
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 next;//这样写会发生隐式类型转换转换成iterator类型//写成这样也可以iterator(next);匿名对象
}clear 清除结点 void clear();
void clear()
{iterator it begin();while (it ! end()){it erase(it);//这里需要注意一下erase掉当前的结点后会导致迭代器失效erase会返回下一个结点的迭代器删除之后接收一下就行}_size 0;
}swap 交换两个链表 void swap(listT l);
void swap(listT li)
{//利用库里面的swap交换两个链表的头结点和size就可以了std::swap(_head, li._head);std::swap(_size, li._size);
}七、list和vector的区别 list篇到这里就结束了欢迎大家来指教我的下一篇stack和queue
