C++:模拟实现STL的list

目录

一.list类

1.list的创建节点

2.list迭代器的运算符操作

3.list的构造函数及析构

4.list的迭代器

5.list的插入及删除

二.整体代码

1.list.h

2.list.cpp

---

在上一节已经了解list在库中的用法,在这里实现list的底层逻辑

一.list类

1.list的创建节点

template<class T>
struct __list_node
{__list_node* _next;__list_node* _prev;T _data;__list_node(const T& x = T()) :_data(x), _next(nullptr), _prev(nullptr) {}
};

2.list迭代器的运算符操作

template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef __list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> Self;Node* _node;__list_iterator(Node* node):_node(node) {}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);//_node = _node->_next;++(*this);return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);//_node = _node->_prev;--(*this);return tmp;}bool operator!=(const Self& it) {return _node != it._node;}bool operator==(const Self& it) {return _node == it._node;}
};

3.list的构造函数及析构

1.list的构造函数

因为list是双向带头循环链表,所以我们只需要让头节点的prev和next都指向头节点

//双向带头循环链表
list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}

2.list的拷贝构造

拷贝构造时我们需要创建一个新的节点,将值依次插入尾部即可,可以通过迭代器遍历,也可以通过范围for

list(const list<T>& lt)
{_head = new Node;_head->_next = _head;_head->_prev = _head;/*const_iterator it = lt.begin();while (it != lt.end()){push_back(*it);++it;}*/for (auto ch : lt)push_back(ch);
}

3.list的赋值

赋值是不需要创建新节点的,因为已经有了,所以只需要插入值即可

list<T>& operator=(const list<T>& lt)
{if (this != &lt){clear();for (auto ch : lt)push_back(ch);}return *this;
}

4.list的析构

析构在这里我们用到clear函数,clear是清空所以数据,只留头节点,但是析构头节点也要释放

~list()
{clear();delete _head;_head = nullptr;
}void clear()
{iterator it = begin();while (it != end()){erase(it++);}
}

4.list的迭代器

iterator begin() 
{return iterator(_head->_next);
}iterator end() 
{return iterator(_head);
}const_iterator begin() const
{return const_iterator(_head->_next);
}const_iterator end() const
{return const_iterator(_head);
}

5.list的插入及删除

push_back

尾部插入一个值时只需要将节点前后连接,并更新头节点的prev

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;
}

insert

任意插入一个值,我们需要创建一个节点,并将其与前后节点连接

void insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;
}

当我们实现了insert后,对于push_back和push_front都可以通过调用insert实现

	void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}

erase

对于erase来说,我们只需要找到删除节点的prev和next,将他们两个连接,删除当前节点即可

void erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;
}

实现erase后,pop_back和pop_front调用erase即可

void pop_back()
{erase(--end());
}void pop_front()
{erase(begin());
}

二.整体代码

1.list.h

#pragma once
#include <iostream>
#include<assert.h>
using namespace std;namespace wzyl
{template<class T>struct __list_node{__list_node* _next;__list_node* _prev;T _data;__list_node(const T& x = T()) :_data(x), _next(nullptr), _prev(nullptr) {}};template<class T, class Ref, class Ptr>struct __list_iterator{typedef __list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> Self;Node* _node;__list_iterator(Node* node):_node(node) {}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);//_node = _node->_next;++(*this);return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);//_node = _node->_prev;--(*this);return tmp;}bool operator!=(const Self& it) {return _node != it._node;}bool operator==(const Self& it) {return _node == it._node;}};template<class T>class list{typedef __list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin() {return iterator(_head->_next);}iterator end() {return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}//双向带头循环链表list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(const list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;/*const_iterator it = lt.begin();while (it != lt.end()){push_back(*it);++it;}*/for (auto ch : lt)push_back(ch);}list<T>& operator=(const list<T>& lt){if (this != &lt){clear();for (auto ch : lt)push_back(ch);}return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){erase(it++);}}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;*/insert(end(), x);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}void erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;}private:Node* _head;};void test_list1(){list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);ls.push_back(4);list<int>::iterator it = ls.begin();while (it != ls.end()){cout << *it << " ";++it;}cout << endl;}struct Date{int _year = 0;int _month = 1;int _day = 1;};void test_list2(){list<Date> ls;ls.push_back(Date());ls.push_back(Date());list<Date>::iterator it = ls.begin();while (it != ls.end()){cout << it->_year << "-" << it->_month << "-" << it->_day << endl;++it;}cout << endl;}void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;}void test_list3(){list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);ls.push_back(4);ls.insert(ls.begin(), 0);ls.push_front(-1);print_list(ls);ls.pop_front();ls.pop_back();print_list(ls);ls.clear();ls.push_back(1);print_list(ls);}void test_list4(){list<int> lst1;lst1.push_back(1);lst1.push_back(2);lst1.push_back(3);lst1.push_back(4);list<int> lst2(lst1);print_list(lst2);list<int> lst3;lst3.push_back(10);lst3.push_back(20);lst3.push_back(30);lst3.push_back(40);lst1 = lst3;print_list(lst1);}
}

2.list.cpp

#include"list.h"int main()
{wzyl::test_list1();//wzyl::test_list2();//wzyl::test_list3();//wzyl::test_list4();return 0;
}