• rust std

    目录

    一，std基本数据结构

    1，std::option

    2，std::result

    二，std容器

    1，Vec（向量、栈）

    2，VecDeque（队列、双端队列）

    3，LinkedList（双向链表）

    4，哈希表

    5，集合

    6，BinaryHeap（二叉堆、优先队列）

    7，字符串

    三，自定义数据结构

    1，单链表（力扣版）

    2，二叉树（力扣版）

    四，std::cmp

    1，min函数、max函数

    2，Reverse

    五，std算法、自实现算法

    1，排序

    （1）vector排序

    （2）自定义排序

    2，二分

    （1）vector二分

    （2）自定义二分

    3，哈希算法

    4，BFS

    5，并查集

    六，通用函数

    1，new函数

    2，from

    七，二元关系特征

    0，继承、一致性大前提

    1，std::cmp::PartialEq、lhs、rhs

    2，std::cmp::Eq

    3，std::cmp::PartialOrd

    4，PartialOrd的二元关系推导

    5，std::cmp::Ord

    6，默认序关系

    7，自定义序关系的场景

    rust std 文档

    一，std基本数据结构

    use std::option;

    1，std::option

    （1）定义

    1. pub enum Option {
    2.     None,
    3.     Some(T),
    4. }

    这是一个枚举值，要么等于整型的None，要么等于泛型的只含一个元素的元组Some

    （2）is_some、is_none

    1. 	let x:Option=Some(2);
    2. 	assert_eq!(x.is_some(),true);
    3. 	assert_eq!(x.is_none(),false);
    4. 	let x:Option=None;
    5. 	assert_eq!(x.is_some(),false);
    6. 	assert_eq!(x.is_none(),true);

    （3）is_some_and

    1. 	let x:Option=Some(2);
    2. 	assert_eq!(x.is_some_and(|x| x>1),true);

    （4）unwrap

    当我们确定一个Option值是Some值时，可以直接调用unwrap把Some里面的值取出来。

    1.     let p = Some(5);
    2.     assert_eq!(p.unwrap(),5);

    2，std::result

    use std::result;

    （1）定义

    1. pub enum Result {
    2.     Ok(T),
    3.     Err(E),
    4. }

    这也是个枚举值，要么是等于泛型的元组OK，要么是等于泛型的元组Err

    2个模板类型可以一样也可以不一样。

    （2）is_ok、is_err

    1. 	let x:Result=Ok(1);
    2. 	assert_eq!(x.is_ok(),true);
    3. 	assert_eq!(x.is_err(),false);
    4. 	let x:Result=Err("456");
    5. 	assert_eq!(x.is_ok(),false);
    6. 	assert_eq!(x.is_err(),true);

    str类型要带取址符。

    （3）is_ok_and、is_err_and

    1. 	let x:Result=Ok(1);
    2.     assert_eq!(x.is_ok_and(|x| x==1),true);
    3. 	assert_eq!(x.is_err(),false);
    4. 	let x:Result=Err("456");
    5. 	assert_eq!(x.is_ok(),false);
    6. 	assert_eq!(x.is_err_and(|x| x=="456"),true);

    （4）ok、err

    用ok、err可以直接取出2个成员值，有一个成员会是Some值，另一个会是None值。

    1. 	let x:Result=Ok(1);
    2.     assert_eq!(x.ok(),Some(1));
    3. 	assert_eq!(x.err(),None);
    4. 	let x:Result=Err("456");
    5. 	assert_eq!(x.ok(),None);
    6. 	assert_eq!(x.err(),Some("456"));

    （5）unwrap

    1.     let x:Result=Ok(1);
    2.     assert_eq!(x.unwrap(),1);
    3.     assert_eq!(x.ok().unwrap(),1);

    （6）map

    源码：

    1.     pub fn map U>(self, op: F) -> Result {
    2.         match self {
    3.             Ok(t) => Ok(op(t)),
    4.             Err(e) => Err(e),
    5.         }
    6.     }

    示例：

    1. fn main() {
    2.     let x:Result=Ok(1);
    3.     let x=x.map(|x| x+1);
    4.     assert_eq!(x,Ok(2));
    5.     let x:Result=Err(1);
    6.     let x=x.map(|x| x+1);
    7.     assert_eq!(x,Err(1));
    8.     print!("end ");
    9. }

    因为Result的map方法是只对Ok生效的

    二，std容器

    1，Vec（向量、栈）

    use std::vec::Vec;

    （1）用作vector

    1.     let nums:Vec=vec![1,2,4,3];
    2. 	assert_eq!(nums.len(),4);
    3. 	assert_eq!(nums[3],3);
    4. 	assert_eq!(nums.is_empty(),false);

    遍历：

    1.   let mut nums:Vec=vec![1,2,4,3];
    2.   for i in 0..nums.len() {
    3.     nums[i]=0;
    4.   }
    5.   assert_eq!(nums, vec![0,0,0,0]);
    6.   for x in nums.iter_mut(){
    7.     *x=1;
    8.   }
    9.   assert_eq!(nums, vec![1,1,1,1]);
    10.   for mut x in nums{
    11.     x=1;
    12.   }
    13.   // assert_eq!(nums, vec![1,1,1,1]); //error，nums丧失了所有权

    vector翻转：

    1. fn vector_reverse (v:&Vec)->Vec{
    2.     let mut ans = Vec::new();
    3.     let mut i = v.len();
    4.     loop {
    5.         if i==0{
    6.             break;
    7.         }
    8.         i-=1;
    9.         ans.push(v[i].clone());
    10.     }
    11.     return ans;
    12. }

    （2）用作栈

    1.     let mut nums:Vec=Vec::new();
    2. 	nums.push(123);
    3. 	assert_eq!(nums.len(),1);
    4. 	assert_eq!(nums.last(),Some(&123));
    5. 	assert_eq!(nums.len(),1);
    6. 	assert_eq!(nums.pop(),Some(123));
    7. 	assert_eq!(nums.len(),0);

    （3）实现原理

    1. pub(crate) struct RawVec {
    2.     ptr: Unique,
    3.     cap: usize,
    4.     alloc: A,
    5. }
    6. pub struct Vecunstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global> {
    7.     buf: RawVec,
    8.     len: usize,
    9. }

    buf中存放的是指针和最大可存储元素个数，len是实际元素个数。

    例如push函数：

    1.     pub fn push(&mut self, value: T) {
    2.         if self.len == self.buf.capacity() {
    3.             self.buf.reserve_for_push(self.len);
    4.         }
    5.         unsafe {
    6.             let end = self.as_mut_ptr().add(self.len);
    7.             ptr::write(end, value);
    8.             self.len += 1;
    9.         }
    10.     }

    每次push都检查len和cap，扩容方案是倍增，同C++。

    reserve函数：

    1.     pub fn reserve(&mut self, additional: usize) {
    2.         self.buf.reserve(self.len, additional);
    3.     }
    4.  
    5.     let mut v = Vec::from([1]);
    6.     v.reserve(10);
    7.     assert_eq!(v.capacity(), 11);
    8.     assert_eq!(v.len(), 1);

    Rust::reverse(n)等价于C++STL::reserve(n+ v.capacity())

    resize函数：

    1.     pub fn resize(&mut self, new_len: usize, value: T) {
    2.         let len = self.len();
    3.         if new_len > len {
    4.             self.extend_with(new_len - len, value)
    5.         } else {
    6.             self.truncate(new_len);
    7.         }
    8.     }
    9.  
    10.  
    11.     let mut vec = vec!["hello"];
    12.     vec.resize(3, "world");
    13.     assert_eq!(vec, ["hello", "world", "world"]);
    14.     let mut vec = vec![1, 2, 3, 4];
    15.     vec.resize(2, 0);
    16.     assert_eq!(vec, [1, 2]);

    resize函数和C++完全相同。

    2，VecDeque（队列、双端队列）

    use std::collections::VecDeque;

    （1）用作队列

    new创建空队列

    len获取长度

    with_capacity创建空队列 但 预占内存

    push_back是尾部插入

    pop_front是头部弹出，并获取弹出值

    1.     let deq:VecDeque = VecDeque::new();
    2.     assert_eq!(deq.len(), 0);
    3.     let mut deq:VecDeque = VecDeque::with_capacity(10);
    4.     assert_eq!(deq.len(), 0);
    5.     deq.push_back(1);
    6.     deq.push_back(2);
    7.     assert_eq!(deq.pop_front(),Some(1));
    8.     assert_eq!(deq.len(), 1);

    （2）用作双端队列

    from从列表创建队列

    get获取任意位置的值

    push_front头部插入

    pop_back尾部弹出，并获取弹出值

    2个队列还可以直接比较

    1.     let mut deq = VecDeque::from([-1, 0, 1]);
    2. 	assert_eq!(deq.get(2),Some(&1));
    3. 	deq.push_front(2);
    4. 	assert_eq!(deq.pop_back(),Some(1));
    5. 	let deq2 = VecDeque::from([2, -1, 0]);
    6. 	assert_eq!(deq,deq2);
    7. 	deq.pop_back();
    8. 	assert_ne!(deq,deq2);

    （3）实现原理

    1. pub struct VecDeque {
    2.     head: usize,
    3.     len: usize,
    4.     buf: RawVec,
    5. }

    不像c++采用分段数组，rust的双端队列采用的是循环数组。

    扩容方案：

    1.     fn grow(&mut self) {
    2.         // Extend or possibly remove this assertion when valid use-cases for growing the
    3.         // buffer without it being full emerge
    4.         debug_assert!(self.is_full());
    5.         let old_cap = self.capacity();
    6.         self.buf.reserve_for_push(old_cap);
    7.         unsafe {
    8.             self.handle_capacity_increase(old_cap);
    9.         }
    10.         debug_assert!(!self.is_full());
    11.     }

    和Vec一样，采用倍增的扩容方案。

    这里的扩容稍微麻烦一点，先reserve_for_push倍增拷贝所有数据，然后handle_capacity_increase再拷贝部分数据（最多一半），调整head和tail

    3，LinkedList（双向链表）

    use std::collections::LinkedList;

    （1）用法

    支持在头部和尾部插入节点，在任意位置删除节点。

    1.     let mut list = LinkedList::new();
    2.     list.push_back(2);
    3.     list.push_back(3);
    4.     list.push_front(1);
    5.     // list is 1->2->3
    6.     assert_eq!(list.remove(1), 2);
    7.     assert_eq!(list.remove(0), 1);
    8.     assert_eq!(list.remove(0), 3);

    与其说这是双向链表，不如说这个有点像数组。

    （2）源码

    1. pub struct LinkedList {
    2.     head: Option>>,
    3.     tail: Option>>,
    4.     len: usize,
    5.     alloc: A,
    6.     marker: PhantomData, A>>,
    7. }
    8.  
    9. struct Node {
    10.     next: Option>>,
    11.     prev: Option>>,
    12.     element: T,
    13. }

    4，哈希表

    use std::collections::HashMap;

    use std::collections::BTreeMap;

    2个哈希表的常用方法相同：

    1.     let mut m = HashMap::new();
    2.     if let Some(p) = m.get_mut(&1){
    3.         *p += 1;
    4.     }else{
    5.         m.insert(1, 1);
    6.     }
    7.  
    8.     let mut m = BTreeMap::new();
    9.     if let Some(p) = m.get_mut(&1){
    10.         *p += 1;
    11.     }else{
    12.         m.insert(1, 1);
    13.     }

    例如，实现一个基于去重计数功能的类：

    1. struct CalNum{
    2.     m:HashMap,
    3. }
    4. impl CalNum{
    5.     fn add(& mut self,x:i32)->i32{
    6.         if let Some(p)=self.m.get_mut(&x){
    7.             *p+=1;
    8.         }else{
    9.             self.m.insert(x,1);
    10.         }
    11.         return self.m.len() as i32;
    12.     }
    13.     fn sub(& mut self,x:i32)->i32{
    14.         if let Some(p)=self.m.get_mut(&x){
    15.             *p-=1;
    16.             if *p <= 0{
    17.                 self.m.remove(&x);
    18.             }
    19.         }
    20.         return self.m.len() as i32;
    21.     }
    22.     fn get(& mut self)->i32{
    23.         return self.m.len() as i32;
    24.     }
    25. }

    5，集合

    use std::collections::HashSet;

    use std::collections::BTreeSet;

    （1）常用方法

    2个集合的常用方法完全相同。

    HashSet：

    1.     let mut m = HashSet::new();
    2.     m.insert(5);
    3.     assert_eq!(m.len(), 1);
    4.     if !m.contains(&6) {
    5.         m.insert(6);
    6.     }
    7.     assert_eq!(m.len(), 2);
    8.     m.insert(6);
    9.     assert_eq!(m.len(), 2);
    10.     m.remove(&5);
    11.     m.remove(&6);
    12.     assert_eq!(m.is_empty(), true);

    BTreeSet：

    1.     let mut m = BTreeSet::new();
    2.     m.insert(5);
    3.     assert_eq!(m.len(), 1);
    4.     if !m.contains(&6) {
    5.         m.insert(6);
    6.     }
    7.     assert_eq!(m.len(), 2);
    8.     m.insert(6);
    9.     assert_eq!(m.len(), 2);
    10.     m.remove(&5);
    11.     m.remove(&6);
    12.     assert_eq!(m.is_empty(), true);

    （2）数据类型约束

    1. impl HashSet
    2. where
    3.     T: Eq + Hash,
    4.     S: BuildHasher,
    5. {
    6. ......
    7. }

    HashSet的泛型实现就约束了T具有Eq和Hash

    1. impl BTreeSet {
    2. ......
    3.     pub fn contains(&self, value: &Q) -> bool
    4.     where
    5.         T: Borrow + Ord,
    6.         Q: Ord,
    7.     {
    8.         self.map.contains_key(value)
    9.     }
    10. ......
    11.     pub fn insert(&mut self, value: T) -> bool
    12.     where
    13.         T: Ord,
    14.     {
    15.         self.map.insert(value, SetValZST::default()).is_none()
    16.     }
    17. ......
    18. }

    BTreeSet的泛型实现约束较少，但是常见的接口需要Ord特征。

    （3）浮点数示例

    如果确保浮点数不会等于NAN，那么可以这么写：

    1. #[derive(PartialEq,PartialOrd)]
    2. struct FloatWithOrd{
    3.     x:f32, // do not let x be NAN
    4. }
    5. impl Eq for FloatWithOrd{
    6. }
    7. impl Ord for FloatWithOrd {
    8.     #[inline]
    9.     fn cmp(&self,other:&FloatWithOrd)->Ordering{
    10.         if(self.x < other.x){
    11.             return Ordering::Less;
    12.         }
    13.         if(self.x > other.x){
    14.             return Ordering::Greater;
    15.         }
    16.         return Ordering::Equal;
    17.     }
    18. }
    19.  
    20. fn main() {
    21.     let mut m = BTreeSet::new();
    22.     m.insert(FloatWithOrd{x:5.0});
    23.     assert_eq!(m.len(), 1);
    24.     if !m.contains(&FloatWithOrd{x:6.0}) {
    25.         m.insert(FloatWithOrd{x:6.0});
    26.     }
    27.     assert_eq!(m.len(), 2);
    28.     m.insert(FloatWithOrd{x:6.0});
    29.     assert_eq!(m.len(), 2);
    30.     m.remove(&FloatWithOrd{x:5.0});
    31.     m.remove(&FloatWithOrd{x:6.0});
    32.     assert_eq!(m.is_empty(), true);
    33.     println!("end");
    34. }

    浮点数类型的HashSet比较麻烦，需要Hash，暂时不研究这个。

    6，BinaryHeap（二叉堆、优先队列）

    use std::collections::BinaryHeap;

    看实现源码是用二叉堆实现的。

    默认堆顶是最大值：

    1.     let mut heap = BinaryHeap::new();
    2.     heap.push(1);
    3.     heap.push(3);
    4.     heap.push(1);
    5.     heap.push(2);
    6.     assert_eq!(heap.peek(),Some(&3));
    7.     heap.pop();
    8.     assert_eq!(heap.peek(),Some(&2));
    9.     heap.pop();
    10.     assert_eq!(heap.peek(),Some(&1));
    11.     heap.pop();
    12.     assert_eq!(heap.peek(),Some(&1));
    13.     heap.pop();
    14.     assert_eq!(heap.peek(),None);

    要想使用堆顶是最小值的堆，有2种方法：自定义序关系、reserve

    （1）自定义序关系

    1. #[derive(Eq,PartialEq)]
    2. struct Node{
    3.     num:i32
    4. }
    5. impl Ord for Node {
    6.     #[inline]
    7.     fn cmp(&self,other:&Node)->Ordering{
    8.         return other.num.cmp(&self.num);
    9.     }
    10. }
    11. impl PartialOrd for Node {
    12.     #[inline]
    13.     fn partial_cmp(&self, other: &Node) ->  Option {
    14.         return Some(self.cmp(other));
    15.     }
    16. }
    17. fn main() {
    18.     let mut heap = BinaryHeap::new();
    19.     heap.push(Node{num:1});
    20.     heap.push(Node{num:3});
    21.     assert_eq!(heap.peek().unwrap().num, 1);
    22.     println!("end");
    23. }

    注意，自己实现PartialOrd但是Ord用默认的话，在堆里面的逻辑也是对的，但是以后如果有别人把这个结构体用于堆之外的场景，可能就有BUG了。

    （2）用reserve

    1. use std::cmp::Reverse;
    2. fn main() {
    3.     let mut heap = BinaryHeap::new();
    4.     heap.push(Reverse(1));
    5.     heap.push(Reverse(3));
    6.     assert_eq!(heap.peek().unwrap(), &Reverse(1));
    7.     assert_eq!(Reverse(1)>Reverse(3), true);
    8.     println!("end");
    9. }

    reserve就像是一个加负号的技巧：

    1. fn main() {
    2.     let mut heap = BinaryHeap::new();
    3.     heap.push(-1);
    4.     heap.push(-3);
    5.     assert_eq!(heap.peek().unwrap(), &-1);
    6.     assert_eq!(-1>-3, true);
    7.     println!("end");
    8. }

    （3）堆排序

    BinaryHeap自带堆排序into_sorted_vec

    （4）源码解析

    虽然BinaryHeap的定义本身没有要求ord特征，但是默认实现的泛型方法要求了Ord特征。

    这里我摘录了核心的几个函数：pop、push、into_sorted_vec，以及其中调用的关键操作。

    1. pub struct BinaryHeap<    T,A: Allocator = Global,> {
    2.     data: Vec,
    3. }
    4.  
    5. impl BinaryHeap {
    6.     。。。。。。
    7.     pub fn pop(&mut self) -> Option {
    8.         self.data.pop().map(|mut item| {
    9.             if !self.is_empty() {
    10.                 swap(&mut item, &mut self.data[0]);
    11.                 // SAFETY: !self.is_empty() means that self.len() > 0
    12.                 unsafe { self.sift_down_to_bottom(0) };
    13.             }
    14.             item
    15.         })
    16.     }
    17.     pub fn push(&mut self, item: T) {
    18.         let old_len = self.len();
    19.         self.data.push(item);
    20.         // SAFETY: Since we pushed a new item it means that
    21.         //  old_len = self.len() - 1 < self.len()
    22.         unsafe { self.sift_up(0, old_len) };
    23.     }
    24.     pub fn into_sorted_vec(mut self) -> Vec {
    25.         let mut end = self.len();
    26.         while end > 1 {
    27.             end -= 1;
    28.             // SAFETY: `end` goes from `self.len() - 1` to 1 (both included),
    29.             //  so it's always a valid index to access.
    30.             //  It is safe to access index 0 (i.e. `ptr`), because
    31.             //  1 <= end < self.len(), which means self.len() >= 2.
    32.             unsafe {
    33.                 let ptr = self.data.as_mut_ptr();
    34.                 ptr::swap(ptr, ptr.add(end));
    35.             }
    36.             // SAFETY: `end` goes from `self.len() - 1` to 1 (both included) so:
    37.             //  0 < 1 <= end <= self.len() - 1 < self.len()
    38.             //  Which means 0 < end and end < self.len().
    39.             unsafe { self.sift_down_range(0, end) };
    40.         }
    41.         self.into_vec()
    42.     }
    43.     unsafe fn sift_up(&mut self, start: usize, pos: usize) -> usize {
    44.         // Take out the value at `pos` and create a hole.
    45.         // SAFETY: The caller guarantees that pos < self.len()
    46.         let mut hole = unsafe { Hole::new(&mut self.data, pos) };
    47.  
    48.         while hole.pos() > start {
    49.             let parent = (hole.pos() - 1) / 2;
    50.  
    51.             // SAFETY: hole.pos() > start >= 0, which means hole.pos() > 0
    52.             //  and so hole.pos() - 1 can't underflow.
    53.             //  This guarantees that parent < hole.pos() so
    54.             //  it's a valid index and also != hole.pos().
    55.             if hole.element() <= unsafe { hole.get(parent) } {
    56.                 break;
    57.             }
    58.  
    59.             // SAFETY: Same as above
    60.             unsafe { hole.move_to(parent) };
    61.         }
    62.  
    63.         hole.pos()
    64.     }
    65.     unsafe fn sift_down_range(&mut self, pos: usize, end: usize) {
    66.         // SAFETY: The caller guarantees that pos < end <= self.len().
    67.         let mut hole = unsafe { Hole::new(&mut self.data, pos) };
    68.         let mut child = 2 * hole.pos() + 1;
    69.  
    70.         // Loop invariant: child == 2 * hole.pos() + 1.
    71.         while child <= end.saturating_sub(2) {
    72.             // compare with the greater of the two children
    73.             // SAFETY: child < end - 1 < self.len() and
    74.             //  child + 1 < end <= self.len(), so they're valid indexes.
    75.             //  child == 2 * hole.pos() + 1 != hole.pos() and
    76.             //  child + 1 == 2 * hole.pos() + 2 != hole.pos().
    77.             // FIXME: 2 * hole.pos() + 1 or 2 * hole.pos() + 2 could overflow
    78.             //  if T is a ZST
    79.             child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize;
    80.  
    81.             // if we are already in order, stop.
    82.             // SAFETY: child is now either the old child or the old child+1
    83.             //  We already proven that both are < self.len() and != hole.pos()
    84.             if hole.element() >= unsafe { hole.get(child) } {
    85.                 return;
    86.             }
    87.  
    88.             // SAFETY: same as above.
    89.             unsafe { hole.move_to(child) };
    90.             child = 2 * hole.pos() + 1;
    91.         }
    92.  
    93.         // SAFETY: && short circuit, which means that in the
    94.         //  second condition it's already true that child == end - 1 < self.len().
    95.         if child == end - 1 && hole.element() < unsafe { hole.get(child) } {
    96.             // SAFETY: child is already proven to be a valid index and
    97.             //  child == 2 * hole.pos() + 1 != hole.pos().
    98.             unsafe { hole.move_to(child) };
    99.         }
    100.     }
    101.     unsafe fn sift_down(&mut self, pos: usize) {
    102.         let len = self.len();
    103.         // SAFETY: pos < len is guaranteed by the caller and
    104.         //  obviously len = self.len() <= self.len().
    105.         unsafe { self.sift_down_range(pos, len) };
    106.     }
    107.  
    108.     unsafe fn sift_down_to_bottom(&mut self, mut pos: usize) {
    109.         let end = self.len();
    110.         let start = pos;
    111.  
    112.         // SAFETY: The caller guarantees that pos < self.len().
    113.         let mut hole = unsafe { Hole::new(&mut self.data, pos) };
    114.         let mut child = 2 * hole.pos() + 1;
    115.  
    116.         // Loop invariant: child == 2 * hole.pos() + 1.
    117.         while child <= end.saturating_sub(2) {
    118.             // SAFETY: child < end - 1 < self.len() and
    119.             //  child + 1 < end <= self.len(), so they're valid indexes.
    120.             //  child == 2 * hole.pos() + 1 != hole.pos() and
    121.             //  child + 1 == 2 * hole.pos() + 2 != hole.pos().
    122.             // FIXME: 2 * hole.pos() + 1 or 2 * hole.pos() + 2 could overflow
    123.             //  if T is a ZST
    124.             child += unsafe { hole.get(child) <= hole.get(child + 1) } as usize;
    125.  
    126.             // SAFETY: Same as above
    127.             unsafe { hole.move_to(child) };
    128.             child = 2 * hole.pos() + 1;
    129.         }
    130.  
    131.         if child == end - 1 {
    132.             // SAFETY: child == end - 1 < self.len(), so it's a valid index
    133.             //  and child == 2 * hole.pos() + 1 != hole.pos().
    134.             unsafe { hole.move_to(child) };
    135.         }
    136.         pos = hole.pos();
    137.         drop(hole);
    138.  
    139.         // SAFETY: pos is the position in the hole and was already proven
    140.         //  to be a valid index.
    141.         unsafe { self.sift_up(start, pos) };
    142.     }
    143.     。。。。。。
    144. }

    sift_down_range是往下调整到指定id，主要用于堆排序

    sift_down是往下调整到底，直接调用sift_down_range

    sift_down_to_bottom是先往下调整到底，之后再往上调整到顶。

    （5）应用实例

    rust源码的注释中，给出了Dijkstra's shortest path algorithm作为示例，如何使用优先队列。

    1. //use std::cmp::Ordering;
    2. //use std::collections::BinaryHeap;
    3.  
    4. #[derive(Copy, Clone, Eq, PartialEq)]
    5. struct State {
    6.     cost: usize,
    7.     position: usize,
    8. }
    9.  
    10. // The priority queue depends on `Ord`.
    11. // Explicitly implement the trait so the queue becomes a min-heap
    12. // instead of a max-heap.
    13. impl Ord for State {
    14.     fn cmp(&self, other: &Self) -> Ordering {
    15.         // Notice that the we flip the ordering on costs.
    16.         // In case of a tie we compare positions - this step is necessary
    17.         // to make implementations of `PartialEq` and `Ord` consistent.
    18.         other.cost.cmp(&self.cost)
    19.             .then_with(|| self.position.cmp(&other.position))
    20.     }
    21. }
    22.  
    23. // `PartialOrd` needs to be implemented as well.
    24. impl PartialOrd for State {
    25.     fn partial_cmp(&self, other: &Self) -> Option {
    26.         Some(self.cmp(other))
    27.     }
    28. }
    29.  
    30. // Each node is represented as a `usize`, for a shorter implementation.
    31. struct Edge {
    32.     node: usize,
    33.     cost: usize,
    34. }
    35.  
    36. // Dijkstra's shortest path algorithm.
    37.  
    38. // Start at `start` and use `dist` to track the current shortest distance
    39. // to each node. This implementation isn't memory-efficient as it may leave duplicate
    40. // nodes in the queue. It also uses `usize::MAX` as a sentinel value,
    41. // for a simpler implementation.
    42. fn shortest_path(adj_list: &Vec>, start: usize, goal: usize) -> Option {
    43.     // dist[node] = current shortest distance from `start` to `node`
    44.     let mut dist: Vec<_> = (0..adj_list.len()).map(|_| usize::MAX).collect();
    45.  
    46.     let mut heap = BinaryHeap::new();
    47.  
    48.     // We're at `start`, with a zero cost
    49.     dist[start] = 0;
    50.     heap.push(State { cost: 0, position: start });
    51.  
    52.     // Examine the frontier with lower cost nodes first (min-heap)
    53.     while let Some(State { cost, position }) = heap.pop() {
    54.         // Alternatively we could have continued to find all shortest paths
    55.         if position == goal { return Some(cost); }
    56.  
    57.         // Important as we may have already found a better way
    58.         if cost > dist[position] { continue; }
    59.  
    60.         // For each node we can reach, see if we can find a way with
    61.         // a lower cost going through this node
    62.         for edge in &adj_list[position] {
    63.             let next = State { cost: cost + edge.cost, position: edge.node };
    64.  
    65.             // If so, add it to the frontier and continue
    66.             if next.cost < dist[next.position] {
    67.                 heap.push(next);
    68.                 // Relaxation, we have now found a better way
    69.                 dist[next.position] = next.cost;
    70.             }
    71.         }
    72.     }
    73.  
    74.     // Goal not reachable
    75.     None
    76. }
    77.  
    78. fn main() {
    79.     // This is the directed graph we're going to use.
    80.     // The node numbers correspond to the different states,
    81.     // and the edge weights symbolize the cost of moving
    82.     // from one node to another.
    83.     // Note that the edges are one-way.
    84.     //
    85.     //                  7
    86.     //          +-----------------+
    87.     //          |                 |
    88.     //          v   1        2    |  2
    89.     //          0 -----> 1 -----> 3 ---> 4
    90.     //          |        ^        ^      ^
    91.     //          |        | 1      |      |
    92.     //          |        |        | 3    | 1
    93.     //          +------> 2 -------+      |
    94.     //           10      |               |
    95.     //                   +---------------+
    96.     //
    97.     // The graph is represented as an adjacency list where each index,
    98.     // corresponding to a node value, has a list of outgoing edges.
    99.     // Chosen for its efficiency.
    100.     let graph = vec![
    101.         // Node 0
    102.         vec![Edge { node: 2, cost: 10 },
    103.              Edge { node: 1, cost: 1 }],
    104.         // Node 1
    105.         vec![Edge { node: 3, cost: 2 }],
    106.         // Node 2
    107.         vec![Edge { node: 1, cost: 1 },
    108.              Edge { node: 3, cost: 3 },
    109.              Edge { node: 4, cost: 1 }],
    110.         // Node 3
    111.         vec![Edge { node: 0, cost: 7 },
    112.              Edge { node: 4, cost: 2 }],
    113.         // Node 4
    114.         vec![]];
    115.  
    116.     assert_eq!(shortest_path(&graph, 0, 1), Some(1));
    117.     assert_eq!(shortest_path(&graph, 0, 3), Some(3));
    118.     assert_eq!(shortest_path(&graph, 3, 0), Some(7));
    119.     assert_eq!(shortest_path(&graph, 0, 4), Some(5));
    120.     assert_eq!(shortest_path(&graph, 4, 0), None);
    121.     println!("endend");
    122. }

    7，字符串

    （0）字符串编码

    参考这里

    （1）String的实现

    use std::string::String;

    1. pub struct String {
    2.     vec: Vec,
    3. }

    （2）String和Vec互转

    String和Vec直接互转，该映射是双射，不会失败

    1.     let s=String::from("1234");
    2.     let v:Vec<char>=s.chars().collect();
    3.     assert_eq!(v.len(),4);
    4.     let s:String = v.into_iter().collect();
    5.     assert_eq!(s,String::from("1234"));

    整数转字符串：

    1. fn int_to_string(x:i32)->String{
    2.     let mut ans = String::new();
    3.     let mut v=Vec::new();
    4.     let mut x = x;
    5.     let mut c='0';
    6.     while x>0 {
    7.         v.insert(0,(c as u8 + (x%10) as u8)as char);
    8.         x/=10;
    9.     }
    10.     return v.into_iter().collect();
    11. }

    字符串转整数

    1. fn string_to_int(v:& Vec<char>)->i32{
    2.     let mut id :usize=0;
    3.     let mut flag:i32 = 1;
    4.     if v[id] == '-' {
    5.         id+=1;
    6.         flag = -1;
    7.     }
    8.     let mut s:i32 = 0;
    9.     while id < v.len() {
    10.         s = s * 10 + v[id].to_digit(10).unwrap() as i32;
    11.         id+=1;
    12.     }
    13.     return s*flag;
    14. }

    （3）String和Vec>互转

    String和Vec>互转， String转Vec 是单射但不是满射，所以from_utf8返回值是Result

    1.     let s=String::from("哈喽，世界");
    2.     let v:Vec = s.into_bytes();
    3.     let s = String::from_utf8(v).unwrap();
    4.     assert_eq!(s,"哈喽，世界");

    （4）&str的实现

    str是内置类型，表示[u8]，即u8类型的切片。

    由于切片类型没有固定的size，不能用于栈中，所以我们一般用的都是&str

    字符串字面量的引用也是&str

    1. fn get_max_char(s:&str) -> char{
    2.     let mut ans:char = s.chars().next().unwrap();
    3.     for x in s.chars(){
    4.         if ans < x {
    5.             ans = x;
    6.         }
    7.     }
    8.     return ans;
    9. }
    10.  
    11. fn main() {
    12.     let s:&str = "hello world";
    13.     assert_eq!(get_max_char(s), 'w');
    14.     println!("end");
    15. }

    （5）&str和String互转

    完整切片：String和&str是双射

    1.     let a:&str = "hello world";
    2.     let b:String = String::from(a);
    3.     let c:&str = &b;
    4.     let d:&str = &b[..];

    部分引用切片：可能panic

    1.     let s: String = String::from("猜猜我是谁");
    2.     let b: &str = &s[0..6];
    3.     assert_eq!(b,"猜猜");
    4.     let c: &str = &s[1..6]; // thread panicked

    也就是说，str和String一样，虽然底层实现是u8组成的，但和u8序列并不双射，而是和字符串双射。

    （6）&str和Vec互转

    1.     let s:&str = "hello world";
    2.     let v:Vec<char>=s.chars().collect();
    3.     let s2:String = v.into_iter().collect();
    4.     let s3:&str=&s2;

    （7）&str和Vec互转

    1.     let s:&str = "hello world";
    2.     let v:Vec = s.as_bytes().to_vec();
    3.     let s2 = String::from_utf8(v).unwrap();
    4.     let s3:&str=&s2;

    （8）完整互转有向图

    左边2个构成u8域，右边3个构成char域，域内双射，从char域到u8域是单射非满射。

    三，自定义数据结构

    1，单链表（力扣版）

    链表定义：

    1. #[derive(PartialEq, Eq, Clone, Debug)]
    2. pub struct ListNode {
    3.   pub val: i32,
    4.   pub next: Option>
    5. }
    6.  
    7. impl ListNode {
    8.   #[inline]
    9.   fn new(val: i32) -> Self {
    10.     ListNode {
    11.       next: None,
    12.       val
    13.     }
    14.   }
    15. }

    单链表和vector的互转：

    1. fn trans_link_list_to_vector(head: Option>)->Vec{
    2.     let mut v=Vec::new();
    3.     if head.is_none(){
    4.         return v;
    5.     }
    6.     let mut p = & mut head.unwrap();
    7.     v.push(p.val);
    8.     loop{
    9.         if let Some(ref mut x) = p.next {
    10.             v.push(x.val);
    11.             p=x;
    12.         }else{
    13.             break;
    14.         }
    15.     }
    16.     return v;
    17. }
    18. fn trans_vector_to_link_list(v:Vec)-> Option> {
    19.     let mut ans = Box::new(ListNode::new(0));
    20.     let mut p =&mut ans;
    21.     for i in 0..v.len() {
    22.         p.next = Some(Box::new(ListNode::new(v[i])));
    23.         if let Some(ref mut x) = p.next{
    24.             p=x;
    25.         }
    26.     }
    27.     return ans.next;
    28. }

    2，二叉树（力扣版）

    二叉树定义：

    1. use std::rc::Rc;
    2. use std::cell::RefCell;
    3. #[derive(Debug, PartialEq, Eq)]
    4. pub struct TreeNode {
    5.   pub val: i32,
    6.   pub left: Option>>,
    7.   pub right: Option>>,
    8. }
    9. impl TreeNode {
    10.   #[inline]
    11.   pub fn new(val: i32) -> Self {
    12.     TreeNode {
    13.       val,
    14.       left: None,
    15.       right: None
    16.     }
    17.   }
    18. }

    序列化和反序列化：

    1.  
    2. fn serialize(root: Option>>, error: i32)->Vec {
    3.     let mut q=VecDeque::new();
    4.     q.push_back(root.clone());
    5.     let mut ans = Vec::new();
    6.     while q.len() > 0{
    7.         let p = q.pop_front().unwrap();
    8.         if p.is_none() {
    9.             ans.push(error);
    10.             continue;
    11.         }
    12.         let r = p.clone().unwrap();
    13.         ans.push(r.borrow_mut().val);
    14.         q.push_back(r.borrow_mut().left.clone());
    15.         q.push_back(r.borrow_mut().right.clone());
    16.     }
    17.     return ans;
    18. }
    19. fn deserialize(v:Vec, error:i32) ->Option>>{
    20.     if v[0]==error {
    21.         return None;
    22.     }
    23.     let mut id:usize = 0;
    24.     let val = v[id];
    25.     id+=1;
    26.     let root = Some(Rc::new(RefCell::new(TreeNode::new(val))));
    27.     let mut q=VecDeque::new();
    28.     q.push_back(root.clone());
    29.     while q.len() > 0 {
    30.         let p = q.pop_front().unwrap();
    31.         let r = p.clone().unwrap();
    32.         let val = v[id];
    33.         id+=1;
    34.         if val != error {
    35.             r.borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(val))));
    36.             q.push_back(r.borrow_mut().left.clone());
    37.         }
    38.         let val = v[id];
    39.         id+=1;
    40.         if val != error {
    41.             r.borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(val))));
    42.             q.push_back(r.borrow_mut().right.clone());
    43.         }
    44.     }
    45.     root
    46. }

    四，std::cmp

    1，min函数、max函数

    std::cmp::min

    std::cmp::max

    2，Reverse

    这是一个泛型的元组结构体，实现了泛型的逆序：

    1. pub struct Reverse(#[stable(feature = "reverse_cmp_key", since = "1.19.0")] pub T);
    2.  
    3. #[stable(feature = "reverse_cmp_key", since = "1.19.0")]
    4. impl PartialOrd for Reverse {
    5.     #[inline]
    6.     fn partial_cmp(&self, other: &Reverse) -> Option {
    7.         other.0.partial_cmp(&self.0)
    8.     }
    9.  
    10.     #[inline]
    11.     fn lt(&self, other: &Self) -> bool {
    12.         other.0 < self.0
    13.     }
    14.     #[inline]
    15.     fn le(&self, other: &Self) -> bool {
    16.         other.0 <= self.0
    17.     }
    18.     #[inline]
    19.     fn gt(&self, other: &Self) -> bool {
    20.         other.0 > self.0
    21.     }
    22.     #[inline]
    23.     fn ge(&self, other: &Self) -> bool {
    24.         other.0 >= self.0
    25.     }
    26. }
    27.  
    28. #[stable(feature = "reverse_cmp_key", since = "1.19.0")]
    29. impl Ord for Reverse {
    30.     #[inline]
    31.     fn cmp(&self, other: &Reverse) -> Ordering {
    32.         other.0.cmp(&self.0)
    33.     }
    34. }

    五，std算法、自实现算法

    1，排序

    （1）vector排序

    1. fn main() {
    2. 	let mut nums=vec![1,2,4,3];
    3. 	nums.sort();
    4. 	println!("{}",nums[3]);
    5. }

    vector的默认排序，从小到大排序，输出4

    （2）自定义排序

    给自定义结构体添加自定义排序规则，需要实现Ord特征

    结构体实现：

    1. #[derive(Eq,PartialEq)]
    2. struct Node{
    3.     id:i32,
    4.     num:i32
    5. }
    6. impl Ord for Node {
    7.     #[inline]
    8.     fn cmp(&self, other: &Node) -> Ordering {
    9.         if self.num != other.num{
    10.             return (*other).num.cmp(&self.num);
    11.         }else{
    12.             return self.id.cmp(&(*other).id);
    13.         }
    14.     }
    15. }
    16. impl PartialOrd for Node{
    17.     fn partial_cmp(&self, other: &Self) -> Option {
    18.         return Some(self.cmp(other)); 
    19.     }
    20. }

    Ordering是枚举值，分别表示小于等于大于。

    形如self.cmp(other)的排序规则是按照数据类型本身的排序规则，基本类型默认是升序。

    形如other.cmp(slef)的排序规则则是反过来的顺序。

    调用代码：

    1. let mut v:Vec=Vec::new();
    2. ......
    3. v.sort_by(|a,b| a.cmp(b));

    注意，自己实现Ord但是PartialOrd用默认的话，在排序里面的逻辑也是对的，但是以后如果有别人把这个结构体用于排序之外的场景，可能就有BUG了。

    2，二分

    （1）vector二分

    1. fn search(nums: &Vec, target:i32)->i32{
    2.     let res = nums.binary_search(&target);
    3.     match res{
    4.         Ok(x)=>x as i32,
    5.         _=>-1
    6.     }
    7. }
    8. fn main() {
    9.     let nums =vec![1,2,4,5];
    10.     println!("{}",search(&nums,1));
    11. 	println!("{}",search(&nums,4));
    12. 	println!("{}",search(&nums,7));
    13. }

    输出：

    1. 0
    2. 2
    3. -1

    非排序数组调用binary_search也能运行，但可能找不到结果。

    降序数组和非排序数组同理。

    有重复数的情况下，找到任意一个就直接结束。

    （2）自定义二分

    1. struct SearchData{
    2.     target:i32
    3. }
    4. impl SearchData{
    5.     fn find(&self, low:i32,high:i32)-> i32{
    6.         let mut low = low;
    7.         let mut high = high;
    8.         if self.check_value(high) == false{
    9.             return high+1;
    10.         }
    11.         if self.check_value(low) == true{
    12.             return low;
    13.         }
    14.         while high - low > 1 {
    15.             let mid = (high + low)/2;
    16.             if self.check_value(mid) == true{
    17.                 high = mid;
    18.             }
    19.             else {
    20.                 low = mid;
    21.             }
    22.         }
    23.         return high;
    24.     }
    25.     fn check_value(&self,x:i32)->bool{
    26.         if x*x*x>self.target{
    27.             return true;
    28.         }
    29.         return false;
    30.     }
    31. }
    32. fn main() {
    33.     let x=SearchData{target:100};
    34.     println!("{}",x.find(0,50));
    35. }

    输出5，即5是满足x*x*x>target的最小值。

    3，哈希算法

    rust提供的哈希方案，是把任意数据结构转换成u8整数序列，而整数序列再次哈希的方案一般就采用默认方案。

    （1）std::hash::Hash

    1. pub trait Hash {
    2.     fn hash(&self, state: &mut H);
    3.     fn hash_slice(data: &[Self], state: &mut H) where
    4.         Self: Sized,
    5.     {
    6.         for piece in data {
    7.             piece.hash(state)
    8.         }
    9.     }
    10. }

    其中是hash函数，就是往state里面依次注册整数。

    state是一个具有Hasher特征的H类型的数据。

    hash_slice就是调用hash函数，把数组的每个成员，依次转换成整数注册到state里面。

    示例：

    1. struct OrderAmbivalentPair(T, T);
    2. impl Hash for OrderAmbivalentPair {
    3.     fn hash(&self, hasher: &mut H) {
    4.         min(&self.0, &self.1).hash(hasher);
    5.         max(&self.0, &self.1).hash(hasher);
    6.     }
    7. }

    （2）std::hash::Hasher

    1. pub trait Hasher {
    2.     fn finish(&self) -> u64;
    3.  
    4.     fn write(&mut self, bytes: &[u8]);
    5.  
    6.     fn write_u8(&mut self, i: u8) {
    7.         self.write(&[i])
    8.     }
    9.     ......
    10. }

    Hasher中提供各种类型数据的write***函数，其他的wtite***函数也都是调用write函数，最终都是生成一个u8的整数序列。

    最后再调用finish函数即可得到一个u64的整数。

    （3）Hash中的hash函数

    常见类型的hash函数：

    1. macro_rules! impl_write {
    2.         ($(($ty:ident, $meth:ident),)*) => {$(
    3.             #[stable(feature = "rust1", since = "1.0.0")]
    4.             impl Hash for $ty {
    5.                 #[inline]
    6.                 fn hash(&self, state: &mut H) {
    7.                     state.$meth(*self)
    8.                 }
    9.  
    10.                 #[inline]
    11.                 fn hash_slice(data: &[$ty], state: &mut H) {
    12.                     let newlen = mem::size_of_val(data);
    13.                     let ptr = data.as_ptr() as *const u8;
    14.                     // SAFETY: `ptr` is valid and aligned, as this macro is only used
    15.                     // for numeric primitives which have no padding. The new slice only
    16.                     // spans across `data` and is never mutated, and its total size is the
    17.                     // same as the original `data` so it can't be over `isize::MAX`.
    18.                     state.write(unsafe { slice::from_raw_parts(ptr, newlen) })
    19.                 }
    20.             }
    21.         )*}
    22.     }
    23.  
    24.     impl_write! {
    25.         (u8, write_u8),
    26.         (u16, write_u16),
    27.         (u32, write_u32),
    28.         (u64, write_u64),
    29.         (usize, write_usize),
    30.         (i8, write_i8),
    31.         (i16, write_i16),
    32.         (i32, write_i32),
    33.         (i64, write_i64),
    34.         (isize, write_isize),
    35.         (u128, write_u128),
    36.         (i128, write_i128),
    37.     }
    38.  
    39.     #[stable(feature = "rust1", since = "1.0.0")]
    40.     impl Hash for bool {
    41.         #[inline]
    42.         fn hash(&self, state: &mut H) {
    43.             state.write_u8(*self as u8)
    44.         }
    45.     }
    46.  
    47.     #[stable(feature = "rust1", since = "1.0.0")]
    48.     impl Hash for char {
    49.         #[inline]
    50.         fn hash(&self, state: &mut H) {
    51.             state.write_u32(*self as u32)
    52.         }
    53.     }
    54.  
    55.     #[stable(feature = "rust1", since = "1.0.0")]
    56.     impl Hash for str {
    57.         #[inline]
    58.         fn hash(&self, state: &mut H) {
    59.             state.write_str(self);
    60.         }
    61.     }

    （4）BuildHasher

    相当于Hasher的再次包装

    1. pub trait BuildHasher {
    2.     /// Type of the hasher that will be created.
    3.     #[stable(since = "1.7.0", feature = "build_hasher")]
    4.     type Hasher: Hasher;
    5.  
    6.     #[stable(since = "1.7.0", feature = "build_hasher")]
    7.     fn build_hasher(&self) -> Self::Hasher;
    8.  
    9.     #[stable(feature = "build_hasher_simple_hash_one", since = "1.71.0")]
    10.     fn hash_one(&self, x: T) -> u64
    11.     where
    12.         Self: Sized,
    13.         Self::Hasher: Hasher,
    14.     {
    15.         let mut hasher = self.build_hasher();
    16.         x.hash(&mut hasher);
    17.         hasher.finish()
    18.     }
    19. }

    （5）特征一致性

    Hash特征应该和PartialEq特征保持一致，即当a==b时hash(a)==hash(b)

    所以在自定义等价关系时，等价的2个数据转换后的u8序列也应该相同。

    4，BFS

    以有向图多起点BFS洪泛为例：

    1. //有向图多起点BFS洪泛，输入起点集v和邻接表m_next，输出经过可达的所有节点集v
    2. //m_next的key是完整的, value可以是空列表
    3. fn bfs(v:& mut Vec, m_next:& mut HashMap>)-> (){
    4.     let mut m=HashMap::new();
    5.     let mut deq=VecDeque::new();
    6.     for i in 0..v.len(){
    7.         m.insert(v[i], 1);
    8.         deq.push_back(v[i]);
    9.     }
    10.     loop {
    11.         if deq.is_empty(){
    12.             break;
    13.         }
    14.         let id = deq.pop_front().unwrap();
    15.         for i in m_next.get_mut(&id).unwrap(){
    16.             if m.get_mut(&i) == None{
    17.                 v.push(*i);
    18.                 m.insert(*i, 1);
    19.                 deq.push_back(*i);
    20.             }
    21.         }
    22.     }
    23. }

    5，并查集

    一个并查集的示例：

    1. struct Union{
    2.     fa:Vec,
    3. }
    4. impl Union{
    5.     fn find(& mut self,x:usize)->usize{
    6.         if self.fa[x] == x{
    7.             return x;
    8.         }
    9.         Union::find(self,self.fa[x]);
    10.         self.fa[x] = self.fa[self.fa[x]];
    11.         return self.fa[x];
    12.     }
    13.     fn in_same(& mut self,x:usize,y:usize)->bool{
    14.         return Union::find(self,x) == Union::find(self,y);
    15.     }
    16.     fn merge(& mut self,x:usize,y:usize)->(){
    17.         Union::find(self,x);
    18.         let fax = self.fa[x];
    19.         self.fa[fax] = y;
    20.     }
    21. }

    一个带权并查集的示例：

    1. struct Union{
    2.     fa:Vec,
    3.     dif:Vec,
    4. }
    5. impl Union{
    6.     fn find(& mut self,x:usize)->usize{
    7.         if self.fa[x] == x{
    8.             return x;
    9.         }
    10.         Union::find(self,self.fa[x]);
    11.         self.dif[x] += self.dif[self.fa[x]];
    12.         self.fa[x] = self.fa[self.fa[x]];
    13.         return self.fa[x];
    14.     }
    15.     fn in_same(& mut self,x:usize,y:usize)->bool{
    16.         return Union::find(self,x) == Union::find(self,y);
    17.     }
    18.     fn merge(& mut self,x:usize,y:usize,x_sub_y:i32)->(){
    19.         Union::find(self,x);
    20.         let fax = self.fa[x];
    21.         self.dif[fax] = x_sub_y - self.dif[x];
    22.         self.fa[fax] = y;
    23.     }
    24. }

    六，通用函数

    1，new函数

    除了智能指针之外，其他的new都是创建空对象。

    1.     let x=Box::new(1);
    2.     let x=RefCell::new(3);
    3.     let x=Rc::new(4);
    4.     let x:Vec=Vec::new();
    5.     let x:VecDeque=VecDeque::new();
    6.     let x:LinkedList=LinkedList::new();
    7.     let x=String::new();

    2，from

    对于整数类型，from可以往更大的类型转，不能往更小的类型转。

    1.     let x=i32::from(1);
    2.     let y=i64::from(x);
    3.     let z=i64::from(y);
    4.     let nums=Vec::from([1,2,4,3]);
    5.     let deq = VecDeque::from([-1, 0, 1]);
    6.     let list = LinkedList::from([1,2,4,3]);
    7.     let s=String::from("123");

    七，二元关系特征

    离散数学中的二元关系

    在c++的stl中，只需要2个关系，分别可以用<和==表示，其中<是序关系，==是等价关系。

    rust中的二元关系更多更细致，我们一个个分析。

    0，继承、一致性大前提

    Ord继承了PartialOrd和Eq，而PartialOrd和Eq都继承了PartialEq

    这是一个钻石环，不过trait没有构造和析构过程，所以也不在乎钻石环。

    由于继承关系的存在，父特征和子特征可以对同一关系做不同的实现，但这是一种很不好的写法。

    rust建议一：保持父特征和子特征中二元关系的一致性，是一个默认的大前提。

    PS：本章列举的rust建议，都是强烈建议，不遵守的代码可能可以编译运行，可能逻辑也暂时是对的，但一定不是好代码。

    1，std::cmp::PartialEq、lhs、rhs

    rust建议二：PartialEq满足对称性、传递性，即PartialEq就是部分等价关系。

    rust建议三：eq和ne保持对偶，即永远不要重写ne函数

    eq就是==，ne就是!=

    1. pub trait PartialEq {
    2.     /// This method tests for `self` and `other` values to be equal, and is used
    3.     /// by `==`.
    4.     #[must_use]
    5.     #[stable(feature = "rust1", since = "1.0.0")]
    6.     fn eq(&self, other: &Rhs) -> bool;
    7.  
    8.     /// This method tests for `!=`. The default implementation is almost always
    9.     /// sufficient, and should not be overridden without very good reason.
    10.     #[inline]
    11.     #[must_use]
    12.     #[stable(feature = "rust1", since = "1.0.0")]
    13.     fn ne(&self, other: &Rhs) -> bool {
    14.         !self.eq(other)
    15.     }
    16. }

    lhs是left-hand side，rhs是right-hand side

    PartialEq的泛型参数是rhs，默认是self，意思是默认和同类型数据进行比较。

    如果用于不同类型的比较，要想满足对称性，2个PartialEq特征都要实现，且需要保持逻辑一致（对偶）。

    2，std::cmp::Eq

    rust建议四：Eq满足自反性、对称性、传递性，即Eq就是等价关系。

    This means, that in addition to a == b and a != b being strict inverses, the equality must be (for all a, b and c):

    • reflexive: a == a;
    • symmetric: a == b implies b == a; and
    • transitive: a == b and b == c implies a == c.
    1. pub trait Eq: PartialEq {
    2.     // this method is used solely by #[deriving] to assert
    3.     // that every component of a type implements #[deriving]
    4.     // itself, the current deriving infrastructure means doing this
    5.     // assertion without using a method on this trait is nearly
    6.     // impossible.
    7.     //
    8.     // This should never be implemented by hand.
    9.     #[doc(hidden)]
    10.     #[no_coverage] // rust-lang/rust#84605
    11.     #[inline]
    12.     #[stable(feature = "rust1", since = "1.0.0")]
    13.     fn assert_receiver_is_total_eq(&self) {}
    14. }

    例如：

    f32就是满足部分等价关系，如果把f32里面的NAN去掉，得到的就是等价关系。

    assert_ne!(NAN, NAN);

    我们很容易有2个疑问：

    （1）从源码可以看出来，Eq是非泛型的，PartialEq是泛型的，为什么这么设计呢？

    因为不同类型的2个元素进行比较，和自反性无关，需要声明自反性的场景一定是同类型数据进行比较的场景。相当于PartialEq泛型是为了更好用，Eq非泛型是为了更简洁。

    （2）Eq和PartialEq的方法是一样的，都是==和!=2个运算符，为什么还要区分2个特征呢？

    因为==运算符无法说明自身是等价关系还是部分等价关系，当我们把PartialEq实现成部分等价关系时，建议Eq是不存在的，当我们把PartialEq实现成等价关系时，建议把默认Eq也声明出来。

    3，std::cmp::PartialOrd

    1. pub trait PartialOrd: PartialEq {
    2.     /// This method returns an ordering between `self` and `other` values if one exists.
    3.     #[must_use]
    4.     #[stable(feature = "rust1", since = "1.0.0")]
    5.     fn partial_cmp(&self, other: &Rhs) -> Option;
    6.  
    7.     /// This method tests less than (for `self` and `other`) and is used by the `<` operator.
    8.     #[inline]
    9.     #[must_use]
    10.     #[stable(feature = "rust1", since = "1.0.0")]
    11.     fn lt(&self, other: &Rhs) -> bool {
    12.         matches!(self.partial_cmp(other), Some(Less))
    13.     }
    14.  
    15.     /// This method tests less than or equal to (for `self` and `other`) and is used by the `<=`
    16.     #[inline]
    17.     #[must_use]
    18.     #[stable(feature = "rust1", since = "1.0.0")]
    19.     fn le(&self, other: &Rhs) -> bool {
    20.         matches!(self.partial_cmp(other), Some(Less | Equal))
    21.     }
    22.  
    23.     /// This method tests greater than (for `self` and `other`) and is used by the `>` operator.
    24.     #[inline]
    25.     #[must_use]
    26.     #[stable(feature = "rust1", since = "1.0.0")]
    27.     fn gt(&self, other: &Rhs) -> bool {
    28.         matches!(self.partial_cmp(other), Some(Greater))
    29.     }
    30.  
    31.     /// This method tests greater than or equal to (for `self` and `other`) and is used by the `>=`
    32.     #[inline]
    33.     #[must_use]
    34.     #[stable(feature = "rust1", since = "1.0.0")]
    35.     fn ge(&self, other: &Rhs) -> bool {
    36.         matches!(self.partial_cmp(other), Some(Greater | Equal))
    37.     }
    38. }

    partial_cmp有4种结果，分别是Ordering的3个枚举值，和None，表示无法比较顺序。

    PartialOrd的另外4个函数，默认实现都是直接调用partial_cmp得到的，分别是<   <=   >   >=

    从源码注释和官方文档可以看到rust建议五：PartialOrd应该满足如下三条特性：

    • irreflexivity of < and >: !(a < a), !(a > a)
    • transitivity of >: if a > b and b > c then a > c
    • duality of partial_cmp: partial_cmp(a, b) == partial_cmp(b, a).map(Ordering::reverse)

    4，PartialOrd的二元关系推导

    由于这一块内容比较复杂，所以我单独写成一节。

    （0）一致性大前提

    partial_cmp返回Equal    等价于    父类的eq返回true

    partial_cmp返回另外3个值    等价于    父类的eq返回false

    所以，==关系具有对称性、传递性

    （1）对偶性

    PartialOrd满足 对偶性，即aa   a==b等价于b==a   a>b等价于b

    （2）反自反

    PartialOrd满足 大于关系的反自反、小于关系的反自反

    （3）传递性

    PartialOrd满足 大于关系的传递性

    通过对偶性和大于关系的传递性，可以推出小于关系也具有传递性。

    （4）对称性

    通过反自反和传递性可以推出，大于关系和小于关系都具有反对称性，不具有对称性。

    根据源码和官方文档，只能推导出上面的这些信息，总结起来就是两句话：

    PartialOrd中的 < 和 > 都是拟序，且2个关系互为对偶，且都和部分等价关系没有交集。

    PartialOrd中的 <= 和 >= 指的是对应的拟序关系和部分等价关系的并集，<= 和 >=互为对偶。

    实际上这些条件是不够的，里面仍然包含了一些非常复杂的情况。

    （5）关系之间的传递性

    根据实际情况，我认为实际上是有rust建议六：partial_cmp最好满足如下4条传递性：

    • 若a>b b==c则a>c
    • 若a
    • 若a==b b>c则a>c
    • 若a==b b

    根据前面的性质和新增的这4条传递性，可以推出<=和>=也具有传递性。

    （6）等价自反子集

    等价自反子集：由满足a==a的所有的a构成的集合。

    例如，对于float集合，去掉NAN得到的就是等价自反子集。

    显然，对于一个具有部分等价关系的集合，它的等价自反子集一定具有等价关系。

    （7）非自反元素的隔离

    rust建议七：如果a!=a，则a和任意元素的partial_cmp都返回None。

    例如，f32类型就是满足建议六和建议七的。

    （8）等价自反子集的映射子集上的偏序

    实际上，即使加上了建议六和建议七，<=仍然不是等价自反子集上的偏序关系。

    示例：

    1. #[derive(Eq,PartialEq,Ord)]
    2. struct Node{
    3.     x:i32,
    4.     y:i32,
    5. }
    6. impl PartialOrd for Node {
    7.     #[inline]
    8.     fn partial_cmp(&self, other: &Node) ->  Option {
    9.         if self.x < (*other).x {
    10.             return Some(Ordering::Less);
    11.         }
    12.         if self.x > (*other).x {
    13.             return Some(Ordering::Greater);
    14.         }
    15.         if self.y <= 0 && (*other).y <= 0 {
    16.             return Some(Ordering::Equal);
    17.         }
    18.         if self.y > 0 && (*other).y > 0 {
    19.             return Some(Ordering::Equal);
    20.         }
    21.         return None;
    22.     }
    23. }

    这还是一个比较简单的例子，还有很多更复杂的例子都满足上面的所有性质和建议。

    一般情况下，在讨论自反性时，我们说a和b是同一个元素，指的是a和b是同一个内存地址中的数据，满足等价关系或者完全相等的数值并不代表是同一个元素。

    所以，我们首先把等价自反子集做一个映射，把所有等价的元素映射到一个元素上，得到等价自反子集的映射子集。

    这样，我们就可以说，在等价自反子集的映射子集上，PartialOrd中的<=是偏序。

    （9）示例

    1. #[derive(Eq,PartialEq,Ord)]
    2. struct Node2{
    3.     x:i32,
    4.     y:i32,
    5. }
    6. impl PartialOrd for Node2 {
    7.     #[inline]
    8.     fn partial_cmp(&self, other: &Node2) ->  Option {
    9.         if self.x == 0 || (*other).x == 0{
    10.             return None;
    11.         }
    12.         if self.x < (*other).x {
    13.             return Some(Ordering::Less);
    14.         }
    15.         if self.x > (*other).x {
    16.             return Some(Ordering::Greater);
    17.         }
    18.         if self.y <= 0 && (*other).y <= 0 {
    19.             return Some(Ordering::Equal);
    20.         }
    21.         if self.y > 0 && (*other).y > 0 {
    22.             return Some(Ordering::Equal);
    23.         }
    24.         return None;
    25.     }
    26. }

    在这个例子中，集合是Node2的定义域，即全体平面{(x,y) | x是整数，y是整数}。这里我们忽略i32的上下界，把它理解成全体整数。

    等价自反子集是{(x,y) | x是整数，x!=0，y是整数}

    等价自反子集的映射子集是{(x,z) | x是整数，x!=0，z=0或1}，映射方式是y<=0则z=0，y>0则z=1

    那么Node2::partial_cmp在这个映射子集上的关系就是偏序。

    （10）不同类型数据之间的PartialOrd

    PartialOrd和PartialEq类似，支持泛型。

    如果用于不同类型的比较，要想满足对称性，2个PartialEq特征都要实现，且需要保持逻辑一致（对偶）。

    5，std::cmp::Ord

    1. pub trait Ord: Eq + PartialOrd {
    2.     #[must_use]
    3.     #[stable(feature = "rust1", since = "1.0.0")]
    4.     fn cmp(&self, other: &Self) -> Ordering;
    5.     ......
    6. }

    （1）数据类型、泛型

    和Eq类似，Ord不支持泛型，即Ord只用于比较同类型数据。

    （2）cmp的二元关系

    （2.1）for all `a`, `b` and `c`: exactly one of `a < b`, `a == b` or `a > b` is true; 这个是强制要求，因为cmp的返回值类型是Ordering，而不是Option。

    （2.2）根据rust建议一：保持父特征和子特征中二元关系的一致性，可以推出一个恒等式：partial_cmp(a, b) == Some(cmp(a, b))，这也是源码和官方文档中给出的式子。

    （2.3）根据（2.1）和（2.2）以及partial_cmp本身蕴含的诸多条件，可以推出，cmp中的<就是严格弱序，<=就是全序。

    （3）PartialOrd和Ord的选择

    上文提到：当我们把PartialEq实现成部分等价关系时，建议Eq是不存在的，当我们把PartialEq实现成等价关系时，建议把默认Eq也声明出来。

    PartialOrd和Ord也是类似的，当我们把PartialOrd（中的<=）实现成全序时，建议把Ord也实现出来，否则，建议Ord是不存在的。

    PS：为什么不给cmp添加默认实现，由partial_cmp推导出cmp呢？参考下文，实际上应该用cmp推导出partial_cmp，所以2个函数都没有默认实现。

    6，默认序关系

    （1）基本类型

    整数类型都有默认的全序关系，1<=2<=3

    浮点数有默认的偏序关系，1<=1.5<=2

    其他基本类型同理。

    （2）结构体的默认序关系

    如果结构体用derive声明默认的PartialOrd或者Ord，则按照字典序推导出序关系。

    当然，能编译通过的前提是所有成员都有相应的序关系。

    （3）容器的默认序关系

    以vec为例，默认序关系就是字典序：

    1. /// Implements comparison of vectors, [lexicographically](Ord#lexicographical-comparison).
    2. #[stable(feature = "rust1", since = "1.0.0")]
    3. impl PartialOrd> for Vec
    4. where
    5.     T: PartialOrd,
    6.     A1: Allocator,
    7.     A2: Allocator,
    8. {
    9.     #[inline]
    10.     fn partial_cmp(&self, other: &Vec) -> Option {
    11.         PartialOrd::partial_cmp(&**self, &**other)
    12.     }
    13. }
    14.  
    15. #[stable(feature = "rust1", since = "1.0.0")]
    16. impl Eq for Vec {}
    17.  
    18. /// Implements ordering of vectors, [lexicographically](Ord#lexicographical-comparison).
    19. #[stable(feature = "rust1", since = "1.0.0")]
    20. impl Ord for Vec {
    21.     #[inline]
    22.     fn cmp(&self, other: &Self) -> Ordering {
    23.         Ord::cmp(&**self, &**other)
    24.     }
    25. }

    7，自定义序关系的场景

    本节内容只讨论同类型数据之间的关系处理原则，不同类型之间没什么要注意的。

    （1）PartialEq和Eq

    正常情况下，我们都应该实现PartialEq特征，而Eq特征虽然继承了PartialEq但并没有自己的方法需要实现。

    （2）偏序的PartialOrd

    如果实现一个偏序，则只实现PartialOrd，无论把PartialOrd实现成什么样，都建议Ord是不存在的。

    比如，这里我实现了PartialOrd，又声明了默认的Ord，则会造成不一致：

    1. #[derive(Eq,PartialEq,Ord)]
    2. struct Node{
    3.     num:i32
    4. }
    5. impl PartialOrd for Node {
    6.     #[inline]
    7.     fn partial_cmp(&self, other: &Node) ->  Option {
    8.         if self.num == 0 || (*other).num == 0 {
    9.             return None;
    10.         }
    11.         return (*other).num.partial_cmp(&self.num);
    12.     }
    13. }
    14. fn main() {
    15.     let x = Node{num:1};
    16.     let y = Node{num:3};
    17.     assert_eq!(x.partial_cmp(&y),Some(Ordering::Greater));
    18.     assert_eq!(x.cmp(&y),Ordering::Less);
    19.     println!("end");
    20. }

    （3）全序的PartialOrd和Ord

    当我们把PartialOrd实现成去全序时，建议一律采用如下的固定实现方式，即只调用cmp推导出partial_cmp。

    1. impl PartialOrd for Node {
    2.     #[inline]
    3.     fn partial_cmp(&self, other: &Node) ->  Option {
    4.         return Some(self.cmp(other));
    5.     }
    6. }

    例如，全序的二叉堆，虽然源码只会调用<=函数，即只会调用partial_cmp而不会调用cmp，但是二叉堆的数据类型必须是含有Ord特征的类型，f32就编译不过。

    因为，有Ord特征就暗示了是全序关系，PartialOrd特征没法说明自身是否是全序，就不能完全满足堆的需求。

    所以，最好就是直接实现cmp，然后用cmp推导出partial_cmp。

    同理，自定义排序，虽然源码只会调用cmp而不会调用partial_cmp，但最好就是直接实现cmp，然后用cmp推导出partial_cmp。

    （4）偏序集的等价自反子集

    例如，我要用浮点数作为堆的类型，而且我知道肯定不会有NAN的出现，那么可以这么写：

    1. #[derive(PartialEq,PartialOrd)]
    2. struct FloatWithOrd{
    3.     x:f32, // do not let x be NAN
    4. }
    5. impl Eq for FloatWithOrd{
    6. }
    7. impl Ord for FloatWithOrd {
    8.     #[inline]
    9.     fn cmp(&self,other:&FloatWithOrd)->Ordering{
    10.         if(self.x < other.x){
    11.             return Ordering::Less;
    12.         }
    13.         if(self.x > other.x){
    14.             return Ordering::Greater;
    15.         }
    16.         return Ordering::Equal;
    17.     }
    18. }
    19. fn main() {
    20.     let mut heap = BinaryHeap::new();
    21.     heap.push(FloatWithOrd{x:1.5});
    22.     heap.push(FloatWithOrd{x:3.0});
    23.     assert_eq!(heap.peek().unwrap().x, 3.0);
    24.     println!("end");
    25. }

  • 相关阅读:
    第二章 Hadoop环境配置之虚拟机安装配置
    py7_初识 Python 中的 OOP 面向对象编程以及类的方法如何使用 self 传参
    excel系列【统计一列中的不重复项】
    LabVIEW专栏七、队列
    html5学习笔记18-web存储、web sql、web worker
    C# yolov8 OpenVINO 同步、异步接口视频推理
    下载eos-studio进行开发遇到的问题解决
    基于遗传算法的新能源电动汽车充电桩与路径选择（Matlab代码实现）
    十四天学会C++之第二天（函数和库）
    PS系统教学24
  • 原文地址：https://blog.csdn.net/nameofcsdn/article/details/134078426