《C++：从代码到机器》：面试官：“说说 list 怎么模拟实现？” 我掏出这份代码，他点头了

Ne0inhk

— 9 min read
《C++：从代码到机器》：面试官：“说说 list 怎么模拟实现？” 我掏出这份代码，他点头了

个人头像

✨ 孤廖：个人主页

🎯 个人专栏：《C++：从代码到机器》

🎯 个人专栏：《Linux系统探幽：从入门到内核》

🎯 个人专栏：《算法磨剑：用C++思考的艺术》

折而不挠，中不为下

在这里插入图片描述

文章目录

正文：

1.list的介绍与使用

1.1 list的介绍 list的介绍

list的文档介绍

在这里插入图片描述

1.2 list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。
1.2.1 list的构造
在这里插入图片描述
1.2.2 list iterator的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点

【注意】:

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
1.2.3 list capacity
在这里插入图片描述
1.2.4 list element access
在这里插入图片描述
1.2.5 list modifiers
在这里插入图片描述
list中还有一些操作，需要用到时大家可参阅list的文档说明。
1.2.6 list的迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭
代器，其他迭代器不会受到影响。vector迭代器失效可以看我主页的一篇文章
《C++：从代码到机器》：vector 的坑只有 C++ 党懂？介绍使用 + 深度剖析 + 模拟实现，帮你全避开

代码解释：

#include<iostream>#include<list>usingnamespace std;// 存在问题的函数voidTestListIterator1(){int array[]={1,2,3,4,5,6,7,8,9,0}; list<int>l(array, array +sizeof(array)/sizeof(array[0]));auto it = l.begin();while(it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值 l.erase(it);++it;}}// 改正后的函数voidTestListIterator(){int array[]={1,2,3,4,5,6,7,8,9,0}; list<int>l(array, array +sizeof(array)/sizeof(array[0]));auto it = l.begin();while(it != l.end()){ l.erase(it++);// it = l.erase(it);}}intmain(){// 可以取消下面的注释来测试函数// TestListIterator1();// TestListIterator();return0;}

2. list的模拟实现

2.1 模拟实现list

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。
希望大家有时间 可以自己实现一下底层 来增强理解
#pragmaonce#include<iostream>#include<assert.h>usingnamespace std;//模拟stl_list//带头双向循环链表namespace twg {template<classT>structlist_node{//数据域 T _data;//指针域 list_node<T>* next; list_node<T>* prev;list_node(const T& data =T()):_data(data),next(nullptr),prev(nullptr){}};template<classT,classRef,classPtr>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self; Node* _node;//原生指针//默认构造 list_iterator<T, Ref, Ptr>(Node* node):_node(node){}//重载运算符//前置 Self&operator++(){ _node = _node->next;return*this;} Self&operator--(){ _node = _node->prev;return*this;}//后置 Self operator++(int){ Self cur =*this; _node = _node->next;return cur;} Self operator--(int){ Self cur =*this; _node = _node->prev;return cur;}//重载* Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};template<classT>classlist{typedef list_node<T> Node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;typedef list<T> container;public:voidempty_init(){ Head =new Node; Head->next = Head; Head->prev = Head; _size =0;}//默认构造list(){empty_init();}//拷贝构造list(const list<T>& s){empty_init();for(auto& e : s){push_back(e);}}//析构~list(){clear();delete Head; Head =nullptr;}//清理 资源voidclear(){auto it =begin();while(it !=end()){ it =erase(it);}}//赋值 list<T>&operator=(const list<T>& s){ list<T>tmp(s);swap(tmp);return*this;}voidswap(container& s){ std::swap(s.Head, Head); std::swap(s._size, _size);}//普通迭代器//begin iterator begin(){return Head->next;//返回时本质是调用了iterator()的构造函数产生了临时对象}//end iterator end(){return Head;}//const 迭代器//begin const_iterator begin()const{return Head->next;//返回时本质是调用了iterator()的构造函数产生了临时对象} const_iterator end()const{return Head;}//insertvoidinsert(iterator pos,const T& x){ Node* cur = pos._node; Node* prev = cur->prev; Node* newnode =new Node; newnode->_data = x; newnode->next = cur; newnode->prev = prev; prev->next = newnode; cur->prev = newnode; _size++;}//erase iterator erase(iterator pos){ iterator tmp = pos;++tmp;assert(pos !=end()); Node* cur = pos._node; iterator next = tmp; cur->prev->next = cur->next; cur->next->prev = cur->prev;delete cur; cur =nullptr; _size--;return next;}//push_bakcvoidpush_back(const T& x){insert(end(), x);}//pop_backvoidpop_back(){assert(_size !=0);erase(--end());}voidprint1()const{auto it =begin();while(it !=end()){ cout <<*it <<" ";++it;} cout << endl;}voidprint2()const{auto it =begin();while(it !=end()){ cout << it->a <<" ";++it;} cout << endl;}boolempty()const{return _size ==0;} size_t size()const{return _size;}private: Node* Head; size_t _size;};voidtest1(){ list<int> l1; l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4); l1.push_back(5); l1.print1();}voidtest2(){structAA{int a =1;}; list<AA> l1; l1.push_back({1}); l1.push_back({2}); l1.push_back({3}); l1.push_back({4}); l1.push_back({5}); l1.print2(); l1.clear(); l1.print2();}}

list的模拟实现码云

2.2 list的反向迭代器

通过前面例子知道，反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

【代码解释】:

template<classIterator>classReverseIterator{typedeftypenameIterator::Ref Ref;typedeftypenameIterator::Ptr Ptr;typedef ReverseIterator<Iterator> Self;public:// 构造ReverseIterator(Iterator it):_it(it){}// 具有指针类似行为 Ref operator*(){ Iterator temp = _it;--temp;return*temp;} Ptr operator->(){return&(operator*());}// 迭代器运算符++ Self&operator++(){--_it;return*this;} Self operator++(int){ Self temp(*this);--_it;return temp;} Self&operator--(){++_it;return*this;} Self operator--(int){ Self temp(*this);++_it;return temp;}// 迭代器支持比较booloperator!=(const Self& l)const{return _it != l._it;}booloperator==(const Self& l)const{return _it == l._it;}private: Iterator _it;};

3. list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
在这里插入图片描述

结语

看到这里，你已经把 STL 里的 list 彻底“吃透”啦——从双向链表的底层逻辑，到迭代器的使用（连容易栽跟头的“失效坑”都摸清了），再到亲手模拟实现核心功能，最后还能清晰对比它和 vector 在“增删效率”“随机访问”“空间利用”上的差异。这些知识就像给你搭好了“序列式容器”的骨架，让你对 STL 的理解更扎实。

不过，STL 的容器家族里，还有**栈（stack）和队列（queue）**这对“特殊选手”等着我们探索～它们看似简单（只允许一端/两端操作），实则藏着巧妙的“适配器”设计（比如依赖其他容器实现自身逻辑），而且在“表达式求值”“广度优先搜索”等场景中是绝对的主力。下一篇，我们就来解锁栈和队列：从它们的接口用法，到适配器模式的底层原理，再到实战中的经典应用，带你把这对“容器搭档”玩明白。

要是现在对 list 的“迭代器模拟”“反向迭代器包装”还有模糊的地方，不妨再翻翻代码注释；想更直观感受 list 和 vector 的性能差距，也可以自己写个测试（比如批量插入 10 万条数据）。欢迎在评论区分享你和 list 打交道的故事，或者聊聊你对栈和队列的好奇，咱们一起把 STL 从“会用”变成“用得溜”～

在这里插入图片描述

Read more

Java+Leaflet:湖南省道路长度WebGIS的构建与实践

Java+Leaflet:湖南省道路长度WebGIS的构建与实践

目录 前言 一、基础空间数据简介 1、涉及相关表 2、省域道路长度检索 二、Java后台实现 1、道路视图对象 2、Mapper空间检索查询 3、控制API实现 三、WebGIS界面实现 1、里程图例及初始化 2、各地市信息展示 四、成果展示 1、总体展示 2、分区域说明 五、总结 前言         在当今数字化时代，地理信息系统（GIS）技术在各个领域都发挥着至关重要的作用。它不仅为城市规划、交通管理、环境保护等提供了强大的技术支持，也为公众获取地理信息提供了便捷的途径。湖南省作为中国中部地区的重要省份，拥有复杂的地理环境和庞大的交通网络。如何高效地管理和展示湖南省的道路长度信息，对于交通规划、物流运输以及公众出行都具有极其重要的意义。因此，我们开展了基于Java和Leaflet的湖南省道路长度WebGIS系统的构建与实践研究。         湖南省地处中国中部，交通网络密集且复杂。随着经济的快速发展和城市化进程的加快，湖南省的道路建设不断推进，

By Ne0inhk

【前端面经】字节前端社招面经分享（已offer）

社招时间线 全程面试时间都是候选人定的，字节效率还是非常高的 * 10.23 HR电话沟通约面 * 10.28 技术一面（两小时后告知通过约面） * 10.30 技术二面（半小时后告知通过约面） * 11.4 技术三面（两小时后告知通过约面） * 11.5 HR面（三小时后告知通过） * 11.5 OC * 11.5 收集薪资流水证明 * 11.6 谈薪 * 11.11 书面offer 面试 基本都是从简历出发深挖问题，没有太多通用性，仅列出偏技术点不涉及具体项目的问题。 因为AI相关内容较多，所以问题也偏AI。 技术一面（1h） 1. 代码输出题：闭包与变量提升相关 2. 手写题：数组转树形结构 3. 手写题：

By Ne0inhk
前端学习日记 - 前端函数防抖详解

前端学习日记 - 前端函数防抖详解

前端函数防抖详解 * 为什么使用防抖 * 函数防抖的应用场景 * 函数防抖原理与手写实现 * 原理 * 手写实现 * 使用 Lodash 的 \_.debounce * 完整示例：防抖搜索组件 * 结语 在现代 Web 应用中，函数防抖（debounce）是一种常见且高效的性能优化手段，用于限制高频事件触发下的函数调用次数，从而减少不必要的计算、网络请求或 DOM 操作。本文将从“为什么使用防抖”切入，介绍典型的应用场景，深入解析防抖原理，并给出从零实现到在实际项目中使用 Lodash 的完整代码示例，帮助你快速掌握前端防抖技术。 为什么使用防抖 函数防抖的核心思想是在连续触发的事件停止后，仅执行最后一次调用，以避免频繁触发带来的性能问题 ([MDN Web Docs][1])。 在不使用防抖的情况下，例如在 input 输入事件或 window.resize 事件中直接调用逻辑，页面可能会因短时间内大量调用而出现卡顿或请求风暴 ([GeeksforGeeks]

By Ne0inhk