[Rust] Vectorをuniqueしたい



# 検証環境
OS: macOS High Sierra 10.13.3
Rust: rustc 1.26.0-nightly (c08480fce 2018-03-23)


# 要素がプリミティブ型の場合
例えば、

```rust
let a = vec![1,2,3,1,2,3];
```

の重複削除したい。
`HashSet` を使えば簡単に実現できそう。

```rust
let uniq: HashSet<i32> = a.into_iter().collect();
println!("{:?}", uniq); // => {2, 3, 1}
```



# 要素がプリミティブな型じゃない場合
例えば、

```rust
struct Person {
    name: String,
    age: u32,
}
```

みたいなやつ
これをHashSetで扱おうとすると、そのままでは出来ない。

https://doc.rust-lang.org/1.24.0/std/collections/struct.HashSet.html

ドキュメントを読んでみると

> As with the HashMap type, a HashSet requires that the elements implement the Eq and Hash traits. 

と書いてある。
つまり、`Eq`トレイトと`Hash`トレイトを実装しろ。と。

> This can frequently be achieved by using #[derive(PartialEq, Eq, Hash)].

とも、ちゃんと書いてある。
つまり、こうすればいいということですかね。
(最初、ここを見ずにそれぞれのトレイトを実装し、あとになって気づいた…)

```rust
#[derive(Debug, PartialEq, Eq, Hash)]
struct Person {
    name: String,
    age: u32,
}
```

※ `Debug` は関係ない

```rust
let people = vec![
    Person{name: "test1".into(), age: 10 },
    Person{name: "test2".into(), age: 20 },
    Person{name: "test3".into(), age: 30 },
    Person{name: "test1".into(), age: 10 },
    Person{name: "test2".into(), age: 10 },
];

let uniq: HashSet<Person> = people.into_iter().collect();
println!("{:?}", uniq); // => {Person { name: "test2", age: 20 }, Person { name: "test2", age: 10 }, Person { name: "test3", age: 30 }, Person { name: "test1", age: 10 }}
```

という感じになる。

# 問題点
1個問題がある。
`into_iter` は move が発生する

```rust
let uniq: HashSet<Person> = people.into_iter().collect();
println!("{:?}", uniq);

println!("{:?}", people);
```

ってやると

```
  --> src/main.rs:44:22
   |
41 |     let uniq: HashSet<Person> = people.into_iter().collect();
   |                                 ------ value moved here
...
44 |     println!("{:?}", people);
   |                      ^^^^^^ value used here after move
   |
   = note: move occurs because `people` has type `std::vec::Vec<Person>`, which does not implement the `Copy` trait
```

コンパイルエラー。

あとからpeopleを使える方法を考えてみた。

まずは、愚直にcloneしてみよう。
PersonのderiveにCloneトレイトを追加する。

```rust
#[derive(Debug, PartialEq, Eq, Hash, Clone)]
struct Person {
    name: String,
    age: u32,
}
```

cloneしてみる

```rust
let uniq: HashSet<Person> = people
    .iter()
    .map(|x| x.clone())
    .collect();
println!("{:?}", uniq);

println!("{:?}", people);
```

コンパイルは通った。

ただ、これだと全部cloneするので無駄な気がする。
で、こうしてみた。

```rust
let uniq: HashSet<Person> = people
    .iter()
    .collect::<HashSet<&Person>>()
    .iter()
    .map(|x| (*x).clone())
    .collect();
```

こうすれば、参照のHashSetにしてからcloneするので、cloneの回数は減るのではないか、と。
(でも、これはこれで、やりたいことの割に複雑で、気持ちよくない)

## ベンチマーク
前者と後者でベンチマークを取ってみた

```rust
#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    #[bench]
    fn all_clone(b: &mut Bencher) {
        let people = vec![
            Person{name: "test1".into(), age: 10 },
            Person{name: "test2".into(), age: 20 },
            Person{name: "test3".into(), age: 30 },
            Person{name: "test1".into(), age: 10 },
            Person{name: "test2".into(), age: 10 },
        ];
        b.iter(||{
            let uniq: HashSet<Person> = people
                .iter()
                .map(|x| x.clone())
                .collect();
        });
    }

    #[bench]
    fn tmp_hashset_clone(b: &mut Bencher) {
        let people = vec![
            Person{name: "test1".into(), age: 10 },
            Person{name: "test2".into(), age: 20 },
            Person{name: "test3".into(), age: 30 },
            Person{name: "test1".into(), age: 10 },
            Person{name: "test2".into(), age: 10 },
        ];
        b.iter(||{
            let uniq: HashSet<Person> = people
                .iter()
                .collect::<HashSet<&Person>>()
                .iter()
                .map(|x| (*x).clone())
                .collect();
        });
    }
}
```

```
test tests::all_clone         ... bench:         565 ns/iter (+/- 15)
test tests::tmp_hashset_clone ... bench:         762 ns/iter (+/- 45)
```

全部cloneしない方が速いという予測はハズレでした。
後者の方が遅い。
なるほど…

# まとめ
- Vec -> HashSetにすれば、重複は除去できる
- 元のVectorの所有権を維持したまま、重複を削除した別の集合を作るスマートな方法はどうするのがいいのだろうか
	- **未解決**