什么是Ownership Ownership是Rust中的一个核心特点，可以理解成是Rust做到内存安全的重要手段。不同于带GC的语言或是C/C++这样显式管理内存的语言，ownership系统实现了在编译期管理内存(但又不需要程序员过分手动介入)从而避免了GC开销。 硬要说的话个人感觉像是C++中的RAII，但是由于带有编译器级别的检查，比C++更不容易出错。 Ownership的规则 Rust中所有的值(value)都有一个作为所有者(owner)的变量(variable) (一个值)同时只能有一个owner(参考Rust中赋值的Move语义和在内存管理中起到的作用) 当owner离开作用域(scope)时，其对应的值(value)就会被释放(dropped)(无论是堆上还是栈上的) 解释 Variable Scope 和其他语言类似，变量离开作用域后，就失效了。当一个变量离开作用域时，Rust会自动调用drop 函数，释放内存 Heap and Stack 和C/C++一样，Rust的内存管理也分为堆和栈，栈上内存由操作系统自动管理，堆上内存需要程序员手动管理（Rust中通过Ownership规则和编译器自动插入释放内存的语句，避免像C/C++那样的显式管理） Move Rust中的简单赋值=大多类似于其他语言中的浅拷贝，仅拷贝栈上内容。在Rust中，这种变量和数据交互(interact)的方式称为Move。当发生Move(我理解为“实际”所有权的转移)后，原变量在离开作用域后，编译器不会插入drop，从而避免内存的重复释放 这里还引出Rust的另一个设计思想：Rust永远不会“自动”(automatically)去“深拷贝”数据。因此，默认赋值行为的运行时代价都可以认为是比较低的 String结构示例 let s1 = String::from("hello") let s2 = s1 Clone 那么如果我们真的需要深拷贝一块数据需要怎么做呢，在Rust中需要显式调用clone。这实际上也是显式提醒程序员，这里有一段特殊的代码要执行，有可能消耗会比较大 fn main() { let s1 = String::from("hello"); let s2 = s1.clone(); println!("s1 = {}, s2 = {}", s1, s2); } Another wrinkle: Stack-Only Data 一些简单数据类型，像整型，我们不调用clone，也不是Move语义，原因在于，这些简单类型在编译期就能确定大小，并且完全存储于栈上，所以拷贝比较快。 Rust中有一种特殊的注解(annotation) Copytrait, 实现了这个trait类型的变量在赋值后依然可以使用。但如果实现了Droptrait，Copy就无法使用 什么样的类型可以实现Copytrait呢？可以参考官方文档，通常来说，没有需要分配资源的类型可以实现。以下是一些实现了Copy的类型 所有整型，如u32 Boolean类型,bool 浮点型, 如f64 字符类型，char 元组(Tuples)，当然只能包含同样实现Copy的类型，如(i32, i32)实现了，但(i32, String)没有 Functions 函数中传参和返回值也一样有ownership的转移问题，传参即赋值，返回值会将ownship move到调用它的函数 ...

树堆的基本概念 树堆（Treap）是二叉排序树（Binary Sort Tree）与堆（Heap）结合产生的一种拥有堆性质的二叉排序树。 但是这里要注意两点，第一点是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap并不一定是；第二点是Treap并不严格满足平衡二叉排序树（AVL树）的要求，即树堆中每个节点的左右子树高度之差的绝对值可能会超过1，只是近似满足平衡二叉排序树的性质。 Treap每个节点记录两个数据，一个是键值，一个是随机附加的优先级，Treap在以关键码构成二叉排序树的同时，又以结点优先级形成最大堆和最小堆。所以Treap必须满足这两个性质，一是二叉排序树的性质，二是堆的性质。如下图，即为一个树堆。 关键步骤 查找 按照正常BST的查找过程即可 插入 给新节点一个随机的权重值，按照普通二叉搜索树，使用key进行插入 为了保证堆的特性，插入完成后要进行旋转操作，保证仍为最大堆或最小堆。以最大堆为例，若插入到右子树，且权重比父结点大，就要实现一次左旋转，使右子树根结点成为新的父节点；反之左旋，直到满足堆的特性为止 删除 按照正常的查找流程找到待删除节点后，有三种情况 待删除结点本身就是叶子结点，直接删除即可 待删除结点只有一个孩子（一棵子树），用这个孩子替换待删除结点，实现删除效果 待删除结点两棵子树均不为空时，先进行旋转。以最大堆为例，找到权重更大的孩子，向相反方向旋转（即若左孩子权重更大，执行右旋），直到待删除结点满足上面两种情况之一，再进行删除 具体实现 参考LeetCode(cn) 第1438题的实现，其中对于旋转的优雅实现值得一学 import "math/rand" type node struct { ch [2]*node priority int key int cnt int } func (o *node) cmp(b int) int { switch { case b < o.key: return 0 case b > o.key: return 1 default: return -1 } } func (o *node) rotate(d int) *node { x := o.ch[d^1] o.ch[d^1] = x.ch[d] x.ch[d] = o return x } type treap struct { root *node } func (t *treap) ins(o *node, key int) *node { if o == nil { return &node{priority: rand.Int(), key: key, cnt: 1} } if d := o.cmp(key); d >= 0 { o.ch[d] = t.ins(o.ch[d], key) if o.ch[d].priority > o.priority { o = o.rotate(d ^ 1) } } else { o.cnt++ } return o } func (t *treap) del(o *node, key int) *node { if o == nil { return nil } if d := o.cmp(key); d >= 0 { o.ch[d] = t.del(o.ch[d], key) } else { if o.cnt > 1 { o.cnt-- } else { if o.ch[1] == nil { return o.ch[0] } if o.ch[0] == nil { return o.ch[1] } d = 0 if o.ch[0].priority > o.ch[1].priority { d = 1 } o = o.rotate(d) o.ch[d] = t.del(o.ch[d], key) } } return o } func (t *treap) insert(key int) { t.root = t.ins(t.root, key) } func (t *treap) delete(key int) { t.root = t.del(t.root, key) } func (t *treap) min() (min *node) { for o := t.root; o != nil; o = o.ch[0] { min = o } return } func (t *treap) max() (max *node) { for o := t.root; o != nil; o = o.ch[1] { max = o } return } func longestSubarray(nums []int, limit int) (ans int) { t := &treap{} left := 0 for right, v := range nums { t.insert(v) for t.max().key-t.min().key > limit { t.delete(nums[left]) left++ } ans = max(ans, right-left+1) } return } func max(a, b int) int { if a > b { return a } return b } 参考 树堆（Treap）图文详解与实现 leecode-cn 1438

介绍一些Rust的基本语法概念，这些概念在很多别的语言中找到类似的表示，有相同也有区分。 Variable and Mutability Rust中的变量默认是不可变的(immutable), Rust的安全性和易写并发的推手(nudge)之一 不可变变量并不等于常量(constants) 始终不可变，并且总是需要[annotate] 可以在任何范围内声明，包括全局(global) 只能用一个常量表达式(constant expression)赋值 const MAX_POINTS: u32 = 100_000; Shadowing 和mut不同 同一个名字可以成为不同的类型 Data Types Rust是静态类型语言(statically typed) 当有多种可能性编译器无法直接推导(infer)出来时，要使用类型注解(type annotation) let guess: u32 = "42".parse().expect("Not a number!"); Scalar Types integers i/u 区分有无符号 有明确大小(an explicit size) 也可以使用isize/usize表示架构相关大小(64/32) 对于原始数值类型(primitive numeric types)，可以使用标准库的特定想法处理overflow, wrapping_*, checked_*, overflowing_*, saturating_* floating-point numbers f32, f64, 默认为f64 Booleans bool true/false characters char single quotes 4bytes, represents a Unicode Scalar Value(U+0000U+D7FF, U+E000U+10FFFF) Compound Types tuples fixed length the types of the different value in the tuple don’t have to be the same optional type annotations use pattern matching to destructure a tuple value x.0/x.1/….is also available arrays also fixed length(use vector if the size needs to be growed or shrinked) every element must have the same type data allocated on the stack rather than the heap optional type annotation: [type; size] [value:size]: a more concise way to initialize an array with the same value using indexing, e.g.[], to access array elements Functions ...

Rust简要概括 Rust是一门编译型语言 rustup是Rust工具链管理工具 rustc是Rust的编译器 cargo是Rust的高级构建工具和包管理工具 rustc可用于简单文件编译，但更建议使用cargo来进行工程化的管理，可适用于更复杂的工程 带!的“函数”是Rust中的Macro，具体见官方教程19章 可使用cargo build –release构建用于发布的应用程序 Cargo.toml可用于依赖管理, Cargo.lock具体跟踪了工程中的版本依赖(不手动修改) 参考资料 Rust官方文档rust offical docs

<!DOCTYPE html> Markmap