C++ list-2. 模拟实现

时间：2024-04-14 10:03:51

由于list的底层是双向循环链表，因此我们得有节点，并且链表最开始是有一个哨兵位的头节点的

namespace byh
{
	template<class T>
	struct ListNode
	{
		ListNode(const T& val = T())
			:_next(nullptr)
			,_prev(nullptr)
			, _val(val)
		{}

		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _val;
	};
    
	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		void push_back(const T& val)
		{
			Node* newNode = new Node(val);
			Node* tail = _head->_prev;
			tail->_next = newNode;
			newNode->_prev = tail;
			newNode->_next = _head;
			_head->_prev = newNode;
			_size++;
		}

	private:
		Node* _head;
		size_t _size;
	};
}

2.1 iterator的设计

尾插数据后，我们想遍历数据，使用for循环不能遍历，因为链表的数据在内存中并不连续；范围for的底层则是迭代器

之前的string和vector的迭代器我们是拿原生指针实现的，一方面指针指向的内容就是我们要遍历的数据，另一方面数据在内存中是连续的，指针++就是往后走

但list如果拿原生指针实现，存在下面的问题：

  • 解引用指针得到的是一个节点，而我们要的是节点中的值
  • list的节点在内存中不连续，指针++走到的不一定是下一个节点

迭代器的目的是不需要我们去考虑底层，所有容器遍历方式都是一样的

我们希望解引用和++按照我们指定的方式来操作节点，而C++中支持运算符重载，于是能不能将迭代器设计成一个类，在类中，我们自主定义*和++ ，再由list提供begin()和end()接口

template<class T>
struct ListIterator
{
	typedef ListNode<T> Node;
	ListIterator(Node* node)
		:_node(node)
	{}
    
	T& operator*()
	{
		return _node->_val;
	}
    
	// ++it
	ListIterator& operator++()
	{
		_node = _node->_next;
		return *this;
	}
    
	// it++
	ListIterator operator++(int)
	{
		ListIterator temp = *this;
		_node = _node->_next;
		return temp;
	}
    
	// --it
	ListIterator& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
    
	// it--
	ListIterator operator--(int)
	{
		ListIterator temp = *this;
		_node = _node->_prev;
		return temp;
	}
    
	bool operator!=(const ListIterator& li)
	{
		return _node != li._node;
	}
    
	bool operator==(const ListIterator& li)
	{
		return _node == li._node;
	}
    
	Node* _node;
};

// list中定义
iterator begin()
{
	return _head->_next;
}

iterator end()
{
	return _head;
}

实际上，list的迭代器其本质还是一个指针，只不过我们对该指针进行封装，并根据语法规则自主定义了该指针的行为

迭代器模拟的就是指针的行为

如果list中的数据类型是一个自定义类型，解引用迭代器得到一个结构体，用.操作符，这点跟C语言相同，但更多的时候我们用结构体的指针加上->来访问结构体中的数据；因此，就需要我们对->进行重载

template<class T>
struct ListIterator
{
    //...
    T* operator->()
	{
		return &this->_node->_val;
	}
    //...
}

struct A
{
	A(int a1 = 0, int a2 = 0)
		:_a1(a1)
		,_a2(a2)
	{}

	int _a1;
	int _a2;
};

void Test_list()
{
	list<A> li;
	li.push_back({ 10,10 });
	list<A>::iterator it = li.begin();
	cout << (*it)._a1 << " " << (*it)._a2 << endl;
	cout << it->_a1 << " " << it->_a1 << endl;
    // 实际上是 it.operator->()->_a1
    // 为了可读性，编译器简化成一个->
}

2.2 const_iterator的设计

void Print_list(const list<int>& cli)
{
	typename list<int>::iterator it = cli.begin();
	while (it != cli.end())
	{
		cout << *it << " ";
         it++
	}
	cout << endl;
}

void Test_list()
{
	list<int> li;
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	Print_list(li);
}

上面代码执行，编译器会报错，原因是cli是const对象，而begin是非const成员函数，const对象不能调用非const成员函数

那给begin()成员函数加上const修饰不就行了？这样做代码确实能跑，但问题是，cli是const对象，内容不能被修改，而我们现在能随意修改cli

正确的做法是重新设计一个const_iterator，给const对象使用

  1. 将ListIterator拷贝一份，修改成ConstListIterator
    • 缺点：代码冗余
  2. 利用模板特性，将Iterator改成模板
template<class T, class Ref, class Ptr>
struct ListIterator
{
    //...
	Ref operator*()
	{
		return _node->_val;
	}
    
	Ptr operator->()
	{
		return &this->_node->_val;
	}
    //...
};

template<class T>
class list
{
    //...
	public:
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;
    //...
}

相关文章