【C++】一篇文章带你深入了解list

在这里插入图片描述

目录

  • 一、list的介绍
  • 二、 标准库中的list类
    • 2.1 list的常见接口说明
      • 2.1.1 list对象的常见构造
        • 2.1.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/list/list/list/)
        • 2.1.1.2 [有参构造函数(构造并初始化n个val)](https://legacy.cplusplus.com/reference/list/list/list/)
        • 2.1.1.3 [有参构造函数(使用迭代器进行初始化构造)](https://legacy.cplusplus.com/reference/list/list/list/)
        • 2.1.1.4 [拷贝构造函数](https://legacy.cplusplus.com/reference/list/list/list/)
      • 2.1.2 list iterator的使用
        • 2.1.2.1 [begin()](https://legacy.cplusplus.com/reference/list/list/begin/) + [end()](https://legacy.cplusplus.com/reference/list/list/end/)
        • 2.1.2.2 [rbegin()](https://legacy.cplusplus.com/reference/list/list/rbegin/) + [rend()](https://legacy.cplusplus.com/reference/list/list/rend/)
      • 2.1.3 list对象的容量操作
        • 2.1.3.1 [empty()函数](https://legacy.cplusplus.com/reference/list/list/empty/)
        • 2.1.3.2 [size()函数](https://legacy.cplusplus.com/reference/list/list/size/)
      • 2.1.4 list对象的增删查改及访问
        • 2.1.4.1 [push_front()函数](https://legacy.cplusplus.com/reference/list/list/push_front/)
        • 2.1.4.2 [pop_front()函数](https://legacy.cplusplus.com/reference/list/list/pop_front/)
        • 2.1.4.3 [push_back()函数](https://legacy.cplusplus.com/reference/list/list/push_back/)
        • 2.1.4.4 [pop_back()函数](https://legacy.cplusplus.com/reference/list/list/pop_back/)
        • 2.1.4.5 [insert()函数](https://legacy.cplusplus.com/reference/list/list/insert/)
        • 2.1.4.6 [erase()函数](https://legacy.cplusplus.com/reference/list/list/erase/)
        • 2.1.4.7 [swap()函数](https://legacy.cplusplus.com/reference/list/list/swap/)
        • 2.1.4.8 [clear()函数](https://legacy.cplusplus.com/reference/list/list/clear/)
        • 2.1.4.9 [front()函数](https://legacy.cplusplus.com/reference/list/list/front/) + [back()函数](https://legacy.cplusplus.com/reference/list/list/back/)
      • 2.1.5 list的迭代器失效
  • 三、list的模拟实现
    • 3.1 list 节点类的实现
    • 3.2 list 中默认成员函数的实现
    • 3.3 list 中 size、empty 和 swap 函数的实现
    • 3.4 list 中 迭代器类 的实现
    • 3.5 list 中 迭代器 、 范围构造函数 和 clear 函数 的实现
    • 3.6 list 中 insert 和 erase 的实现
    • 3.7 list 中 push_back、pop_back、push_front 和 pop_front 函数的实现
    • 3.8 list 中 反向迭代器类 和 反向迭代器 的实现
    • 3.9 list 实现汇总及函数测试
  • 四、 list 与 vector 的对比
  • 结尾

一、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类

2.1 list的常见接口说明

2.1.1 list对象的常见构造

2.1.1.1 无参构造函数
list();

int main()
{list<int> l;return 0;
}

在这里插入图片描述

2.1.1.2 有参构造函数(构造并初始化n个val)
list (size_type n, const value_type& val = value_type());

int main()
{list<int> l(5, 4);return 0;
}

在这里插入图片描述

2.1.1.3 有参构造函数(使用迭代器进行初始化构造)
template <class InputIterator>list (InputIterator first, InputIterator last);

int main()
{string s("Love");list<int> l(s.begin(), s.end());return 0;
}

在这里插入图片描述

2.1.1.4 拷贝构造函数
list (const list& x);

int main()
{list<int> l1(5,6);list<int> l2(l1);return 0;
}

在这里插入图片描述

2.1.2 list iterator的使用

2.1.2.1 begin() + end()
	  iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iteratoriterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iterator

int main()
{list<int> l;for (int i = 0; i < 10; i++){l.push_back(i);}list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << ' ';++it;}cout << endl;return 0;
}

在这里插入图片描述

2.1.2.2 rbegin() + rend()
	  reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator 

int main()
{list<int> l;for (int i = 0; i < 10; i++){l.push_back(i);}list<int>::reverse_iterator it = l.rbegin();while (it != l.rend()){cout << *it << ' ';++it;}cout << endl;return 0;
}

在这里插入图片描述

注意：

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

2.1.3 list对象的容量操作

2.1.3.1 empty()函数
bool empty() const;         判断是否为空

int main()
{list<int> l;cout << l.empty() << endl;l.push_back(1);cout << l.empty() << endl;return 0;
}

在这里插入图片描述

2.1.3.2 size()函数
size_type size() const;      获取数据个数

int main()
{list<int> l;cout << l.size() << endl;for (int i = 0; i < 10; i++){l.push_back(i);}cout << l.size() << endl;return 0;
}

2.1.4 list对象的增删查改及访问

2.1.4.1 push_front()函数
void push_front (const value_type& val);  头插

int main()
{list<int> l;l.push_front(1);l.push_front(2);l.push_front(3);l.push_front(4);for (auto e : l){cout << e << ' ';}cout << endl;return 0;
}

在这里插入图片描述

2.1.4.2 pop_front()函数
void pop_front();  头删

在这里插入图片描述

2.1.4.3 push_back()函数
void push_back (const value_type& val);   尾插

int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);for (auto e : l){cout << e << ' ';}cout << endl;return 0;
}

在这里插入图片描述

2.1.4.4 pop_back()函数
void pop_back();  尾删

int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);for (auto e : l){	cout << e << ' ';	}cout << endl;l.pop_back();for (auto e : l){	cout << e << ' ';	}cout << endl;return 0;
}

在这里插入图片描述

2.1.4.5 insert()函数
iterator insert (iterator position, const value_type& val);
insert()函数能够在position之前插入val，并返回插入数据位置的 iterator void insert (iterator position, size_type n, const value_type& val);
insert()函数能够在position之前插入 n 个 val             template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last);
insert()函数能够在position之前插入一段迭代器区间的数据       		

int main()
{list<int> l;string s("Love");l.push_back(1);l.push_back(2);for (auto e : l){	cout << e << ' ';	}cout << endl;// insert()函数能够在position之前插入val，并返回插入数据位置的 iterator cout << *(l.insert(l.begin(), 20)) << endl;for (auto e : l){cout << e << ' ';}cout << endl;// insert()函数能够在position之前插入 n 个 val        l.insert(++l.begin() , 3 ,30);for (auto e : l){cout << e << ' ';}cout << endl;// insert()函数能够在position之前插入一段迭代器区间的数据       		l.insert(++l.begin(), s.begin() , s.end());for (auto e : l){cout << e << ' ';}cout << endl;return 0;
}

在这里插入图片描述

2.1.4.6 erase()函数
iterator erase (iterator position);
erase()函数能够删除在position位的的数据，并返回删除数据后面数据位置的 iteratoriterator erase (iterator first, iterator last);
erase()函数能够删除在迭代器区间 [first,last) 的的数据，并返回删除数据后面数据位置的 iterator             

int main()
{list<int> l;for (int i = 0; i < 10; i++){l.push_back(i);}cout << endl;for (auto e : l){cout << e << ' ';}cout << endl;// erase()函数能够删除在position位的的数据// 并返回删除数据后面数据位置的 iteratorcout << *(l.erase(l.begin())) << endl;for (auto e : l){cout << e << ' ';}cout << endl;// erase()函数能够删除在迭代器区间 [first,last) 的的数据// 并返回删除数据后面数据位置的 iterator        cout << *(l.erase(++l.begin(),--l.end())) << endl;for (auto e : l){cout << e << ' ';}cout << endl;return 0;
}

在这里插入图片描述

2.1.4.7 swap()函数
void swap (list& x);
交换两个list的数据空间

int main()
{list<int> l1(4, 10);list<int> l2(5, 5);for (auto e : l1){	cout << e << ' ';	}cout << endl;for (auto e : l2){	cout << e << ' ';	}cout << endl;l1.swap(l2);for (auto e : l1){	cout << e << ' ';	}cout << endl;for (auto e : l2){	cout << e << ' ';	}cout << endl;return 0;
}

在这里插入图片描述

2.1.4.8 clear()函数
void clear();
清除list中的有效数据

int main()
{list<int> l(4, 10);cout << l.size() << endl;l.clear();cout << l.size() << endl;return 0;
}

在这里插入图片描述

2.1.4.9 front()函数 + back()函数
访问list中的第一个数据reference front();
const_reference front() const;访问list中的最后一个数据reference back();
const_reference back() const;

int main()
{list<int> l;for (int i = 0; i < 10; i++){l.push_back(i);}cout << "front:" << l.front() << endl;cout << "back:" << l.back() << endl;return 0;
}

在这里插入图片描述

2.1.5 list的迭代器失效

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

int main()
{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;}return 0;
}// 改正
int main()
{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()){l.erase(it++); // it = l.erase(it);}
}

三、list的模拟实现

3.1 list 节点类的实现

namespace aj
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()):_val(val){}ListNode<T>* _prev = nullptr;ListNode<T>* _next = nullptr;T _val;};
};

3.2 list 中默认成员函数的实现

namespace aj
{//listtemplate<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:// List的构造list(){CreateHead();}// 构造并用n个val初始化list(int n, const T& value = T()){CreateHead();while (n--){push_back(value);}}// 链表的拷贝构造// list(const list<T>& l)list(list<T>& l){CreateHead();for (auto e : l){push_back(e);}}list<T>& operator=(const list<T> l){swap(l);return *this;}~list(){clear();delete _head;_head = nullptr;}void swap(list<T>& l){std::swap(_head, l._head);std::swap(_size, l._size);}private:void CreateHead(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}PNode _head;    // 头结点int _size;      // 记录链表中节点的个数};
};

3.3 list 中 size、empty 和 swap 函数的实现

namespace aj
{template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:size_t size()const{return size;}bool empty()const{return _head->_next == _head && _head->_prev == _head;}void swap(list<T>& l){std::swap(_head, l._head);std::swap(_size, l._size);}private:void CreateHead(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}PNode _head;    // 头结点int _size;      // 记录链表中节点的个数};
};

3.4 list 中 迭代器类 的实现

namespace aj
{//List的迭代器类//template<class T>template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;// 成员变量PNode _pNode;public:// 迭代器的构造函数ListIterator(PNode pNode = nullptr):_pNode(pNode){}Ref operator*(){return _pNode->_val;}Ptr operator->(){return &(_pNode->_val);}Self& operator++(){_pNode = _pNode->_next;return *this;}Self operator++(int){Self tmp(*this);++* this;return tmp;}Self& operator--(){_pNode = _pNode->_prev;return *this;}Self operator--(int){Self tmp(*this);--* this;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}};
};

3.5 list 中 迭代器 、 范围构造函数 和 clear 函数 的实现

namespace aj
{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;template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(first._pNode->_val);++first;}}// List Iteratoriterator begin(){// return iterator(_head->_next);return _head->_next;}iterator end(){// return iterator(_head);return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}void clear(){list<T>::iterator lit = begin();while (lit != end()){lit = erase(lit);}}private:void CreateHead(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}PNode _head;    // 头结点int _size;      // 记录链表中节点的个数};
};

3.6 list 中 insert 和 erase 的实现

namespace aj
{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;// 在pos位置前插入值为val的节点,返回插入新节点的位置iterator insert(iterator pos, const T& val){// 通过迭代器找到所需的节点指针Node* cur = pos._pNode;Node* prev = cur->_prev;// 创建新的节点Node* newnode = new Node(val);// 节点间相互连接newnode->_prev = prev;prev->_next = newnode;cur->_prev = newnode;newnode->_next = cur;// 节点数量++_size++;//return iterator(newnode);return newnode;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){assert(_size > 0);// 找到所需要的节点指针Node* cur = pos._pNode;Node* next = cur->_next;Node* prev = cur->_prev;// 节点相互连接next->_prev = prev;prev->_next = next;// 删除节点delete cur;cur = nullptr;// 减少节点数目--_size;// 返回删除节点的下一个位置// return iterator(next);return next;}private:void CreateHead(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}PNode _head;    // 头结点int _size;      // 记录链表中节点的个数};
};

3.7 list 中 push_back、pop_back、push_front 和 pop_front 函数的实现

namespace aj
{template<class T>class list{public:typedef ListNode<T> Node;typedef Node* PNode;void 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()); }private:PNode _head;    // 头结点int _size;      // 记录链表中节点的个数};
};

3.8 list 中 反向迭代器类 和 反向迭代器 的实现

反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

注意:反向迭代器类可以被所有的容器封装成反向迭代器使用。

下面两种反向迭代器的实现虽然不同，但是功能是相同的。反向迭代器类的实现不同，那么对应封装迭代器的时候也要做出相应的改变。

在这里插入图片描述

reverse_iterator.h 反向迭代器非对称版本

#pragma once// 不对称版本
namespace aj
{// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{typedef Reverse_iterator<Iterator,Ref,Ptr> Self;Reverse_iterator(const Iterator& it):_it(it){}Ref operator*(){return *_it;}Ptr operator->(){return _it.operator->();}Self& operator++(){--_it;return *this;}Self operator++(int){Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self tmp(*this);++_it;return tmp;}bool operator!=(const Self& s){return _it != s._it;}bool operator==(const Self& s){return _it == s._it;}Iterator _it;};
}

list.h 反向迭代器非对称版本

#include"reverse_iterator.h"namespace aj
{template<class T>class list{public:typedef ListNode<T> Node;typedef Node* PNode;public:// typedef ListIterator<T> iterator;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;public:// reverse_iterator 不对称版本reverse_iterator rbegin(){// return iterator(_head->_next);return --end();    //这里可以使用--end()也可以使用end()-1，但是没有写operator-()}                      //这里就使用--end()，这里能使用--end()的原因是//end()返回传值返回的自定义类型的临时对象，具有常性，是常量//但是这里有编译器的特殊处理//使得const对象可以调用非const成员函数reverse_iterator rend(){// return iterator(_head);return end();}const_reverse_iterator rbegin()const{return --end();}const_reverse_iterator rend()const{return end();}private:void CreateHead(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}PNode _head;    // 头结点int _size;      // 记录链表中节点的个数};
};

reverse_iterator.h 反向迭代器对称版本

#pragma once
// 对称版本
namespace aj
{// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{typedef Reverse_iterator<Iterator,Ref,Ptr> Self;Reverse_iterator(const Iterator& it):_it(it){}Ref operator*(){Iterator tmp(_it);return *--tmp;}Ptr operator->(){return --_it.operator->();}Self& operator++(){--_it;return *this;}Self operator++(int){Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self tmp(*this);++_it;return tmp;}bool operator!=(const Self& s){return _it != s._it;}bool operator==(const Self& s){return _it == s._it;}Iterator _it;};
}

list.h 反向迭代器对称版本

#include"reverse_iterator.h"namespace aj
{template<class T>class list{public:typedef ListNode<T> Node;typedef Node* PNode;public:// typedef ListIterator<T> iterator;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;public:// reverse_iterator 对称版本reverse_iterator rbegin(){// return iterator(_head->_next);return end();}reverse_iterator rend(){// return iterator(_head);return begin();}const_reverse_iterator rbegin()const{return end();}const_reverse_iterator rend()const{return begin();}private:void CreateHead(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}PNode _head;    // 头结点int _size;      // 记录链表中节点的个数};
};

3.9 list 实现汇总及函数测试

reverse_iterator.h

#pragma once// 不对称版本
//namespace aj
//{
//	// 适配器 -- 复用
//	template<class Iterator, class Ref, class Ptr>
//	struct Reverse_iterator
//	{
//		typedef Reverse_iterator<Iterator,Ref,Ptr> Self;
//
//		Reverse_iterator(const Iterator& it)
//			:_it(it)
//		{}
//
//		Ref operator*()
//		{
//			return *_it;
//		}
//
//		Ptr operator->()
//		{
//			return _it.operator->();
//		}
//
//		Self& operator++()
//		{
//			--_it;
//			return *this;
//		}
//
//		Self operator++(int)
//		{
//			Self tmp(*this);
//			--_it;
//			return tmp;
//		}
//
//		Self& operator--()
//		{
//			++_it;
//			return *this;
//		}
//
//		Self operator--(int)
//		{
//			Self tmp(*this);
//			++_it;
//			return tmp;
//		}
//
//		bool operator!=(const Self& s)
//		{
//			return _it != s._it;
//		}
//
//		bool operator==(const Self& s)
//		{
//			return _it == s._it;
//		}
//		Iterator _it;
//	};
//}// 对称版本
namespace aj
{// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{typedef Reverse_iterator<Iterator,Ref,Ptr> Self;Reverse_iterator(const Iterator& it):_it(it){}Ref operator*(){Iterator tmp(_it);return *--tmp;}Ptr operator->(){return --_it.operator->();}Self& operator++(){--_it;return *this;}Self operator++(int){Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self tmp(*this);++_it;return tmp;}bool operator!=(const Self& s){return _it != s._it;}bool operator==(const Self& s){return _it == s._it;}Iterator _it;};
}

list.h

#pragma once#include<iostream>
#include<assert.h>
#include <string>
#include <vector>
using namespace std;#include"reverse_iterator.h"namespace aj
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()):_val(val){}ListNode<T>* _prev = nullptr;ListNode<T>* _next = nullptr;T _val;};//List的迭代器类//template<class T>template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T ,Ref , Ptr> Self;// 成员变量PNode _pNode;// typedef ListIterator<T, Ref, Ptr> Self;public:// 迭代器的构造函数ListIterator(PNode pNode = nullptr):_pNode(pNode){}Ref operator*(){return _pNode->_val;}Ptr operator->(){return &(_pNode->_val);}Self& operator++(){_pNode = _pNode->_next;return *this;}Self operator++(int){Self tmp(*this);++* this;return tmp;}Self& operator--(){_pNode = _pNode->_prev;return *this;}Self operator--(int){Self tmp(*this);--* this;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}};//list类template<class T>class list{public:typedef ListNode<T> Node;typedef Node* PNode;public:// typedef ListIterator<T> iterator;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator,const T&,const T*> const_reverse_iterator;public:///// List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();while (n--){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(first._pNode->_val);++first;}}// 链表的拷贝构造// list(const list<T>& l)list(list<T>& l){CreateHead();for (auto e : l){push_back(e);}}//list<T>& operator=(const list<T> l)list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _head;_head = nullptr;}///// List Iteratoriterator begin(){// return iterator(_head->_next);return _head->_next;}iterator end(){// return iterator(_head);return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;} reverse_iterator 不对称版本//reverse_iterator rbegin()//{//    // return iterator(_head->_next);//    return --end();    //这里可以使用--end()也可以使用end()-1，但是没有写operator-()//}                      //这里就使用--end()，这里能使用--end()的原因是//                       //end()返回传值返回的自定义类型的临时对象，具有常性，是常量//                       //但是这里有编译器的特殊处理//                       //使得const对象可以调用非const成员函数//reverse_iterator rend()//{//    // return iterator(_head);//    return end();//}//const_reverse_iterator rbegin()const//{//    return --end();//}//const_reverse_iterator rend()const//{//    return end();//}// reverse_iterator 对称版本reverse_iterator rbegin(){// return iterator(_head->_next);return end();}reverse_iterator rend(){// return iterator(_head);return begin();}const_reverse_iterator rbegin()const{return end();}const_reverse_iterator rend()const{return begin();}///// List Capacitysize_t size()const{return size;}bool empty()const{return _head->_next == _head && _head->_prev == _head;}// List AccessT& front(){assert(_head->_next != _head);return _head->_next->_val;}const T& front()const{assert(_head->_next != _head);return _head->_next->_val;}T& back(){assert(_head->_prev != _head);return _head->_prev->_val;}const T& back()const{assert(_head->_prev != _head);return _head->_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* cur = pos._pNode;Node* prev = cur->_prev;// 创建新的节点Node* newnode = new Node(val);// 节点间相互连接newnode->_prev = prev;prev->_next = newnode;cur->_prev = newnode;newnode->_next = cur;// 节点数量++_size++;//return iterator(newnode);return newnode;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){assert(_size > 0);// 找到所需要的节点指针Node* cur = pos._pNode;Node* next = cur->_next;Node* prev = cur->_prev;// 节点相互连接next->_prev = prev;prev->_next = next;// 删除节点delete cur;cur = nullptr;// 减少节点数目--_size;// 返回删除节点的下一个位置// return iterator(next);return next;}void clear(){list<T>::iterator lit = begin();while (lit != end()){lit = erase(lit);}}void swap(list<T>& l){std::swap(_head, l._head);std::swap(_size, l._size);}private:void CreateHead(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}PNode _head;    // 头结点int _size;      // 记录链表中节点的个数};struct AA{AA(int a1 = 0 , int a2 = 0):_a1(a1),_a2(a2){}int _a1;int _a2;};//template<class T>//void print_list(const list<T>& l)//{//    // list<T>未实例化的类模板，编译器不能去他里面去找//    // 那么编译器就无法确定这里的//    // const_iterator是静态变量还是内嵌类型//    // 加上typename就相当于告诉编译器这里是内嵌类型//    // 等list<T>初始化后再到类中去取//    typename list<T>::const_iterator it = l.begin();//    while (it != l.end())//    {//        cout << *it << ' ';//        ++it;//    }//    cout << endl;//}template<class Container>void print_container(const Container& l){typename Container::const_iterator it = l.begin();while (it != l.end()){cout << *it << ' ';++it;}cout << endl;}///// 测试无参构造、n个val的构造、迭代器区间构造void test_list1(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);list<int> l1(10, 20);list<int> l2(++l1.begin(), --l1.end());for (auto e : l){cout << e << ' ';}cout << endl;for (auto e : l1){cout << e << ' ';}cout << endl;for (auto e : l2){cout << e << ' ';}cout << endl;}// 测试 insert push_back push_front// 测试 iterator 范围for// 测试 operator !=  operator* void test_list2(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);l.push_front(10);l.push_front(20);list<int>::iterator lit = l.begin();while (lit != l.end()){cout << *lit << ' ';++lit;}cout << endl;for (auto& e : l){e += 10;cout << e << ' ';}cout << endl;}// 测试 erase pop_back pop_frontvoid test_list3(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);for (auto e : l){cout << e << ' ';}cout << endl;l.pop_back();for (auto e : l){cout << e << ' ';}cout << endl;l.pop_front();for (auto e : l){cout << e << ' ';}cout << endl;}// 测试 operator++  operator++(int)// 测试 operator--  operator--(int)void test_list4(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);list<int>::iterator lit1 = l.begin();cout << *(lit1++) << endl;cout << *(++lit1) << endl;list<int>::iterator lit2 = l.end();cout << *(--lit2) << endl;cout << *(lit2--) << endl;cout << endl;}// 测试 operator==  operator!=void test_list5(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);list<int>::iterator lit = l.end();cout << (lit == lit) << endl;cout << (lit != lit) << endl;cout << endl;}void test_list6(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);for (auto e : l){cout << e << ' ';}cout << endl;cout << l.front() << ' ' << l.back() << endl;l.pop_back();l.pop_front();for (auto e : l){cout << e << ' ';}cout << endl;cout << l.front() << ' ' << l.back() << endl;l.pop_back();l.pop_front();for (auto e : l){cout << e << ' ';}cout << endl;cout << l.front() << ' ' << l.back() << endl;}// 测试 operator->void test_list7(){list<AA> l1;l1.push_back(AA(1, 1));l1.push_back(AA(2, 2));l1.push_back(AA(3, 3));l1.push_back(AA(4, 4));list<AA>::iterator it = l1.begin();while (it != l1.end()){cout << it->_a1 << ' ' << it->_a2 << endl;++it;}}// 测试拷贝构造和赋值重载  void test_list8                                                                      (){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);// 拷贝构造l2list<int> l2(l1);// 输出l1和l2的值for (auto e : l1){cout << e << ' ';}cout << endl;for (auto e : l2){cout << e << ' ';}cout << endl;// l2中的值都*10，并输出for (auto& e : l2){e *= 10;cout << e << ' ';}cout << endl;// 将l2赋值给l1l1 = l2;// 输出l1和l2的值for (auto e : l1){cout << e << ' ';}cout << endl;for (auto e : l2){cout << e << ' ';}cout << endl;}// 测试print_containervoid test_list9(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);print_container(l1);list<string> l2;l2.push_back("1111111111111111111");l2.push_back("2222222222222222222");l2.push_back("3333333333333333333");l2.push_back("4444444444444444444");print_container(l2);vector<string> v;v.push_back("1111111111111111111");v.push_back("2222222222222222222");v.push_back("3333333333333333333");v.push_back("4444444444444444444");print_container(v);}void test_list10(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);list<int>::reverse_iterator it = l1.rbegin();while (it != l1.rend()){cout << *it << ' ';++it;}cout << endl;}
};

四、 list 与 vector 的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

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

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/2978710.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

TR5 - Transformer的位置编码

TR5 - Transformer的位置编码

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 目录 前言什么是位置编码1. 定义2. 三角函数3. 位置编码公式4. 位置编码示例 可视化理解位置编码1. 代码实现2. 观察不同位置对应的曲线3. 整句话的位置编码可…
阅读更多...
ffmpeg支持MP3编码的方法

ffmpeg支持MP3编码的方法

目录 现象 解决办法 如果有编译包没有链接上的情况 现象 解决办法 在ffmpeg安装包目录下 &#xff0c;通过./configure --list-encoders 和 ./configure --list-decoders 命令可以看到&#xff0c;ffmpeg只支持mp3解码&#xff0c;但是不支持mp3编码。 上网查寻后发现&…
阅读更多...
新的全息技术突破计算障碍

新的全息技术突破计算障碍

一种突破性的方法利用基于Lohmann透镜的衍射模型实时创建计算机生成全息图&#xff08;CGH&#xff09;&#xff0c;在保持3D可视化质量的同时&#xff0c;大大降低了计算负荷要求。 全息显示为制作逼真的三维图像提供了一条令人兴奋的途径&#xff0c;这种图像给人以连续深度…
阅读更多...
【WEB前端2024】开源元宇宙：乔布斯3D纪念馆-第9课-摆件美化

【WEB前端2024】开源元宇宙：乔布斯3D纪念馆-第9课-摆件美化

【WEB前端2024】开源元宇宙&#xff1a;乔布斯3D纪念馆-第9课-摆件美化 使用dtns.network德塔世界&#xff08;开源的智体世界引擎&#xff09;&#xff0c;策划和设计《乔布斯超大型的开源3D纪念馆》的系列教程。dtns.network是一款主要由JavaScript编写的智体世界引擎&#…
阅读更多...
合合信息Embedding模型：引领中文文本向量化技术新高度

合合信息Embedding模型：引领中文文本向量化技术新高度

目录 &#x1f345;前言&#x1f353;赛事含金量&#x1f353;Embedding技术简介&#x1f353;Embedding在大模型中的价值&#x1f353;合合信息Embedding模型特点及优势&#x1f353;合合信息Embedding模型测试&#x1f353;技术突破&#x1f353;公司介绍 &#x1f345;总结 …
阅读更多...
Matplotlib官网查阅资料

Matplotlib官网查阅资料

Matplotlib官网详细的地址&#xff1a; 英文文档&#xff1a;https://matplotlib.org/stable/contents.html中文文档&#xff1a;https://www.matplotlib.org.cn/ Matplotlib英文官网: 查找属性&#xff1a; 1.进入官网。 2.查找参数属性。 Matplotlib中文官网: 查找属性:…
阅读更多...
光纤、以太网电缆和 DSL 的比较：技术指南

光纤、以太网电缆和 DSL 的比较：技术指南

了解光纤、以太网电缆和 DSL 之间的差异对于做出有关互联网连接的明智决策至关重要。本技术指南对这些技术进行了全面比较&#xff0c;讨论了它们的独特功能、性能指标和应用。它旨在为您提供必要的知识&#xff0c;以选择最适合您的特定需求的选项。 光纤、以太网电缆和 DSL …
阅读更多...
Qwen1.5微调

Qwen1.5微调

引子 由于工作上需要&#xff0c;一直在用Qwen做大模型推理&#xff0c;有个再训练的需求&#xff0c;特此琢磨下Qwen的训练。OK&#xff0c;我们开始吧。 一、安装环境 查看显卡驱动版本 根据官网推荐 OK&#xff0c;docker在手&#xff0c;天下我有。 docker pull qwenll…
阅读更多...
Recommended Azure Monitors

Recommended Azure Monitors

General This document describes the recommended Azure monitors which can be implemented in Azure cloud application subscriptions. SMT incident priority mapping The priority “Blocker” is mostly used by Developers to prioritize their tasks and its not a…
阅读更多...
论文辅助笔记：处理geolife数据

论文辅助笔记：处理geolife数据

论文笔记&#xff1a;Context-aware multi-head self-attentional neural network model fornext location prediction-CSDN博客 对应命令行里 python preprocessing/geolife.py 20 这一句 1 读取geolife数据 pfs, _ read_geolife(config["raw_geolife"], print_…
阅读更多...
Spring的过滤器、拦截器、切面区别及案例分析

Spring的过滤器、拦截器、切面区别及案例分析

Spring的过滤器、拦截器、切面 三者的区别&#xff0c;以及对应案例分析 一、三者的实现方式 1.1 过滤器 xxxFilter 过滤器的配置比较简单&#xff0c;直接实现Filter接口即可&#xff0c;也可以通过WebFilter注解实现对特定URL的拦截&#xff0c;Filter接口中定义了三个方法…
阅读更多...
工作记录：vue-grid-layout 修改 margin 导致 item 高度剧烈变化

工作记录：vue-grid-layout 修改 margin 导致 item 高度剧烈变化

问题 用 vue-gird-layout 时发现&#xff0c;当改变 margin 值时&#xff0c;item 的尺寸也会跟着变化。 如下图&#xff1a;row height 和每个 item 的 h 都保持不变。修改 margin-y&#xff0c;item 的实际高度也跟着变了&#xff1a; 原因 研究了一番&#xff0c;发现原…
阅读更多...
如何查看全球历史影像

如何查看全球历史影像

目录 示例 2024年3月28日 2022年9月21日 2021年11月3日 2020年11月18日 2019年5月15日 2017年2月27日 2016年12月20日 如何在ArcGIS中加载 如何查看全球历史影像&#xff0c;今天给大家分享一个可以在线直接访问查看全球历史影像的网站&#xff08;网址见文末&#xf…
阅读更多...
flutter 设置启屏页 flutter_native_splash 坑记录

flutter 设置启屏页 flutter_native_splash 坑记录

flutter_native_splash | Flutter packageCustomize Flutters default white native splash screen with background color and splash image. Supports dark mode, full screen, and more.https://pub.dev/packages/flutter_native_splash 发现一直白屏 原因是 代码中 下面…
阅读更多...
前端路由的实现原理

前端路由的实现原理

当谈到前端路由时&#xff0c;指的是在前端应用中管理页面导航和URL的机制。前端路由使得单页应用&#xff08;Single-Page Application&#xff0c;SPA&#xff09;能够在用户与应用交互时动态地加载不同的视图&#xff0c;而无需每次都重新加载整个页面。 在前端开发中&…
阅读更多...
vue3+elementui-plus实现无限递归菜单

vue3+elementui-plus实现无限递归菜单

效果图 实现方式是&#xff1a;通过给定的数据结构层数来动态生成多级菜单 menu.vue<template><el-menu:default-active"activeIndex"class"el-menu-demo"mode"horizontal"select"handleSelect"background-color"#f8f…
阅读更多...
Echarts的饼图有哪些配置项，一文告诉你。

Echarts的饼图有哪些配置项，一文告诉你。

Echarts中的饼图&#xff08;Pie Chart&#xff09;有以下一些常用的配置项&#xff1a; 配置项一 Echarts中的饼图&#xff08;Pie Chart&#xff09;有以下一些常用的配置项&#xff1a; title&#xff1a;饼图的标题配置&#xff0c;包括text&#xff08;标题文本&#xf…
阅读更多...
冈萨雷斯数字图像处理资源(课后习题答案+代码+图片)

冈萨雷斯数字图像处理资源(课后习题答案+代码+图片)

冈萨雷斯数字图像处理相关资源整理&#xff0c;资源全部来源互联网&#xff0c;方便大家下载 冈萨雷斯数字图像处理相关资源整理 课后习题 冈萨雷斯数字图像处理源代码
阅读更多...
程序猿成长之路之数据挖掘篇——朴素贝叶斯

程序猿成长之路之数据挖掘篇——朴素贝叶斯

朴素贝叶斯是数据挖掘分类的基础&#xff0c;本篇文章将介绍一下朴素贝叶斯算法 情景再现 以挑选西瓜为例&#xff0c;西瓜的色泽、瓜蒂、敲响声音、触感、脐部等特征都会影响到西瓜的好坏。那么我们怎么样可以挑选出一个好的西瓜呢&#xff1f; 分析过程 既然挑选西瓜有多个…
阅读更多...
静态缺省路由的应用

静态缺省路由的应用

静态缺省路由的应用 缺省路由是目的地址全零的特殊路由&#xff0c;可以由路由协议自动生成&#xff0c;也可以由手动配置。手动配置缺省路由&#xff0c;可以简化网络的配置&#xff0c;称为静态缺省路由。如果报文的目的地址无法匹配路由表中的任何一项&#xff0c;路由器将…
阅读更多...
最新文章

Copyright @ 2022~2023