• list容器模拟实现【c++】

    文章目录：

    🌏list介绍

    在这里插入图片描述

    1、list是一个序列式容器，可以允许在常数时间内对容器中的任意位置进行插入和删除的操作，且list是一个双向链表，该容器可以前后双向迭代。
    2、list与forward_list非常相似：最主要的区别是forward_list是单向链表，只能向前迭代，让其更简单更高效。
    3、list与其它标准序列容器(array、vector和deque)相比，list在任意位置进行插入和删除元素执行更高效。
    4、与其它序列式容器相比，list和forward_list最大的缺陷是不支持随机访问容器中任意位置的元素。

    🌏list结构

    在这里插入图片描述

    🌏list模拟实现

    list基本框架

    #pragma once
#include
#include
using namespace std;

namespace hy
{
	//定义list的节点类
	template
	struct __list_node
	{
		T _data;
		__list_node* _prev;
		__list_node* _next;

		__list_node(const T& data = T())
			:_data(data)
			,_prev(nullptr)
			,_next(nullptr)
		{}
	};

	template
	class list
	{
	public:
		typedef __list_node node;

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
	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

    list的构造函数

    1️⃣ 空初始化list
    2️⃣ n个val值初始化list
    3️⃣ 用一段迭代器区间初始化链表

    empty_list_init()
{
	_head = new node(T()); //无法确定传入的参数类型，所以传匿名函数构造
	_head->_next = _head;
	_head->_prev = _head;
}

list()
{
	empty_list_init();
}

list(size_t n, const T& val = T())
{
	empty_list_init();

	for (size_t i = 0;i < n;++i)
		push_back(val);
}

template
list(InputIterator first, InputIterator last)
{
	empty_list_init();

	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

    • 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

    list的正向迭代器和反向迭代器

    🌑迭代器的实现有两种方式，具体应该根据容器底层的数据结构实现：

    • 原生态指针，如：vector
    • 将原生态指针进行封装，因为迭代器的使用形式与指针相同，所以自定义类中需要实现以下方法：
      1、指针可以解引用访问数据，因此迭代器类中需要重载operator*()
      2、指针通过->访问其指向空间的成员，迭代器类中需要重载operator->()
      3、指针需要依次向后（向前）移动，所以需重载operator++()与operator++(int),反向迭代器需重载operator–()与operator–(int)
      5、需要比较是否相等，所以重载operator==()和operator!=()

    反向迭代器用正向迭代器去适配

    template
struct __list_iterator
{
	typedef __list_node Node;
	typedef __list_iterator Self;

	Node* _node;

	__list_iterator(Node* node = nullptr)
		:_node(node) 
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	const T& operator*()const
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	//后置 ++it   it.operator++(&it)
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

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

	//前置 it++   it.operator++(&it,0)
	Self operator++(int)
	{
		Self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	Self operator--(int)
	{
		Self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	bool operator==(const Self& lt)const
	{
		return _node == lt._node;
	}

	bool operator==(const Self& lt)const
	{
		return _node != lt._node;
	}
};

template
struct Reverse_iterator
{
	Iterator _it;
	typedef Reverse_iterator Self;

	Reverse_iterator(Iterator it)
		:_it(it)
	{}

	Ref operator*()
	{
		Iterator tmp(_it);
		return *(--tmp);
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	Self& operator++()
	{
		--_it;
		return *this;
	}

	Self operator++(int)
	{
		Self tmp(*this);
		--_it;
		return tmp;
	}

	Self& operator--()
	{
		++_it;
		return *this;
	}

	self operator--(int)
	{
		Self tmp(*this);
		++_it;
		return tmp;
	}

	bool operator==(const Self& s)
	{
		return _it == s._it;
	}

	bool operator!=(const Self& s)
	{
		return _it != s._it;
	}
};

    • 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

    拷贝构造和赋值运算符重载

    🗺️写法一:

    拷贝构造: 新链表申请头节点，遍历传入的链表，将其中的值依次尾插到新的链表。
    赋值运算符重载: 检查是否自己给自己赋值，清理原有链表资源，遍历赋值的链表，将其中的值依次尾插到新的链表。

    list(const list& lt)
{
	_head = new node(T());
	_head->_prev = _head;
	_head->_next = _head;

	for (const auto& e : lt)
	{
		push_back(e);
	}
}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    🗺️写法二:

    拷贝构造: 用传入的lt对象的[begin,end)区间构造一个tmp对象，将tmp和需要的对象交换。
    赋值运算符重载: 函数的参数使用传值传参，传值传参拷贝了lt对象，将lt和需要赋值的交换。

    void clear()
{
	iterator it = begin();
	while (it != end())
	{
		//erase删除一个后会返回下一个位置
		it = erase(it);
	}
}

list(const list& lt)
{
	list tmp(lt.begin(), lt.end());
	empty_list_init();
	swap(tmp);
}

list& operator=(list lt)
{
	swap(lt);
    return *this;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    list容量相关 size 、resize

    🛩️resize: 若n大于原有效节点数量，我们只需要删除多余的节点，若n小于原有效节点数量，调用push_back 插入val值。注意：我们需要先保存原有节点的数量，因为我们进行插入或删除时链表的size会随着改变。

    size_t size()const
{
	size_t count = 0;
	node* cur = _head->_next;
	while (cur != _head)
	{
		++count;
		cur = cur->_next;
	}
	return count;
}

void resize(size_t n, const T& val = T())
{
	size_t oldSize = size();
	if (n < oldSize)
	{
		//将有效元素减少到n
		while (n < oldSize)
		{
			pop_back();
			oldSize--;
		}
	}
	else
	{
		while (n > oldSize)
		{
			push_back(val);
			oldSize++;
		}
	}
}

    • 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

    list的插入和删除

    在这里插入图片描述

    //在pos位置插入值为val的节点
iterator insert(iterator pos, const T& val)
{
	assert(pos._node);
	node* newnode = new node(val);
	node* cur = pos._node;
	// 插入新的节点
	newnode->_next = cur;
	newnode->_prev = cur->_prev;
	cur->_prev = newnode;
	newnode->_prev->_next = newnode;

	return iterator(newnode);
}

//删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
	assert(pos._node);
	assert(pos != end());
	node* prev = pos._node->_prev;
	node* next = pos._node->_next;
	delete pos._node;
	prev->_next = next;
	next->_prev = prev;

	return iterator(next);//返回删除节点的下一个位置
}

void push_back(const T& val)
{
	insert(end(), val);
}

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

void push_front(const T& val)
{
	insert(begin(), val);
}

void pop_front()
{
	erase(begin());
}

    • 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

    list元素的访问操作

    T& front()
{
	return _head->_next->_data;
}

T& back()
{
	return _head->_prev->_data;
}

const T& front()const
{
	return _head->_next->_data;
}

const T& back()const
{
	return _head->_prev->_data;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    🌏list模拟实现完整代码

    #pragma once
#include
#include
using namespace std;

namespace hy
{
	//定义list的节点类
	template
	struct __list_node
	{
		T _data;
		__list_node* _prev;
		__list_node* _next;

		__list_node(const T& data = T())
			:_data(data)
			,_prev(nullptr)
			,_next(nullptr)
		{}
	};

	template
	struct __list_iterator
	{
		typedef __list_node Node;
		typedef __list_iterator Self;

		Node* _node;

		__list_iterator(Node* node = nullptr)
			:_node(node) 
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		const T& operator*()const
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		//后置 ++it   it.operator++(&it)
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

		//前置 it++   it.operator++(&it,0)
		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		Self operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		bool operator==(const Self& lt)const
		{
			return _node == lt._node;
		}

		bool operator!=(const Self& lt)const
		{
			return _node != lt._node;
		}
	};

	template
	struct Reverse_iterator
	{
		Iterator _it;
		typedef Reverse_iterator Self;

		Reverse_iterator(Iterator it)
			:_it(it)
		{}

		Ref operator*()
		{
			Iterator tmp(_it);
			return *(--tmp);
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp(*this);
			--_it;
			return tmp;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self operator--(int)
		{
			Self tmp(*this);
			++_it;
			return tmp;
		}

		bool operator==(const Self& s)
		{
			return _it == s._it;
		}

		bool operator!=(const Self& s)
		{
			return _it != s._it;
		}
	};

	template
	class list
	{
	public:
		typedef __list_node node;
		typedef __list_iterator iterator;
		typedef __list_iterator const_iterator;

		//反向迭代器适配支持
		typedef Reverse_iterator reverse_iterator;
		typedef Reverse_iterator const_reverse_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);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(iterator(end()));
		}

		reverse_iterator rend()
		{
			return reverse_iterator(iterator(begin()));
		}

		const_reverse_iterator rbegin()const
		{
			return const_reverse_iterator(iterator(end()));
		}

		const_reverse_iterator rend()const
		{
			return const_reverse_iterator(iterator(begin()));
		}

		T& front()
		{
			return _head->_next->_data;
		}

		T& back()
		{
			return _head->_prev->_data;
		}

		const T& front()const
		{
			return _head->_next->_data;
		}

		const T& back()const
		{
			return _head->_prev->_data;
		}

		void empty_list_init()
		{
			_head = new node(T());//无法确定传入的参数类型，所以传匿名函数构造
			_head->_next = _head;
			_head->_prev = _head;
		}

		list()
		{
			empty_list_init();
		}

		list(size_t n, const T& val = T())
		{
			empty_list_init();

			for (size_t i = 0;i < n;++i)
				push_back(val);
		}

		template
		list(InputIterator first, InputIterator last)
		{
			empty_list_init();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		/*list(const list& lt)
		{
			_head = new node(T());
			_head->_prev = _head;
			_head->_next = _head;

			for (const auto& e : lt)
			{
				push_back(e);
			}
		}*/
		/*
		list& operator=(const list& lt)
		{
			if (lt != &this)
			{
				clear();
				for (const auto& e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}*/

		void swap(list& lt)
		{
			std::swap(_head, lt._head);
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				//erase删除一个后会返回下一个位置
				it = erase(it);
			}
		}

		list(const list& lt)
		{
			list tmp(lt.begin(), lt.end());
			empty_list_init();
			swap(tmp);
		}

		list& operator=(list lt)
		{
			swap(lt);
		    return *this;
		}

		size_t size()const
		{
			size_t count = 0;
			node* cur = _head->_next;
			while (cur != _head)
			{
				++count;
				cur = cur->_next;
			}
			return count;
		}

		void resize(size_t n, const T& val = T())
		{
			size_t oldSize = size();
			if (n < oldSize)
			{
				//将有效元素减少到n
				while (n < oldSize)
				{
					pop_back();
					oldSize--;
				}
			}
			else
			{
				while (n > oldSize)
				{
					push_back(val);
					oldSize++;
				}
			}
		}

		//在pos位置插入值为val的节点
		iterator insert(iterator pos, const T& val)
		{
			assert(pos._node);
			node* newnode = new node(val);
			node* cur = pos._node;
			// 插入新的节点
			newnode->_next = cur;
			newnode->_prev = cur->_prev;
			cur->_prev = newnode;
			newnode->_prev->_next = newnode;

			return iterator(newnode);
		}

		//删除pos位置的节点，返回该节点的下一个位置
		iterator erase(iterator pos)
		{
			assert(pos._node);
			assert(pos != end());
			node* prev = pos._node->_prev;
			node* next = pos._node->_next;
			delete pos._node;
			prev->_next = next;
			next->_prev = prev;

			return iterator(next);//返回删除节点的下一个位置
		}

		void push_back(const T& val)
		{
			insert(end(), val);
		}

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

		void push_front(const T& val)
		{
			insert(begin(), val);
		}

		void pop_front()
		{
			erase(begin());
		}

		void empty()
		{
			return begin() == end();
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
	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
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399
    • 400
    • 401
  • 相关阅读:
    期货开户手机APP有哪些？
    华为云云耀云服务器L实例评测｜企业项目最佳实践之私有库搭建verdaccio(八)
    JAVAWEB_实验三 Servlet 相关技术
    Hadoop到底是什么？他又由哪些组成？
    内核学习——1、list_head
    es的nested查询
    牛客Mysql——SQL必知必会
    JavaScript 67 JavaScript HTML DOM 67.5 JavaScript HTML DOM - 改变 HTML
    linux进程间信号量通信IPC（sem）
    数据化运营11 业务摸底：如何通过少量样本推断整体业务情况？
  • 原文地址：https://blog.csdn.net/qq_61939403/article/details/126876481