C++笔记 - - list的模拟实现和使用

目录

1.list的介绍和使用

1.1 list的介绍

 1.2 list的使用

1.2.1 list的构造

1.2.2 list的迭代器使用

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

1.2.6 list中的iterator迭代器失效问题

2.list的模拟实现

节点的类模板：

list的类模板：

迭代器的类模板

1.list的介绍和使用

1.1 list的介绍

首先看一下文档当中是怎么说的

list的文档介绍

 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素) 

1.2 list的使用

1.2.1 list的构造

explicit list (const allocator_type& alloc = allocator_type());

explicit list (size_type n, const value_type& val = value_type(),
                const allocator_type& alloc = allocator_type());

template 
  list (InputIterator first, InputIterator last,
         const allocator_type& alloc = allocator_type());

list (const list& x);

1.2.2 list的迭代器使用

注意：begin/end是正向迭代器，对迭代器执行++操作，迭代器向后移动

rbegin/rend是反向迭代器，对迭代器执行++操作，迭代器向前移动

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

1.2.6 list中的iterator迭代器失效问题

在list中，因为是一个个单独的节点构成，所以迭代器指向的是一个单独的节点。迭代器失效即迭代器指向的节点无效，节点被删除了。list底层是带头双向循环链表，进行插入迭代器不会失效，只有进行删除时才会失效，并且失效的只有指向被删除的节点的迭代器，其他迭代器不受到影响。

2.list的模拟实现

list的底层是使用带头双向循环链表实现的

节点的类模板：

template<class T>
	struct list_node//这个类需要被外部访问，使用struct
	{
		typedef list_node Node;
		//成员变量
		T _val;
		list_node* _next;//类类型指针,指向自己的下一个节点
		list_node* _prev;
		//成员函数
		list_node(const T& val = T())//将参数val存入_val中
			:_val(val),
			_next(nullptr),
			_prev(nullptr)
		{
		}
	};

成员变量：_val存储有效数据，_prev/_next分别指向前一个节点和后一个节点

构造函数：将_val传入构造，无参的val就根据模板参数T创建匿名对象

list的类模板：

template<class T>
	class list
	{
		typedef list_node Node;
	public:
		typedef __list_iterator iterator;
		typedef __list_iteratorconst T&, const T*> const_iterator;
		void first_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		list()
		{
			first_init();
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		void swap(list& tmp)
		{
			std::swap(_head, tmp._head);
		}
		bool empty()
		{
			return _head->_next == nullptr;
		}
		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			first_init();
			while (first != last)
			{
				push_back(first._node.val);
				first++;
			}
		}
		list(const list& lt)
		{
			first_init();
			list tmp(lt.begin(), lt.end());
			swap(tmp);
		}
		list& operator=(list lt)
		{
			swap(lt);
			return *this;
		}
		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);
		}
		iterator insert(const iterator& pos, const T& val)
		{
			//申请节点
			Node* newnode = new Node(val);
			Node* front = pos._node->_prev;
			//进入链表
			newnode->_next = pos._node;
			newnode->_prev = front;
			front->_next = newnode;
			pos._node->_prev = newnode;
			return iterator(newnode);
		}
		void push_back(const T& val)
		{
			insert(end(), val);//尾差，传_head位置的迭代器
		}
		void push_front(const T& val)
		{
			insert(begin(), val);//头插，传第一个元素的迭代器
		}
		iterator erase(iterator pos)
		{
			assert(pos != end());
			//删除节点
			Node* front = pos._node->_prev;
			Node* back = pos._node->_next;
			delete pos._node;
			//链接链表
			front->_next = back;
			back->_prev = front;
			return iterator(back);
		}
		void pop_back()
		{
			erase(iterator(_head->_prev));//尾删，传最后一个位置的迭代器
		}
		void pop_front()
		{
			erase(begin());//头删，传第一个位置的迭代器
		}
	private:
		Node* _head;
	};

迭代器的类模板

template<class T, class Ref, class Ptr>//ref引用，ptr指针
	struct __list_iterator//迭代器需要被外部访问，使用struct
	{
		typedef __list_iterator iterator;
		typedef list_node Node;
		//成员变量
		Node* _node;
 
		__list_iterator(Node* node)//传节点的指针做形参，默认析构函数不对指针类型做处理
			:_node(node)
		{
		}
		bool operator!=(const iterator& it)//两个迭代器使用!=实际比较的是他们的指向是否指向同一节点
		{
			return _node != it._node;
		}
		bool operator==(const iterator& it)//加const可以匹配const_iterator类型，加引用表示对类的成员不可做修改
		{
			return _node == it._node;
		}
 
		iterator& operator++()//前置++返回++后的迭代器
		{
			_node = _node->_next;
			return *this;
		}
		iterator operator++(int)//后置++返回++前的迭代器  传值传参，因为tmp迭代器是临时对象，临时对象出了函数作用域会被销毁
		{
			iterator tmp(_node);
			_node = _node->_next;
			return tmp;
		}
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		iterator operator--(int)
		{
			iterator tmp(_node);
			_node = _node->_prev;
			return tmp;
		}
 
		Ref operator*()//返回节点中_val的引用，因为val可能是一个自定义类型，传值返回会发生拷贝
		{
			return _node->_val;
		}
 
		Ptr operator->()
		{
			return &(operator*());
		}
	};