关于标准库中的list（涉及STL的精华-迭代器的底层）

目录

关于list

list常见接口实现

? ? ? ? ? STL的精华之迭代器

---

关于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来说这可能是一个重要的因素。

常见接口：

---

list常见接口实现（参考部分g++版本下stl底层源码）

namespace dw
{
	template<class T>
	struct list_node //链表节点
	{
		list_node<T>* _prev;
		list_node<T>* _next;
		T _data;
	};

	//迭代器实现

	template<class T>
	class list
	{
		typedef list_node<T> node;
	public:
		//代码实现


	private:
		node* _head;
	};

	//------------------------------------------------
	void list_test()
	{
		;
	}

}

1.注意：类名不是类型，建议声明类型的时候都加上模板参数

举例来说这里 list_node 是类名， ??list_node<T> 是类型

如果不加上模板参数运行程序会报错

typedef list_node<T> node;

typedef list_node node;

2.注意：这里使用的 struct? 定义类，struct 定义的类默认访问权限是公开。

构造函数

无参

		void empty_init() //初始化头节点
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list()
		{
			empty_init();
		}

push_back

		void push_back(const T& x)
		{
			node* tail = _head->_prev;
			node* newnode = new node(x);

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;

		}

注意，这里测试运行会发现：

原因出在：

node* newnode = new node(x);

所以关于链表节点 list_node 的这个类也需要实现构造函数

		list_node(const T& x = T()) //这里是匿名对象调用构造函数
			:_prev(nullptr)
			,_next(nullptr)
			,_data(x)
		{}

---

? ?

?STL的精华之迭代器

? ? ? ? ?这样就完成了需要的准备工作，接下来就可以进行神奇的迭代器部分了，看完大呼 - 还可以这样玩。

? ? ? ? ?上面的代码可以通过测试以及调试观看到具体状态，那么怎么进行成员访问？

? ? ? ? ?我们知道，vector 迭代器使用的是原生指针(g++版本) vector相关迭代器的实现，因为 vector 可以看作是一块连续的物理空间，我们通过下标就可以访问到下一个元素

? ? ? ?但是链表可以这样玩吗？肯定是不可以的！所以，这里 list 迭代器的实现不能使用原生指针，而是需要一个类去进行封装。

iterator

//迭代器实现
	template<class T>
	struct __list_iterator
	{
	public:
		typedef list_node<T> node;

		typedef __list_iterator self;

		node* _node;

		__list_iterator(node* x)
			:_node(x)
		{}

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

		self& operator++() 
		{
			_node =  _node->_next;
			return *this;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

	};

注意：c++一般不喜欢内部类，所以一般都使用自定义类型

继而我们需要在 list 类进行 typedef?

typedef __list_iterator<T> iterator;

begin()

begin（）是第一个节点的位置

        iterator begin()
		{
			iterator tmp(_head->_next);
			return tmp;
		}

		

end()

end（）是头节点的位置

        iterator end()
		{
			return iterator(_head);
		}

注：这里和 begin( ) 的写法其实没什么不同，本质上是运用了匿名对象。

• ?? ??? ?其实这里可以看到，虽然vector，list 表面上都是 iterator，但是底层却千差万别，这些都源自于底层的封装

• ? ? ? ? 并且，可以明显的感觉到迭代器很好体现了类的设计价值。如果一个内置类型无法满足我们的需求，那么我们可以使用一个自定义类型去封装，然后重载运算符，继而改变它的行为

• ?? ??? ?比如说这里的 iterator 是一个节点的指针，++， * 不满足我们的需求，我们可以去进行封装, 用类去封装一个node* 重载++， * 运算符的函数

• ? ? ? ? 重载运算符函数的具体实现以及行为完全由我们自己来定义，这是自定义类型＋运算符重载＋类的定义等等的价值

? ? ? ? 其次，关于下面这句代码，我们并没有实现拷贝构造，编译器会默认生成，默认生成的拷贝构造是浅拷贝，那么，这里可以使用浅拷贝嘛？为什么没报错?

list<int>::iterator it = lt.begin();

//首先:这里是需要浅拷贝的，因为这里拷贝的是指向节点的指针

//其次，为什么没报错 ? 是因为迭代器没有写析构函数，那么为什么没写 ??

//是因为迭代器不需要释放节点。更深层次一些，为什么不需要释放节点 ?

//虽然这里迭代器有指向节点的指针，但是并不支持释放节点，因为释放节点是链表的行为

//链表会有析构函数释放节点，也可以简单把这里迭代器理解为工具，可以支持读或者写

//但是只有使用权限，并没有归属权限，所以这里浅拷贝也就没有问题了。

然后现在就可以丰富一些 迭代器 __list_iterator 这个类，后置 ++ ，--，等等

template<class T>
	struct __list_iterator
	{
	public:
		typedef list_node<T> node;

		typedef __list_iterator<T> self;

		node* _node;

		__list_iterator(node* x)
			:_node(x)
		{}

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

		self& operator++()
		{
			_node =  _node->_next;
			return *this;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

		self& operator++(int) //编译器会默认传一个整型，进行占位，更前置进行区分
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		bool operator==(const self& s)
		{
			return _node == s._node;
		}

	};

const_iterator

接下来是关于 const 修饰的迭代器，如果是下面这样环境，该怎么办？

这里的迭代器就需要使用const 进行修饰了，那么请问这样写法可不可以？

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

		iterator end() const
		{
			return iterator(_head);
		}

这里运行编译通过，但是存在一个问题，明明是const修饰，为什么还能构造迭代器?
因为这里的const修饰的是*this 也就是指向的内容，*this 是这个节点的指针，const修饰的是这个指针的本身不能被改变，也就是_head不能被改变，但是可以拷贝。

结果发现并不符合我们的预期，因为这里我们期望迭代器被 const 修饰之后内容不可修改。这里不仅可读，并且可写，显然程序是有些不正确的。

所以这里的写法是我们需要再完成一个类，也就是 __list_const_iterator

    template<class T>
	struct __list_const_iterator
	{
	public:
		typedef list_node<T> node;

		typedef __list_const_iterator<T> self;

		node* _node;

		__list_const_iterator(node* x)
			:_node(x)
		{}

		const T& operator*()
		{
			return _node->_data;
		}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

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

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		bool operator==(const self& s)
		{
			return _node == s._node;
		}

	};

注意：c++一般不喜欢内部类，所以一般都使用自定义类型

继而我们需要在 list 类进行 typedef?

typedef __list_const_iterator<T> const_iterator;

begin()

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

end()

        const_iterator end() const
		{
			return const_iterator(_head);
		}

代码程序正常运行

但是观察上面这两个类我们会发现，__list_iterator?与?__list_const_iterator

他们的区别只在于重载运算符解引用的实现不同，更细节一点只是解引用的返回值不同

__list_iterator?

?__list_const_iterator

? ? ? ? 但是却写了两个类，这样会显得代码很臃肿，会让人觉得一模一样的代码为什么要写两遍，所以这里提出了一个新的语法知识 -? -? -?添加模板参数

代码如下：

    template<class T, class Ref>
	struct __list_iterator
	{
	public:
		typedef list_node<T> node;

		typedef __list_iterator<T, Ref> self;

		node* _node;

		__list_iterator(node* x)
			:_node(x)
		{}

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

		self& operator++()
		{
			_node =  _node->_next;
			return *this;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

		self& operator++(int) //编译器会默认传一个整型，进行占位，更前置进行区分
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		bool operator==(const self& s)
		{
			return _node == s._node;
		}

	};

这样?__list_iterator?与?__list_const_iterator 就可以合并为一个类

再修改一些 list ，模板参数不同，调用逻辑也不同

        typedef __list_iterator<T, T&> iterator;

		typedef __list_iterator<T, const T&> const_iterator;

		//typedef __list_const_iterator<T> const_iterator; //注释掉

例：

? ? ? ?如果你认为到这里就结束了，那么不好意思，还差一点。因为观察库里 list 的实现，我们会发现迭代器的模板参数是三个。

附上stl部分底层源码：

template<class T, class Ref, class Ptr>
struct __list_iterator {
  typedef __list_iterator<T, T&, T*>             iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
  typedef __list_iterator<T, Ref, Ptr>           self;

  typedef bidirectional_iterator_tag iterator_category;
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef __list_node<T>* link_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

  link_type node;

  __list_iterator(link_type x) : node(x) {}
  __list_iterator() {}
  __list_iterator(const iterator& x) : node(x.node) {}

  bool operator==(const self& x) const { return node == x.node; }
  bool operator!=(const self& x) const { return node != x.node; }
  reference operator*() const { return (*node).data; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  self& operator++() { 
    node = (link_type)((*node).next);
    return *this;
  }
  self operator++(int) { 
    self tmp = *this;
    ++*this;
    return tmp;
  }
  self& operator--() { 
    node = (link_type)((*node).prev);
    return *this;
  }
  self operator--(int) { 
    self tmp = *this;
    --*this;
    return tmp;
  }
};

源码的? Ptr 是什么？因为这里不仅重载了*，还重载了 ->，那么什么时候要去调用->呢?

1.迭代器要么就是原生指针
⒉.迭代器要么就是自定义类型对原生指针的封装，模拟指针的行为

解释这个原因的话，先看一个测试用例：

这时候我们会发现，之所以会报错是因为AA这个类没有自己实现一个流插入

所以要是想让代码跑起来，有很多的解决办法

方法一便是根据AA这个类型重载一个流插入

所以回过头来也能发现，c++新增运算符重载，而不是继续使用printf函数，是因为printf函数有局限性，printf只能打印内置类型，%d，%lf等等。

但是打印也不是没有其他办法，比如说上面这种，但是看到似乎是有点怪，解引用之后﹒去访问成员
所以这样为了看起来更顺畅一些，我们需要去实现? ->

这里返回值是T*，但是如果是const迭代器呢?

所以这里就不能使用T*，而是需要新增加函数模板参数 Ptr

	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
	public:
		typedef list_node<T> node;

		typedef __list_iterator<T, Ref, Ptr> self;

		node* _node;

		__list_iterator(node* x)
			:_node(x)
		{}

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

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

		self& operator++()
		{
			_node =  _node->_next;
			return *this;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

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

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		bool operator==(const self& s)
		{
			return _node == s._node;
		}

	};

以上就是list底层源码的实现逻辑，补充一点：

这里看着是有些怪异的，因为

it-> _a1
it-> ->_a1

本来这里应该是两个 ->

一个是运算符重载的调用

一个是有了结构体的指针再使用 -> 去访问

这里为了增加代码的可读性，省略了一个-> ，可以理解为是一个特殊处理

看似是：

cout << it->_a1 << ":" << it->_a2 << endl;

实际上：

cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;

另外需要说明的点是：

迭代器用原生指针只是一个偶然，用类去封装才是一个常态

但是底层的本质都可以认为是指针，只说是嵌入了一个自定义类型去封装指针，在编译器看来是自定义类型而不是指针

并且自定义类型使用运算符只能去重载运算符，至于重载运算符函数的行为，完全是由我们自己来控制的

包括vector的迭代器，? 在g++版本下（linux系统）是原生指针，但是vs下也不是原生指针，因为vs需要重载运算符函数，比如 * 用来判断迭代器是否失效。

要注意，不同编译器底层实现不同。以上就是?stl 的精华部分，关于迭代器。
? ? ? ?

---

swap

		void swap(list<T>& tmp)
		{
			std::swap(_head, tmp._head);
		}

迭代器区间构造

        template<class Iterator>
		list(Iterator first, Iterator last)
		{
			empty_init();

			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

拷贝构造

        //现代写法
		list(const list<T>& lt)
		{
			empty_init();

			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		//传统写法
		list(const list<T>& lt)
		{
			empty_init();

			for (auto e : lt)
			{
				push_back(e);
			}
		}

赋值

		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

insert

		void insert(iterator pos, const T& x)
		{
			node* cur = pos._node;
			node* prev = cur->_prev;

			node* new_node = new node(x);

			prev->_next = new_node;
			new_node->_next = cur;
			new_node->_prev = prev;
			cur->_prev = new_node;
		}

erase

		void erase(iterator pos)
		{
			assert(pos != end());
			node* next = pos._node->_next;
			node* prev = pos._node->_prev;

			next->_prev = prev;
			prev->_next = next;
			delete pos._node;
		}

        //看需求
        iterator erase(iterator pos)
		{
			assert(pos != end());
			node* next = pos._node->_next;
			node* prev = pos._node->_prev;

			next->_prev = prev;
			prev->_next = next;
			delete pos._node;

			return iterator(next);
		}

push_front

		void push_front(const T& x)
		{
			insert(begin(), x);
		}

pop_back

		void pop_back()
		{
			erase(--end());
		}

pop_front

		void pop_front()
		{
			erase(begin());
		}

clear

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it++);
				
				//it = erase(it);  //两种方法都可以，这中 erase 需要有返回值
			}
		}

析构函数

		~list()
		{
			clear();

			delete _head;
			_head = nullptr;

		}

---

最后附上全部代码以及测试用例：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?list.h

namespace dw
{
	template<class T>
	struct list_node //链表节点
	{
		list_node<T>* _prev;
		list_node<T>* _next;
		T _data;

		list_node(const T& x = T())
			:_prev(nullptr)
			,_next(nullptr)
			,_data(x)
		{}
	};



	//迭代器实现

	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
	public:
		typedef list_node<T> node;

		typedef __list_iterator<T, Ref, Ptr> self;

		node* _node;

		__list_iterator(node* x)
			:_node(x)
		{}

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

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

		self& operator++()
		{
			_node =  _node->_next;
			return *this;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

		self& operator++(int) //编译器会默认传一个整型，进行占位，更前置进行区分
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		bool operator==(const self& s)
		{
			return _node == s._node;
		}

	};
	

	/*
	template<class T>
	struct __list_const_iterator
	{
	public:
		typedef list_node<T> node;

		typedef __list_const_iterator<T> self;

		node* _node;

		__list_const_iterator(node* x)
			:_node(x)
		{}

		const T& operator*()
		{
			return _node->_data;
		}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		bool operator!=(const self& s)
		{
			return _node != s._node;
		}

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

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		bool operator==(const self& s)
		{
			return _node == s._node;
		}

	};
	*/


	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;

		//typedef __list_const_iterator<T> const_iterator;

		void empty_init() //初始化头节点
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list()
		{
			empty_init();
		}

	
		void swap(list<T>& tmp)
		{
			std::swap(_head, tmp._head);
		}

		//现代写法
		list(const list<T>& lt)
		{
			empty_init();

			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		//传统写法
		//list(const list<T>& lt)
		//{
		//	empty_init();

		//	for (auto e : lt)
		//	{
		//		push_back(e);
		//	}
		//}

		template<class Iterator>
		list(Iterator first, Iterator last)
		{
			empty_init();

			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

		//lt2 = lt1
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		iterator begin() 
		{
			iterator tmp(_head->_next);
			return tmp;
		}

		iterator end() 
		{
			return iterator(_head);
		}

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

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		void push_back(const T& x)
		{
			node* tail = _head->_prev;
			node* newnode = new node(x);

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;

		}

		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());
			node* next = pos._node->_next;
			node* prev = pos._node->_prev;

			next->_prev = prev;
			prev->_next = next;
			delete pos._node;

			return iterator(next);
		}

		void insert(iterator pos, const T& x)
		{
			node* cur = pos._node;
			node* prev = cur->_prev;

			node* new_node = new node(x);

			prev->_next = new_node;
			new_node->_next = cur;
			new_node->_prev = prev;
			cur->_prev = new_node;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it++);
				
				//it = erase(it);  //两种方法都可以，这中 erase 需要有返回值
			}
		}

		~list()
		{
			clear();

			delete _head;
			_head = nullptr;

		}


	private:
		node* _head;
	};




	//------------------------------------------------

	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//(*it) *= 2;
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}


	void list_test1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		print_list(lt);

		list<int> lt2(lt);

		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;


		list<int> lt3 = lt2;

		for (auto e : lt3)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void list_test2()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.push_back(1000); //测试尾插
		lt.push_front(100); // 测试头插

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.pop_back(); // 测试尾删
		lt.pop_front(); //测试头删

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		auto pos = lt.begin();
		++pos;

		lt.insert(pos, 9); //测试任意位置插入
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		pos = lt.begin();
		++pos;

		lt.erase(pos); // 测试任意位置删除
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

	}

}