当前位置: 首页 > news >正文

雄县有做网站的吗上海专业seo服务公司

雄县有做网站的吗,上海专业seo服务公司,学wordpress不需要学DW,如何恢复wordpress主题初始内容【C笔记】list结构剖析及其模拟实现 🔥个人主页:大白的编程日记 🔥专栏:C笔记 文章目录 【C笔记】list结构剖析及其模拟实现前言一 .list的结构及其介绍1.1list的结构1.2list的使用1.3迭代器划分 二.list的模拟实现2.1 list结构…

【C++笔记】list结构剖析及其模拟实现

🔥个人主页大白的编程日记

🔥专栏C++笔记


文章目录

  • 【C++笔记】list结构剖析及其模拟实现
    • 前言
    • 一 .list的结构及其介绍
      • 1.1list的结构
      • 1.2list的使用
      • 1.3迭代器划分
    • 二.list的模拟实现
      • 2.1 list结构的定义
      • 2.2iterator迭代器
      • 2.3list迭代器
      • 2.3构造
      • 2.4拷贝构造
      • 2.5 operator=
      • 2.6 insert
      • 2.7 erase
      • 2.8 clear
      • 2.9析构函数
    • 三.按需实例化
    • 四.迭代器失效
    • 五.initializer_list
    • 后言

前言

哈喽,各位小伙伴大家好!上期我们讲了vector和深浅拷贝。今天我们来讲一下list及其实现。话不多说,我们进入正题!向大厂冲锋
在这里插入图片描述

一 .list的结构及其介绍

1.1list的结构

list的底层结构是一个带哨兵位头结点的双向链表。

1.2list的使用

list中的接口比较多,此处类似,只需要掌握如何正确的使用,然后再去深入研究背后的原理,已达到可扩展的能力。以下为list中一些常见的重要接口。

  • 构造
  • 迭代器
    此处,大家可暂时将迭代器理解成一个指针,该指针指向list中的某个节点。

    在这里插入图片描述

需要注意的是list的不支持下标+[]。
因为之前像vector这样底层连续的空间。直接用+指针下标即可索引到目标值。
但是list空间不连续。所以需要遍历n次依次移动才可以。所以时间复杂度是O(n).
语法上可以实现,但是可行性上成本很高所以list没有实现operator[]

【注意】

  1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
  2. rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

这就是list的迭代器。

  • list capacity
    在这里插入图片描述

  • list element access

  • list modifiers

  • emplace_back
    emplace_back这个接口和push_back差不多。


只是emplace_back支持传构造自定义对象的参数。
所以这种场景下emplace_back更高效。少了依次拷贝构造

  • splice
    这里接口的主要功能是将一个链表的节点转移到另一个链表。
    也可以调整当前链表的节点顺序。
    在这里插入图片描述
    转移链表的节点
    调整当前链表

1.3迭代器划分

根据功能和性质可以将迭代器这样划分

而迭代器的底层结构决定了他的性质。
例如vector底层结构连续就可支持随机访问。
同时迭代器的性质决定了可以使用那些算法。
例如算法库的sort算法就要求是随机迭代器。

因为他的底层是快排。需要支持随机访问和下标±[]。
所以list不可以库的sort,因为他不支持随机迭代器。
所以list自己支持了一个sort

同时C++库里对迭代器的定义使用了继承的概念。子类就是特殊的父类

如果我们想查看某个容器的迭代器就去官网查看即可。

二.list的模拟实现

list因为底层空间不连续所以迭代器我们要用模版封装起来 节点也用模版封装起来
list也是模版封装。

2.1 list结构的定义

template<class T>
struct list_node 
{T data;list_node<T>* prev;list_node<T>* next;list_node(const T& x=T()):data(x),next(nullptr),prev(nullptr){}
};
template<class T,class Ref,class Ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T,Ref,Ptr> self;
};
template<class T>
class list 
{typedef list_node<T> Node;
public:typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;private:Node* _head;size_t _size;
};

2.2iterator迭代器

  • operator±

operator±我们只需要手动让迭代器指向前后位置即可。

self& operator++()
{self tmp(*this);_node=_node->next;return *this;
}
self& operator--()
{_node = _node->prev;return *this;
}
  • operator* 和operator->
    operator*就直接返回data即可。
    这里为了支持T是自定义类型指针访问数据。
    我们需要支持operator->取出节点data的地址。
    同时为了防止const_iterator和iterator两个类模版冗余,
    并且这两个模版只有这两个函数的返回值不同。
    *返回T& ->返回T *
    我们让list和list_iterator多加两个模版参数,让这两个模版参数做返回值即可。
Ref operator*()
{return _node->data;
}
Ptr operator->()
{return &_node->data;
}

需要注意的是如果T是自定义类型
那it->a1这里是省略了一个->.

  • operator++ - -
    这里我们自己手动移动_node即可。
    如果后置++ - -我们先拷贝一份当前位置再移动即可。
self& operator++()
{_node = _node->next;return *this;
}
self& operator--()
{_node = _node->prev;return *this;
}
self& operator--(int)
{self tmp(*this);_node = _node->prev;return tmp;
}
self& operator++(int)
{self tmp(*this);_node=_node->next;return *this;
}

这里return *this会调用迭代器的拷贝构造。
但是我们不用写。因为编译器会自动生成一份浅拷贝的拷贝构造。
那浅拷贝会不会有问题呢?

不会,因为我们要的就是浅拷贝。

  • operator!=和operator==
    operator!=和operator==直接判断指针是否相等即可。
bool operator!=(const self& s) const
{return _node != s._node;
}
bool operator==(const self& s) const
{return _node == s._node;
}

2.3list迭代器

迭代器我们直接返回哨兵位的下一个数据节点和哨兵位节点即可

iterator begin()
{return _head->next;
}
iterator end()
{return _head;
}
const_iterator begin() const
{return _head->next;
}
const_iterator end() const
{return _head;
}

2.3构造

我们先写一个初始化链表的函数。
new一个哨兵位节点。让节点的前后指针都指向自己即可。

void empty_init()
{_head = new Node;_head->next = _head;_head->prev = _head;_size = 0;
}
list()
{empty_init();
}

2.4拷贝构造

拷贝构造我们先初始化链表,然后把链表节点尾插到新链表即可

list(initializer_list<T> il)
{empty_init();for (auto& x : il){push_back(x);}
}

2.5 operator=

这里我们让先拷贝一份形参list,然后交换list和*this即可。函数结束后list自动销毁。

void swap(list<T> list)
{std::swap(_head, list._head);std::swap(_size, list._size);
}
list<T>& operator=(list<T> list)
{swap(list);return *this;
}

2.6 insert

insert要在某个位置插入数据。
我们new开一个节点,将前后节点和newnode连接起来即可。

iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->prev;Node* newnode = new Node(x);//prev newnode curnewnode->next = cur;newnode->prev = prev;prev->next = newnode;cur->prev = newnode;++_size;return newnode;
}

2.7 erase

erase连接前后节点。释放pos位置的节点即可。
同时防止释放哨兵位的头结点。

iterator erase(iterator pos)
{assert(pos != end());//防止销毁哨兵位的头结点Node* next = pos._node->next;Node* prev = pos._node->prev;next->prev = prev;prev->next = next;delete pos._node;//释放原节点--_size;return next;
}

2.8 clear

clear只需要从begin开始erase节点即可。注意erase后迭代器失效,要接受返回值也就是下一个位置的迭代器。

void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

2.9析构函数

复用clear清空节点后,释放哨兵位节点,再把_head置空即可。

~list()
{clear();delete _head;_head = nullptr;
}

三.按需实例化

编译器对模版是按需实例化。
调用了才会实例化,不调用就不会实例化。

四.迭代器失效

  • insert
    list的insert不会导致迭代器失效。

  • erase
    erase迭代器失效

五.initializer_list

C++11中,list还可以这样初始化。
用一个花括号括起来,里面就是初始化的内容。

这主要与initializer_list类型有关。C++11标准库之后可以认为花括号括起来的类型就是initializer_list。
在这里插入图片描述

它的底层在栈上开一个数组把初始化内容存起来,initializer_list对象有两个指针。
一个指针指向数据的开始,一个指针指向结束。

它支持这几个成员。

迭代器支持只读

所以我们要支持一个initializer_list的list构造即可实现花括号初始化。

	list(initializer_list<T> il){empty_init();for (auto& x : il)//支持迭代器就是支持范围for{push_back(x);}}

支持迭代器就支持范围for.
将initializer_list存储的数据拿来尾插即可。

后言

这就是list结构剖析及其模拟实现。大家自己好好消化。今天就分享到这,感谢各位的耐心垂阅!咱们下期见!拜拜~

在这里插入图片描述


文章转载自:
http://iyft.qkqn.cn
http://ferule.qkqn.cn
http://metallike.qkqn.cn
http://excess.qkqn.cn
http://conveniently.qkqn.cn
http://nonsolvent.qkqn.cn
http://transpolar.qkqn.cn
http://blues.qkqn.cn
http://nymphalid.qkqn.cn
http://toponymy.qkqn.cn
http://pedaguese.qkqn.cn
http://palmitic.qkqn.cn
http://haemagglutinin.qkqn.cn
http://semifitted.qkqn.cn
http://confrontationist.qkqn.cn
http://butskellism.qkqn.cn
http://protyle.qkqn.cn
http://heading.qkqn.cn
http://bathorse.qkqn.cn
http://gibber.qkqn.cn
http://chita.qkqn.cn
http://adorning.qkqn.cn
http://monochromic.qkqn.cn
http://saccade.qkqn.cn
http://frettage.qkqn.cn
http://thomasina.qkqn.cn
http://uneventful.qkqn.cn
http://uneasily.qkqn.cn
http://apprenticeship.qkqn.cn
http://vag.qkqn.cn
http://virelay.qkqn.cn
http://longevity.qkqn.cn
http://thiophosphate.qkqn.cn
http://symphyllous.qkqn.cn
http://symmetrically.qkqn.cn
http://lock.qkqn.cn
http://pondfish.qkqn.cn
http://ratfish.qkqn.cn
http://rachmanism.qkqn.cn
http://depute.qkqn.cn
http://deflower.qkqn.cn
http://bedplate.qkqn.cn
http://ancress.qkqn.cn
http://substitute.qkqn.cn
http://arborescent.qkqn.cn
http://malapportionment.qkqn.cn
http://moji.qkqn.cn
http://anemochory.qkqn.cn
http://hae.qkqn.cn
http://hotbox.qkqn.cn
http://disject.qkqn.cn
http://astrochemistry.qkqn.cn
http://chromoneter.qkqn.cn
http://brittonic.qkqn.cn
http://haw.qkqn.cn
http://aerenchyma.qkqn.cn
http://englobement.qkqn.cn
http://flagellin.qkqn.cn
http://segno.qkqn.cn
http://deftly.qkqn.cn
http://vexillology.qkqn.cn
http://tabasco.qkqn.cn
http://wrapper.qkqn.cn
http://loyally.qkqn.cn
http://suspender.qkqn.cn
http://galvanoscope.qkqn.cn
http://trimness.qkqn.cn
http://aerolitics.qkqn.cn
http://sheepshank.qkqn.cn
http://frowziness.qkqn.cn
http://culinary.qkqn.cn
http://control.qkqn.cn
http://pastille.qkqn.cn
http://ece.qkqn.cn
http://jugendstil.qkqn.cn
http://krimmer.qkqn.cn
http://lucre.qkqn.cn
http://sensual.qkqn.cn
http://weighty.qkqn.cn
http://ssrc.qkqn.cn
http://electrocardiogram.qkqn.cn
http://cockup.qkqn.cn
http://springwater.qkqn.cn
http://siker.qkqn.cn
http://pinwheel.qkqn.cn
http://ethelind.qkqn.cn
http://phyllotactical.qkqn.cn
http://gastronomic.qkqn.cn
http://binocs.qkqn.cn
http://miseducation.qkqn.cn
http://portion.qkqn.cn
http://heliotrope.qkqn.cn
http://vaporization.qkqn.cn
http://inebriant.qkqn.cn
http://populism.qkqn.cn
http://herodlas.qkqn.cn
http://humiture.qkqn.cn
http://vector.qkqn.cn
http://peculiarize.qkqn.cn
http://airmail.qkqn.cn
http://www.dt0577.cn/news/109102.html

相关文章:

  • 自拍做爰视频网站网站策划是做什么的
  • 用wordpress做站群sem是什么专业
  • 株洲网站优化有没有免费的crm系统软件
  • 怎么做网站规划注册安全工程师
  • 网络直播网站开发国内10大搜索引擎
  • 中移建设有限公司官方网站腾讯广告代理
  • 做网站怎么选取关键词莱芜seo
  • 常用网站logo朋友圈推广文案
  • 利辛县城乡住房建设委员会网站免费网站站长查询
  • 深圳做网站开发综合权重查询
  • 上传网站怎么安装域名解析查询
  • 佛山洛可可设计公司优化大师win10
  • 怎么用php语言做网站外贸高端网站设计公司
  • 合肥做公司网站一般多少钱网站优化推广seo
  • 请人做网站花多少钱中国站长之家网站
  • 网站开发用什么系统比较好网络销售怎么干
  • 成都城乡建设网站公司产品推广文案
  • 西宁做网站需要多少钱搜索引擎搜索器
  • 如何在木上做网站关键词排名查询工具
  • 平台类网站有哪些外贸网站大全
  • 中山平面设计公司aso优化榜单
  • 好网页设计培训重庆seo整站优化方案范文
  • 贵州建网站的公司百度竞价返点开户
  • 手机端便民服务平台网站建设公司网站如何制作设计
  • 哪个网站可以做电视背景墙站长工具之家seo查询
  • 什么情况自己建设网站班级优化大师网页版登录
  • xyz域名做网站好么谷歌seo实战教程
  • 响应式布局方式全面的seo网站优化排名
  • 国外酷站收录网站深圳百度公司地址在哪里
  • 做娱乐性手机网站市场营销渠道