list

文档链接

list与vector

list

• 优点
  • list头部、中间插入不再需要挪动数据
  • 插入数据是新增节点，不需要增容
• 缺点
  • 不支持随机访问

vector

• 优点
  • 支持下标的随机访问，间接的就很好的支持排序、二分查找、堆算法等
• 缺点
  • 头部和中间插入删除效率低
  • 插入数据时空间不够需要增容，代价大

list的本质

list的本质实际上就是一个带头双向循环链表

list() {
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}

节点

list节点存放的是上一个节点的指针、下一个节点的指针、数据。

	template <class T>
	struct __list_node {//节点的封装
		__list_node<T>* _next;
		__list_node<T>* _prev;
		T _data;

		__list_node(const T& x = T())//new 一个节点时，对节点的初始化
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x) {}
	};

迭代器

list的迭代器和string与vector的有所不同，string和vector的迭代器是一个原生指针，而list的迭代器则是一个自定义的类型，里面封装了一个节点的指针以及有关迭代器的一系列操作

	template <class T>
	struct __list_iterator {//list的迭代器实际上是一个指向节点的指针
		typedef __list_node<T> Node;
		Node* _node;

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

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

		//前置++
		__list_iterator<T>& operator++() {

			_node = _node->_next;
			return *this;
		}

		//前置--
		__list_iterator<T>& operator--() {
			_node = _node->_prev;
			return *this;
		}

		//后置++
		__list_iterator<T> operator++(int) {
			__list_iterator<T> temp(*this);
			_node = _node->_next;
			return temp;
		}

		//后置--
		__list_iterator<T> operator--(int) {
			__list_iterator<T> temp(*this);
			_node = _node->_prev;
			return temp;
		}

		//==
		bool operator==(const __list_iterator<T>& it) {
			return _node == it._node;
		}

		//!=
		bool operator!=(const __list_iterator<T>& it) {
			return _node != it._node;
		}

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

迭代器失效

在list中，插入数据的操作是不会导致迭代器失效的，因为迭代器保存的是节点的指针，插入新数据的时候，已有的内存地址并不会改变。

删除数据则会导致迭代器失效，删除节点后，原本指向的节点已经被释放，此时迭代器变成了空指针，继续访问则会导致出错。