impl push(self , item : T) for a struct with 2 Vecs<T>

Question

I've been trying to impl the push for this struct:

struct StackMin<T: std::cmp::Ord>
{
    stack : Vec<T>,
    min : Vec<T>
}

like this:

fn push(&mut self, item: T) {
    let l = self.stack.len();
    let x: T;
    match l {
        0 => println!("There is nothing in the stack."),
        n => {
            if item <= self.stack[l - 1] {
                self.stack.push(item); //item moved here
                self.min.push(item); // so I can't use it again here
            } else {
                self.stack.push(item);
            }
        }
    }
}

The problem is item moves with the first Vec<T>::push so I can't use it immediately at the second call of push(). I thought about making a variable let a = &item and use it in the second call, but push requires "T" and not "&T".

Also, if I try to do a=self.stack[l-1], it's an error because the T type doesn't have the Copy/Clone traits.

LATER EDIT: I also need to print the last value from the min Vector. But it doesn't have the std::fmt::Display , and I don't think it can be impl!? Any ideas?

How would you approach this?

Assuming that you do need the two vectors of T, there's not much you can do here. A thing can't be in two places at the same time. Either have one (or both) of the vectors store &T (at this point you'll have to deal with lifetimes) or additionally constrain T to Clone or Copy. — Sergio Tulentsev
Buy how do I proceed to create the Clone/Copy traits for the <T> type? — thebalkandude
It is simply impossible to implement given these constraints, which suggests this is an XY problem. Back up a bit: what are you trying to make? — trentcl

Sören Sören · Accepted Answer · 2021-03-23T22:01:13

Assuming you can change the inner values of the struct StackMin, but not the trait requirements, you could do something like this:

struct MinStack<T: std::cmp::Ord> {
    // T is the data you want to store
    // and usize points to the smallest T
    inner: Vec<(T, usize)>
}

impl<T: std::cmp::Ord> MinStack<T> {
    fn push(&mut self, val: T) {
        let min_index = self.inner.last()
            // get last min value and its index
            .map(|(_, index)| (&self.inner[*index].0, index))
            // check if it is smaller then the current value
            .and_then(|(prev_min, min_index)| 
                (prev_min < &val).then(|| *min_index)
            )
            // if not smaller or does not exist
            // set it to the current index
            .unwrap_or(self.inner.len());

        self.inner.push((val, min_index));
    }
}

Here is a full implementation of the MinStack challenge Rust Playground.
Let me know if i should clarify something in the above code.

Docs for the used methods:

impl push(self , item : T) for a struct with 2 Vecs<T>

1 Answers