节点类1.2

list的底层和vector和string不同实现也有所差别特别是在迭代器的设计上本文讲介绍list的简单模拟实现。

list整体由三个类组成

list节点类是一个模板类以适合于任何类型的ist对象封装了一个节点需要的基本成员

成员变量

只有一个构造函数用于初始化节点data数据和置空指针构造函数的x参数是缺省参数适应不同场景。

注意节点类不需要拷贝构造和析构函数对于节点的拷贝构造在list中只需要浅拷贝即可节点的释放也不在节点类中进行

templateclass

迭代器类也是封装节点但是迭代器类不会构造节点只会利用现有节点构造一个迭代器在迭代器内部通过各种运算符重载对节点的状态做修改

其次会涉及返回节点指针或数据data的引用所以需要在构造对象时将list数据类型的指针和引用类型传给迭代器对象

迭代器在不访问data的情况下返回的都是迭代器将声明本迭代器类型self在函数操作完成时返回self迭代器即可

//2、迭代器要么就是自定义类型对原生指针的封装模拟指针的行为

templateclass

};迭代器对象不会凭空创造节点只会利用现有的节点迭代器节点类型与list节点类型相同所以不需要拷贝构造和析构函数浅拷贝足以

1.3

xT()):_next(nullptr),_prev(nullptr),_data(x){}

成员变量只有结点node对结点进行初始化

因为是带头的链表所以在实例化时必须事先申请一个头结点所以所有的构造函数都会在操作前申请一个头结点为了避免代码的冗余我们将头节点的创建封装为一个函数在构造函数初始化时调用创建头结点。

当我们需要构造空链表时直接调用empty_init();函数即可

templateclass

last){push_back(*first);first;}}private:node*

_head;

析构函数需要释放所有结点以及头结点在释放前需要判断当前链表是否为空如果为空直接置空头节点

~list()

对于赋值重载与拷贝构造相似但是赋值重载在传递参数时使用传值传参这样就自动帮我们构造了一个临时对象我们只需要swap一下临时对象的头节点即可将我们现在的链表交给临时对象销毁这样就完成了赋值。

有时可能需要连等所以需要返回对象的引用。

//lt1lt3

拷贝构造最好采用现代写法构造临时对象使用swap交换在此之前因为是构造函数所以需要创造头结点调用empty_init()函数再进行拷贝

//lt2(lt1)

const类型的对象只能使用const类型的迭代器那么const类型的迭代器如何实现呢、需要再重新封装吗像上面那样。

可以但是没有必要因为那样代码的冗余度就会很高我们只需要给模板增加两个参数就可以了。

即templateclass

T,class

//2、迭代器要么就是自定义类型对原生指针的封装模拟指针的行为

templateclass

iterator(_head-_next);}const_iterator

begin()

const_iterator(_head-_next);}iterator

end(){//iterator

iterator(_head);}const_iterator

end()

const_iterator(_head);}五、list的增容和删除

5.1

3.修改_head和tail之间的链接关系再其中链入new_node

void

任意位置插入是在pos迭代器位置前插入一个结点并返回这个结点的迭代器

2.获取pos位置的当前结点pos._node获取pos位置的前驱结点cur-_prev

4.将新节点new_node链入pos结点与pos前驱结点之间

iterator

}任意位置删除时删除pos迭代器位置的结点并返回删除结点的下一个结点的迭代器

4.链接pos._node-_prev和pos._node-_next结点剥离pos结点

5.删除pos结点

6.返回pos._node-_next结点的迭代器(即pos的下一个结点的迭代器)

iterator

xT()):_next(nullptr),_prev(nullptr),_data(x){}};//1、迭代器要么就是原生指针//2、迭代器要么就是自定义类型对原生指针的封装模拟指针的行为templateclass

T,class

_node;__list_const_iterator(node*

n):_node(n){}const

iterator(_head-_next);}const_iterator

begin()

const_iterator(_head-_next);}iterator

end(){//iterator

iterator(_head);}const_iterator

end()

last){push_back(*first);first;}}//lt2(lt1)

拷贝构造传统写法/*list(const

lt.end());swap(tmp);}//lt1lt3listT

operator(listT

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);listint::iterator

lt.begin();while

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for

(auto

endl;lt.push_back(100);lt.push_front(1000);for

(auto

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

(auto

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for

(auto

endl;lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);for

(auto

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for

(auto

lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);lt3.push_back(40);lt3.push_back(50);for

(auto

{//zl::test_list1();//zl::test_list2();//zl::test_list3();//zl::test_list4();zl::test_list5();//std::vectorint::iterator

it;//cout