【C++】STL容器：list的模拟实现-创新互联

一、list的结构 1. list的节点

list的底层是一个带头双向循环链表，但list本身和list的节点是不同的结构，需要分开实现。

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名与空间、虚拟主机、营销软件、网站建设、砀山网站维护、网站推广。

list节点的结构：

templatestruct list_node
{list_node* _next;
	list_node* _prev;
	T _data;
	//构造：使用x初始化节点的数据
	list_node(const T& x)
		:_next(nullptr)
		, _prev(nullptr)
		, _data(x)
	{}
};

2. list的结构

class list
{typedef list_nodenode;
	//……
private:
	node* _head;
	size_t _size;
};

---

二、list的迭代器

list的迭代器不能再像vector一样用普通指针作为迭代器，因为存储节点的空间不保证连续。

list迭代器必须有能力指向list的节点，并能够正确的进行++、--、*、->等操作，所谓正确是指：++时指向下一个节点，--时指向上一个节点，*取的是节点的数据值，->取的是节点数据成员的地址。

list的迭代器使用封装 + 操作符重载，以达到在使用方式上如同指针一样的目的。

list是一个双向链表，迭代器必须具有前移++、后移- -，所以list的迭代器是一个双向迭代器。

1. 正向迭代器

templatestruct __list_iterator
{typedef list_nodenode;
	typedef __list_iteratorSelf;
	node* _pnode;//迭代器内部要有一个指针，指向list的节点
	
	//constructor
	__list_iterator(node* p)
		:_pnode(p)
	{}
	
	Ptr operator->()
	{//return &_pnode->_data;
		return &(operator*());//标准做法
	}

	// iterator it
	// *it
	// ++it;
	// 解引用取到的是节点的数据值
	Ref operator*()
	{return _pnode->_data;
	}

	const T& operator*() const
	{return _pnode->_data;
	}
	
	// ++it
	Self& operator++()
	{_pnode = _pnode->_next;
		return *this;
	}

	// it++
	Self operator++(int)//返回类型为迭代器自己
	{//拷贝构造，这里只需要浅拷贝，使用系统生成的即可满足需求
		Self tmp(*this);
		_pnode = _pnode->_next;
		return tmp;
	}
	//--it
	Self& operator--()
	{_pnode = _pnode->_prev;
		return *this;
	}
	//it--
	Self operator--(int)
	{Self tmp(*this);
		_pnode = _pnode->_prev;
		return tmp;
	}
	//比较指向节点的指针即节点的地址
	bool operator!=(const Self& it) const
	{return _pnode != it._pnode;
	}

	bool operator==(const Self& it) const
	{return _pnode == it._pnode;
	}
};

---

2. 反向迭代器

反向迭代器的实现体现了泛型思维。反向迭代器是正向迭代器的封装，内部有一个正向迭代器成员

模板参数Iterator：给我不同容器的正向迭代器，适配出对应的这个容器需要的反向迭代器。比如要实现vector的反向迭代器只需将其正向迭代器作为参数传入即可。

// 适配器 -- 复用
templateclass ReverseIterator
{typedef ReverseIteratorSelf;
private:
	Iterator _it;
public:
	ReverseIterator(Iterator it)
		:_it(it)
	{}
	Ref operator* ()
	{Iterator tmp = _it;
		return *(--tmp);//先--再解引用原因是用正向迭代器的end构造了rbegin
	}
	Ptr operator->()
	{return &(operator*());//显示调解引用再取地址
	}
	//前置++
	Self& operator++ ()
	{--_it;//反向迭代器的++是正向迭代器的--
		return *this;
	}
	//后置++
	Self operator++ (int)
	{ReverseIterator tmp(_it);
		--_it;
		return tmp;
	}
	//前置--
	Self& operator-- ()
	{++_it;
		return *this;
	}
	//后置--
	Self operator-- (int)
	{ReverseIterator tmp(_it);
		++_it;
		return tmp;
	}
	bool operator!= (const Self& s)
	{return _it != s._it;
	}
};

3. 迭代器失效问题

list的一个性质：插入操作不会造成原迭代器失效。删除操作也只有”指向“被删除元素的迭代器失效，其他不受影响。

4. 具体实现

templateclass list
{typedef list_nodenode;
private:
	node* _head;
	size_t _size;
	//……
public:
	//前面使用模板参数是为了根据传入参数不同实现不同迭代器
	typedef __list_iteratoriterator;
	typedef __list_iteratorconst_iterator;

	typedef ReverseIteratorreverse_iterator;
	typedef ReverseIteratorconst_reverse_iterator;

	//反向迭代器
	reverse_iterator rbegin()
	{return reverse_iterator(end());
	}

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

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

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

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

	const_iterator end() const
	{return const_iterator(_head);
	}

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

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

可以发现正向迭代器和反向迭代器是对称的，这也是为什么在反向迭代器实现中会有如下代码：

Ref operator* ()
{Iterator tmp = _it;
	return *(--tmp);//先--再解引用原因是用正向迭代器的end构造了rbegin
}

---

三、构造和析构

• 构造一个空链表

void empty_initialize()
{_head = new node(T());
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}
list() {empty_initialize(); }//生成一个空链表

• 区间构造

templatelist(InputIterator first, InputIterator last)
{empty_initialize();
	while (first != last)
	{push_back(*first);
		++first;
	}
}

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

//传统写法
// lt2(lt1)
//list(const list& lt)
//{//	empty_initialize();

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

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

//	return *this;
//}
void swap(list& lt)
{std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}
// lt2(lt1)
list(const list& lt)
//list(const list& lt) //虽然C++语法支持类名作为类型，但是不建议
{empty_initialize();

	listtmp(lt.begin(), lt.end());
	swap(tmp);
}

// lt3 = lt1
list& operator=(listlt)
//list& operator=(list lt) // 不建议
{swap(lt);
	return *this;
}

• 析构

void clear()
{iterator it = begin();
	while (it != end())
	{it = erase(it);
	}
}
~list()
{clear();//clear完成除头节点外其他节点的销毁工作
	delete _head;
	_head = nullptr;
}

---

四、insert和erase

//在pos前插入
iterator insert(iterator pos, const T& x)
{node* newnode = new node(x);
	node* cur = pos._pnode;
	node* prev = cur->_prev;

	// prev newnode cur
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;

	++_size;

	return iterator(newnode);
}

iterator erase(iterator pos)
{assert(pos != end());

	node* prev = pos._pnode->_prev;
	node* next = pos._pnode->_next;

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

	delete pos._pnode;
	--_size;

	return iterator(next);
}

---

五、其他元素操作

void push_back(const T& x)
{//node* newnode = new node(x);
	//node* tail = _head->_prev;
	 _head         tail   newnode
	//tail->_next = newnode;
	//newnode->_prev = tail;
	//newnode->_next = _head;
	//_head->_prev = newnode;

	insert(end(), x);
}

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

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

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

---

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

当前文章：【C++】STL容器：list的模拟实现-创新互联
本文路径：http://cqcxhl.com/article/ddisch.html