Extension traits

Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на упр.08 задача 1 от Деян Делчев

Обратно към всички решения

Към профила на Деян Делчев

Код

use std::rc::Rc;
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Rc<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
pub struct Iter<'a, T> {
node: Option<&'a Node<T>>,
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
match self.node {
None => None,
Some(node) => {
let value = &node.elem;
self.node = node.next.as_deref();
Some(value)
}
}
}
}
impl<T> List<T> {
pub fn new() -> Self {
Self { head: None }
}
pub fn head(&self) -> Option<&T> {
self.head.as_ref().map(|ptr| &ptr.elem)
}
pub fn tail(&self) -> List<T> {
match &self.head {
None => Self::new(),
Some(head) => Self {
head: head.next.as_ref().map(|ptr| Rc::clone(ptr)),
},
}
}
pub fn prepend(&self, value: T) -> List<T> {
Self {
head: Some(Rc::new(Node {
elem: value,
next: self.head.as_ref().map(|ptr: &Rc<Node<T>>| Rc::clone(ptr)),
})),
}
}
pub fn iter(&self) -> Iter<'_, T> {
Iter {
node: self.head.as_deref(),
}
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut curr = self.head.take();
while let Some(ptr)= curr {
match Rc::try_unwrap(ptr) {
// the strong counter is greater that 1 => there is another list that is using this node and its tail => return
Err(_) => return,
Ok(node) => curr = node.next
}
}
}
}

История (1 версия и 1 коментар)

Деян качи първо решение на 02.12.2025 20:01 (преди 3 дена)

Проблемът беше, че drop се викаше рекурсивно, което създава нова стекова рамка за всеки node. Първоначално мислех, че компилаторът ще се опита да направи опашкова рекурсия, но или не достатъчно умен да го направи (за което се съмнявам), или след викането на drop(next) има допънителна логика, което ще попречи да стане опашкова рекурсия.

Решението което ми хрумна е да направя drop-a итертивен. Докато скролвах асоциативните функции на Rc, видях try_unwrap.