【C++精华铺】12.STL list模拟实现

07-16 1715阅读

1.序言

        STL (Standard Template Library)是C++标准库中的一个重要组件，提供了许多通用的数据结构和算法。其中，STL list是一种带头双向链表容器，可以存储任意类型的元素。

【C++精华铺】12.STL list模拟实现
（图片来源网络，侵删）

list的特点包括：

  1. 双向性：list中的元素可以根据需要在前向和后向方向上进行遍历和访问。

  2. 动态大小：list的大小可以根据需要动态增长和收缩，不像数组需要预先定义大小。

  3. 高效的插入和删除：在list中插入或删除元素的操作非常高效，时间复杂度为常数时间。

  4. 不支持随机访问：由于list的实现是基于链表的，所以不支持随机访问，只能通过遍历来访问指定位置的元素。

list提供了一系列的成员函数来操作元素，包括：

  1. push_back()和push_front()：分别在list的尾部和头部插入一个元素。

  2. pop_back()和pop_front()：分别删除list的尾部和头部的元素。

  3. insert()：在指定位置插入一个或多个元素。

  4. erase()：删除指定位置的一个或多个元素。

  5. size()：返回list中元素的个数。

  6. empty()：判断list是否为空。

        值得注意的是，由于list是双向链表，所以在内存上的开销相对较大，而且无法通过下标直接访问元素。因此，在选择容器时需要根据实际需求进行权衡。

2.list整体结构

template
struct list_node
{
	list_node* _next;
	list_node* _prev;
	T _Data;
	list_node(const T& x = T())
		:_next(nullptr)
		, _prev(nullptr)
		, _Data(x)
	{}
};
template
struct __list_iterator
{
	typedef list_node node;
	typedef __list_iterator iterator;     
	node* _node; 
      //···········
};
template
class list
{
	typedef list_node node;
public:
	typedef __list_iterator iterator;
	typedef __list_iterator const_iterator;
		//······
private:
	node* _head;
	};

3.list迭代器

3.1 operator*()

        operator*() 返回的是list某节点存储的数据，并且返回时要能修改数据，所以返回类型是T&（Ref：是个模板参数，兼顾 T& 和 const T &，用哪个传那个 ）。

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

3.2 operator->()

        operator->() 用于取list存储的数据对象里面的属性，也是模拟指针的行为，返回数据对象的地址。

Ptr operator->()
{
	return &_node->_Data;
}

        需要注意的是如果我们使用这个 -> 的运算符重载，假设一迭代器对象 it ：it.operator->()->(某属性) 等价于 it->->(某属性) ，这里实际上有俩个 -> ,为了增加代码的可读性，这里进行了特殊处理，优化成了一个 -> ：it->(某属性) 。

3.3 operator++() 和 operator++(int)、operator--() 和 operator--(int)

        operator++()（operator--()）是前置++（--），返回++（--）后的值，operator++(int)（operator--()）是后置++（--），返回++前的值（--）。

iterator& operator++()
{
	_node = _node->_next;
	return *this;
}
iterator operator++(int)
{ 
	iterator tmp(*this);
	_node = _node->_next;
	return tmp;
}
iterator& operator--()
{
	_node = _node->_prev;
	return *this;
}
iterator operator--(int)
{
	iterator tmp(*this);
	_node = _node->_prev;
	return tmp;
}

 3.4 operator==() 和 operator!=()

bool operator==(const iterator& it)
{
	return _node == it._node;
}
bool operator!=(const iterator& it)
{
	return _node != it._node;
}

3.5 迭代器完整代码

template
struct list_node
{
list_node* _next;
list_node* _prev;
T _Data;
list_node(const T& x = T())
	:_next(nullptr)
	, _prev(nullptr)
	, _Data(x)
{}
};
template
struct __list_iterator
{
typedef list_node node;
typedef __list_iterator iterator;
__list_iterator(node* n)
	:_node(n)
{}
Ref operator*()
{
	return _node->_Data;
}
Ptr operator->()
{
	return &_node->_Data;
}
iterator& operator++()
{
	_node = _node->_next;
	return *this;
}
iterator operator++(int)
{ 
	iterator tmp(*this);
	_node = _node->_next;
	return tmp;
}
iterator& operator--()
{
	_node = _node->_prev;
	return *this;
}
iterator operator--(int)
{
	iterator tmp(*this);
	_node = _node->_prev;
	return tmp;
}
bool operator==(const iterator& it)
{
	return _node == it._node;
}
bool operator!=(const iterator& it)
{
	return _node != it._node;
}
node* _node; 
};

4.list接口

4.1构造函数

list()
{
	_head = new node;
	_head->_next = _head->_prev = _head;
}
~list()
{
	while (end() != _head)
	{
		erase(end());
	}
	delete _head;
	_head = nullptr;
}
template
list(Iterator first, Iterator last)
{
	_head = new node;
	_head->_next = _head->_prev = _head;
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}
void swap(list& tmp)
{
	std::swap(_head, tmp._head);
}
list(const list& l)
{
	_head = new node;
	_head->_next = _head->_prev = _head;
	list tmp(l.begin(), l.end());
	swap(tmp);
}

4.2 push_back() push_front() pop_back() pop_front()

void push_back(const T& x)
{
	node* tail = _head->_prev;
	node* newnode = new node(x);
	newnode->_prev = tail;
	newnode->_next = tail->_next;
	tail->_next = newnode;
	_head->_prev = newnode;
}
void push_front(const T& x)
{
	node* head = _head->_next;
	node* newnode = new node(x);
	newnode->_prev = _head;
	newnode->_next = head;
	_head->_next = newnode;
	head->_prev = newnode;
}
void pop_back()
{
	node* tail = _head->_prev;
	
	_head->_prev = tail->_prev;
	tail->_prev->_next = _head;
	delete tail;
}
void pop_front()
{
	node* head = _head->_next;
	_head->_next = head->_next;
	head->_next->_prev = _head;
	delete head;
}

 4.3迭代器

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

 4.4 insert() 和 erase()

        注意erase的迭代器失效，需要更新pos

void insert(iterator pos, const T& x)
{
	node* cur = pos._node;
	node* newnode = new node(x);
	newnode->_next = cur;
	newnode->_prev = cur->_prev;
	cur->_prev->_next = newnode;
	cur->_prev = newnode;
}
iterator erase(iterator pos)
{
	assert(pos != end());
	node* prev = pos._node->_prev;
	node* next = pos._node->_next;
	prev->_next = next;
	next->_prev = prev;
	delete pos._node;
	return iterator(next);
}

5. list完整代码

#pragma once
#include
#include
using namespace std; 
namespace zy
{
	template
	struct list_node
	{
		list_node* _next;
		list_node* _prev;
		T _Data;
		list_node(const T& x = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _Data(x)
		{}
	};
	template
	struct __list_iterator
	{
		typedef list_node node;
		typedef __list_iterator iterator;
		__list_iterator(node* n)
			:_node(n)
		{}
		Ref operator*()
		{
			return _node->_Data;
		}
		Ptr operator->()
		{
			return &_node->_Data;
		}
		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		iterator operator++(int)
		{ 
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		iterator operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		bool operator==(const iterator& it)
		{
			return _node == it._node;
		}
		bool operator!=(const iterator& it)
		{
			return _node != it._node;
		}
		node* _node; 
	};
	template
	class list
	{
		typedef list_node node;
	public:
		typedef __list_iterator iterator;
		typedef __list_iterator const_iterator;
		list()
		{
			_head = new node;
			_head->_next = _head->_prev = _head;
		}
		~list()
		{
			while (end() != _head)
			{
				erase(end());
			}
			delete _head;
			_head = nullptr;
		}
		template
		list(Iterator first, Iterator last)
		{
			_head = new node;
			_head->_next = _head->_prev = _head;
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		void swap(list& tmp)
		{
			std::swap(_head, tmp._head);
		}
		list(const list& l)
		{
			_head = new node;
			_head->_next = _head->_prev = _head;
			list tmp(l.begin(), l.end());
			swap(tmp);
		}
		
		list& operator=(list lt)
		{
			swap(lt);
			return *this;
		}
		
		void push_back(const T& x)
		{
			node* tail = _head->_prev;
			node* newnode = new node(x);
			newnode->_prev = tail;
			newnode->_next = tail->_next;
			tail->_next = newnode;
			_head->_prev = newnode;
		}
		void push_front(const T& x)
		{
			node* head = _head->_next;
			node* newnode = new node(x);
			newnode->_prev = _head;
			newnode->_next = head;
			_head->_next = newnode;
			head->_prev = newnode;
		}
		void pop_back()
		{
			node* tail = _head->_prev;
			
			_head->_prev = tail->_prev;
			tail->_prev->_next = _head;
			delete tail;
		}
		void pop_front()
		{
			node* head = _head->_next;
			_head->_next = head->_next;
			head->_next->_prev = _head;
			delete head;
		}
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return iterator(_head->_next);
		}
		const_iterator end() const
		{
			return iterator(_head);
		}
		void insert(iterator pos, const T& x)
		{
			node* cur = pos._node;
			node* newnode = new node(x);
			newnode->_next = cur;
			newnode->_prev = cur->_prev;
			cur->_prev->_next = newnode;
			cur->_prev = newnode;
		}
		iterator erase(iterator pos)
		{
			assert(pos != end());
			node* prev = pos._node->_prev;
			node* next = pos._node->_next;
			prev->_next = next;
			next->_prev = prev;
			delete pos._node;
			return iterator(next);
		}
	private:
		node* _head;
	};
}
VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]