各種集合演算について
各種集合演算の結果は iterator で返ってくる。必要に応じて Vec や HashSet などに変換する。
以下の演算が用意されている
Python みたいに s1 - s2 みたいには書けない。
use std::collections::BTreeSet;
use std::ops::Bound::{Excluded, Unbounded};
let v = vec![0, 1, 2, 3, 4, 5];
let set: BTreeSet<usize> = v.into_iter().collect();
// 全体のmin, max
assert_eq!(*set.iter().min().unwrap(), 0);
assert_eq!(*set.iter().max().unwrap(), 5);
// set.iter().copied().min().unwrap() と書いてしまうと
// 普通の Iterator の min が呼ばれて O(n) の計算量になってしまう。
// 範囲指定をした上でのmin, max
let x = 2;
assert_eq!(*set.range(x..).min().unwrap(), 2); // lower_bound相当
assert_eq!(*set.range((Excluded(x), Unbounded)).min().unwrap(), 3); // upper_bound相当
assert_eq!(*set.range(..x).max().unwrap(), 1); // xより小さい要素の中で最大の要素
assert_eq!(*set.range(2..).nth(2).unwrap(), 4);
assert_eq!(*set.range(..=3).rev().nth(2).unwrap(), 1);
min は next、max は next_back でもOK。
内部的には、min や max は next, next_back で実装されている。
next, next_back と書いたほうが計算量がO(1) か O(log n) であることがわかりやすくて良い。
min, max だと O(n) かかりそうな感じもする。事故って、普通の Iterator の min を呼んでしまったら O(n) になってしまうという罠もある。