有经验的做网站,wordpress分类指定页面,台州高端网站建设,广州网络营销选择目录
前言
1. list的简介
2.list讲解和模拟实现
2.1 默认构造函数和push_back函数
2.2 迭代器实现
2.2.1 非const正向迭代器
2.2.2 const正向迭代器
2.2.3 反向迭代器
2.3 插入删除函数
2.3.1 insert和erase
2.3.2 push_back pop_back push_front pop_front
2.4 构…目录
前言
1. list的简介
2.list讲解和模拟实现
2.1 默认构造函数和push_back函数
2.2 迭代器实现
2.2.1 非const正向迭代器
2.2.2 const正向迭代器
2.2.3 反向迭代器
2.3 插入删除函数
2.3.1 insert和erase
2.3.2 push_back pop_back push_front pop_front
2.4 构造函数赋值拷贝函数析构函数
总结 前言
这篇文章讲述常用容器list的使用和一些重要部分的简单模拟实现仅仅只是了解一些实现方法。内容丰富干货多多。 1. list的简介 list是序列容器允许在序列内的任何位置进行常量时间的插入和删除操作以及两个方向的迭代。列表容器被实现为双链表;双链表中每个元素存储在互不相关的几点钟在节点中通过指针指向其前一个元素和后一个元素。它们与forward_list非常相似:主要区别在于forward_list对象是单链表因此它们只能向前迭代让其更简单高效。与其他基本标准序列容器(array、vector和deque)相比列表在容器内的任何位置插入、提取和移动元素方面通常表现更好。与其他序列容器相比列表和forward_lists的主要缺点是它们无法通过位置直接访问元素;例如要访问列表中的第八个元素必须从已知位置(如开始或结束)迭代到该位置这需要在两者之间的距离上花费线性时间。它们还消耗一些额外的内存来保存与每个元素相关联的链接信息(对于包含小元素的大型列表来说这可能是一个重要因素)。 下面是展示list类的内部成员变量结构并且之后要简单模拟实现所以加上一个命名空间防止与库中list起冲突。list即是双向链表结构我们使用模版定义一个ListNode类内部成员变量有两个指针指向前一个元素和后一个元素还有存储T类型的元素。在list类中我们可以使用typedef简化LIstNodeT成Node。Node类型的指针变量_head代表第一个哨兵位结点不存放元素。其中ListNode使用struct而不用class因为struct默认权限是公有的且ListNode类里面的所有内容list都会使用到所以直接用struct定义这个类。
namespace User
{templateclass Tstruct ListNode{ListNode*T _next;ListNode*T _prev;T _data;//...};templateclass Tclass list{typedef ListNodeT Node; //...private:Node* _head;};
} 2.list讲解和模拟实现
2.1 默认构造函数和push_back函数
默认构造函数构造一个只含有哨兵位结点的链表并且哨兵位结点的的两个指针指向自身。我们暂时使用库里的list先创建一个int类型的list容器调用的是默认构造函数之后尾插几个整数。遍历整个链表一般使用迭代器还可以使用范围for。因为物理结构是不连续的不支持使用下标方括号遍历链表。
list();//默认构造函数void test_list1()
{std::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);listint::iterator it1 lt1.begin();while (it1 ! lt1.end()){cout *it1 ;it1;}cout endl;for (const auto e : lt1){cout e ;}cout endl;
}
运行结果如下 实现一个list的默认构造函数使用new动态开辟一个Node类型元素的内存空间传入一个T类型的值调用LIstNode类的构造函数。下面写的是T()表示如果是自定义类型就调用该自定义类型的构造函数如果是内置类型会初始化一个该类型的值整型一般初始化为0。既然list构造函数中调用了LIstNode类的构造函数LIstNode的构造函数也需要实现。构造函数的参数是const修饰的T类型引用的data变量顺便给上一个缺省值T()跟上面的用法相同。push_back函数先动态开辟一个新结点传入x初始化。然后再改变结点指向的位置即可。
templateclass T
struct ListNode
{ListNode*T _next;ListNode*T _prev;T _data;ListNode(const T data T()):_next(nullptr),_prev(nullptr),_data(data){}
};templateclass T
class list
{typedef ListNodeT Node;
public:list(){_head new Node(T());_head-_next _head;_head-_prev _head;}void push_back(const T x){Node* newnode new Node(x);Node* tail _head-_prev;// head tail newnodetail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;}private:Node* _head;
}; 2.2 迭代器实现
2.2.1 非const正向迭代器
list因本身物理空间不连续需要通过结点存储前后元素地址进行访问。那么list的迭代器需要封装成一个类重载前置后置--!*等符号。 templateclass T
struct ListIterator
{typedef ListNodeT Node;typedef ListIteratorT Self;Node* _node;//...
};
typedef可以帮我们简化类名称方便之后使用重命名ListNodeT类为Node还有将ListIteratorT类重命名为Self。 ListIterator(Node* node):_node(node){}构造函数实现一个有参的构造函数使用初始化列表初始化_node。 templateclass T
class list
{typedef ListNodeT Node;public:typedef ListIteratorT iterator;iterator begin(){//iterator it(_head-_next);//return it//下面是隐士类型转换调用return iterator(_head-_next);}iterator end(){return iterator(_head);}};
在list中提供begin和end函数对迭代器进行初始化或者遍历时做判断。begin函数中可以先创建一个iterator对象再返回该对象。也可以直接使用匿名对象内部传结点参数进行隐式类型转换。end函数提供最后一个元素的下一个位置所以用哨兵位结点进行构造。 // it 前置Self operator(){_node _node-_next;return *this;}// it 后置Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}// --it 前置Self operator--(){_node _node-_prev;return *this;}
前置表示访问后一个元素让_node赋值为_next指针即可。返回类型使用Self的引用不用再次拷贝更高效记得要返回*this。后置返回当前的位置但是迭代器自身指向下一个元素。创建一个Self类型的tmp变量对*this进行拷贝构造然后自身赋值为下一个结点指针返回tmp。前置--表示访问前一个元素。做法跟前置类似让_node赋值为它的_prev指针即可。也是使用Self引用类型返回。 T operator*(){return _node-_data;}
*符号表示要解引用到Node类型存储的元素。返回类型使用T类型的引用直接返回data的别名减少拷贝。 bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}
!和可直接返回两个迭代器结点地址比较结果。 -符号比较特别表示当前结点元素数据的地址可以像结构体-一样使用。 T* operator-(){return _node-_data;}
虽然operator-看起来比较奇特但是也有它的应用场景。
看下面的代码我们定义一个PosPos是表示坐标位置的类。我们创建一个数据类型为Pos的list容器尾插三个Pos类对象数据。使用迭代遍历。如果在while循环使用*it进行打印程序会报错这是因为Pos类没有匹配的cout流插入函数在全局作用域下也没有重载cout函数。所以可以用(*it)._row这样的方式打印两个整型坐标*符号返回的是结点的数据别名在这里是Pos类变量的别名我们可以用.符号进行打印但是看起来太别扭了。重载的-就派上用场了我们使用-就像结构体指针访问内部对象。不过正常来说应该是两个-符号代码中有展开示例。为了可读性只用写一个-符号就可以使用。
struct Pos
{int _row;int _col;Pos(int row 0, int col 0):_row(row), _col(col){}
};void test_list2()
{listPos lt1;lt1.push_back(Pos(100, 100));lt1.push_back(Pos(200, 100));lt1.push_back(Pos(300, 100));//临时对象可以调用非静态成员函数但是不能引用定义listPos::iterator it lt1.begin();while (it ! lt1.end()){//cout *it endl;//error,这样写无法运行成功。//可以这样写但是太别扭了//cout (*it)._row : (*it)._col ;//为了可读性省略了一个-cout it-_row : it-_col endl;//cout it--_row : it--_col ; 展开就成了下面的样子cout it.operator-()-_row : it.operator-()-_col endl;it;}cout endl;
}
运行结果如下 2.2.2 const正向迭代器
非const对象的迭代器迭代器指向的元素可以修改但是有时候容器内部元素加上const修饰不可以修改。因此还要提供const类型的迭代器。我们可以使用上面的代码只要将operator*和operator-函数的返回类型加上const修饰就行。
templateclass T
struct ListIterator
{typedef ListNodeT Node;typedef ListIteratorT Self;Node* _node;ListIterator(Node* node Node())//默认构造:_node(node){}Self operator(){_node _node-_next;return *this;}Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}Self operator--(){_node _node-_prev;return *this;}const T operator*(){return _node-_data;}const T* operator-(){return _node-_data;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}
};templateclass T
class list
{typedef ListNodeT Node;public:typedef ListIteratorT iterator;typedef ListIteratorT const_iterator;const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}//...
}; 但是这两类迭代器就只有operator*和operator-函数的返回类型不同而已返回类型上有区别其实我们可以借助模版解决。只需要在定义两个模版类型参数Ref和Ptr分别表示引用和指针在list中分别传不同的参数表示iterator和const_iterator。 templateclass T, class Ref, class Ptrstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;Node* _node;ListIterator(Node* node Node())//默认构造:_node(node){}Self operator(){_node _node-_next;return *this;}Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}Self operator--(){_node _node-_prev;return *this;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}};templateclass Tclass list{typedef ListNodeT Node;public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T* const_iterator;const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}//...}; 2.2.3 反向迭代器
反向迭代器的模拟实现和正向迭代器类似需要注意和--跟正向迭代器的的方向完全反过来还要注意迭代器begin和end函数给的结点位置。 templateclass T, class Ref, class Ptrstruct Reverse_ListIterator{typedef ListNodeT Node;typedef Reverse_ListIteratorT, Ref, Ptr Self;Node* _node;Reverse_ListIterator(Node* node):_node(node){}Self operator()//前置赋值为前面的结点的指针{_node _node-_prev;return *this;}Self operator(int)//后置{Self tmp(_node);_node _node-_prev;return tmp;}Self operator--(){_node _node-_next;return *this;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}};templateclass T
class list
{typedef ListNodeT Node;public:typedef Reverse_ListIteratorT, T, T* reverse_iterator;typedef Reverse_ListIteratorT, const T, const T* reverse_const_iterator;reverse_const_iterator rbegin() const{return reverse_const_iterator(_head-_prev);} reverse_const_iterator rend() const{return reverse_const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(_head-_prev);}reverse_iterator rend(){return reverse_iterator(_head);}//...
}; 2.3 插入删除函数
2.3.1 insert和erase
insert函数是在指定结点位置前插入一个新的结点。需要改变各个结点的指向问题可以创建几个变量表示结点。因为该函数传入的参数类型是迭代器所以还要考虑迭代器失效的问题。解决方法是返回指向新结点位置的迭代器类型的变量。下面采用的是匿名对象。
iterator insert(iterator pos, const T x)
{Node* cur pos._node;Node* newnode new Node(x);Node* prev cur-_prev;//prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;return iterator(newnode);
} erase函数是删除传入的迭代器变量指向的结点。也可以创建几个变量表示结点改变各个结点的指向问题。返回类型也是迭代器返回的是被删除结点的下一个结点迭代器类型变量。
//erase后Pos失效因为被释放了
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;return iterator(next);
} 2.3.2 push_back pop_back push_front pop_front
完成了对insert和erase函数的实现头部或者尾部插入和删除的函数都可以复用这两个函数。
push_back函数是在尾部插入一个结点insert是在指向结点前插入新结点因为end函数是哨兵位结点在它前面插入新结点就是尾插所以传end函数作为迭代器即可。pop_back函数是删除最后一个结点最后一个结点在哨兵位结点之前即end函数所代表的迭代器所以需要--。push_front和pop_front同理。
void push_back(const T x)
{insert(end(), x);
}void pop_back()
{erase(--end());
}void push_front(const T x)
{insert(begin(), x);
}void pop_front()
{erase(begin());
} 写一个测试函数
void Func(const listint lt)
{listint::const_iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;
}void test_list3()
{listint lt1;//按需实例化lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);Func(lt1);lt1.push_front(10);lt1.push_front(20);lt1.push_front(30);Func(lt1);lt1.pop_back();lt1.pop_back();lt1.pop_back();Func(lt1);lt1.pop_front();lt1.pop_front();lt1.pop_front();Func(lt1);
}
运行结果如下 2.4 构造函数赋值拷贝函数析构函数
构造函数这块有四种类型默认构造initializer初始化器构造迭代器区间构造和拷贝构造。
首先封装一个创建哨兵位头结点的函数因为后面的构造函数都需要用到。再写一个遍历打印整个链表的函数。默认构造函数直接调用empty_init函数初始化一个头结点。
void Printlist(const listint lt)
{for (const auto e: lt1){cout e ; }cout endl;
}void empty_init()
{_head new Node(T());_head-_next _head;_head-_prev _head;
}list()
{empty_init();
} initializer_list函数是针对花括号内部有相同类型的构造函数
list(initializer_listT il)
{empty_init();for (const auto e : il){push_back(e);}}void test1()
{listint lt1 { 1,2,3,4,5,6,7,8 };Printlist(lt1);
} 需要注意判断条件只能是!不能是之类的符号。
template class InputIterator
list(InputIterator first, InputIterator last)
{empty_init();while (first ! last){push_back(*first);first;}
}void test2()
{listint lt1 { 1,2,3,4,5,6,7,8 };Printlist(lt2);listint lt2(lt1.begin(), lt2.end());Printlist(lt2);
} 拷贝构造函数可以使用范围for尾插元素实现。
//lt1(lt2)
list(const listT lt)
{empty_init();for (const auto e : lt){push_back(e);}
}void test3()
{listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);Printlist(lt2);listint lt2(lt1);Printlist(lt2);
} 赋值拷贝函数可以先删除原链表的结点然后再一个个尾插结点。但是更好的方法就是用正常模版类型参数list接受被拷贝对象此时的lt就是待拷贝对象的一份临时拷贝然后使用交换函数交换头结点因为lt是一份临时拷贝函数结束后会自动调用析构函数销毁原链表的内容。
//lt1 lt3
listT operator(listT lt)
{std::swap(_head, lt._head);return *this;
}void test3()
{listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);Printlist(lt2);listint lt2;lt2 lt1;Printlist(lt2);
} 析构函数需要先一个个释放结点再释放头结点。
void clear()
{auto it begin();while (it ! end()){it erase(it);it;}
}~list()
{clear();delete _head;_head nullptr;
} 总结
看完整篇文章我相信你对list的使用和一些底层实现原理有进一步的了解你也可以尝试自己手撕一个简单的list容器实现。树欲静而风不止既然我们无法改变大势但是我们可以改变自己
创作不易希望这篇文章能给你带来启发和帮助如果喜欢这篇文章请留下你的三连你的支持的我最大的动力
