Sorted unique list from Iterator<T: Ord + Hash>?

We have T: Ord + Hash.

Input: I have an Iterator<T>

Output: I want a vec containing in sorted order the elements of the iterator.

I am currently doing something like:

let mut v = it.collect::<HashSet<_>>().iter().collect::<Vec<_>>();
v.sort();
return v;

Question: The above seems a bit hacky. Is there a more elegant approach to this ?

You can skip the HashSet and call v.dedup(); after sorting it

5 Likes

A BTreeSet would also give you order. That might be preferable if there are a lot of duplicates, and you don't want the overhead of storing them before vec sort+dedup.

4 Likes

You can .dedup() the sorted vec to deduplicate elements. If most input elements are unique this can be more performant as it skip the HashSet.

https://doc.rust-lang.org/stable/std/vec/struct.Vec.html#method.dedup

1 Like

If you're open to using external crates, you could do something like this (untested):

use itertools::Itertools;
let v:Vec<_> = it.sorted().dedup().collect();
1 Like

.sorted() constructs a intermediate vector which can't be reused on .collect() due to the .dedupe().

3 Likes

Right; it's less efficient due to the extra allocation & copy. That may be an acceptable price to pay for the simpler code, especially in a prototyping stage.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.