集合类型

Vec

slice.first(), slice.last(), slice.get(index)

获取Option<&T>

slice.first_mut(), slice.last_mut(), slice.get_mut(index)

获取Option<&mut T>

to_vec

// Get a copy of a slice
let my_copy = buffer[4..12].to_vec();  // requires Clone

大多数获取元素的方法都是返回引用，但to_vec是复制。

vec.reserve(n), vec.reserve_exact(n), shrink_to_fit

reserve预留n的内存，但可能会超过。reserve_exact会预留n，不会多。shrink_to_fit会将多余的空间去掉，也就是让capacity等于len。

vec.push(value), vec.pop()

vec.insert(index, value), vec.remove(index)

vec.resize(new_len, value), vec.resize_with(new_len, closure)

vec.truncate(new_len), vec.clear()

truncate将长度减小到len，capacity不变。如果new_len大于现在的len什么都不做，和resize差不多。

vec.extend(iterable), vec.append(&mut vec2)

区别就是append之后vec2还存在，只是len变成0。

vec.drain(range), vec.retain(test)

vec.dedup(), vec.dedup_by(same), vec.dedup_by_key(key)

只会除去相邻的重复元素。

slices.concat(), slices.join(&separator)

splitting

let mut v = vec![0, 1, 2, 3];
let a = &mut v[i];
let b = &mut v[j];

这样是不合法的，v不能有两个可变引用。（因为索引可能相同，所以整个slice都不能被引用？）
rust有很多方法可以从一个切片生成一些没有重叠的部分，这样分别对其取可变引用就可以了。

Swapping

slice.swap(i, j), slice_a.swap(&mut slice_b), vec.swap_remove(i)

Sorting and Searching

slice.sort(), slice.sort_by(cmp), slice.sort_by_key(key), slice.reverse(), slice.binary_search(&value), slice.binary_search_by(&value, cmp), slice.binary_search_by_key(&value, key), slice.contains(&value)

Comparing Slices

如果原色是PartialEq，则可以用= !=进行相等判断，如果元素是PartialOrd则可以进行大小比较。
slice.starts_with(other), slice.ends_with(other)

Random Elements

slice.choose(&mut rng), slice.shuffle(&mut rng)

VecDeque

常用方法是从头和尾加元素和取元素，以及取元素的引用。Deque的存储方式：

很多Vec的方法，Deque也有，.len() and .is_empty(), .insert(index, value), .remove(index), .extend(iterable), 等。但因为Deque不是顺序存储的，Vec的方法并不能全部支持。方法make_contiguous可以将其内存变成顺序的。

Vec和Deque之间可以方便的相互转换：Vec::from(deque)，VecDeque::from(vec)。没有像vec!这样的宏来生成Deque，当可以利用上面的from方法来生成deque：

let v = VecDeque::from(vec![1, 2, 3, 4]);

BinaryHeap

heap.peek_mut()

可以先看一眼，然后用类型关联方法来pop最大的元素

use std::collections::binary_heap::PeekMut;
if let Some(top) = heap.peek_mut() {
    if *top > 10 {
        PeekMut::pop(top);
    }
}

BinaryHeap的迭代器是按随机的顺序输出的，所以要按从大到小的顺序便利需要用：

while let Some(task) = heap.pop() {
    handle(task);
}

HashMap and BTreeMap

HashMap

BtreeMap

Rust用B-tree而不是balanced binary tree是因为B-tree有更好的locality，在搜索的时候更容易用到CPU cache，在现代计算机上性能更好。

创建的方法

HashMap::new(), BTreeMap::new(), iter.collect(), HashMap::with_capacity(n)
iter.collect()中的iter的类型需要是Iterator。
因为HashMap将值存在一个类似Vec的序列里，所以有和capacity相关的一些方法，BtreeMap没有。

判断相关

map.len(), map.is_empty(), map.contains_key(&key)

获取值

map.get(&key) , map.get_mut(&key)
一般来说map允许获取值的可变引用，而不能获取键的，因为map的内部结构是按键规划的，改变key会改变map的整体结构。
map[&key]取值，如果key不存在会panic。

修改

map.insert(key, value) 如果相同的key已经有value则返回Some(value)。
map.extend(iterable), map.append(&mut map2)
map.remove(&key)返回Option，map.remove_entry(&key)返回Option<(K, V)>。
map.retain(test)

btree_map.split_off(&key)将一个树从key劈成两半，把大于key的那一半返回。

entry

pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>

返回的Entry是一个特殊的这个map的可变引用。这个需要的key是个值，而不是引用。（可能是因为Entry可以用来往对应的key的位置插入值，这时候就需要有这个key的所有权。）
Entry的定义是一个enum

// (in std::collections::hash_map)
pub enum Entry<'a, K, V> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>)
}

map.entry(key).or_insert(value)
返回的是一个对于值的可变引用，可以直接用来修改map里的值

let mut vote_counts: HashMap<String, usize> = HashMap::new();
for name in ballots {
    let count = vote_counts.entry(name).or_insert(0);
    *count += 1;
}

map.entry(key).or_default()
和or_insert类似，返回默认值。

map.entry(key).or_insert_with(default_fn)
使用一个函数或闭包来插入默认值。类似Python的defaultdict。

map的迭代

可以用for (k, v) in map的形式迭代map。有值，不可变引用和可变引用三种形式，可变引用的形式也只有值可变，key不可变。
还可以用方法来生成迭代器：map.keys()，map.values()，map.values_mut()。
还有各种序列类型都有的iter，iter_mut。

遍历的时候HashMap是无序的，BtreeMap是有序的。

HashSet and BTreeSet

内部实现是包装了HashMap和BTreeMap。
set.insert(value) 如果值已存在了返回false。set.remove(&value)如果值不存在返回false，否则移除value并返回true。

set的遍历也不能对值进行可变应用的遍历。顺序和map一样hash无序，Btree有序。

相等却不同

有的值在比较上是相等的，但值的内容可能不同，比如相等的两个字符串所存放的位置是不同的。想要使用这种不同的时候用以下方法：
set.get(&value)获取和value相等的元素的引用，返回Option<&T>。
set.take(&value)将和value相等的元素从集合移除并返回，如果存在的话。
set.replace(value)，用新值替换原来的值，返回旧值Option。

集合的整体操作

交集：.intersection方法返回一个迭代器；&操作符返回一个新的集合，&的操作数必须是集合是引用，不能是值。
并集：union，|
差集（补集）：difference，-
对称差：symmetric_difference，^，在两个集合之一但不能都在。

is_disjoint：判断是否有交集
is_subset：是否是子集
is_superset：
集合可以用 = 和 != 进行判断

Hashing

HashMap和HashSet的元素必须实现std::hash::Hash。大多数内建的实现了Eq的类型都实现了Hash。比如整形，char，String都是，元素是Hash的切片，数组，向量，元组等也都是Hash。
标准库的一个原则是，一个值的哈希值，无论它存在哪，怎么存，怎么取，都是不会变的，所以值，引用，Box的哈希都应该一样，相同元素的Vec和切片的哈希值也一样。

枚举和结构体默认不实现Hash，但如果它们的元素都是Hash就可以derive Hash。
如果一个类型是实现了自定义的PartialEq那也应该自定义Hash。否则hash的逻辑可能出错，因为相等的两个值必须有相同的哈希值。

实现hash一般可以用类型本身的哈希函数和标准库的哈希算法(hasher)

use std::hash::{Hash, Hasher};
impl Hash for Artifact {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        // Delegate hashing to the MuseumNumber.
        self.id.hash(hasher);
    }
}

自定义哈希算法

std::hash::BuildHasher：是用来保存哈希算法的初始状态和一些参数（比如秘钥，初始状态等）的。一般计算哈希值的过程是：

use std::hash::{Hash, Hasher, BuildHasher};
fn compute_hash<B, T>(builder: &B, value: &T) -> u64
    where B: BuildHasher, T: Hash
{
    let mut hasher = builder.build_hasher();  // 1. start the algorithm
    value.hash(&mut hasher);                  // 2. feed it data
    hasher.finish()                           // 3. finish, producing a u64
}

要使用自定义的哈希算法来实现HashMap或HashSet，只需要将HashMap或HashSet的可选的算法参数变成自己的就行

/// A `HashMap` using a default FNV hasher.
pub type FnvHashMap<K, V> = HashMap<K, V, FnvBuildHasher>;
/// A `HashSet` using a default FNV hasher.
pub type FnvHashSet<T> = HashSet<T, FnvBuildHasher>;