TreeSet Drop implementation


Very recently I’ve started playing with Rust.
Inspired by I have created simple Queue:

use std::rc::Rc;
use std::cell::RefCell;

pub struct Queue<T> {
    head: Link<T>,
    tail: Link<T>,

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T> {
    item: T,
    previous: Link<T>,

impl<T> Queue<T> {   
    pub fn enque(&mut self, item: T) {
    pub fn deque(&mut self) -> Option<T> {

Implementing Drop for it is quite straithforward:

impl<T> Drop for Queue<T> {
    fn drop(&mut self) {
        while self.deque().is_some() {}

Now I’m on a quest to implement something slightly more complicated, a TreeSet:

use std::cmp::Ordering;

pub struct TreeSet<T: PartialOrd> {
    root: Link<T>,

type Link<T> = Option<Box<Node<T>>>;

struct Node<T: PartialOrd> {
    item: T,
    left: Link<T>,
    right: Link<T>,

However, I can’t really figure out how Drop should look like in this case. I’m not really able to understand BTreeSet yet (not mentioning lots of unsafe code which I 'm trying not to use at this stage).


I suspect you don’t actually need to implement Drop for that set. There’s no Rc-cycle like the queue has, so the Drop of the inner types (especially Box) should just do the right thing.


Is your tree balanced? Then you won’t have any stack exhaustion issues on drop anyway. If the tree has a worst case of looking like a list, you might consider it.


@bluss What do you mean? Dropping a ‘list like’ tree manually could be potentially more performant?


The idea is that a recursive drop can exhaust the stack memory if the list is too long, whereas popping items one at a time keeps it all local. It might also perform better, but the memory is the first concern.


Thank you all for the answers.