【C++】STL--list

目录

list的介绍

list的使用

list的构造

list iterator的使用

list capacity

list modifiers

list的迭代器失效

list模拟实现

---

list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3.与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

list的使用

list的构造

1.list(size_t n,const T& lt = T())

说明：构造的list中包含n个值为val的元素

2.list()

说明：构造空的list

3.list(const list& x)

说明：拷贝构造函数

4.list(InputIterator first,InputIterator  last)

说明：用[first,last)区间中的元素构造list

list iterator的使用

此时，我们暂且将迭代器理解成一个指针，该指针指向list中的某个节点。

begin+end：返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

rbegin+rend：返回第一个元素的reverse_iterator，即end位置，返回最后一个元素下一个位置的reverse_iterator，即begin位置

注意：

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

list capacity

empty：检测list是否为空，是返回true，否则返回false

size：返回list中有效节点个数

list modifiers

push_front：在list首元素前插入值为val的元素

pop_front：删除list中的第一个元素

push_back：在list尾部插入值为val的元素

pop_back：删除list中的最后一个元素

insert：在pos位置插入值为val的元素

erase：删除pos位置的元素

swap：交换两个list中的元素

clear：清空list中的有效元素

list的迭代器失效

我们将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){//错误示范//erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
其赋值//l.erase(it);//++it;//正确it = l.erase(it);}
}

list模拟实现

namespace ghs
{template<class T>struct ListNode{ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}ListNode<T>* _next;ListNode<T>* _prev;T _data;};template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator Self;Node* _node;ListIterator(Node* node):_node(node){}//*it//不能传值返回，*it只能传引用返回，因为除了读还有写的功能//T& operator*()Ref operator*(){return _node->_data;}//++itSelf& operator++(){_node = _node->_next;return *this;}//it++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//--itSelf& operator--(){_node = _node->_prev;return *this;}//it--Self operator--(int){Self tmp(*this);_node = _node._prev;return tmp;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it->_node;}//T* operator->()Ptr operator->(){return &_node->_data;}};//template<class T>//struct ListConstIterator//{//	typedef ListNode<T> Node;//	typedef ListConstIterator Self;//	Node* _node;//	ListConstIterator(Node* node)//		:_node(node)//	{}//	//*it//	//不能传值返回，*it只能传引用返回，因为除了读还有写的功能//	const T& operator*()//	{//		return _node->_data;//	}//	//++it//	Self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	//it++//	Self operator++(int)//	{//		Self tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	//--it//	Self& operator--()//	{//		_node = _node->_prev;//		return *this;//	}//	//it--//	Self operator--(int)//	{//		Self tmp(*this);//		_node = _node._prev;//		return tmp;//	}//	bool operator!=(const Self& it)//	{//		return _node != it._node;//	}//	bool operator==(const Self& it)//	{//		return _node == it->_node;//	}//	const T* operator->()//	{//		return &_node->_data;//	}//};template<class T>class list{typedef ListNode<T> Node;public:/*typedef ListIterator<T> iterator;typedef ListConstIterator<T> const_iterator;*/typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;//iterator begin()//{//	//匿名对象  //	return iterator(_head->_next);//}iterator begin(){return _head->_next;}iterator end(){return _head;}//如果返回值类型是const iterator，那表示迭代器本身不能被修改，而不是迭代器指向的内容不能被修改//我们需要的是迭代器指向的内容不能被修改，const iterator不是我们需要的迭代器const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}//lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//需要析构，一般就需要自己写深拷贝//不需要析构，一般就不需要自己写深拷贝，默认浅拷贝就可以void swap(list<T> lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt)//()里调用了拷贝构造{swap(lt);return *this;}//void push_back(const T& x)//{//	Node* newnode = new Node(x);//	Node* tail = _head->_prev;//	tail->_next = newnode;//	newnode->_prev = tail;//	newnode->_next = _head;//	_head->_prev = newnode;//}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());}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);//prev newnode cur newnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;_size++;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}size_t size()const{return _size;}bool empty(){return _size == 0;}//不清除头结点，只是把数据清掉void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size;};
}