189 8069 5689

C++——模拟实现list-创新互联

目录

成都创新互联-专业网站定制、快速模板网站建设、高性价比杂多网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式杂多网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖杂多地区。费用合理售后完善，10年实体公司更值得信赖。

1.链表节点的构建

2.迭代器的初步实现

3.成员变量以及默认构造

4.普通迭代器接口

5.插入接口

6.删除与find接口

7.const迭代器实现与接口

8.范围拷贝与拷贝构造

9.如果实例化参数是自定义类型

10.析构函数

11.完整代码

1.链表节点的构建

链表的节点有指针与和数据域，所以无法用任何一个内置类型来表示它，我们需要自定义好节点的类型。list容器使用的是带头双向循环链表。

templatestruct list_node		//节点类型
	{
		list_node* _next;
		list_node* _prev;
		T _val;
		list_node(const T& val = T()) 
			:_val(val)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
2.迭代器的初步实现

链表的节点所占用的内存空间是不连续的，所以不能使用原生指针来代替迭代器。我们需要自定义迭代器的行为(例如++是从前一个节点移动到后一个节点)。

templatestruct list_iterator
	{
		typedef list_nodenode;
		node* pnode;
		
		list_iterator(node* p)
			:pnode(p)
		{}

		list_iterator& operator++()
		{
			pnode = pnode->_next;
			return *this;
		}

		bool operator!=(list_iterator& lt)
		{
			return pnode != lt.pnode;
		}
	};
3.成员变量以及默认构造

定义空容器时，容器是存在头节点(哨兵卫)的。

templateclass list
	{
	public:
		typedef list_nodenode;
		typedef list_iteratoriterator;

		void empty_init()
		{
			_head = new node(T());		//哨兵卫
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();		//复用
		}

	private:
		node* _head;
		size_t size;		//记录有节点个数(除哨兵卫)
	};
4.普通迭代器接口
iterator begin()
{
	return iterator(_head->_next);
}
iterator end()
{
	return iterator(_head);		//尾后迭代器
}
5.插入接口

插入有头插、尾插、随机插。我们重点实现随机插，头插和尾插复用随机插。

void push_back(const T& val)
{
	insert(end(), val);		//在哨兵卫头插就是尾插
}

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

iterator insert(iterator pos, const T& val)
{
	node* newnode = new node(val);
	node* prev = pos.pnode->_prev;

	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = pos.pnode;
	pos.pnode->_prev = newnode;
			
	++_size;
	return iterator(newnode);		//返回插入节点的位置(防止迭代器失效)
}
6.删除与find接口

删除有头删、尾删、随机删。我们重点实现随机删，头删和尾删复用随机删。

void pop_back()
{
	erase(end().pnode->_prev);
}
		
void pop_front()
{
	erase(begin());
}

iterator erase(iterator pos)
{
	assert(end() != pos);		//不能删除哨兵卫
			
	node* prev = pos.pnode->_prev;
	node* next = pos.pnode->_next;

	prev->_next = next;
	next->_prev = prev;

	delete pos.pnode;
	--_size;
	return iterator(next);		//返回删除节点的下一个节点位置(防止迭代器失效)
			
}

iterator find(iterator first, iterator last, const T& val)
{
	assert(first != last);
	while (first != last)
	{
		if (*first == val) return first;
		++first;
	}
	return end();
}
7.const迭代器实现与接口

不能使用const成员函数重载，因为我们要的效果是底层const而非顶层const(即指向的内容不可变，迭代器本身可变)。所以我们有两套方案，一是再构建一个迭代器类模板；二是在原来的迭代器模板基础上添加一个模板参数。再构建一个迭代器的方案与原模板的唯一区别就是返回值不同。所以否决第一套设计方案。

现在先统一一下迭代器接口：

typedef list_iteratoriterator;
typedef list_iteratorconst_iterator;

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

迭代器设计：

template//多使用一个模板参数
struct list_iterator
{
	typedef list_nodenode;
	typedef list_iteratorself;		//为了方便
	node* pnode;
		
	list_iterator(node* p)
		:pnode(p)
	{}

	ref operator*()
	{
		return pnode->_val;
	}

	self& operator++()
	{
		pnode = pnode->_next;
		return *this;
	}

	bool operator!=(self& lt)
	{
		return pnode != lt.pnode;
	}
};
8.范围拷贝与拷贝构造

我们实现更加全面的构造接口。

templatelist(InputIterator first, InputIterator last)		//范围拷贝
{
	empty_init();
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}
		
void swap(list& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}
list(const list& lt)		//拷贝构造现代写法
{
	empty_init();
	listtmp(lt.begin(), lt.end());
	swap(tmp);
}

list& operator=(listlt)		//赋值运算符重载现代写法
{
	swap(lt);
	return *this;
}
9.如果实例化参数是自定义类型

如果链表的节点是一个自定义类型，那么使用 * 将无法读取自定义类型的数据。所以我们需要完善访问自定义类型成员的功能，即 ->运算符重载。此重载函数的返回值是实例化参数类型的指针，这个指针也有const与非const之分，并且调用此重载的对象可能是const或非const对象，也就是说迭代器可能是const迭代器与非const迭代器。那么我们依然为迭代器模板添加一个参数，并且完善迭代器的功能。

别忘了对迭代器的重命名需要更新一下：

typedef list_iteratoriterator;
typedef list_iteratorconst_iterator;
template//多使用一个模板参数
struct list_iterator
{
	typedef list_nodenode;
	typedef list_iteratorself;		
	node* pnode;
		
	list_iterator(node* p)
		:pnode(p)
	{}

	ref operator*()
	{
		return pnode->_val;
	}

	ptr operator->()
	{
		return &pnode->_val;
	}

	self& operator++()
	{
		pnode = pnode->_next;
		return *this;
	}

	self operator++(int)		//后置++
	{
		node* tmp(pnode);
		pnode = pnode->_next;
		return tmp;
	}

	self& operator--()
	{
		pnode = pnode->_prev;
		return *this;
	}

	self operator--(int)		//后置--
	{
		node* tmp(pnode);
		pnode = pnode->_prev;
		return tmp;
	}

	bool operator!=(const self& lt)
	{
		return pnode != lt.pnode;
	}

	bool operator==(const self& lt)
	{
		return pnode == lt.pnode;
	}
};
10.析构函数

释放分为两个部分，一是不释放哨兵卫，将有效节点释放；而是全部释放。我们实现一个clear接口，让析构复用此接口。

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

void clear()
{
	auto it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}
11.完整代码

这里只实现了list容器常用的接口，并没有完全依照标准库1：1模拟实现。代码会有很多细节没有处理好，并不是会报错，而是有些地方显得不够严谨。

#include 
#include 
namespace ly
{
	templatestruct list_node		//节点类型
	{
		list_node* _next;
		list_node* _prev;
		T _val;
		list_node(const T& val = T()) 
			:_val(val)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};

template//多使用一个模板参数
struct list_iterator
{
	typedef list_nodenode;
	typedef list_iteratorself;		
	node* pnode;
		
	list_iterator(node* p)
		:pnode(p)
	{}

	ref operator*()
	{
		return pnode->_val;
	}

	ptr operator->()
	{
		return &pnode->_val;
	}

	self& operator++()
	{
		pnode = pnode->_next;
		return *this;
	}

	self operator++(int)		//后置++
	{
		node* tmp(pnode);
		pnode = pnode->_next;
		return tmp;
	}

	self& operator--()
	{
		pnode = pnode->_prev;
		return *this;
	}

	self operator--(int)		//后置--
	{
		node* tmp(pnode);
		pnode = pnode->_prev;
		return tmp;
	}

	bool operator!=(const self& lt)
	{
		return pnode != lt.pnode;
	}

	bool operator==(const self& lt)
	{
		return pnode == lt.pnode;
	}
};

	templateclass list
	{
	public:
		typedef list_nodenode;
		typedef list_iteratoriterator;
		typedef list_iteratorconst_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);
		}

		void empty_init()
		{
			_head = new node(T());		//哨兵卫
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();		//复用
		}

		templatelist(InputIterator first, InputIterator last)		//范围拷贝
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		
		void swap(list& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list(const list& lt)		//拷贝构造现代写法
		{
			empty_init();
			listtmp(lt.begin(), lt.end());
			swap(tmp);
		}

		list& operator=(listlt)		//赋值运算符重载现代写法
		{
			swap(lt);
			return *this;
		}


		void pop_back()
		{
			erase(end().pnode->_prev);
		}
		
		void pop_front()
		{
			erase(begin());
		}

		iterator erase(iterator pos)
		{
			assert(end() != pos);		//不能删除哨兵卫
			
			node* prev = pos.pnode->_prev;
			node* next = pos.pnode->_next;

			prev->_next = next;
			next->_prev = prev;

            delete pos.pnode;
			--_size;
			return iterator(next);		//返回删除节点的下一个节点位置(防止迭代器失效)
			
		}

		iterator find(iterator first, iterator last, const T& val)
		{
			assert(first != last);
			while (first != last)
			{
				if (*first == val) return first;
				++first;
			}
			return end();
		}


		void push_back(const T& val)
		{
			insert(end(), val);		//在哨兵卫头插就是尾插
		}

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

		iterator insert(iterator pos, const T& val)
		{
			node* newnode = new node(val);
			node* prev = pos.pnode->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = pos.pnode;
			pos.pnode->_prev = newnode;
			
			++_size;
			return iterator(newnode);		//返回插入节点的位置(防止迭代器失效)
		}



	private:
		node* _head;
		size_t _size;		//记录有节点个数(除哨兵卫)
	};
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


当前文章：C++——模拟实现list-创新互联
本文来源：http://cdxtjz.cn/article/pcioh.html

其他资讯