C++ list常用接口和模拟实现实例代码

目录

• 下面了解一下list的常用接口
• 1.构造函数
• 2.迭代器
• 3.容量操作
• 4.元素获取
• 5.增删改查
• 下面给出list的模拟实现
• 1.节点list_node设计
• 2.迭代器设计
• 3.常用接口的模拟实现

C++中list容器底层实现是使用带头双向循环链表的结构，通过指针指向前一个和后一个节点。它也具有双向链表的优缺点，比如优点是对于在任意位置插入和删除不用移动数据，缺点是不能任意位置的随机访问，必须遍历到要访问的节点才可以；并且list还需要额外的空间来存储前一个和后一个节点的信息。

下面了解一下list的常用接口

1.构造函数

//构造空的list
list()
//拷贝构造
list (const list& x);
//迭代器构造，使用模板能适合不同的类型
template <class InputIterator>
list (InputIterator first, InputIterator last);
//构造n个值为val的list
list (size_type n, const value_type& val = value_type())

2.迭代器

//返回开始位置的迭代器
iterator begin();
const_iterator begin() const;
//返回结束位置的迭代器
iterator end();
const_iterator end() const;

需要注意的是这里的迭代器在底层并不是原生指针，具体实现在后文给出。

3.容量操作

//判断是否为空
bool empty() const;
//返回有效节点的个数
size_type size() const;

4.元素获取

//返回首元素的引用
reference front();
const_reference front() const;
//返回末尾元素的引用
reference back();
const_reference back() const;

5.增删改查

//头插
void push_front (const value_type& val);
//尾插
void push_back (const value_type& val);
//头删
void pop_front();
//尾删
void pop_back();
//在任意位置插入
iterator insert (iterator position, const value_type& val);
//在任意位置删除
iterator erase (iterator position);
//交换两个链表中的元素
void swap (list& x);
//清空链表中的元素
void clear();

在了解了链表的增删查改之后我们思考一个问题

list是否会像vector和string一样出现迭代器失效的原因？由于这里是链式结构，它的内存在物理空间上并不连续，因此如果仅仅是插入一个元素并不会出现迭代器失效的问题，只有删除时会发生迭代器失效的问题，并且这里只有删除节点的迭代器会失效。

下面给出list的模拟实现

1.节点list_node设计

节点的结构就是双向链表的结构，这里也可以写成结构直接默认类成员公有的也可以。

template<class T>
	class list_node
	{
	public:
		list_node<T>* _next;
		list_node<T>* _prev;
		T _val;
		list_node(const T& val = T())//默认匿名对象
			:_next(nullptr)
			,_prev(nullptr)
			,_val(val)
		{}
	};

2.迭代器设计

关于const的迭代器设计与之前的string和vector都有所不同，对于节点的指针进行了又一层的封装。因为这里要支持->箭头和的重载。我们对于一个指针变量进行解引用通常是要访问其中存储的数据的内容（_val）；而->是要访问数据内容的成员。从这个特性就可以得到一个结论，在实现list迭代器时，重载解引用和箭头的返回类型不同，那么编程客栈我们要怎样控制呢？

事实上在这里只需要控制模板参数就可以实现这种效果。具体代码如下

template<class T,class Ref ,class Ptr>
	class _list_iterator
	{
	public:
        //这里事实上迭代器只是借用节点进行访问，而不是管理这些节点，链表才管理节点    
		typedef list_node<T> Node;
		typedef _list_iterator<T, Ref,Ptr> self;
		Node* _node;
		_list_iterator(Node* node)
			:_node(node)
		{}
		Ref operator*()//这里控制解引用的返回类型
		{
			return _node->_val;
		}
		Ptr operator->()
		{
			return &_node->_val;
		}
		//前置++
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		self operator++(int)
		{
			self temp(*this);
			_node = _node->_next;
			return temp;
		}
		//前置--
		self& operator--()
		{
			_node = _node编程->_prev;
			return *this;
		}
		//后置--
		self operator--(int)
		{
			self temp(*this);
			_node = _node->_prev;
			return temp;
		}
		bool operator!=(const self& it) const
		{
			return _node != it._node;
		}
		bool operator==(const self& it) const
		{
			return _node == it._node;
		}
	};

这里的Ref控制解引用的返回类型，Ptr控制箭头的返回类型；并且在这个类中利用typedef的方法控制自增和自减的返回类型。

并且这样写还有一点好处是，对于普通的迭代器使用正常的模板参数即可，对于const迭代器使用const的模板参数即可。

3.常用接口的模拟实现

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;
		//这里const迭代器的设计是错误的，因为const迭代器是希望指向内容不被修改
		//这样的设计是迭代器本身不能修改
		//typedef const _list_iterator<T> const_iterator;
		iterator begin() 
		{
			return _head->_next;//单参数的构造函数支持隐式类型转换
		}
		const_iterator begin() const
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator end() const
		{
			return _head;
		}
		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
		list()
		{
			empty_init();
		}
		//lt2(lt1)
		list(const list<T>& lt)
		//list(const list& lt)//不推荐这样使用
		{
			empty_init();
			//遍历lt1，直接把lt2尾插到lt1
			//这里传引用效率高
			for (const auto& e : lt)
			{
				push_back(e);
			}
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
		}
		list<T>& operator=(list<T> lt)
		//list& operator=(list lt)//这里与上面的js拷贝构造同理
		{
			swap(lt);
			return *this;
		}
		~list()
		{
			clear();
			delete _head;
			_head =javascript nullptr;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		void pop_back()
		{
			erase(--end());//这里调用--，头节点的prev就是尾
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(begin());
		}
		iterator insert(iterator pos, cphponst T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);
			prev->_next = newnode;
			newnode->_next = cur;
			cur->_prev = newnode;
			newnode->_prev = prev;
			return newnode;
		}
		iterator erase(iterator pos)//这里会有迭代器失效，返回下一个位置的迭代器
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return next;
		}
		size_t size()
		{
			size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}
			return sz;
		}
	private:
		Node* _head;
	};

这里的常用接口实现都类似与数据结构中的带头的双向链表。需要注意的就是爹迭代器失效的问题。

最后总结一下vector和list的各自优劣

（1）底层结构：vector是连续存储的，是一个动态的顺序表；list是不连续存储，是一个带头的双向循环链表

（2）随机访问：vector支持[]随机访问；list不支持随机访问

（3）插入和删除效率：vector的插入和删除需要移动数据；list的插入和删除不需要移动数据。

（4）空间利用率：vector底层是连续的存储空间，不容易造成内存碎片的问题，空间利用率高；list底层是不连续的存储空间，小的节点容易出现内存碎片的问题，空间利用率低。

（5）迭代器：vector的迭代器是原生指针；list的迭代器对原生指针进行了再一层的封装。

（6）迭代器失效的问题：vector再插入和删除时都会导致迭代器失效，需要重新赋值；list只有再删除时才会导致迭代器失效。

到此这篇关于C++ list常用接口和模拟实现实例代码的文章就介绍到这了,更多相关C++ list常用接口内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！