How to repeatedly loop over subsets of a collection determined by an attribute of the items?

Question

I have a collection of objects owned by a struct Manager. These objects have optional attributes such as printable or dynamic. I want to repeatedly loop over all printable objects to print them and loop over all dynamic objects to update them. My rather naive implementation is this:

struct Object {
    state: i32,
    printable: Option<i32>,
    dynamic: Option<i32>
}

struct Manager {
    objects: Vec<Object>,
}

impl Manager {
    fn print_objects(&self) {
        for o in &self.objects {
            if let Some(i) = o.printable {
                print!("{}: {}, ", i, o.state);
            }
        }
        println!();
    }

    fn update_objects(&mut self) {
        for o in &mut self.objects {
            if let Some(i) = o.dynamic {
                o.state += i;
            }
        }
    }
}

fn main() {
    let mut mgr = Manager{objects: Vec::new()};

    mgr.objects.push(Object{state: 0, printable: Some(10), dynamic: None});
    mgr.objects.push(Object{state: 0, printable: None, dynamic: Some(1)});
    mgr.objects.push(Object{state: 0, printable: Some(20), dynamic: Some(2)});

    for _ in 0..3 {
        mgr.update_objects();
        mgr.print_objects();
    }
}

This solution has the drawback that it needs to loop over all objects and check each for the appropriate flag. Assuming that only a small fraction of the objects are dynamic, I'd rather avoid looping over all of them. In C++ I would simply create a list of pointers to the dynamic objects and loop over that. Attempting this:

struct Manager<'a> {
    objects: Vec<Object>,     // objects owned by Manager
    dynamic: Vec<&'a Object>  // references to dynamic objects
}

impl<'a> Manager<'a> { /* ... */ }

fn main() {
    let mut mgr = Manager{objects: Vec::new(), dynamic: Vec::new()};

    mgr.objects.push(Object{state: 0, printable: Some(10), dynamic: None});
    mgr.objects.push(Object{state: 0, printable: None, dynamic: Some(1)});
    mgr.objects.push(Object{state: 0, printable: Some(20), dynamic: Some(2)});

    mgr.dynamic.push(&mgr.objects[1]);
    mgr.dynamic.push(&mgr.objects[2]);

    for _ in 0..3 {
        mgr.update_objects();  // can't mutably borrow because of reference held by mgr.dynamic
        mgr.print_objects();
    }
}

It seems to be a very basic problem that I can't keep a reference to elements in Manager.objects and at the same time borrow it mutably. Thus, I've started to doubt my whole approach. Is there an idiomatic way to implement such a pattern in Rust?

I believe that keeping references to objects prevents me from mutating them, but I'd be happy to learn a way around that. A future goal would be to change printable or dynamic during update, but I'd like to figure out the basic stuff before tackling that step.

You can create a vector of indexes into the first vector, but I don't know how idiomatic that is - it seems a bit like cheating to get around the safety checks. And it will cause issues e.g. if the order of items in the source vector changes. — interjay, Aug 27 '17 at 09:03
@interjay it's not *cheating*, it's just another level of indirection, but one that can checked for safety at runtime (via bounds checks). References are checked at compile time. If it were allowed, they could be invalidated for the reasons you mention. — Shepmaster, Aug 27 '17 at 14:47
@Shepmaster It's safe in that it won't cause invalid memory access errors. But it can access the wrong element if you previously deleted an element in the vector, which I would consider unsafe (to a lesser degree) even if it isn't unsafe in Rust terminology. — interjay, Aug 27 '17 at 15:01
@interjay we like to be *very* precise about the "unsafe" word, so I'd strongly advocate for just using the more conventional "incorrect". Besides, if you tell someone their program does "the wrong thing", it's probably much easier to understand than "it does an unsafe thing". — Shepmaster, Aug 27 '17 at 15:05
@Shepmaster OK, I'll try not to use the term "unsafe" except for what the rust compiler considers unsafe. But "incorrect" or "wrong" are not really valid alternatives: There is a potential for shooting yourself in the foot but you'll be fine if you're careful. And my point above was that this potential is a spectrum and not a dichotomy, even in Rust: Unsafe raw pointers are more dangerous than "safe" vector indexes, and vector indexes are more dangerous than `Rc`. — interjay, Aug 27 '17 at 15:47
@interjay also, FWIW, indices are how [petgraph](https://crates.io/crates/petgraph) works, so it's certainly a well-respected solution. — Shepmaster, Aug 27 '17 at 17:21
@interjay indexing does not sound like a bad idea at all. I guess it comes at a higher runtime cost when iterating, but that's not necessarily a show stopper. — MB-F, Aug 27 '17 at 17:26

Shepmaster · Accepted Answer · 2017-08-27T18:08:39.840

struct Manager<'a> {
    objects: Vec<Object>,     // objects owned by Manager
    dynamic: Vec<&'a Object>  // references to dynamic objects
}

This does not work and has been thoroughly discussed in Why can't I store a value and a reference to that value in the same struct?.

One solution is to have multiple owners of a single value, known as shared ownership. One implementation is Rc.

You also want to have mutability that is not tied to the scope of the program but instead to the runtime characteristics, which can be enabled with interior mutability. One implementation of is RefCell:

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

#[derive(Debug)]
struct Object {
    state: i32,
    printable: Option<i32>,
    dynamic: Option<i32>,
}

#[derive(Debug, Default)]
struct Manager {
    objects: Vec<Rc<RefCell<Object>>>,
    printable: Vec<Rc<RefCell<Object>>>,
    dynamic: Vec<Rc<RefCell<Object>>>,
}

impl Manager {
    fn add(&mut self, state: i32, printable: Option<i32>, dynamic: Option<i32>) {
        let obj = Object { state, printable, dynamic };
        let obj = Rc::new(RefCell::new(obj));

        self.objects.push(obj.clone());

        if printable.is_some() {
            self.printable.push(obj.clone())
        }

        if dynamic.is_some() {
            self.dynamic.push(obj.clone())
        }
    }

    fn print_objects(&self) {
        for o in &self.printable {
            let o = o.borrow();
            if let Some(i) = o.printable {
                print!("{}: {}, ", i, o.state);
            }
        }
        println!();
    }

    fn update_objects(&mut self) {
        for o in &self.dynamic {
            let mut o = o.borrow_mut();
            if let Some(i) = o.dynamic {
                o.state += i;
            }
        }
    }
}

fn main() {
    let mut mgr = Manager::default();

    mgr.add(0, Some(10), None);
    mgr.add(0, None, Some(1));
    mgr.add(0, Some(20), Some(2));

    for _ in 0..3 {
        mgr.update_objects();
        mgr.print_objects();
    }
}

You still have all the inherent problems of transitioning an item from one group to another.

Seems pretty obvious in retrospect. Amazing how learning rust makes me feel all inept again... anyway, thank's a lot! — MB-F, Aug 27 '17 at 17:30

How to repeatedly loop over subsets of a collection determined by an attribute of the items?

1 Answers1