Qual è lo scopo di SizeHint in Iterator :: unzip?

Question

Dalla libreria standard Rust implementation of unzip:

fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) where 
    FromA: Default + Extend<A>, 
    FromB: Default + Extend<B>, 
    Self: Sized + Iterator<Item=(A, B)>, 
{ 
    struct SizeHint<A>(usize, Option<usize>, marker::PhantomData<A>); 
    impl<A> Iterator for SizeHint<A> { 
     type Item = A; 

     fn next(&mut self) -> Option<A> { None } 
     fn size_hint(&self) -> (usize, Option<usize>) { 
      (self.0, self.1) 
     } 
    } 

    let (lo, hi) = self.size_hint(); 
    let mut ts: FromA = Default::default(); 
    let mut us: FromB = Default::default(); 

    ts.extend(SizeHint(lo, hi, marker::PhantomData)); 
    us.extend(SizeHint(lo, hi, marker::PhantomData)); 

    for (t, u) in self { 
     ts.extend(Some(t)); 
     us.extend(Some(u)); 
    } 

    (ts, us) 
} 

Queste due linee:

ts.extend(SizeHint(lo, hi, marker::PhantomData)); 
us.extend(SizeHint(lo, hi, marker::PhantomData)); 

in realtà non si estendono ts o us da nulla, in quanto il metodo di SizeHint rendimenti Nonenext. Qual è lo scopo di farlo?

Answer 1

È un bel trucco. Dando questo suggerimento sulle dimensioni, dà ts e us la possibilità di riservare lo spazio per le chiamate extend nel ciclo. Secondo la documentation

size_hint() è principalmente destinato ad essere utilizzato per ottimizzazioni ad esempio riservare spazio per gli elementi del iteratore, ma non deve essere attendibile per esempio ometti i controlli dei limiti in codice non sicuro. Un'implementazione errata di size_hint() non dovrebbe comportare violazioni della sicurezza della memoria.

nota che la creazione di SizeHint è necessaria perché la chiamata extend a ciclo è fatto con un valore Some (Optional attua la Iterator tratto), e il size_hint per un valore Some è (1, Some(1)). Ciò non aiuta con la pre-assegnazione.

Ma guardando il codice per Vec, questo non avrà alcun effetto (né in HashMap e VecDeque). Altre implementazioni Extend potrebbero essere diverse.

L'esecuzione di ts.extend(SizeHint(lo, hi, marker::PhantomData)); non attiva un resize, dal next restituisce None. Forse qualcuno dovrebbe scrivere una patch.

impl<T> Vec<T> { 
    fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) { 
     // This function should be the moral equivalent of: 
     // 
     //  for item in iterator { 
     //   self.push(item); 
     //  } 
     while let Some(element) = iterator.next() { 
      let len = self.len(); 
      if len == self.capacity() { 
       let (lower, _) = iterator.size_hint(); 
       self.reserve(lower.saturating_add(1)); 
      } 
      unsafe { 
       ptr::write(self.get_unchecked_mut(len), element); 
       // NB can't overflow since we would have had to alloc the address space 
       self.set_len(len + 1); 
      } 
     } 
    } 
} 

Answer 2

Si tratta di un hack dubbia!

Implementa un iteratore con un suggerimento di dimensioni false (sovrastimato) per incoraggiare la raccolta prodotta a riservare la capacità eventualmente appropriata in anticipo.

Fantastico trucco, ma lo fa implementando un suggerimento di dimensione in cui il limite inferiore stimato è maggiore del numero effettivo di elementi prodotti (0). Se il limite inferiore non è noto, l'iteratore dovrebbe restituire un limite inferiore di 0. Questa implementazione è discutibilmente molto bacata per questo motivo, e l'estensione Extend della collezione potrebbe reagire con errori simili (ma ovviamente non problemi di memoria).