企业网站设计解决方案,用邮箱找回智慧团建密码,wordpress删除评论别人,网站移动化建设方案文章目录 list介绍list的使用构造函数#xff08;constructor#xff09;迭代器list capacitylist modify#xff08;修改#xff09;其他接口函数list迭代器失效问题 list实现基础框架(节点类#xff09;基础框架#xff08;迭代器类#xff09;基础框架#xff08;链… 文章目录 list介绍list的使用构造函数constructor迭代器list capacitylist modify修改其他接口函数list迭代器失效问题 list实现基础框架(节点类基础框架迭代器类基础框架链表主体类链表主体函数 二次修改于date2024320 list介绍 在STL中list底层使用的是双向带头循环链表这是一个很完善的结构可以做到在O1时间内完成pos位置的插入删除。 唯一的缺点是不支持随机访问如果要访问list中的第三个元素只能通过遍历迭代器或者范围for来访问第三个元素。 所以list不支持算法库里面的sort因为算法库中的sort底层是快速排序快速排序为了防止最坏的情况也就是已排序好的数据在这种情况下的效率就是ON^2)因此引入了三数取中但是如果不支持随机访问三数取中就不可以使用了 要想对sort进行排序只能使用list自带的sort来进行排序但是list也很少排序如果是需要排序的数据一般是用顺序表来存储。其次list内置sort效率很低数据量大的时候甚至不如先将数据拷贝到vector中排序完再拷贝回来。 这是list的双向带头循环链表的一个逻辑结构图 常见的迭代器类型 单向----只能例如forword_list和unorder_map 双向----可和–例如list 随机访问----可以/–//-//-等任意方式访问有vector和string 在文档中根据迭代器名称可以判断出当前函数支持什么类型的迭代器这几个迭代器从上到下满足继承关系单向的迭代器可以调用的函数双向的迭代器一定也可以但是双向可以调用的函数单向的不一定能调用。 list的使用
构造函数constructor C这里提供了四种构造函数 1.不传参数构造空链表也就是只有一个头结点alloc是空间配置器也就是内存池 2.使用n个val来构造链表 3.使用了一个迭代器区间来构造左闭右开可以是其他容器的迭代器来构造链表 4.拷贝构造 #includeiostream
#includelist
#includestringusing namespace std;templateclass T
void Print(T tmp)
{typename T::iterator it tmp.begin();while (it ! tmp.end()){cout *it ;it;}cout endl;
}
int main()
{listint l1;listint l2(10, 6);string s(hello kisskernel);listchar l3(s.begin(), s.end());Print(l1);Print(l2);Print(l3);return 0;
}这里实现了一个可以打印任意类型容器的模板打印函数在访问模板内的内嵌类型的时候如果不加typename就会报错因为模板在没有实例化之前是不能取模板的内嵌类型的这时候编译器根本就不认识T也不知道T是什么类型取内嵌的iterator就会报错。所以前面加上了typename就是告诉编译器这个参数是个模板类型等实例化之后再去里面取内嵌类型。 迭代器 list的迭代器和其他容器一样的不多赘述。 虽然迭代器的使用类似指针的操作在前面的vector和string中迭代器也确实就是指针但是list迭代器如果单单是指针的话不能满足list这里的迭代器要求比如it如果时原生指针就时地址并不能跳到下一个节点。 所以list的迭代器封装了节点的指针然后通过重载运算符来完成迭代器的操作包括后面的map和set也是类似的。 迭代器的价值
封装底层实现不暴露底层细节统一访问方式减少学习成本 算法中的函数模板理论上都是通用的传什么迭代器都是可以的但是因为算法中可能用到了不同的迭代器操作有一些迭代器可能不支持这些操作比如sort需随机访问list的iterator是不支持的。 注意begin的位置就是第一个节点的位置end的位置是最后一个节点的下一个位置也就是头结点哨兵位的位置。 结构如下 begin是正向迭代器的开始向着逆时针移动。 rbegin是反向迭代器的开始向着顺时针方向移动 反向迭代器关于反向迭代器这里为了让end和rbegin保持一致所以他们都是指向头结点的但是rbegin解引用拿到的是最后一个节点4这是因为反向迭代器的实现重载*的时候是返回的前一个位置的值。所以rend解引用拿到的就是头结点这里会报错这也证明了拿到的确实就是头节点。 list capacity 1.判断链表是否为空用迭代器begin和end判断是不是相等的就可以了相等就是空 2.返回链表的元素个数可以遍历链表来计数也可在成员中加一个_size来记录插入就删除就– list modify修改 修改函数只需要了解框选出来的即可。 1.push_front头插 2.popfront头删 3.push_back尾插 4.pop_back尾删 5.insert随机插入在pos位置之前插入 返回值是新插入的元素的第一个位置如果只插入一个元素就返回这个插入的元素的位置。 6.erase删除 返回的迭代器是最后一个被删除的位置的下一个位置的迭代器。如果已将容器最后一个元素删除那么返回的就是end() 7.swap交换 8.clear清空链表 其他接口函数 assign就是将对象重新赋值第一个就是将容器内的数据清空然后将这个迭代器区间内的数据插入进去第二个就是清空然后插入n个val splice的意思就是拼接结合的意思。将一个容器的元素接合到另一个容器中。 1.将x容器内的元素全部接合到调用容器的position位置。 2.将x容器内的i之后的元素接合到pos位置。 3.将x容器[ firstlast的这个区间接合到pos位置。 list迭代器失效问题 list底层是双向带头循环链表使用迭代器插入一个节点并不会导致迭代器失效因为插入的节点不会导致其他节点的物理地址的变换。使用erase删除一个节点同样也不会导致迭代器失效只会导致删除的这个节点失效。 list实现 需要了解list容器总共有几部分组成list内成员就是一个指针指向双向带头循环链表的头节点。然后将节点封装成一个类。vector和string的迭代器都可以使用原生指针来实现因为他们的存储空间是连续的 或者-- 后就能找到附近的元素但是list的存储空间是不连续的。 所以list的原生指针行为不能满足list对于迭代器的定义就需要通过类来封装原生指针重载运算符来实现迭代器功能。这里一共需要三个类list_list_node , _list_iterator。 正因为使用类封装迭代器重载了运算符所以在使用的时候可以不需要关注容器底层到底是数组链表或者是树形结构都可以使用简单统一的方法来访问修改容器这其实就是迭代器的意义。 基础框架(节点类 //封装节点类templateclass Tstruct _list_node{typedef _list_nodeT node;_list_node(const T val T()):_val(val),_next(nullptr),_prev(nullptr){}T _val;_list_node* _next;_list_node* _prev;};
基础框架迭代器类
//封装迭代器类templateclass T,class Ref, class Ptrstruct _list_iterator{typedef _list_nodeT node;typedef _list_iteratorT,Ref,Ptr self;_list_iterator(node* pnode):_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);_pnode _pnode-_next;return tmp;}//前置--self operator--(){_pnode _pnode-_prev;return *this;}//后置--self operator--(int){self tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator(const self it){return _pnode it._pnode;}bool operator!(const self it){return _pnode ! it._pnode;}self operator(int x){while (x--)_pnode _pnode-_next;return *this;}self operator-(int x){while (x--)_pnode _pnode-_prev;return *this;}node* _pnode;};基础框架链表主体类 //list主体类templateclass Tclass list{typedef _list_nodeT node;public://迭代器typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;//.................private:node* _head;};迭代器类使用了三个模板参数主要为了适配const对象而加上了两个对象。因为如果是const对象调用operator*的时候返回的必须是const T使得这个对象只能读不能写。如果像前面那样直接写成函数重载这里就会有问题了因为迭代器并不是const类型的所以只有返回值类型不相同的两个函数是不能构成函数重载的。 还有方法就是再写一个const_iterator类但是这个类除了除了operator*和operator-这两个函数的返回值不同以外其他的函数都是相同的所以代码会有很多的冗余。 这就要使用模板将这两个函数的返回值都写成模板参数const和非const只需要在模板实例化的时候控制就可以了实际上还是生成了两个类但是这是编译器替我们写的并不需要我们自己动手。 链表主体函数 //迭代器typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;iterator begin(){return iterator(_head-_next);}const_iterator begin() const{return const_iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}////构造函数list(){empty_initialize();}list(size_t n, const T val T()):_head(nullptr){file_initialize(n, val);}list(int n, const T val T()):_head(nullptr){file_initialize(n, val);}templateclass InputIteratorlist(InputIterator first, InputIterator last){empty_initialize();InputIterator it first;while (it ! last){push_back(*it);it;}}void swap(listT lt){std::swap(_head, lt._head);}//copy constructlist(const listT lt):_head(nullptr){empty_initialize();listT tmp(lt.begin(), lt.end());swap(tmp);}listT operator(listT tmp){swap(tmp);return *this;}//析构~list(){clear();delete _head;_head nullptr;//cout _head endl;}//自定义类型交换void push_back(const T x){node* newnode new node(x);node* tail _head-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;}void push_front(const T x){insert(begin(), x);}iterator insert(iterator pos, const T x){node* newnode new node(x);node* cur pos._pnode;node* prev (pos._pnode)-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;return pos;}iterator erase(iterator pos){node* cur pos._pnode;node* next cur-_next;node* prev cur-_prev;prev-_next next;next-_prev prev;delete cur;return next;}iterator pop_front(){return erase(_head-_next);}iterator pop_back(){return erase(_head-_prev);}void clear(){node* cur _head-_next;while (cur ! _head){node* next cur-_next;delete cur;cur next;}_head-_next _head;_head-_prev _head;}//size_t size() const{size_t count 0;node* cur _head-_next;while (cur ! _head){count;cur cur-_next;}return count;}bool empty() const{return _head-_next _head;}//T front(){return _head-_next-_val;}T back(){return _head-_prev-_val;}void empty_initialize(){_head new node;_head-_prev _head;_head-_next _head;}void file_initialize(size_t n, const T val){empty_initialize();for (size_t i 0; i n; i){push_back(val);}}在编写成员函数的时候要注意重复冗余的代码可以抽离出来实现成为单独的函数使用的地方进行调用逻辑相近的代码可以复用比如写完insert和erase头插头删尾插尾删都可以复用。这样不仅代码简洁而且可维护性更好。 下面着重说一下迭代器重载的operator-的作用。 比如这里有一个类date class date
{
public:date(int year 0, int month 1, int day 1):_year(year),_month(month),_day(day){}int _year;int _month;int _day;
};如果list里面存放的是date类对象要输出的时候就会遇到问题想要只输出year只能先解引用然后再使用点来访问date里面的数据。 void test5()
{xzj::listdate ld;ld.push_back({ 1900,2,28 });ld.push_back({ 1901,3,29 });ld.push_back({ 1902,4,20 });ld.push_back({ 1903,5,20 });xzj::listdate::iterator it ld.begin();while (it ! ld.end()){cout (*it)._year endl;it;}}指针访问结构体里面的数据都是使用-那么在这里我们也可以使用-只需要重载-操作符 Ptr operator-(){return _pnode-_val;}有了上面的重载我们就可以直接使用-来访问date对象内的数据了 void test5()
{xzj::listdate ld;ld.push_back({ 1900,2,28 });ld.push_back({ 1901,3,29 });ld.push_back({ 1902,4,20 });ld.push_back({ 1903,5,20 });xzj::listdate::iterator it ld.begin();while (it ! ld.end()){cout it-_year endl;it;}
}但是这里it-实际调用方式是it . operator-()这个函数返回了date*这个类型的地址但是仅有一个地址是不可以的我们是不是还需要一个-才能访问数据呢所以一共需要两个- 理论上来讲是这样的但是这里编译器做了优化所以这里只需要一个箭头就可以访问了。
