且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

可以在无需额外分配的情况下移动和修改向量吗?

更新时间:2023-11-22 23:19:28

让我们看看

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())
    }
}

这开始看起来像魔术,但也许相关的

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::newVec::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.