4

I have a slice of items and a slice of indices into the first slice, essentially giving me a sub-group of items that I want to modify. To iterate over the items and manipulate them I can create the following helper function.

fn process_things_by_index_loop<T>(things: &mut [T], indices: &[usize], f: &dyn Fn(&mut T)) {
    for &ix in indices {
        let t = &mut things[ix];
        f(t);
    }
}

This works fine, but I would actually just like to get an iterator over the items so I can apply, e.g., a filter to them before further processing.

It looks like this could just be a mapping of indices to items like so:

fn iterate_thigns<'a, T>(
    things: &'a mut [T],
    indices: &'a [usize],
) -> impl Iterator<Item = &'a mut T> {
    indices.iter().map(|&ix| -> &mut T { &mut things[ix] })
}

This can't work of course, since I could have the same index twice in the indices slice and when collecting the iterator I would create two mutable references to the same item. So this gives appropriately a life-time error:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
 --> src\main.rs:4:47
  |
4 |     indices.iter().map(|&ix|->  &mut T { &mut things[ix]})
  |                                               ^^^^^^^^^^
  |

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
 --> src\main.rs:4:47
  |
4 |     indices.iter().map(|&ix|->  &mut T { &mut things[ix]})
  |                                               ^^^^^^^^^^
  |
note: first, the lifetime cannot outlive the lifetime '_ as defined on the body at 4:24...
 --> src\main.rs:4:24
  |
4 |     indices.iter().map(|&ix|->  &mut T { &mut things[ix]})
  |                        ^^^^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
 --> src\main.rs:4:47
  |
4 |     indices.iter().map(|&ix|->  &mut T { &mut things[ix]})
  |                                               ^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the function body at 3:19...
 --> src\main.rs:3:19
  |
3 | fn iterate_thigns<'a, T>(things: &'a mut [T], indices: &'a [usize]) -> impl Iterator<Item=&'a mut T>{
  |                   ^^
  = note: ...so that the types are compatible:
          expected &mut T
             found &'a mut T

This also means the return type probably can't be a simple Iterator at all.

This issues seems also related to this blog post from 2013 on "Iterators yielding mutable references", which states that no standard solutions for this pattern exist yet.

There is also a related question asking about mutable multi threaded access to the content of a vector, but I am really interested in a single threaded, iterator-like solution, which might even allow indices to repeat.

So, is there something that enables an iterator-like interface for sequential iteration of the items indicated by the indices?

Michael Mauderer
  • 3,777
  • 1
  • 22
  • 49
  • I would take a set of indices instead of a slice (to guarantee uniqueness) and use unsafe code. – Boiethios Aug 14 '19 at 10:08
  • I just added a note about a blog post that also mentions an unsafe solution. For my specific use case going through a set might actually work quite well. – Michael Mauderer Aug 14 '19 at 10:31
  • Or you can keep the slice and have a policy about the duplicates: either return an error or ignore the other times an index appears. – Boiethios Aug 14 '19 at 11:30
  • 1
    I guess with a set you could even just reverse iteration (iterate the things and check whether the item's index is in the set) and do it all safely. – Michael Mauderer Aug 14 '19 at 11:53
  • ...but that is a lot slower. Quick benching shows a slowdown of about 50x compared to the loop solution. – Michael Mauderer Aug 14 '19 at 14:02
  • How is that possible? Do you have a code example? – Boiethios Aug 14 '19 at 14:05
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/197942/discussion-between-michael-mauderer-and-french-boiethios). – Michael Mauderer Aug 14 '19 at 14:06
  • It looks like your question might be answered by the answers of [Simultaneous mutable access to arbitrary indices of a large vector that are guaranteed to be disjoint](https://stackoverflow.com/q/55939552/155423). If not, please **[edit]** your question to explain the differences. Otherwise, we can mark this question as already answered. – Shepmaster Aug 14 '19 at 14:10
  • @Shepmaster I have addressed the difference in the desired outcome in the question. – Michael Mauderer Aug 14 '19 at 14:20
  • The question is about multithreaded, yes, but none of the answers are. Please review the **answers** and see if they answer your question. – Shepmaster Aug 14 '19 at 14:28
  • *which might even allow indices to repeat* — absolutely 100% not possible and would lead to memory unsafety. [How can I create my own data structure with an iterator that returns mutable references?](https://stackoverflow.com/q/25730586/155423). See also [How do I write an iterator that returns references to itself?](https://stackoverflow.com/q/30422177/155423) – Shepmaster Aug 14 '19 at 14:28
  • I think what I had in mind was a somewhat restricted iterator, that, e.g., only allows chaining of `for_each` and not "collect", thus avoiding the issue of multiple concurrent mutable references. But I guess then the answer is that something like that just doesn't exist and needs workarounds like proposed in those answer (and my question) – Michael Mauderer Aug 14 '19 at 14:39
  • Actually this is what I was looking for: https://stackoverflow.com/a/30422716/1175813 "Streaming iterators" – Michael Mauderer Aug 14 '19 at 14:48
  • So you'd be happy marking this as a duplicate of the streaming iterators Q? – Shepmaster Aug 14 '19 at 14:54
  • Sure, go for it. – Michael Mauderer Aug 14 '19 at 14:55

0 Answers0