是中根遍历，先左子节点，然后根节点，最后右子节点。 • 为什么是中根遍历？因为刚刚说了二叉排序树的规则是：左子节点＜父节点＜右子节点。 • 这刚好是中根遍历的顺序，左中右。所以迭代器的 ++ 方向刚好是 K 越来越大的方向。 • 结论：遍历时，总是会按 K 从小到大的顺序。 k k k k k k v v v v v v 小 大 第三章：二叉排序树 高效的查找离不开我 高效的查找离不开我 回顾 set 容器 set 容器又可以分为 set 、 multiset 、 unordered_set 、 unordered_multiset 四类。 • set 容器和 map 的相似之处在于他的底层实现都是二叉排序树，现在让我们来鞋习一下他吧 。 vector 查找为什么低效 • vector 又称线性数组。在 vector 中查找元素可以用 头文件里的 std::find 。 • set a = { 1, 4, 2, 8, 5, 7 }; • a.find(5); • set 之所以能够实现 O(logn) 复杂度高效查找，是因为他内部预先构建好了一棵二叉排序树。 • 如何构建的？请看动画： 1 4 2 8 5 7 待插入的数 set 查找为什么高效 • set 又称集合（数学概念），是专为查找优化的容器，查找元素要用他自带的 find 函数。 •

写作动机 当情况不明时，抱着一个纯粹的目标干事就行了，其他 的留给时间检验。不懂就学，技术写作更像一种共创， 要反复总结和修改 ( 费曼学习法 ) 。 写作本书给我的启示 基础、排序、查找、树、图 代码框、颜色、图片绘制均由 Latex 完成 可参考点 为什么 为什么讲这个话题？ 为什么要讲数据结构和算法两部分？ 算法相关知识 算法相关知识 • 抽象数据类型 • 时空复杂度 Rust 实现算法 • 蒂姆排序 • 字典树 • 图 Rust 实现算 法 蒂姆排序 什么是蒂姆排序？ 蒂姆排序 位运算 高低位排序区别处理 https://github.com/QMHTMY/RustBook/blob/main/publication/code/chapter07/tim_sort_without_gallop.rs 字典树 怎么确定单词结束？ 需要区分大小写吗？

Poll 的执行逻辑 (Join / Select / Timeout) • 动态的调用关系 • 痛点：观测与调试工具无法理解灵活的执行逻辑 • Backtrace 不够直观 ( 调用栈 -> 调用树 ) • Tracing 无法追踪调用关系的变化 Async Rust 观测与调试的痛点 Async Rust 回顾 • 特性：用户态调度的无栈协程 • Pending Task 不存在栈空间 追踪关键 Future 的生命周期和控制流 • Init, First Poll, Pending, Next Poll, Ready, Cancel • 实时将 Task 的执行状态维护为一棵树 • 显示目前正在阻塞 / 执行的 Await Point • 得名 Await-Tree 基本用例 Await Tree 的设计原理与实现 基本用例 Await Tree 的设计原理与实现 Cancellation Await Tree 的维护 Await Tree 的设计原理与实现 • 下一次 Handle Await Tree 的实现 Await Tree 的设计原理与实现 • 一棵树代表一个 Task 的执行状态 • Task 单线程执行 • 在 Task-Local Storage 中无竞争维护 • 使用 Arena Tree 简化实现 • 无 Unsafe 代码 Await

list 都可以调用 std::find （ set 则直接提供了 find 作为成员函数，稍后 讨论） set 和 vector 迭代器的不同点 • set 的迭代器对象也重载了 + + 为红黑树的遍历。 • vector 提供了 + 和 += 的重 载，而 set 没有。这是因为 vector 中的元素在内存中是连 续的，可以随机访问。而 set 是不连续的，所以不能随机访 问，只能顺序访问。 ，里面的元素都是完全随机 的顺序，和插入的顺序也不 一样。虽然你可能注意到这 里的刚好和插入的顺序相反 ？巧合而已，具体怎么顺序 是和 glibc 实现有关的。 • set 基于红黑树实现，相当 于二分查找 树， unordered_set 基于散 列哈希表实现，正是哈希函 数导致了随机的顺序。 不同版本的 set 容器比较 类型 去重 有序 查找 插入 vector × × O(n) O(1)

可视化图探索分析 【亮点】 • K 步邻居查询、属性过滤 • 最短路径、全路径分析 • 按实体、边类型匹配查询 • 子图识别、环路识别等在 线图挖掘分析 • 实体、边可视化统计分析 • 树、层次、分组等多种布 局方式 • 基于 D3 自研的万级别实 体展现 可视化图探索分析 AtlasGraph 架构及实现 图技术简介 Takeway AtlasGraph 图数据库关键特性

bit 存储，一个 char 可以存储 8 个 bit 用 map 来存储 读取：如果不存在，则读到 0 写入：如果不存在，则创建该表项 用 unordered_map 来存储 map 基于红黑树，会按照键值排序，需要键值具有 operator< 重载，复杂度 O(logn) C++11 新增的 unordered_map 基于哈希表，不保证顺序但更高效，需要键值能被哈希，复杂度 O(1)

来管理，省的每个类实 现一遍原子引用计数器。 管理资源的类， 请删除他的拷贝 是数据结构：如果可以，定义拷贝和移动 • 这个类是你精心设计的数据结构，包括我们刚 刚发明的 Vector ，还有链表，红黑树等。如 果这些数据结构是可以支持拷贝的（比如 Vector 就可以），你可能需要自己一个个定义。 如果不支持，那就删除（ = delete ）。 函数参数：如何避免不必要的拷贝 • 注意到，如果函数的参数声明为值类型，

遍历二维的网格，然后用 mdec(t) 求出要访问 元素的 (x,y) 坐标，这样可以保证的数据在时间 t 上是接近的，同时二 维空间上 (x,y) 也是接近的，有利于访存局域性。 • 莫顿码还可用于构建八叉树、 BVH 等，但不是今天的话题。 https://cloud.tencent.com/developer/article/1461134 莫顿编码 (encode) 和解码 (decode) 的实现