测试list的简单模拟封装迭代器insert模拟erase模拟头插、尾插、头删、尾删模拟自定义类型迭代器遍历const迭代器clear和析构函数拷贝构造传统写法拷贝构造现代写法

本文源代码已上传至我的gitee仓库欢迎查看list模拟实现源代码

在学习STL时一定要先阅读C文档

list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。

list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。

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

与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

这里罗列列表的基本操作非常简单相信大家在学习完string、vector后学习list的功能非常简单

define

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);//迭代器listint::iterator

lt.begin();while

lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt.splice(lt.begin(),

lt1);for

rand();lt1.push_back(e);lt2.push_back(e);}//

begin1

lt1){v.push_back(e);}sort(v.begin(),

v.end());size_t

}测试结果发现list的sort排序效率很低在实际应用中使用的很少

templateclass

_data(x){}};模板类ListNode表示双向链表中的节点。

该节点包括三个成员_next指向下一个节点的指针、_prev指向上一个节点的指针和

定义了一个构造函数用于初始化节点的数据成员如果不提供具体的数据则使用默认值进行初始化。

templateclass

这是类的构造函数用于初始化链表。

在构造函数中首先创建了一个头节点

_next

这是一个成员函数用于在链表尾部插入新的元素。

在函数中首先创建了一个新的节点

newnode

Self;定义了一个别名Self它代表了当前类的类型这样就可以在类内部使用Self来引用当前类的对象。

Node*

_node;声明了一个指针成员变量_node它用于指向链表中的节点。

node):_node(node){}

node)接受一个指向链表节点的指针作为参数将其赋值给成员变量_node。

operator*(){return

解引用操作符operator*()返回当前迭代器指向的节点的数据成员的引用。

Self

}前置递增操作符operator()将迭代器指向下一个节点并返回递增后的迭代器自身的引用。

Self

后置递增操作符operator(int)创建当前迭代器的副本tmp然后将迭代器指向下一个节点并返回tmp。

Self

置和后置递减操作符的定义与递增操作符类似只不过是将迭代器指向前一个节点。

bool

不等于操作符operator!比较两个迭代器的_node成员如果它们不相等则返回true否则返回false。

源代码

iterator(_head-_next);}iterator

end(){return

iterator(_head);}begin()函数返回一个迭代器它指向链表中的第一个元素也就是头节点的下一个节点。

end()函数返回一个迭代器它指向链表中最后一个元素的下一个位置也就是头节点本身。

insert模拟

iterator(next);}注意最后返回一个指向下一个节点的迭代器以便在调用方继续操作链表。

头插、尾插、头删、尾删模拟

pop_back(){erase(--end());}void

pop_front(){erase(begin());}自定义类型迭代器遍历

自定义一个结构体A然后进行插入删除操作

};lt.push_back(aa1);lt.push_back(aa1);lt.push_back(A(2,

2));lt.push_back({

endl;语句打印当前迭代器it指向的A类型对象的_a1和_a2成员变量的值中间用冒号分隔并在末尾换行。

这里使用了解引用操作符(*)来获取迭代器指向的对象然后通过点操作符(.)访问对象的成员变量_a1和_a2

(*it)._a1:

(*it)是迭代器it指向的元素即链表中的一个A类型对象.是成员访问运算符_a1是这个A类型对象的成员变量_a1的值。

所以(*it)._a1表示获取当前迭代器指向的对象的_a1成员变量的值。

void

};lt.push_back(aa1);lt.push_back(aa1);lt.push_back(A(2,

2));lt.push_back({

定义了一个operator-()重载函数箭头运算符用于访问对象的成员而对于指向对象的指针使用箭头运算符来访问成员会更方便

const

这是函数的返回类型表示返回一个指向类型为T的常量数据的指针。

也就是说该函数返回的是一个指向T类型常量数据的指针。

operator-():

这是重载的箭头运算符函数名。

当我们通过指向某个对象的指针使用箭头运算符时就会调用此函数来执行操作。

return

函数体内部返回了一个指向_node-_data的指针。

在这里_node是一个指向节点的指针_data是节点中存储的数据。

通过返回_node-_data实际上是返回了指向节点数据的指针。

it-

};lt.push_back(aa1);lt.push_back(aa1);lt.push_back(A(2,

2));lt.push_back({

endl;}it-_a1和it-_a2就是使用迭代器it来访问链表中当前元素的成员变量_a1和_a2的值。

这里的it-_a1和it-_a2相当于(*it)._a1和(*it)._a2

const迭代器

const_iterator是迭代器指向的内容不能修改迭代器指向的元素不可修改模拟实现的是const

p2const

iterator是迭代器本身不能修改这个const修饰的是iteratoriterator是自定义类型前面加了const那就是不能修改这个自定义类型模拟实现的是T*

const

iterator(_head-_next);}const_iterator

end()

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);PrintList(lt);}使用模板封装一个迭代器

templateclass

类型适用于不同类型的链表例如整数、字符串、自定义对象等。

Ref表示引用类型。

在

T*指向

erase(it);}}~list(){clear();delete

_head;_head

方法可以确保在销毁链表对象时先清空链表中的所有节点然后再释放头节点的内存。

这样做有助于避免内存泄漏并正确地释放链表所占用的资源。

拷贝构造传统写法

lt){push_back(e);}}empty_init()

初始化空的链表。

它创建了一个新的节点作为头结点并将头结点的指针指向自己形成一个循环链表。

同时将链表的大小

_size

方法来初始化一个空的链表即新建一个头结点。

然后通过遍历传入的链表

push_back(e)

的对应成员的值。

这样可以在不需要额外内存分配的情况下快速交换两个链表的内容。

赋值运算符重载函数

erase(it);}}~list(){clear();delete

_head;_head

pop_back(){erase(--end());}void

pop_front(){erase(begin());}void

insert(iterator

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);listint::iterator

lt.begin();while

endl;lt.push_front(10);lt.push_front(20);lt.push_front(30);for

(auto

endl;lt.pop_back();lt.pop_front();for

(auto

};lt.push_back(aa1);lt.push_back(aa1);lt.push_back(A(2,

2));lt.push_back({

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);PrintList(lt);listint