16｜数据结构：Vec<T>、&[T]、Box<[T]> ，你真的了解集合容器么？

问老师一个工程性上的问题，也困扰了我好久，之前我在用rust开发项目的时候，数据解析性项目，会存在一个字段被多个类，或者函数使用，由于所有权的问题，导致代码中出现了大量的clone函数，后面在做性能分析的时候，发现20%的时间竟然浪费在clone上，求问老师，如何减少clone的调用次数？

1. 不可以，但稍微改造下也是可以的 str 实现了 AsRef<[u8]>，AsRef<OsStr>，AsRef<Path>，AsRef<str> 如果 T: AsRef<[U]>，编译器可以推断出 str 是 AsRef<[u8]>，即 U 是 u8 类型 如果 T: AsRef<U>，编译器就懵逼了，因为它有四种选择。 问题的关键就在于编译器无法推断出 U 的类型，因此如果稍微改造下，其实还是可以通过手动标记来通过编译的： ```rust use std::fmt; fn main() { let s = String::from("hello"); print_slice1::<_, [u8]>(&s); // [104, 101, 108, 108, 111] print_slice1::<_, str>(&s); // "hello" } fn print_slice1<T, U: ?Sized>(s: T) where T: AsRef<U>, U: fmt::Debug, { println!("{:?}", s.as_ref()); } ``` 2. 看了下 rxjs 的定义，第二个参数如果小于第一个参数的话，得到的结果好像没啥意义（反正我个人是没看懂）， 所以只处理了第二个参数不小于第一个参数的情况。 ```rust struct WindowCountIter<T: Iterator> { iter: T, window_size: usize, start_window_every: usize, } impl<T: Iterator> Iterator for WindowCountIter<T> { type Item = Vec<<T as Iterator>::Item>; fn next(&mut self) -> Option<Self::Item> { let mut item = Vec::with_capacity(self.window_size); for _ in 0..self.window_size { if let Some(v) = self.iter.next() { item.push(v); } } for _ in 0..(self.start_window_every - self.window_size) { self.iter.next(); } if item.is_empty() { None } else { Some(item) } } } trait IteratorExt: Iterator { fn window_count(self, window_size: usize, start_window_every: usize) -> WindowCountIter<Self> where Self: Sized, { if start_window_every > 0 && start_window_every < window_size { panic!("start_window_every 不能小于 window_size") } WindowCountIter { iter: self, window_size, start_window_every: if start_window_every == 0 { window_size } else { start_window_every }, } } } impl<T: Iterator> IteratorExt for T {} ```

怎么留言越来越少了…… 不要放弃啊，我也有被卡好几天的时候，但慢慢地就走出来了。 1. 编译器推断不出 U 的类型，因为 T 实现了多个 AsRef trait。可以使用 turbofish 手动指定 U，同时也要注意到对于 str 和 [u8] 来说，U 需要是 ?Sized。 2. 一开始我以为 WindowCount 结构体 next 方法返回的是一个新的 Iterator，这个新的 Iterator 里是 count 个 Item。后来我发现这不可能实现啊……我为什么一开始是这么想的呢，是受 slice 的 chunks 方法影响，chunks 方法这不是正好符合题目要求么，但 slice 是有长度信息的，而 Iterator 只能一直 next。后来我偷瞄了老师的实现，发现原来是想用 Vec 来承载每一组数据…… 具体实现代码就不贴了，和老师的差不多。 但我又回过头来想 rxjs 的 windowCount 好像不是这个意思，它的每一组数据还是一个流。那它怎么实现的呢？ 我想这可能跟 rxjs 的设计有关，它是把数据 push 到订阅者，而 Iterator 是 pull。 rxjs 单独使用 windowCount 是这样的效果：假如数据源是点击事件，count 是 3，一开始还没点击就产生一个 Observable（我们叫它 A），然后我点击第一下，这次点击就被推送到 A 了，点击第二下，也推送到 A，点击第三下，也推送到 A，这时候 A 已经吐 3 个数据了，紧接着就会产生下一个高阶 Observable B，用来承载接下来的三次点击…… 但这个 Iterator 是个同步模型，而且还没有数据总量的信息，我根本无法判断这次 next 是应该返回 None 还是 Some。 建议类似题目可以给出多一点的提示……

老师问个问题，为什么rust解引用是用&T 来表示，而不是用*T

还有个问题, 为啥需要 import FromIterator 才能使用 String::from_iter呢? String不都已经impl了吗? https://doc.rust-lang.org/src/alloc/string.rs.html#1866-1872

1. 有歧义, U可以是str, 也可以是[u8]; 2. 用vec作弊了: eagerly load window_size大小的element; 没有lazy load https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e6759f0d43bfbbb9f9a4b4aaf4a8ed8b 没有贴tests; 在link里面有 ``` struct WindowCount<T> where T: Iterator, { window_size: usize, start_window_every: usize, iter: T, } impl<T> Iterator for WindowCount<T> where T: Iterator, { type Item = <Vec<<T as Iterator>::Item> as IntoIterator>::IntoIter; fn next(&mut self) -> Option<Self::Item> { if self.window_size == 0 { return None; } let mut v = Vec::with_capacity(self.window_size); for _ in 0..self.window_size { if let Some(item) = self.iter.next() { v.push(item); } else { break; } } // advance steps for _ in 0..self.start_window_every { if self.iter.next().is_none() { break; } } if v.is_empty() { None } else { Some(v.into_iter()) } } } trait IteratorExt: Iterator { fn window_count(self, window_size: usize, start_window_every: usize) -> WindowCount<Self> where Self::Item: std::fmt::Debug, Self: Sized, { WindowCount { window_size, start_window_every, iter: self, } } } impl<T: Iterator> IteratorExt for T {} ```

写了一个缓存库，想问一下老师如何优化hashmap的性能，目前为了算法上的O1，使用了box和raw指针，但是会box和rebox又让性能慢了一些。https://github.com/al8n/caches-rs

let b1 = v1.into_boxed_slice(); let mut b2 = b1.clone(); let v2 = b1.into_vec(); println!("cap should be exactly 5: {}", v2.capacity()); assert!(b2.deref() == v2); b2的类型是Box([T]), 为何对b2做deref就变成Vec了？在标准库里没找到针对Box slice的Deref实现😭

1. 可以为同一个具体类型实现不同的AsRef Trait, 编译器无法从上下文中推断出U的具体类型，所以不能这样写。 2. 不知道实现的符不符合要求，以及有什么问题。 pub struct Window<I> { iter: I, count: usize, start: usize, } pub trait IteratorExt: Iterator { fn window_count(self, count: usize, start: usize) -> Window<Self> where Self: Sized, { Window { iter: self, count, start, } } } impl<T: Iterator> IteratorExt for T {} impl<I: Iterator> Iterator for Window<I> { type Item = Vec<<I as Iterator>::Item>; fn next(&mut self) -> Option<Self::Item> { if self.count == 0 { return None; } for _ in 0..self.start { self.iter.next()?; } let mut v = Vec::with_capacity(self.count); for _ in 0..self.count { v.push(self.iter.next()?); } Some(v) } } #[test] fn if_it_works() { let v1 = vec!['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']; let mut window = v1.iter().window_count(0, 0); assert_eq!(window.next(), None); let mut window = v1.into_iter().window_count(3, 0); assert_eq!(window.next(), Some(vec!['a', 'b', 'c'])); assert_eq!(window.next(), Some(vec!['d', 'e', 'f'])); assert_eq!(window.next(), Some(vec!['g', 'h', 'i'])); assert_eq!(window.next(), None); let v2 = vec!['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']; let mut window = v2.into_iter().window_count(3, 0); assert_eq!(window.next(), Some(vec!['a', 'b', 'c'])); assert_eq!(window.next(), Some(vec!['d', 'e', 'f'])); assert_eq!(window.next(), None); let v3 = vec![1, 2, 3, 4, 5, 6, 7, 8]; let mut window = v3.into_iter().window_count(3, 3); assert_eq!(window.next(), Some(vec![4, 5, 6])); assert_eq!(window.next(), None); let v4 = [1, 2, 3, 4, 5, 6, 7, 8]; let mut window = v4.iter().window_count(3, 100); assert_eq!(window.next(), None); }

漂亮，老师叕解答了我的好多疑惑。现在唯一有点要适应的就是函数数式编程。C++ 和 Go 写多了，一上来就是 for 循环，要适应 Rust 的想法也是个不小的挑战。