【C++模拟实现】list的模拟实现

【C++模拟实现】list的模拟实现

---

作者：爱写代码的刚子

时间：2023.9.3

前言：本篇博客关于list的模拟实现和模拟实现中遇到的问题

list模拟实现的部分代码

namespace test
{
	template<class T>
	struct list_node//默认公有
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _val;

		list_node(const T& val = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_val(val)
		{}
	};

	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=nullptr)
		:_node(node)
		{}
		__list_iterator(const Self&l)
		:_node(l._node)
		{}
		
		Ref operator*()
		{
			return _node->_val;
		}
		Ptr operator->()
		{
			return &_node->_val;
		}

		Self& operator++()
		{
			_node=_node->_next;
      return *this;
		}

		Self& operator++(int)
		{
			Self tmp(_node);
        return tmp;
		}
		Self& operator--() 
    {
       _node=_node->_prev;
			return *this;
    }
    Self& operator--(int) 
    {
        Self tmp(*this);
        _node=_node->_prev;
			  return *this;
    }
		bool operator!=(const Self& it) const//引用时一定要注意是否要加上const，防止权限放大，这里需要加上！！！
		{
			return _node!=it._node;
		}

		bool operator==(const Self& it) const
		{
			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 _head->_next;
			return iterator(_head->_next);
		}

		iterator end()
		{
			//return _head;
			return iterator(_head);
		}

		list()
		{
			_head=new Node;
      _head->_prev=_head;
      _head->_next=_head;
		}

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

		void push_back(const T& x)
		{
			insert(end(),x);//注意这里是end(),不是end()-1;
		}

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

		iterator insert(iterator pos, const T& x)
		{
			Node*newnode = new Node(x);
			
			pos._node->_prev->_next=newnode;
			newnode->_prev=pos._node->_prev;
			
			newnode->_next=pos._node;
			pos._node->_prev=newnode;
			return newnode;
		}
		iterator erase(iterator pos)
		{
			Node*tmp=pos._node;
			Node*next=tmp->_next;
			tmp->_prev->_next=tmp->_next;
			tmp->_next->_prev=tmp->_prev;
			delete tmp;
			tmp = nullptr;
			return next;
		}
	private:
		Node* _head;
    };
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

list模拟实现中的要点

const_iterator的实现

我们选择使用模版参数，复用iterator的类，设置三个模版参数：template并且typedef __list_iterator const_iterator,具体看代码的实现

push_back

push_back函数中复用了insert函数，但是注意的是传入的参数是end(),并不和pop_back函数中一样传入–end();

operator运算符重载

由于迭代器的实现类使用了模版参数，所以有两种类：const_iterator和iterator，所以在使用引用作为传入参数时需注意引用要加const！！！防止使用const_iterator类时权限放大！！！

iterator begin()函数

在此函数中可以使用return _head->_next;编译器会自动使用构造函数构造iterator类

---

附：类的拷贝构造一定要使用引用，并考虑是否再加上const。