rust之vector笔记
描述
vector就是rust里面的动态增加元素的列表类型。官网中的定义是一个在堆上分配内存，可以持续增长的array类型。写作Vec，也是声明的定义。Vectors有O(1)的索引时间复杂度，在尾部插入和弹出也是O(1)的时间复杂度。
声明定义
rust的声明定义如下，其实我也看不太懂，反正是一个struct。
pub struct Vec<T, A = Global>
where
A: Allocator,
{ /* fields omitted */ }
属性
vector的属性iu两个，但是我们都没办法直接访问。
pub struct Vec<T, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global> {
buf: RawVec<T, A>,
len: usize,
}
len()
获取当前vector长度
capacity()
获取当前容量。
is_empty()
当前vector是否为空
初始化
初始化有两种方式
- 调用new方法
let mut vec = Vec::new();
vec.push(1);
vec.push(2);
- 使用宏
let vec = vec![1,2,3];
vec.push(4);
assert_eq!(vec, [1,2,3,4]);
还支持，初始化单一值的快捷方式
let vec = vec![0; 5]; // 初始化5个0
assert_eq!(vec, [0, 0, 0, 0, 0]);
- 只申请空间不初始化
可以使用with_capacity函数来申请空间，我们可以看到vec的长度是0，空间是我们申请的大小。但是一般不这么做，官网说这样性能不好。
let vec: Vec<i32> = Vec::with_capacity(10);
assert_eq!(0, vec.len());
assert_eq!(10, vec.capacity());
索引元素
vec支持类似数组的方式索引元素。因为他们都实现了index的trait。
let v = vec![0, 2, 4, 6];
println!("{}", v[1]); // it will display '2'
但是如果索引不存在的元素、越界的元素会导致panic。
let v = vec![0, 2, 4, 6];
println!("{}", v[6]); // it will panic!
安全的索引元素的方式是使用get、get_mut函数。
get函数返回的结果是一个Opiton的slice。参数是单个位置的索引或者多个位置索引的slice。
let v = vec![10, 40, 30];
assert_eq!(Some(&40), v.get(1));
assert_eq!(Some(&[10, 40][..]), v.get(0..2));
assert_eq!(None, v.get(3));
assert_eq!(None, v.get(0..4));
get_mut函数的参数和get函数一致，但是返回的结果是可以修改的引用。
let mut x = vec![0, 1, 2];
if let Some(elem) = x.get_mut(1) {
*elem = 42;
}
assert_eq!(x, &[0, 42, 2]);
改变容积
reserve
保留容积到某个值。下面的例子是保留到10，所以vec要至少保留当前元素的容量+10。实际的容量一般是20，vector内部有一套申请容积的规则。
let mut vec = vec![1];
vec.reserve(10);
assert!(vec.capacity() >= 11);
reserve_exact
名字也可以看出来，作用是保留确切大小的容积。
shrink_to_fit
也是减少容积。[todo] 具体的作用和reserve的不同之处
添加元素
append
添加另一个vector的所有元素，并清空另一个vector。
let mut vec = vec![1, 2, 3];
let mut vec2 = vec![4, 5, 6];
vec.append(&mut vec2);
assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
assert_eq!(vec2, []);
插入元素
insert
在对应索引处，插入一个元素，将后面的元素右移
let mut vec = vec![1, 2, 3];
vec.insert(1, 4);
assert_eq!(vec, [1, 4, 2, 3]);
vec.insert(4, 5);
assert_eq!(vec, [1, 4, 2, 3, 5]);
push
在vector末尾插入一个元素
删除元素
pop
弹出vector最后一个元素。
clear
清空所有元素，但是不释放空间
let mut v = vec![1, 2, 3];
v.clear();
assert!(v.is_empty());
assert_eq!(v, []);
truncate
就是直接删除，包括空间。有以下几种情况
let mut vec = vec![1, 2, 3, 4, 5];
vec.truncate(2); //就剩两元素
assert_eq!(vec, [1, 2]);
let mut vec = vec![1, 2, 3];
vec.truncate(8); //没有删除任何元素
assert_eq!(vec, [1, 2, 3]);
let mut vec = vec![1, 2, 3];
vec.truncate(0); // 相当于clear函数
assert_eq!(vec, []);
remove
删除元素，并返回。剩下的所有元素左移。
swap_remove
删除单个元素，返回删除元素，并将最后一个元素挪到删除元素位置。
swap
交换给定索引的元素
let mut v = vec![1, 2, 3];
v.swap(1,2);
assert_eq!(vec![1,3,2], v);
遍历
iter
iter返回都是引用，这个函数返回的是不可变的引用。
let v = vec![1, 2, 3];
for x in v.iter() {
println!("{}", x);
}
iter_mut
可变的iter
let mut v = vec![1, 2, 3];
for x in v.iter_mut() {
*x += 1;
}
assert_eq!(vec![2,3,4], v);
查找
contains
判断元素是否在vector内，参数需要是一个引用类型
let v = vec![10, 40, 30];
assert!(v.contains(&30));
assert!(!v.contains(&50));
start_with
从开始位置判断slice是否在vector内。
let v = vec![10, 40, 30];
assert!(v.starts_with(&[10]));
assert!(v.starts_with(&[10, 40]));
assert!(!v.starts_with(&[50]));
assert!(!v.starts_with(&[10, 50]));
end_with
从末尾判断slice是否在vector内
let v = vec![10, 40, 30];
assert!(v.ends_with(&[30]));
assert!(v.ends_with(&[40, 30]));
assert!(!v.ends_with(&[50]));
assert!(!v.ends_with(&[50, 30]));
binary_search
对一个排好序的vec，使用二分查找，返回查找元素的索引的slice。
let s = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
assert_eq!(s.binary_search(&13), Ok(9));
assert_eq!(s.binary_search(&4), Err(7));
assert_eq!(s.binary_search(&100), Err(13));
let r = s.binary_search(&1);
assert!(match r { Ok(1..=4) => true, _ => false, });
排序
sort
对vector进行排序，排序的结果是stable的（不会改变相同元素的位置）。算法复杂度是O(nlogn)。算法的实现是timsort的类似实现。
let mut v = vec![-5, 4, 1, -3, 2];
v.sort();
assert_eq!(v, [-5, -3, 1, 2, 4]);
sort_unstable
要比sort方法理论上快。
split
split_off
根据给的索引，将vec分裂成两个vectors
let mut vec = vec![1, 2, 3];
let vec2 = vec.split_off(1);
assert_eq!(vec, [1]);
assert_eq!(vec2, [2, 3]);
字符串操作
concat
拍平一个vector
assert_eq!(["hello", "world"].concat(), "helloworld");
assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
join
将vector的所有元素进行拼接（拍平），可以添加分隔符号。
assert_eq!(["hello", "world"].join(" "), "hello world");
assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]);
assert_eq!([[1, 2], [3, 4]].join(&[0, 0][..]), [1, 2, 0, 0, 3, 4]);
获取slice
从一个vector获取他的slice的方式有两种，一种是通过引用的方式，一种是通过函数。
let mut v = vec![1, 2, 3];
let v_slice = &v; // 常用
let v_slice_part = &v[1..2]; // 获取第二个和第三个元素的slice
let v_slice_all = &v[..]; // 不常用的
let v_slice_all_1 = &v[0..];; // 也不是很常用
as_slice
let mut buffer = vec![0; 3];
let buffer = buffer.as_slice();
as_mut_slice
let mut buffer = vec![0; 3];
let buffer = buffer.as_mut_slice()
总结
把官方ref里面关于vector中常用的方法进行总结了下，文档看了好几遍，没有把lambda相关，以及night版本的函数加进来。