如果我们需要FIFO或LIFO集合(基本上是push
,pop
和front
/ back
)我们应该在Rust中使用什么?像C ++中的std::queue
或std::stack
。
首先,Rust没有(在标准库中)提供任何具有保证的添加元素延迟的库:Rust集合通常可以在添加新元素时分配内存,并且在最坏的情况下分配内存可能需要无限量的时间。
话虽如此,每个案例都有两个竞争者:
Vec
或LinkedList
(都是pop_back
和push_back
)之上实现VecDeque
或LinkedList
(都是pop_front
和push_back
)之上实现Vec*
和LinkedList
之间的区别在于后者是简单化的:每次调用push_back
都会进行内存分配。一方面,这很好,因为这意味着push_back
的成本与集合中已有元素的数量无关,另一方面......内存分配可能需要很长时间。
前者有点复杂:
push_back
push_back
,即使没有提前保留过剩的产能一般来说,我建议使用Vec
作为堆栈,使用VecDeque
作为队列。
VecDeque
和LinkedList
都有push
/ pop
_front
/ back
。
Matthieu M.说得很完美。 Vec
是你的堆栈(LIFO),VecDeque
是一个双端队列,支持所有4种变体(FIFO,FILO,LIFO和LILO),使用:
.push_front(x) | .front() | .pop_front()
.push_back(x) | .back() | .pop_back()
如果您希望最大限度地提高效率,我建议您查看"Unterstanding Rust’s Vec and its capacity for fast and efficient programs"。它详细介绍了如何在Vec
和VecDeque
中进行分配和重新分配,但最大的收获是,如果你能预测队列中你需要的最大元素数,你可以使用VecDeque::with_capacity(x)
,如果你知道的话当你初始化它,或者.reserve_exact(x)
,如果在某些时候你确切知道你需要多少个插槽
我强烈建议您查看std::collections
上的Rust文档,它有一个很好的Rust列表中最常用的集合,以及何时选择每个集合的建议
最后一点,VecDeque
不是Rust中默认前奏的一部分,所以如果你想使用它,你需要包含这个:
use std::collections::VecDeque;