问题描述
考虑以下代码:
let u: Vec<u8> = (64..74).collect();
let v: Vec<u8> = u.iter().map(|i| i + 1).collect();
u
没有移动,因此不可避免地重新分配了v
.
u
was not moved, therefore v
was inevitably newly allocated.
但是,如果我执行以下操作:
But if I do the following:
let w: Vec<u8> = u.into_iter().map(|i| i + 1).collect();
u
已移动,w
是其转换的名称.这是一些代表我的意思的伪代码:
u
was moved and w
is the name of its transformation. Here is some pseudo-code representing what I mean:
mark u as "moved"
for i = 0..10:
u[i] += 1
w = u
(在我看来)不需要新的分配,因为我们将类型映射到自身.这段代码不是这样的:
There is (in my opinion) no need for a new allocation, since we map a type to itself. This wouldn't be the case for this code:
let t: Vec<u8> = (64..74).collect();
let s: String = t.into_iter().map(|i| i as char).collect();
总结我的问题
当我们将Vec
转换为迭代器,然后将该迭代器映射到相同类型元素上的迭代器时,是否分配了新的Vec
,然后将结果收集到一个Vec
?
Is there an allocation of a new Vec
when we convert a Vec
into an iterator and then map this iterator to an iterator on elements of the same type and then collect the result into a Vec
?
如果确实有分配,为什么?
And if there is indeed an allocation, why?
我尝试了--emit=mir
,但是找不到答案.我每晚使用rustc 1.20(如果这样的话).
I tried to --emit=mir
, but I wasn't able to find the answer. I'm using rustc 1.20 nightly (if that matters).
推荐答案
让我们看看用于Vec<T>
的into_iter()
实现的来源:
Let's see the source of the implementation of into_iter()
for Vec<T>
:
fn into_iter(mut self) -> IntoIter<T> {
unsafe {
let begin = self.as_mut_ptr();
assume(!begin.is_null());
let end = if mem::size_of::<T>() == 0 {
arith_offset(begin as *const i8, self.len() as isize) as *const T
} else {
begin.offset(self.len() as isize) as *const T
};
let cap = self.buf.cap();
mem::forget(self);
IntoIter {
buf: Shared::new(begin),
cap: cap,
ptr: begin,
end: end,
}
}
}
创建IntoIter
迭代器会产生一些额外的分配,但不会分配给向量的元素;相反,将注册向量的基础内存详细信息. 代码如何在map()
后面?
Creating the IntoIter
iterator incurs several extra allocations, but not for the elements of the vector; instead, the vector's underlying memory details are registered. How about the code behind map()
?
fn map<B, F>(self, f: F) -> Map<Self, F> where
Self: Sized, F: FnMut(Self::Item) -> B,
{
Map{iter: self, f: f}
}
这里也没有分配额外的向量.最后一个难题是 collect()
:
No extra vectors allocated here either. The last piece of the puzzle is collect()
:
fn collect<B: FromIterator<Self::Item>>(self) -> B where Self: Sized {
FromIterator::from_iter(self)
}
这里没有答案; 的实现 c14>代表Vec<T>
?
No answers here; what about the implementation of from_iter()
for Vec<T>
?
impl<T> FromIterator<T> for Vec<T> {
#[inline]
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vec<T> {
<Self as SpecExtend<T, I::IntoIter>>::from_iter(iter.into_iter())
}
}
这开始看起来像魔术,但也许相关的 SpecExtend代码将显示我们正在寻找的内容:
This is beginning to look like magic, but perhaps the related SpecExtend code will reveal what we're looking for:
impl<T, I> SpecExtend<T, I> for Vec<T>
where I: Iterator<Item=T>,
{
default fn from_iter(mut iterator: I) -> Self {
// Unroll the first iteration, as the vector is going to be
// expanded on this iteration in every case when the iterable is not
// empty, but the loop in extend_desugared() is not going to see the
// vector being full in the few subsequent loop iterations.
// So we get better branch prediction.
let mut vector = match iterator.next() {
None => return Vec::new(),
Some(element) => {
let (lower, _) = iterator.size_hint();
let mut vector = Vec::with_capacity(lower.saturating_add(1));
unsafe {
ptr::write(vector.get_unchecked_mut(0), element);
vector.set_len(1);
}
vector
}
};
<Vec<T> as SpecExtend<T, I>>::spec_extend(&mut vector, iterator);
vector
}
default fn spec_extend(&mut self, iter: I) {
self.extend_desugared(iter)
}
}
在这段代码中,我们终于可以看到Vec::new
和Vec::with_capacity
方法,它们为所得的向量分配新的空间.
In this code we can finally see the Vec::new
and Vec::with_capacity
methods called which allocate fresh space for the resulting vector.
TL; DR :不,如果没有额外的分配,不可能移动和修改向量.
TL;DR: no, it is not possible to move and modify a vector without an extra allocation.
这篇关于可以在无需额外分配的情况下移动和修改向量吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!