無需額外分配即可移動和修改矢量嗎？

考慮下面的代碼：無需額外分配即可移動和修改矢量嗎？

let u: Vec<u8> = (64..74).collect(); 
let v: Vec<u8> = u.iter().map(|i| i + 1).collect();

u未動，因此v不可避免地新分配。

但是，如果我做到以下幾點：

let w: Vec<u8> = u.into_iter().map(|i| i + 1).collect();

u感動，w是其轉型的名字。這裏是一些僞代碼代表了我的意思：

mark u as "moved" 
for i = 0..10: 
    u[i] += 1 
w = u

有（在我看來）不需要新的分配，因爲我們一個類型映射到自身。這不會是這個代碼的情況：

let t: Vec<u8> = (64..74).collect(); 
let s: String = t.into_iter().map(|i| i as char).collect();

總結我的問題

是否有新Vec的分配，當我們轉換一個Vec成一個迭代器，然後映射這個迭代器在相同類型的元素的迭代器，然後收集結果成Vec？

，如果有確實的分配，爲什麼呢？

我試圖--emit=mir，但我沒能找到答案。我使用rustc 1.20夜間（如果該事項）。

If you want to play with code: Try it online!

來源

2017-08-18 jferard

雖然這是一個關於優化的有趣問題，但請注意，如果您只是爲'i in＆mut u {* i + = 1; }'。 –

@PavelStrakhov如果我理解正確，你的代碼大約是我的僞代碼的Rust翻譯，沒有原始的「功能風格」。另外請注意，在我的例子中，'u'不可變。 – jferard

讓我們看到into_iter()實施the source爲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迭代招致一些額外的撥款，而不是爲向量的元素;相反，向量的底層內存細節已註冊。 the codemap()後面怎麼樣？

fn map<B, F>(self, f: F) -> Map<Self, F> where 
    Self: Sized, F: FnMut(Self::Item) -> B, 
{ 
    Map{iter: self, f: f} 
}

這裏沒有額外的矢量分配。最後一塊拼圖是collect()：

fn collect<B: FromIterator<Self::Item>>(self) -> B where Self: Sized { 
    FromIterator::from_iter(self) 
}

這裏沒有答案; the implementation的from_iter()爲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 code將揭示什麼，我們正在尋找：

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方法稱爲其爲結果向量分配新的空間。

TL; DR：不，不可能移動和修改一個向量而不需要額外的分配。

來源

2017-08-18 11:43:09 ljedrz

您的文章不論是否有任何編譯器階段都可以優化那些| | * TL; DR：否* - 他問是否有分配。 – the8472

@ the8472你已經就你的答案中的必要優化提出了一個很好的一般性論點;我只是展示了證明過程複雜性的必要步驟，這使得實際上不可能（在這一點上）。在TL; DR中，我正在回答問題的標題，儘管我同意 - 當我在PC上時我會更加清楚。 – ljedrz

嗯，不清楚你試圖回答的問題的哪一部分 – the8472

是否有新的VEC的分配時，我們把A VEC爲迭代器，然後這個迭代器映射到一個迭代器上相同類型的元素，然後收集結果爲A VEC？

是的，必要的優化，以避免分配實在太高級別爲任何編譯器層級的執行，因爲他們將不得不推理堆分配和指針魔術在不安全的代碼塊去上支持Vec實施。雙所以在一般情況下下拉處理程序中，map和類似的東西里面恐慌開始發揮作用。

可能可以通過specializing
collect() -> Vec<T>特定類型如std::iter::Map<std::vec::IntoIter<T>, _>在庫級進行優化，但這些優化將有一個案件逐案基礎那裏它被稱爲是安全的得到應用。

如果我理解正確，你的代碼大概是我的僞代碼的Rust翻譯，沒有原始的「功能樣式」。

對於功能的風格有加for_each到迭代計劃，所以如果你需要一個iter_mut等價的東西可以用在圖書館或編譯器側面少得多的神勇表現來實現。

而且它實際上反映了更直接地做某件事的意圖，而不是僅僅做一些神奇的優化，然後可能在輕微的修改下令人驚訝地中斷。

來源

2017-08-18 10:38:39 the8472

無需額外分配即可移動和修改矢量嗎？

回答

相關問題