欢迎各位大佬光临本文章！！！

 

还请各位大佬提出宝贵的意见，如发现文章错误请联系冰冰，冰冰一定会虚心接受，及时改正。

本系列文章为冰冰学习编程的学习笔记，如果对您也有帮助，还请各位大佬、帅哥、美女点点支持，您的每一分关心都是我坚持的动力。

我的博客地址：bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=blog

我的gitee：冰冰棒 (bingbingsupercool) - Gitee.comhttps://gitee.com/bingbingsurercool

系列文章推荐

冰冰学习笔记：《一步一步带你实现《双向循环带头链表》》

冰冰学习笔记：《vector的简单模拟》

目录

系列文章推荐

前言

1.list的接口简介

2.list的迭代器

3.list的模拟实现

3.1insert与erase

3.2remove与clear

3.3size与resize

4.list与vector的对比

前言

        list与vector一样，都是C++中STL提供的一种容器，list的底层结构实际上为带头双向循环列表。因此，list支持在常数范围内任意位置的插入删除，相比于vector来说不需要数据的移动覆盖。但是list并不支持任意位置的随意访问，因为list底层存储空间的地址并不是连续的。list的函数接口与前面的vector和string类似，使用时可以结合文档使用。

1.list的接口简介

        list的构造函数接口有多个，支持一段迭代器区间的构建，也支持n个元素的构建。

        迭代器接口中提供了各种迭代器，但是由于list的内部地址空间并不连续，因此list的迭代器不再是简单的指针，底层进行了一系列的封装。正向迭代器的begin()指向第一个存储元素的位置，end()则指向最后一个数据的下一个位置，也就是头节点。正向迭代器进行++操作时是向后移动。

        对于反向迭代器，rbegin()指向的是最后一个元素的位置，rend()指向的则是第一个数据的位置。反向迭代器进行++操作则是向前移动。

         对于数据管理的接口，我们最常用的也就是头插尾插，头删尾删，以及任意位置的插入和删除。

        其他的接口我们如果在使用时用到，完全可以查看文档，根据文档的介绍进行使用。

2.list的迭代器

        当我们打开STL源码来了解list的时候，我们发现list的底层结构远没有我们写的带头双向循环链表那么简单。尤其是迭代器部分，STL对其进行了各种封装，让其能够向在一块连续空间上的地址一样进行使用。

        STL将list的节点结构，迭代器，以及list本身的实现封装成三个类来实现。

        那list究竟是怎么做到将不连续的地址空间变成像普通连续的地址一样进行迭代访问的呢？

        list将迭代器设计成一个类型，并通过返回对象的方式进行迭代器的创建。迭代器类型中的成员变量就是节点指针类型。并且采用模板来实现，根据不同的类型生成不同类型的迭代器。并提供构造函数，将其进行初始化。

	struct __list_iterator//迭代器
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> iterator;
		
		//类成员变量
		Node* _node;

		//构造函数
		__list_iterator(Node* node)
			:_node(node)
		{}

        C++最大的特性就是支持运算符的重载。我们将迭代器使用的运算符进行重载，在迭代器进行操作符变换的时候就会使用我们自己重载的运算符。

        例如，我们想让迭代器使用++运算符向后迭代，list本身是一个双向循环链表，当前的节点想迭代成后面的节点，只需要将当前的指针更新成next即可。所以我们的运算符可以重载成下面这样。

        iterator& operator++()//前置++it
		{
			 _node=_node->_next;
			 return *this;
		}

        有了这种思路，剩下的迭代器中使用的运算符我们都可以进行重载。

        bool operator != (const iterator& it)const
		{
			return _node != it._node;
		}
		
		bool operator ==(const iterator& it)const
		{
			return _node == it._node;
		}
        iterator& operator++(int)//后置it++
		{
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		iterator& operator--()//前置--it
		{
			_node = _node->_prev;
			return *this;
		}

		iterator& operator--(int)//后置it--
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

        迭代器包含两种，即const类型和普通类型，普通类型支持元素的读写操作，const类型只支持读操作。那么这两种迭代器返回的类型不一样又是怎么区分的呢？list是用模板参数进行了区分。由于const和普通类型返回的元素不同，因此直接将模板中添加两种模板类型，一种负责区分const类型和普通类型的引用，一种则是区分指针。并通过迭代器类型来进行推断返回哪种数据类型。

        但是，迭代器不仅要支持迭代，还有支持元素的访问，因此我们还得重载解引用操作符和箭头操作符。 

        解引用操作符好理解，就是访问迭代器指向的节点中Data。通过Ref来确定是否为const类型。

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

        对于箭头操作符的重载，我们需要注意，这里调用会省略一个箭头，因此看起来怪怪的，不好理解。我们先是使用解引用操作符找到对应的数据，然后取其地址，使其变成一个指针类型，然后返回这个指针，但是这个指针想访问数据应该还需要一个箭头操作符才能指向数据，编译器将其优化掉了，最终形成了一个箭头。

        Ptr operator ->()

		{
			return &(operator *());//&(_node->Data)
		}

3.list的模拟实现

        list的构造、拷贝、析构等函数的模拟与vector类似，这里不在一一介绍，我们主要介绍其他的函数。

3.1insert与erase

        insert函数为任意位置的插入数据，根据参数中的pos确定位置，并且在pos位置之前插入新的节点。因此，我们需要先将pos的前节点进行保存，然后创建出新节点并将数据放入新节点，此处我们采用定位new进行操作，因为定位new可以调用构造函数进行初始化。然后我们进行节点连接并返回新节点的迭代器位置。

        iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);
			prev->_next = newnode;
			newnode->_next = cur;
			newnode->_prev = prev;
			cur->_prev = newnode;
			return iterator(newnode);
		}

        erase 就是删除pos位置的节点，并返回删除前下一个位置的迭代器。首先我们要做的就是检查pos是否在合理范围内，当pos满足条件时在进行删除。

        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 iterator(next);
		}

        insert与erase实现完毕，就可以直接复用实现头插头删，尾插尾删。

        void push_back(const T& x)
		{
			insert(end(), x);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_back()
		{
			erase(--end());
		}
		void pop_front()
		{
			erase(begin());
		}

3.2remove与clear

        remove是删除链表中所有与指定val相同的元素，我们只需要遍历链表，寻找并使用erase删除即可。clear则是清除链表中所有的元素，但是并不释放头节点，析构函数才会释放头节点。

        void remove(const T& val)
		{
			iterator it = begin();
			while (it != end())
			{
				if (*it == val) { it = erase(it); }
				else { ++it; }
			}
		}
		void clear()//不清除头节点
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
        ~list()//析构
		{
			clear();
			delete _head;
			_head = nullptr;
		}

3.3size与resize

        size函数返回链表存储元素的个数，每次调用都需要遍历链表计算，因此我们应该少调用。resize则是将链表设置为指定的大小，当数值n大于size时需要进行尾插，数值n小于size时则进行尾删。

void resize(size_t n, const T& val = T())
		{
			size_t size = this->size();
			if (n < size)
			{
				size_t i = size - n;
				while (i--)
				{
					pop_back();
				}
			}
			else
			{
				size_t i =  n-size;
				while (i--)
				{
					push_back(val);
				}
			}
		}
		
		size_t max_size()const
		{
			return (size_t)-1;
		}
		size_t size()const
		{
			size_t size = 0;
			const_iterator first = begin();
			while (first != end())
			{
				++size;
				++first;
			}
			return size;
		}

4.list与vector的对比