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

1

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 ?

2

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

5 Likes
3

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
4

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.

1 Like
5

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
6

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

3 Likes
7

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
8

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.