es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Cómo implementar `Iterator` para una pila de tamaño variable utilizando `NonNull`?

14 Jul, 2023 Programación

Estoy siguiendo la guía para implementar una pila de arreglo de redimensionamiento usando NonNull:

rust
pub struct ResizingStack<T> {
a: NonNull<T>,
n: usize,
capacity: usize,
}

Ahora las funcionalidades básicas (por ejemplo, push y pop) funcionan bien. El código completo se puede encontrar aquí. Pero tengo problemas para implementar el rasgo Iterator.

Para un iterador forward, una solución simple es hacer que ResizingStack se comporte como una slice.

rust
impl<T> Deref for Vec<T> {
type Target = [T];
fn deref(&self) -> &[T] {
unsafe {
std::slice::from_raw_parts(self.a.as_ptr(), self.n)
}
}
}

Sin embargo, una pila, de hecho, debería tener un iterador backward. Estos son mis intentos:

pub struct StackIter<'a, T> {
    buf: &'a ResizingStack<T>,
    index: usize,
}

impl<T> ResizingStack<T> {
    pub fn iter(&self) -> StackIter<'_, T> {
        StackIter {
            buf: self,
            index: self.n,
        }
    }
}

impl<'a, T> Iterator for StackIter<'a, T> {
    type Item = &'a T;

<pre><code>fn next(&amp;mut self) -&gt; Option&lt;Self::Item&gt; {
    if self.index == 0 {
        None
    } else {
        let item;
        unsafe {
            item = Some(ptr::read(self.buf.a.as_ptr().add(self.index - 1)));
            self.index -= 1;
        }
        item // ERROR: expected `Option&lt;&amp;T&gt;`, but found `Option&lt;T&gt;`.
    }
}
</code></pre>

}
Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Solución para el Iterador ResizingStack

    Para implementar un iterador hacia atrás para una implementación de ResizingStack, podemos definir un tipo StackIter que contenga el búfer y el índice actual. El método iter en ResizingStack devuelve un StackIter que comienza en el último elemento del búfer.

    pub struct StackIter<'a, T> {
    buf: &'a ResizingStack<t>,
    index: usize,
}

impl<t> ResizingStack<t> {
    pub fn iter(&self) -> StackIter<t> {
        StackIter {
            buf: self,
            index: self.n,
        }
    }
}

    El método next en StackIter puede iterar hacia atrás disminuyendo el índice en cada llamada hasta que llegue al primer elemento. Podemos usar el método add en punteros para acceder al elemento en el índice actual. Sin embargo, debemos tener cuidado de no mover los datos fuera del búfer ResizingStack. Podemos envolver el elemento con un tipo Option para evitar mover los datos.

    impl<'a, T> Iterator for StackIter<'a, T> {
    type Item = Option<&'a T>;

    fn next(&mut self) -> Option<self::item> {
        if self.index == 0 {
            None
        } else {
            self.index -= 1;
            Some(unsafe { &*self.buf.a.as_ptr().add(self.index) })
        }
    }
}

    El método next devuelve un Option<option<&'a t="">>, donde el inner Option se utiliza para evitar mover los datos fuera del búfer. El outer Option se utiliza para indicar cuándo el iterador ha llegado al final del búfer. El bloque unsafe es necesario para leer el elemento en el índice actual sin moverlo fuera del búfer.

    Con estos cambios, ahora podemos iterar hacia atrás sobre un ResizingStack utilizando un bucle for, un bucle while let o cualquier otra construcción que admita la iteración.

    use rust_learning::stack::ResizingStack;

fn main() {
    let mut stack = ResizingStack::new();
    stack.push(1);
    stack.push(2);
    stack.push(3);

    for item in stack.iter() {
        println!("{:?}", item);
    }
}

    Esto imprimirá:

    Some(&3)
    Some(&2)
    Some(&1)    </option<&’a>

Comments are closed.