如何对迭代器进行排序而不将其全部放入向量中？

我正在构建一个类似于生成器的通用接口，它将数据从一个流传输到另一个流，最终执行以下操作：

file |> toCsv |> filter |> sort |> filter...

我知道如何对向量/切片进行排序，但是如何从传入流/迭代器中进行排序而不将其全部放入向量中？

stream.iter().collect_sorted()

我需要融合向量、树、文件、数据库等，所以有时我不知道传入的数据有多大，而不消耗它们。

我不反对存储结果。问题在于排序与切片/向量相关。我需要能够做到：

datasource |> Algo.sort |> next...

代替：

let data = datasource |> into_vec
data.sort()
data |> next...

不同的用例存在不同的排序算法，因此最终我希望对手头的数据应用最好的算法：

datasource |> Algo.MergeSort |> next...
datasource |> Algo.BubbleSort |> next...

对一组值进行排序实际上是不可能的without拥有所有数据。例如，如果迭代器有 10 亿个实例1随后是一个0，直到你到达那里之前，你根本不知道零需要先走。您可能希望重新熟悉以下概念在线和离线算法 https://en.wikipedia.org/wiki/Online_algorithm.

无需将其全部放入向量中

这很简单：不要使用向量，使用任何实现的类型FromIterator https://doc.rust-lang.org/std/iter/trait.FromIterator.html。例如，您可以收集到BinaryHeap:

use std::{collections::BinaryHeap, iter};

fn main() {
    let a_lot_of_numbers = iter::repeat(1).take(100).chain(iter::once(0));
    let data: BinaryHeap<_> = a_lot_of_numbers.collect();
}

这是否是一个好主意完全取决于您的情况。

如果你只是不想see向量或只是希望保留链接，那么我建议使用Itertools::sorted https://docs.rs/itertools/0.8.0/itertools/trait.Itertools.html#method.sorted。这使用了一个Vec在内部，这意味着所有数据都存储在内存中在返回第一个值之前：

use itertools::Itertools; // 0.8.0
use std::iter;

fn main() {
    let a_lot_of_numbers = iter::repeat(1).take(100).chain(iter::once(0));

    for v in a_lot_of_numbers.sorted() {
        println!("{}", v);
    }
}

这是数据库的常见问题，加载所有数据然后排序是不明智的

数据库是极其复杂的软件，需要经过多年的努力并仔细权衡权衡。您不会在包管理器中找到该级别的算法。即使可以，数据库也并不总是正确，需要熟练的程序员调整查询以提高性能。关于 Postgres 排序你需要知道的一切 https://madusudanan.com/blog/all-you-need-to-know-about-sorting-in-postgres/涵盖了 Postgres 的一系列功能。

理论上应该可以编写一个迭代器适配器，将所有数据写入磁盘，在那里执行排序，然后从磁盘重新读取数据。这就是所谓的外部排序 https://en.wikipedia.org/wiki/External_sorting.