当前位置：首页 > news >正文

初识C++|list类的使用及模拟实现

news 来源：原创 2024/9/20 16:50:03

🍬 mooridy-CSDN博客

🧁C++专栏（更新中！）

list的介绍

list的使用

list的构造

list 容量

list 访问

list 增删查改

迭代器

迭代器失效问题

list模拟实现

list与vector的对比

emplace_back和push_back的区别

list的介绍

list底层——带头双向循环链表

list的使用

list的构造

构造函数（ (constructor)）	接口说明
list (size_type n, const value_type& val = value_type())	构造的 list 中包含 n 个值为 val 的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用 [first, last) 区间中的元素构造 list

list<int> lt1;                                // 构造空列表
list<int> lt2 (4,100);                       // 构造有4个100的列表
list<int> lt3 (lt2.begin(),lt2.end());  // 用迭代器构造
list<int> lt4 (third);                       // 拷贝构造

list 容量

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

list 访问

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

list 增删查改

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置前插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

list<int> first (3,100);   
list<int> second (5,200);  it = first.begin();
first.insert(it,5);//在it前加1个5
first.insert(it,2,6);//在it前加2个6first.swap(second);

迭代器

之前我们学习vector容器时可以简单的将迭代器理解为指针。然而在list中，这有的理解显然是有失偏颇的。如list的介绍中所提到的，list的底层实现是带头双向循环链表，而我们知道链表的空间是不连续的，如果还以为迭代器是指针，那么++的位置只能是结点的下一个位置，但这个理解显然不对。

那又为什么我们却能像vector一样的去使用list的迭代器呢？
而且*就是访问的数据，++和- -就能找到结点的后一个结点和前一个结点。

我们能用类似vector迭代器的方式操作list迭代器，是因为C++的类封装和操作符重载。迭代器封装了复杂的容器遍历逻辑，通过重载++、--和*等操作符，让我们能以直观方式访问元素，而无需关心其底层实现细节。

具体是如何实现的，可以看看下面的list模拟实现部分。

在使用过程中，需注意list的迭代器只有++，--的功能，一步步的移动迭代器，是无法像vector的迭代器一样实现+或-功能进行跨越的加减。

迭代器按性质划分：

性质	代表容器	功能
单向ForwardIterator	forward_lisr/unordered_map...	++
双向BidirectionalIterator	list/map/set...	++/--
随机RandomAcessIterator	vector/string/deque	++/--/+/-

底层结构可以决定使用哪些算法。

迭代器失效问题

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

insert不会失效——只是修改了指针指向关系，而没有修改迭代器本身

erase——指向删除元素的迭代器失效

list模拟实现

//list.h
#include<iostream>
using namespace std;namespace AA
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()){_val = val;_prev = nullptr;_next=nullptr;}ListNode<T>* _prev;ListNode<T>* _next;T _val;};//List的迭代器类template<class T,class Ref, class Ptr>class ListIterator{typedef ListNode<T> Node;typedef ListIterator<T,Ref,Ptr> Self;public:ListIterator(Node* pNode = nullptr) {_pNode = pNode;}ListIterator(const Self& l) {*this = l;}Ref operator*() {return _pNode->_val;}Ptr operator->() {return &_pNode->_val;}Self& operator++() {_pNode = _pNode->_next;return *this;}Self operator++(int) {Self* tmp(*this);_pNode = _pNode->_next;return tmp;}Self& operator--() {_pNode = _pNode->_prev;return *this;}Self& operator--(int) {Self* tmp(*this);_pNode = _pNode->_prev;return tmp;}bool operator!=(const Self& l) {return _pNode != l._pNode;}bool operator==(const Self& l) {return _pNode == l._pNode;}private:Node* _pNode;};//list类template<class T>class list{typedef ListNode<T> Node;//typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;public:///// List的构造list() {_pHead = new Node;_pHead->next = _pHead;_pHead->prev = _pHead;_size = 0;}list(int n, const T& value = T()) {_pHead = new Node;Node* pcur = _pHead;for (int i = 0; i < n; i++) {Node* newnode = new Node;newnode->val = value;newnode->next = _pHead;newnode->prev = pcur;pcur->next = newnode;pcur = newnode;_pHead->prev = pcur;}_size = n;}template <class Iterator>list(Iterator first, Iterator last);list(const list<T>& l);list<T>& operator=(const list<T> l);~list() {clear();delete _pHead;_pHead = nullptr;_size = 0;}///// List Iteratoriterator begin() {return _pHead->next;}iterator end() {return _pHead->prev;}const_iterator begin() {return _pHead->next;}const_iterator end() {return _pHead->prev;}///// List Capacitysize_t size()const {return _size;}bool empty()const {return size == 0;}// List AccessT& front() {return _pHead->next->_val;}const T& front()const {return _pHead->next->_val;}T& back() {return _pHead->prev->_val;}const T& back()const {return _pHead->prev->_val;}// List Modifyvoid push_back(const T& val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T& val) { insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val) {Node* newnode = new Node;newnode->_val = val;Node* pcur = pos._pNode;Node* prev = pcur->_prev;newnode->_next = pcur;newnode->_prev = prev;prev->_next = newnode;pcur->_prev = newnode;++_size;return newnode;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos) {Node* pcur = pos._pNode;Node* prev = pcur->_prev;Node* next = pcur->_next;delete pcur;pcur = nullptr;prev->_next = next;next->_prev = prev;--_size;return next;}void clear() {Node* pcur = _pHead->next;while (pcur!=_pHead) {pcur = erase(pcur);}}void swap(list<T>& l) {std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:size_t _size;Node* _pHead;};
};

list与vector的对比

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率 O(1)	不支持随机访问，访问某个元素效率 O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为 O(N) ，插入时有可能需要增容，增容需要开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为 O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针 ( 节点指针 ) 进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
应用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问