Derive + Generic структури

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

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

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

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

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

Резултати

  • 4 точки от тестове
  • 1 бонус точка
  • 5 точки общо
  • 2 успешни тест(а)
  • 0 неуспешни тест(а)

Код

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

Лог от изпълнението

Updating crates.io index
     Locking 17 packages to latest compatible versions
   Compiling proc-macro2 v1.0.103
   Compiling quote v1.0.42
   Compiling unicode-ident v1.0.22
   Compiling futures-sink v0.3.31
   Compiling futures-core v0.3.31
   Compiling futures-channel v0.3.31
   Compiling slab v0.4.11
   Compiling syn v2.0.111
   Compiling futures-task v0.3.31
   Compiling pin-project-lite v0.2.16
   Compiling pin-utils v0.1.0
   Compiling futures-io v0.3.31
   Compiling memchr v2.7.6
   Compiling solution v0.1.0 (/tmp/d20251211-1757769-14khao5/solution)
   Compiling futures-macro v0.3.31
   Compiling futures-util v0.3.31
   Compiling futures-executor v0.3.31
   Compiling futures v0.3.31
    Finished `test` profile [unoptimized + debuginfo] target(s) in 8.41s
     Running tests/solution_test.rs (target/debug/deps/solution_test-ee0783488e12dce9)

running 2 tests
test solution_test::test_iterator ... ok
test solution_test::test_list ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

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

Деян качи първо решение на 02.12.2025 20:01 (преди около 2 месеца)

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

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