How do I form a slice from a HashSet?

Question

A struct is defined as:

struct Node {
    set: HashSet<usize>,
    // other fields omitted
}

I have to implement a function for a trait (compatibility issues) which needs to return all elements in the set as a slice.

I am aware of something like the following function won't work:

impl Node {
    pub fn set_slice(&self) -> &[usize] {
        let elems: Vec<_> = self.set.iter().cloned().collect();
        &elems[..]
    }
}

The problem is:

error[E0597]: `elems` does not live long enough
  --> src/main.rs:11:10
   |
11 |         &elems[..]
   |          ^^^^^ borrowed value does not live long enough
12 |     }
   |     - borrowed value only lives until here
   |
note: borrowed value must be valid for the anonymous lifetime #1 defined on the method body at 9:5...
  --> src/main.rs:9:5
   |
9  | /     pub fn set_slice(&self) -> &[usize] {
10 | |         let elems: Vec<_> = self.set.iter().cloned().collect();
11 | |         &elems[..]
12 | |     }
   | |_____^

I know this requirement may sound strange. Despite why I have to do this, is there any 'good' way to achieve this?

If it is possible, I want keep the HashSet container for a O(1) lookup, and I don't want to introduce new struct members in order to save memory.

There is likely an XY problem here. Consider showing more context around the use of that trait. Also keep in mind that [owning containers such as `Vec` can coerce to slices](https://stackoverflow.com/q/40006219/1233251). — E_net4, May 08 '18 at 14:58

Shepmaster · Accepted Answer · 2019-04-27T13:28:42.953

7

No, your requirements are 100% completely impossible in safe Rust.

A HashSet / HashMap do not have a contiguous collection of data, thus there's no way to get a slice from them.

If you can change things, then you have options.

You can "render a view" of the HashSet if you can store a Vec and the method is &mut self:

struct Node {
    set: HashSet<usize>,
    view: Vec<usize>,
    // other fields omitted
}

impl Node {
    pub fn set_slice(&mut self) -> &[usize] {
        self.view.clear();
        self.view.extend(self.set.iter().cloned());
        &self.view
    }
}

You could return a Cow which would be either borrowed or owned:

use std::borrow::Cow;

impl Node {
    pub fn set_slice(&self) -> Cow<[usize]> {
        self.set.iter().cloned().collect::<Vec<_>>().into()
    }
}

You could return an iterator over the values:

impl Node {
    pub fn set_slice<'a>(&'a self) -> impl Iterator<Item = &'a usize> + 'a {
        self.set.iter()
    }
}

There's possibly a crate that uses a tightly-packed Vec as its backing storage, which could then be exposed as a slice.

edited Apr 27 '19 at 13:28

answered May 08 '18 at 14:42

Shepmaster

388,571
95
1,107
1,366

Thanks for your answer. Will adding lifetime constraints to the temporary variable `elems` work? – Allen Lee May 08 '18 at 14:47
2

@Yang no. I mean it when I say impossible. If you can't change the `HashSet` or the trait and won't add fields, there's no solution. – Shepmaster May 08 '18 at 14:49
I am trying to use `Cow`, once I have `let cow = Cow::from(&slice[..])` or `let cow = Cow::from(vec) `, how can I get back `&slice[..]`. I have used `cow.borrow()`, but error `type annotations required: cannot resolve 'std::borrow::Cow<'_, [u32]>: std::borrow::Borrow<_>'` shown up – Allen Lee May 08 '18 at 16:57
@Yang `&cow[..]` ? – Shepmaster May 08 '18 at 17:28

Alex Koz. · Answer 2 · 2018-05-16T15:52:34.457

That is impossible in simple (basic) ways.

That's possible with Box, mut static but I recommend to modify your trait and return something like in following example:

You can use AsRef<[T]> instead of &[usize] in your trait. Or simply return an iterator.

struct Node {
    set: HashSet<usize>,
}

trait SetSlice {
    type Slice: AsRef<[usize]>;
    fn get_slice_cloned(&self) -> Self::Slice;
}

impl SetSlice for Node {
    type Slice = Vec<usize>;
    fn get_slice_cloned(&self) -> Self::Slice { self.set.iter().cloned().collect() }
}

// there we use auto-impl of Iterator trait
// and return the iter.
// NOTE: we cannot use auto-impl in trait methods.
impl Node {
    fn get_neat_iter(&self) -> impl Iterator<Item = &usize> { self.set.iter() }
}

fn need_slice(slice: &[usize]) {}

fn main() {
    let n = Node { set: Default::default(), };

    // as_ref
    let all = n.get_slice_cloned();
    need_slice(all.as_ref());

    // iter-way
    let all: Vec<_> = n.get_neat_iter().cloned().collect();
    need_slice(&all);
}

This is only two ways from many.

How do I form a slice from a HashSet?

2 Answers2

Linked

Related