Rust有序迭代器扩展库sorted-iter使用指南

sorted-iter是一个Rust库，提供了一系列高效排序迭代器适配器和工具函数，用于处理已排序或需要排序的迭代器。

主要特性

• 提供已排序迭代器的适配器
• 实现高效的合并、交集、差集等集合操作
• 保持排序状态的同时进行各种操作
• 性能优于先收集再排序的传统方法

安装

在Cargo.toml中添加依赖：

[dependencies]
sorted-iter = "0.4.0"

基本使用方法

1. 创建排序迭代器

use sorted_iter::sorted_iterator::SortedByKey;

let a = [1, 3, 5];
let b = [2, 4, 6];

let iter_a = a.iter().sorted();
let iter_b = b.iter().sorted();

2. 合并两个排序迭代器

use sorted_iter::sorted_iterator::SortedIterator;
use sorted_iter::assume::AssumeSortedByKeyExt;

let a = [1, 3, 5];
let b = [2, 4, 6];

let merged = a.iter().assume_sorted_by_key().merge(b.iter().assume_sorted_by_key());
assert_eq!(merged.collect::<Vec<_>>(), vec![&1, &2, &3, &4, &5, &6]);

3. 集合操作

use sorted_iter::assume::AssumeSortedByKeyExt;

let a = [1, 2, 3, 4].iter().assume_sorted_by_key();
let b = [3, 4, 5, 6].iter().assume_sorted_by_key();

// 交集
let intersection = a.intersection(b);
assert_eq!(intersection.collect::<Vec<_>>(), vec![&3, &4]);

// 并集
let union = a.union(b);
assert_eq!(union.collect::<Vec<_>>(), vec![&1, &2, &3, &3, &4, &4, &5, &6]);

// 差集
let difference = a.difference(b);
assert_eq!(difference.collect::<Vec<_>>(), vec![&1, &2]);

4. 使用自定义排序键

use sorted_iter::assume::AssumeSortedByKeyExt;

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

let people = [
    Person { name: "Alice".into(), age: 30 },
    Person { name: "Bob".into(), age: 25 },
    Person { name: "Charlie".into(), age: 35 },
];

// 按年龄排序
let sorted_by_age = people.iter().assume_sorted_by_key(|p| p.age);

for person in sorted_by_age {
    println!("{}: {}", person.name, person.age);
}
// 输出:
// Bob: 25
// Alice: 30
// Charlie: 35

高级用法

1. 链式操作

use sorted_iter::assume::AssumeSortedByKeyExt;

let a = [1, 3, 5, 7].iter().assume_sorted_by_key();
let b = [2, 4, 6, 8].iter().assume_sorted_by_key();
let c = [3, 6, 9].iter().assume_sorted_by_key();

let result = a.merge(b)
    .intersection(c)
    .filter(|&&x| x % 2 == 0)
    .collect::<Vec<_>>();

assert_eq!(result, vec![&6]);

2. 处理大型数据集

use sorted_iter::sorted_iterator::SortedByKey;
use std::iter::repeat_with;
use rand::Rng;

// 生成大型随机数据集
let mut rng = rand::thread_rng();
let data: Vec<u32> = repeat_with(|| rng.gen_range(0..1000))
    .take(1_000_000)
    .collect();

// 使用sorted-iter处理而不需要先排序整个向量
let result = data.iter()
    .sorted()
    .take(100)  // 只需要前100个元素
    .collect::<Vec<_>>();

assert_eq!(result.len(), 100);

性能提示

1. 对于已经排序的数据，使用assume_sorted_by_key()比sorted()更高效
2. 链式操作会保持排序状态，避免中间收集和重新排序
3. 对于大型数据集，惰性求值可以显著减少内存使用

sorted-iter特别适合处理需要排序的大型数据集或需要高效集合操作的场景，能够在不收集所有数据到内存的情况下进行处理。

完整示例代码

use sorted_iter::{assume::AssumeSortedByKeyExt, sorted_iterator::SortedIterator};
use rand::Rng;

fn main() {
    // 示例1: 创建排序迭代器
    let nums = [3, 1, 4, 1, 5, 9];
    let sorted_nums = nums.iter().sorted();
    println!("排序后的数字: {:?}", sorted_nums.collect::<Vec<_>>());
    
    // 示例2: 合并两个已排序的迭代器
    let a = [1, 3, 5].iter().assume_sorted_by_key();
    let b = [2, 4, 6].iter().assume_sorted_by_key();
    let merged = a.merge(b);
    println!("合并结果: {:?}", merged.collect::<Vec<_>>());
    
    // 示例3: 集合操作
    let set1 = [1, 2, 3, 4].iter().assume_sorted_by_key();
    let set2 = [3, 4, 5, 6].iter().assume_sorted_by_key();
    
    println!("交集: {:?}", set1.intersection(set2.clone()).collect::<Vec<_>>());
    println!("并集: {:?}", set1.union(set2.clone()).collect::<Vec<_>>());
    println!("差集: {:?}", set1.difference(set2.clone()).collect::<Vec<_>>());
    
    // 示例4: 自定义排序键
    #[derive(Debug)]
    struct Product {
        id: u32,
        price: f64,
    }
    
    let products = [
        Product { id: 1, price: 99.9 },
        Product { id: 2, price: 49.9 },
        Product { id: 3, price: 199.9 },
    ];
    
    let by_price = products.iter().assume_sorted_by_key(|p| p.price);
    println!("按价格排序的产品:");
    for p in by_price {
        println!("ID: {}, 价格: {}", p.id, p.price);
    }
    
    // 示例5: 链式操作
    let nums1 = [1, 3, 5, 7].iter().assume_sorted_by_key();
    let nums2 = [2, 4, 6, 8].iter().assume_sorted_by_key();
    let nums3 = [3, 6, 9].iter().assume_sorted_by_key();
    
    let result = nums1.merge(nums2)
        .intersection(nums3)
        .filter(|&&x| x % 2 == 0)
        .collect::<Vec<_>>();
    println!("链式操作结果: {:?}", result);
    
    // 示例6: 处理大型数据集
    let mut rng = rand::thread_rng();
    let large_data: Vec<u32> = (0..10_000).map(|_| rng.gen_range(0..1000)).collect();
    
    let top10 = large_data.iter()
        .sorted()
        .take(10)
        .collect::<Vec<_>>();
    println!("大型数据集中的前10个最小元素: {:?}", top10);
}