# Add .dedup() for Iterator **URL:** \ **Category:** libs\ **Created:** [February 9, 2015, 12:30am UTC](https://internals.rust-lang.org/t/add-dedup-for-iterator/1567 "2015-02-09T00:30:21Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![lambda-fairy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/lambda-fairy/32/2045_2.png) [@lambda-fairy](https://internals.rust-lang.org/u/lambda-fairy)\ **Post date:** [February 9, 2015, 12:30am UTC](https://internals.rust-lang.org/t/add-dedup-for-iterator/1567/1 "2015-02-09T00:30:21Z")
Currently, the [`.dedup()`](http://doc.rust-lang.org/collections/vec/struct.Vec.html#method.dedup) method only exists on `Vec`. But it can be implemented on any `Iterator` as well: [https://gist.github.com/lfairy/0f952345ddf07c26eabe](https://gist.github.com/lfairy/0f952345ddf07c26eabe) Much of the complexity in the implementation boils down to one issue: how do we yield values as early as possible? The naive algorithm consumes a whole run before yielding, which is elegant but falls flat on infinite sequences (e.g. `repeat(1)`). It is also suboptimal when the underlying `.next()` is slow, say when we’re streaming data from the network or from disk. Why can’t we yield the first element straight away? Because then we’ll have no element to compare with on the next iteration, since the previous element has already been moved out. There are a few ways to approach this problem: 1. `.clone()` the value before we return it. This is nice and simple but requires a `Clone` bound and an extra copy. 2. Use [`Peekable`](http://doc.rust-lang.org/std/iter/struct.Peekable.html) as a one-element buffer. We `.peek()` at the next item before returning the current one, effectively doing the comparison one step in advance. This has the advantage of not requiring `Clone`, but the drawback of consuming an extra element. 3. Return a reference to the element, rather than moving it out. This would be the ideal solution, but requires a `StreamingIterator` interface. My implementation uses solution (2). It’s unlikely we’ll get the trait needed for (3), and copying is often more expensive than consuming an extra element. I haven’t run benchmarks yet, but the `Vec` version should be faster as it works in-place. We could write the in-place `.dedup()` in terms of the iterator one – it’s safe because we yield fewer values than we consume – but I’m not sure if that’s worth the trouble. So, any questions, comments? In particular, is an iterator `.dedup()` worth adding to the standard library? ---
**Author:** ![aidancully](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/aidancully/32/5532_2.png) [@aidancully](https://internals.rust-lang.org/u/aidancully)\ **Post date:** [February 9, 2015, 2:27am UTC](https://internals.rust-lang.org/t/add-dedup-for-iterator/1567/2 "2015-02-09T02:27:10Z")
I like the design, but is there a need for it in the standard library, rather than just making it a [crates.io](http://crates.io) repository? ---
**Author:** ![lambda-fairy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/lambda-fairy/32/2045_2.png) [@lambda-fairy](https://internals.rust-lang.org/u/lambda-fairy)\ **Post date:** [February 9, 2015, 2:44am UTC](https://internals.rust-lang.org/t/add-dedup-for-iterator/1567/3 "2015-02-09T02:44:47Z")
I just found it strange that `.dedup()` was implemented on `Vec`, but not `Iterator`. I guess given that `.concat()` and `.connect()` aren’t on `Iterator` either, there’s precedent for not adding iterator versions when they’re less efficient than the specialized ones. And since there are multiple solutions to this problem, all with different tradeoffs, perhaps it’s better to iterate (hehe) in a separate library. (It seems the `itertools` crate already has a [`Dedup` implementation](http://bluss.github.io/rust-itertools/doc/itertools/struct.Dedup.html), which uses the naive solution.) ---
**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\ **Post date:** [February 9, 2015, 10:01am UTC](https://internals.rust-lang.org/t/add-dedup-for-iterator/1567/4 "2015-02-09T10:01:46Z")
itertools’ dedup uses the solution you describe as (2). Dedup itself is easy to add to the iterator, but I understand why it’s on the vec – it makes much more sense to use it together with sort. ---
**Author:** ![lambda-fairy](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/lambda-fairy/32/2045_2.png) [@lambda-fairy](https://internals.rust-lang.org/u/lambda-fairy)\ **Post date:** [February 9, 2015, 9:50pm UTC](https://internals.rust-lang.org/t/add-dedup-for-iterator/1567/5 "2015-02-09T21:50:18Z")
> [@blake](#): > > itertools' dedup uses the solution you describe as (2) Not quite. Consider the code: ```rust repeat(1).dedup().next() ``` My implementation returns `Some(1)` straight away, whereas itertools' loops forever. This is because itertools' dedup consumes a whole run of equal values before it yields, whereas my implementation delays consuming the remainder until the next iteration. It's subtle I admit, but since infinite iterators are a valid use case I think it's important to handle them properly. I'll be happy to submit a patch for itertools if you're interested. > [@blake](#): > > Dedup itself is easy to add to the iterator, but I understand why it's on the vec -- it makes much more sense to use it together with sort. Agreed. ---
**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\ **Post date:** [February 9, 2015, 11:59pm UTC](https://internals.rust-lang.org/t/add-dedup-for-iterator/1567/6 "2015-02-09T23:59:18Z")
ok, good point, that example makes it clear. If you want to patch it you are very welcome. ---
**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\ **Post date:** [March 25, 2019, 8:23am UTC](https://internals.rust-lang.org/t/add-dedup-for-iterator/1567/7 "2019-03-25T08:23:53Z")
Closed on March 25, 2019, 8:23am UTC This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.