邢台市网站建设,网站方案设计,汕头市小程序定制公司,网站建设i rskylist介绍 list 是一个支持在常数范围内#xff0c;任意位置进行插入删除的序列式容器#xff0c;且这个容器可以前后双向迭代。我们可以把 list 理解为 双向循环链表的结构。
于其他结构的容器相比#xff0c;list在 任意位置进行插入和函数的效率要高很多#xff1b;而li…list介绍 list 是一个支持在常数范围内任意位置进行插入删除的序列式容器且这个容器可以前后双向迭代。我们可以把 list 理解为 双向循环链表的结构。
于其他结构的容器相比list在 任意位置进行插入和函数的效率要高很多而list 的缺点也很明显它在随机访问容器当中的数据的时候它只能从已知位置开始线性寻找这样寻找相比于其他容器来说有时间上的消耗而且在存储方面因为是一个结点一个结点分开存储所以会多开空间来存储各个结点之间的关系在存储消耗上也更高。 list 的使用 构造函数
构造函数 (constructor)接口说明list (size_type n, const value_type val value_type())构造的list中包含n个值为val的元素list()构造空的listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list
list 的构造函数和 string vector是类似的具体可以看以下博客
C string类 迭代器 范围for_cstring迭代器_chihiro1122的博客-CSDN博客 迭代器 list 的迭代器不再像是 string 和 vector 当中使用 原生指针 来简单实现而是使用类和对象来进行包装这样可以让 指针 不能实现list 当中的 等等操作用运算符重载函数来实现具体迭代器的实现请看 list 的模拟实现。
函数声明接口说明begin end返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbegin rend返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的 reverse_iterator,即begin位置 注意
因为 list 的存储结构和 string 之类的 存储结构不一样string 存储结构是 一块连续的区间所以对于string类的迭代器就支持 类似 str.begin() 5 这样的操作但是因为 list 是不连续的空间对于 这个操作符的代价就比 string要高所以在list 的迭代器当中就没有实现 operator 这个函数迭代器的使用 不能用 的形式来判断迭代器的区间因为 list 的各个结点的存储空间不连续如果直接用 来比较比较的是指针存储的地址大小这样会出大问题对于迭代器的使用一般是 这样的 :
listint L( 10 , 1 );
list::iterator it L.begin();while(it ! L.end())
{cout *it ;it;
}
cout endl; 其他基本操作 在STL 当中这些函数基本使用都差不多集体可以参照之前介绍 string 和 vector 的博客
C string类 迭代器 范围for_cstring迭代器_chihiro1122的博客-CSDN博客
C string类-2_chihiro1122的博客-CSDN博客
C - 初识vector类 迭代器失效_chihiro1122的博客-CSDN博客
list capacity
函数声明接口说明empty检测list是否为空是返回true否则返回falsesize返回list中有效节点的个数
list element access
函数声明接口说明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用 list modifiers
函数声明接口说明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 当中的迭代器失效 list 当中的insert函数就没有迭代器失效了因为之前在vector 当中出现的 insert函数迭代器失效是因为vector 是一段连续的空间需要扩容操作而扩容就会导致迭代器失效但是list 当中的每一次插入数据都是要开辟新空间并不会影响到list 当中已经存在了的元素。
但是对于删除的函数来说比如 erase函数还是会存储迭代器失效的问题
int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
listint l(array, arraysizeof(array)/sizeof(array[0]));
auto it l.begin();
while (it ! l.end())
{
// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给
其赋值
l.erase(it);
it;
如上述例子就是外部的迭代器失效问题当it 指向的空间被删除之后it指向空间也就被释放那么在while语句当中的 it 这个重载运算符函数就找不到下一个了。
改正;
while (it ! l.end())
{
l.erase(it); // it l.erase(it);
} STL当中的迭代器认识 我们先来看下面三个函数的不同迭代器类型 上述有三种迭代器类型 InputIterator单向迭代器只能用 的操作。 BidirectionalIterator双向迭代器可以用 / -- 两个操作。RandomAccessIterator随机迭代器可以用 / -- / / - 四个操作。 不同的容器类型对于迭代器的使用就有要求 比如单链表就只能用 单向迭代器双向和随机都不能用那么对于库当中的双向和随机迭代器实现的函数单链表也不能使用。
但是这三个迭代器是向上兼容的就是说 随机 是 双向的 一种特殊情况所以使用随机迭代器的容器就可以使用 双向迭代器的函数同样双向 是 单向的一种特殊情况双向的可以使用单向的。 list的模拟实现 大致框架
#pragma oncenamespace My_List
{templateclass Tstruct List_Node // 结点指针结构体{
·············};templateclass Tstruct List_iterator // 非const 迭代器{
··········};templateclass Tclass List // List 类{
············private:Node* _head;};
} 结点的结构体定义 在官方的List源代码当中List容器的结点定义就是定义在 同一命名空间下的 一个结构体当中因为在C 当中结构体已经升级为了类所以在结构体当中也可以定义构造函数。
所以因为结点当中有数值域和指针域我们就把这个结构体当做是一个构造结点的函数来实现效果也是一样的只不过使用的时候使用new的方式来开空间和定义 templateclass Tstruct List_Node{List_NodeT* _next;List_NodeT* _prev;T _val;// List_Node 的构造函数List_Node(const T val T()):_next(nullptr),_prev(nullptr),_val(val){}};
当然为了数值域的复用性使用模版来对数值域的类型进行模版化。 构造函数和析构函数 无参数的构造函数 List(){_head new Node;_head-_next _head;_head-_prev _head;}
因为List的底层是 带头循环双向链表所以没有结点的链接方式如上只有一个头结点。 析构函数 ~List(){clear();delete _head;_head nullptr;} 这里可以直接复用clear函数。
增删查改 push_back void push_back(const T x){Node* tail _head-_prev;Node* newNode new Node(x);_head-_prev newNode;tail-_next newNode;newNode-_prev tail;newNode-_next _head;// 实现insert函数之后// insert(end() , x);}
直接开空间然后修改链接关系即可。 insert函数
这里的insert函数的当中传入的 pos 指针不用检查合法性因为这里是带头结点循环的链表在头结点的前面和后面删都是可以的。代码 iterator insert(iterator pos, const T x){Node* cur pos._Node;Node* prev cur-_prev;Node* newNode new Node(x);prev-_next newNode;newNode-_next cur:cur-_prev newNode;newNode-_prev prev;return newNode;}
因为pos位置前插入元素之后pos迭代器向后移动了以为我们认为这样也属于迭代器失效所以要返回新插入的元素的位置防止外部迭代器失效。
erase函数 erase函数同样有迭代器失效的问题所以亚需要返回新的迭代器 iterator erase(iterator pos){assert(pos ! end());Node* cur pos._Node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete[] cur; // 这里会有 pos 迭代器失效的问题所要要返回新的迭代器return next;} push_front(): 直接复用insert函数 void push_front(const T x){insert(begin(), x);} pop_back() 和 pop_front(): void pop_back(){erase(--end());}void pop_front(){erase(begin());} clear 和 size size_t size(){return _size;}void clear(){iterator it begin();while (it ! end()){it erase(it);}_size 0;} 赋值运算符重载函数和swap函数 void swap(ListT L){std::swap(_head, L._head);std::swap(_head, L._size);}ListT operator(ListT L){swap(L);return *this;} 上述原理参考文章(1条消息) C-string类的模拟实现_chihiro1122的博客-CSDN博客当中赋值操作符重载函数比较大小标题下的介绍。
其实上述的 赋值重载运算符函数当中的模板类的类型名可以不用 ListT,我们知道ListT是类型名List是类名对于模版类类型名不是 List而是ListT但是如果是在类模板当中写可以写类名也可以写类型名下述写法也可以
List operator(List L) 迭代器重点 非const迭代器 在上述介绍List迭代器的时候也介绍了List当中的迭代器不是原生指针而是自定义类型所以在定义的时候有些难度但是这样的好处是和 普通的原生指针迭代器一样可以直接 后移*解引用来访问元素等等因为自定义类型当中有运算符重载函数这样就可以实现。 其实List的迭代器本质上还是一个指针只不过这个指针现在指向的是一个结点空间其中不仅仅有数据域还有指针域那么直接解引用是不能访问到数据域的这时候就要重载 “ * ”解引用运算符实现也很简单直接返回结点的数据域即可 T operator* (){return _Node-_val;} 我们再思考我们在使用迭代器的时候会使用哪一些运算符如下所示 while (it ! L.end()){cout *it ;it; // 因为只重载了 前置的}cout endl; 我们要对上述用到的运算都要进行重载那么这个迭代器才能正常使用 List_iteratorT operator (){_Node _Node-_next;return *this;}bool operator! (const List_iteratorT L){return _Node ! L._Node;}bool operator (const List_iteratorT L){return _Node L._Node;} 最后是整个 迭代器结构体的构建上述也说过C把结构体升级为了类那么就可以使用构造函数来构造这个 迭代器对象。
首先这个迭代器的成员其实就一个就是某一个结点的指针那么这个结构体的构造函数就只用对这一个对象进行初始化就行了只需要在构造的时候传入这个结点的指针就可以 typedef List_NodeT Node;Node* _Node;List_iterator(Node* node):_Node(node){} 那么整个非const的迭代器就实现了如下所示 templateclass Tstruct List_iterator{typedef List_NodeT Node;Node* _Node;List_iterator(Node* node):_Node(node){}T operator* (){return _Node-_val;}List_iteratorT operator (){_Node _Node-_next;return *this;}bool operator! (const List_iteratorT L){return _Node ! L._Node;}bool operator (const List_iteratorT L){return _Node L._Node;}}; 然后在类当中也需要给出 begin和end两个接口begin指向头结点 _head 的后一个end 指向 _head 就行了 typedef List_iteratorT iterator; // 一定要是公有的不然不能访问iterator begin(){//return _head-_next; // 可以这样写只有一个参数的构造函数发生 隐式类型的转换// 上下两种都是一样的return iterator(_head-_next);}// 返回值应该是引用要不然 函数会出错 传值返回返回的不是 _head 是 _head 的一个拷贝 // 临时对象具有常性 ······· 1iterator end(){return _head; // 同样发生隐式类型的转换// 上下两种都可以//return iterator(_head);} 需要注意几个问题 上述代码注释当中提到的返回值类型应该是引用的问题1其实不用这样做上述的 begin和end函数是在 operator! 函数 和 构造函数当中使用的所以只需要把 operator! 函数的参数修改为 const 即可上述已经做出了更改。My_List::Listint::iterator it L.begin(); 这里不是赋值而是拷贝构造因为L.begin() 是一个已经存在了的对象赋值给另一个对象需要调用拷贝构造函数但是迭代器没有实现拷贝构造这里的编译器自己实现的浅拷贝这里的浅拷贝没有问题因为我们这里需要的就是浅拷贝。My_List::Listint::iterator it L.begin(); 这里的两个指针都指向一个对象那么为什么编译器没有报错呢这是因为迭代器类没有实现析构函数编译器就会自己调用默认析构函数去 释放迭代器指针空间而迭代器指向的结点空间并不需要迭代器类来进行释放在List类的析构函数当中进行释放。
const迭代器 这里的const 迭代器针对的是 const 对象如果是const 修饰的对象是不用普通的迭代器的因为 从 const 对象 const 的迭代器指针返回给非 const迭代器构造函数的时候从事const 变成了 非const造成了权限的放大。
所以还是需要单独实现const 迭代器对于const 迭代器和普通的迭代器功能类似只不过在 operator* 这个函数当中返回的不是 非const 对象而是 const 对象 templateclass Tstruct const_List_iterator{typedef List_NodeT Node;Node* _Node;const_List_iterator(Node* node):_Node(node){}const T operator* (){return _Node-_val;}const_List_iteratorT operator (){_Node _Node-_next;return *this;}bool operator! (const const_List_iteratorT L){return _Node ! L._Node;}bool operator (const const_List_iteratorT L){return _Node L._Node;}};const_iterator begin() const{return _head-_next;}const_iterator end() const{return const_iterator(_head);}
这样做虽然能够实现const迭代器的效果但是太冗余了不太好。
所以这个时候我们有了多个模版参数的使用如下所示是 普通迭代器类的模版 templateclass T, class Refstruct List_iterator{······················
此时在类当中的 typedef 哑鼓这样写 typedef List_iteratorT , T iterator; // 一定要是公有的不然不能访问typedef List_iteratorT , const T const_iterator;
这样就可以在同一个类当中区分出 const类和 非 const 类那么之间对 opeartor* 函数的修改就可以是这样的了; Ref operator* (){return _Node-_val;}
同样在类当中不同的地方都要进行修改完整代码如下所示
templateclass T, class Refstruct List_iterator{typedef List_NodeT Node;typedef List_iteratorT,Ref selt;Node* _Node;List_iterator(Node* node):_Node(node){}Ref operator* (){return _Node-_val;}selt operator (){_Node _Node-_next;return *this;}selt operator (int){_Node _Node-_next;return *this;}bool operator! (const selt L){return _Node ! L._Node;}bool operator (const selt L){return _Node L._Node;}};templateclass Tclass List{typedef List_NodeT Node;public:typedef List_iteratorT , T iterator; // 一定要是公有的不然不能访问typedef List_iteratorT , const T const_iterator;·········································
这样的话看似是写了一个类其实是写了两个类但是代码的大小就节省了这就是模版带来的好处。
在迭代器当中还会使用到 - 这个操作符所以这个操作符也需要重载 T* operator- (){return _Node-_val;}
但是在使用的时候下面这个场景就有些怪如下所示
struct A{A(int a1 0, int a2 0):_a1(a1), _a2(a2){}int _a1;int _a2;};void test_list2(){listA lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));listA::iterator it lt.begin();while (it ! lt.end()){//cout (*it)._a1 (*it)._a2 endl;cout it-_a1 it-_a2 endl;it;}cout endl;} 上述的 cout 流当中的 it 用法其实应该这样写
it -- _a2
上面才是正常写法但是在 operator- 函数的使用当中却直接 it - _a2 这样使用了这是因为运算符重载要求可读性编译器在这个地方进行特殊处理省略了一个 - 。 而上述的 operator- 这个函数如果是 const 的迭代器当中是实现的话返回值应该是 const T*所以这里对迭代器类模版的参数再加上一个 ptr 来使用
最终迭代器的代码 templateclass T, class Ref , class ptrstruct List_iterator{typedef List_NodeT Node;typedef List_iteratorT,Ref, ptr selt;Node* _Node;List_iterator(Node* node):_Node(node){}Ref operator* (){return _Node-_val;}selt operator (){_Node _Node-_next;return *this;}selt operator (int){_Node _Node-_next;return *this;}selt operator-- (){_Node _Node-_prev;return *this;}selt operator-- (int){_Node _Node-_prev;return *this;}bool operator! (const selt L){return _Node ! L._Node;}bool operator (const selt L){return _Node L._Node;}ptr operator- (){return _Node-_val;}};templateclass Tclass List{typedef List_NodeT Node;public:typedef List_iteratorT , T , T* iterator; // 一定要是公有的不然不能访问typedef List_iteratorT , const T , const T* const_iterator;·······················································
list的反向迭代器 通过前面例子知道反向迭代器的就是正向迭代器的--反向迭代器的--就是正向迭代器的因此反向迭代器的实现可以借助正向迭代器即反向迭代器内部可以包含一个正向迭代器对正向迭代器的接口进行包装即可。
templateclass Iterator
class ReverseListIterator
{// 注意此处typename的作用是明确告诉编译器Ref是Iterator类中的类型而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIteratorIterator Self;
public://// 构造ReverseListIterator(Iterator it) : _it(it) {}//// 具有指针类似行为Ref operator*() {Iterator temp(_it);--temp;return *temp;}Ptr operator-() { return (operator*()); }//// 迭代器支持移动Self operator() {--_it;return *this;}Self operator(int) {Self temp(*this);--_it;return temp;}Self operator--() {_it;return *this;}Self operator--(int){Self temp(*this);_it;return temp;}
//
// 迭代器支持比较
bool operator!(const Self l)const { return _it ! l._it; }
bool operator(const Self l)const { return _it ! l._it; }
Iterator _it;
};
list和vector 的比较 list 就是链表 vector 是顺序表两者的结构不同导致两者的使用场景不同两者也是典型的连续空间存储和链式空间存储不同特性的表现下表是对两者进行的简单比较
vector list底 层 结 构动态顺序表是一段连续空间带头结点的双向循环链表随 机 访 问支持随机访问访问某个元素效率O(1)不支持随机访问访问某个元素 效率O(N)插 入 和 删 除任意位置插入和删除效率低需要搬移元素时间复杂 度为O(N)插入时有可能需要增容增容开辟新空 间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不 需要搬移元素时间复杂度为 O(1)空 间 利 用 率底层为连续空间不容易造成内存碎片空间利用率 高缓存利用率高底层节点动态开辟小节点容易 造成内存碎片空间利用率低 缓存利用率低迭 代 器原生态指针对原生态指针(节点指针)进行封装迭 代 器 失 效在插入元素时要给所有的迭代器重新赋值因为插入 元素有可能会导致重新扩容致使原来迭代器失效删 除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效 删除元素时只会导致当前迭代 器失效其他迭代器不受影响使 用 场 景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随 机访问
