Sorted Iter

关于

该包为编译时已知排序的所有标准库迭代器提供集合和关系操作。

集合操作

use sorted_iter::SortedIterator;

let primes = btreeset! { 2, 3, 5, 7, 11, 13u64 }.into_iter();
let fibs = btreeset! { 1, 2, 3, 5, 8, 13u64 }.into_iter();
let fib_primes = primes.intersection(fibs);

可以有效地在排序迭代器上定义集合操作。排序迭代器在标准库中非常常见。例如，BTreeSet 的元素或 BTreeMap 的键都保证按元素顺序排序，如可迭代的范围 0..100。

还有一些迭代器操作可以保持排序顺序。例如，如果迭代器已排序，则 take、take_while 等操作也将产生一个排序迭代器。

由于 Rust 中迭代器的完整类型通常是可见的，因此可以在类型级别上编码这些规则。这就是该包所做的事情。

有关可用的集合操作，请参阅 SortedIterator。有关标准库中的排序迭代器，请参阅 SortedByItem 标记特质的实例。

关系操作

use sorted_iter::SortedPairIterator;

let cities = btreemap! {
  1 => "New York",
  2 => "Tokyo",
  3u8 => "Berlin"
}.into_iter();
let countries = btreemap! {
  1 => "USA",
  2 => "Japan",
  3u8 => "Germany"
}.into_iter();
let cities_and_countries = cities.join(countries);

根据第一个元素/键排序的有序对迭代器在标准库和其他地方也非常常见。例如，BTreeMap 的元素保证按照键顺序排序。

对于保持排序顺序的规则与排序迭代器相同，除了有一些额外的操作可以保持排序顺序。例如，仅对值进行操作的任何操作，如 map 或 filter_map，都保证保持排序顺序。

在有序对操作上可以定义的操作是关系代数/SQL中已知的关系操作，即连接（join）、左连接（left_join）、右连接（right_join）和外连接（outer_join）。

有关可用的关系操作，请参阅SortedPairIterator。有关标准库中的有序迭代器，请参阅SortedByKey标记特质的具体实例。

允许保留顺序的转换

use sorted_iter::*;

let odd = (1..31).step_by(2);
let multiples_of_3 = (3..30).step_by(3);
let either = odd.union(multiples_of_3);

可能改变顺序的转换将失去有序属性

use sorted_iter::*;

// we have no idea what map does to the order. could be anything!
let a = (1..31).map(|x| -x);
let b = (3..30).step_by(3);
let either = a.union(b); // does not compile!

假设排序顺序

对于大多数标准库迭代器，这个库已经提供了实例。但偶尔会有来自第三方库的迭代器，您知道它是正确排序的。

对于这种情况，有一个逃生门

// the assume_ extensions have to be implicitly imported
use sorted_iter::*;
use sorted_iter::assume::*;
let odd = vec![1,3,5,7u8].into_iter().assume_sorted_by_item();
let even = vec![2,4,6,8u8].into_iter().assume_sorted_by_item();
let all = odd.union(even);

let cities = vec![(1u8, "New York")].into_iter().assume_sorted_by_key();
let countries = vec![(1u8, "USA")].into_iter().assume_sorted_by_key();
let cities_and_countries = cities.join(countries);

标记自己的迭代器

如果您有一个库，并想标记一些迭代器为有序，这可以通过实现适当的标记特质SortedByItem或SortedByKey来实现。

// marker traits are not at top level, since usually you don't need them
use sorted_iter::sorted_iterator::SortedByItem;
use sorted_iter::sorted_pair_iterator::SortedByKey;

pub struct MySortedIter<T> { whatever: T }
pub struct MySortedPairIter<K, V> { whatever: (K, V) }

impl<T> SortedByItem for MySortedIter<T> {}
impl<K, V> SortedByKey for MySortedPairIter<K, V> {}

通过重新导出扩展特质，您将为使用您的库的人提供无缝的体验。

extern crate sorted_iter;
pub use sorted_iter::{SortedIterator, SortedPairIterator};

测试

测试使用神奇的quickcheck crate进行，通过与BTreeSet和BTreeMap上定义的操作进行比较。