微软博客：常数空间线性时间算法删除目录中除最近10个文件外的所有文件A constant-space linear-time algorithm for deleting all but the 10 most recent files in a directory

假设你有一个包含大量文件的目录，想要删除除最新创建的10个文件之外的所有文件。能否让 FindFirstFile 按日期顺序枚举这些文件？

不行，无法让 FindFirstFile 按日期顺序枚举文件。FindFirstFile 枚举的文件顺序由文件系统驱动决定，例如 FAT 通常按照目录列表中的顺序枚举，这可能与创建时间一致（如果文件是依次添加的），也可能因重命名或删除操作而变得混乱无序。

由于无法控制文件的枚举顺序，你必须自行完成排序。一种简单的方法是读取所有文件条目，按最后修改时间排序，然后保留最新的十个文件，其余删除。这种方法的空间复杂度为 O(n)，运行时间为 O(n log n)。

但我们可以做得更好。

这个问题适合使用优先队列（priority queue）来解决。优先队列是一种支持以下操作的数据结构，其中 n 表示队列中元素的数量：

上述描述适用于最大优先队列。也存在最小优先队列，其最后两个操作分别是“查找最小值”和“移除最小值”。两种版本本质上是等价的，只需通过反向比较即可相互转换。

我们的做法是遍历所有文件，并将它们逐个加入一个按修改时间排序的最小优先队列中。该队列始终保留最新的文件。当队列大小超过 10 时，我们删除对应最早（“最小”）条目的文件，并从队列中移除该条目。

由于优先队列的大小被固定限制在 10 以内，所有操作的时间复杂度均为 O(1)，因为 n 被限定为一个预定义的常数。（当然，上限越大，这个常数也越大。）因此整个算法的时间复杂度为 O(n)，其中 n 是目录中文件的总数。

下面是一个解决方案的概要。为了构建最小堆，我们需要反转 dateAscending 的比较逻辑。

constexpr int files_to_keep = 10;

auto dateAscending = [](const WIN32_FIND_DATA& a, const WIN32_FIND_DATA& b) {
    return CompareFileTime(&a.ftLastWriteTime, &b.ftLastWriteTime) > 0;
    };

std::priority_queue<WIN32_FIND_DATA,
        std::vector<WIN32_FIND_DATA>, decltype(dateAscending)>
        names(dateAscending);

WIN32_FIND_DATA wfd;
wil::unique_hfind findHandle( FindFirstFileW(L"*.*", &wfd));
if (findHandle.is_valid())
{
    do
    {
        if (wfd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) {
            // Skip directories
            continue;
        }

        names.push(wfd);
        if (names.size() > files_to_keep) {
            DeleteFileW(names.top().cFileName);
            names.pop();
        }
    } while (FindNextFileW(findHandle.get(), &wfd));
}

遗憾的是 std::priority_queue 没有提供推导指南来自动推断 Comparator 类型。我们必须显式指定它，并且由于 Comparator 位于 Container 之后，不得不手动写出容器类型，而无法依赖类型推导。

同样遗憾的是，很难对 priority_queue 内部隐藏的 vector 调用 reserve() 方法。这意味着 names.push() 可能会抛出异常。不过我们使用了 RAII 类型 wil::unique_hfind 来确保不会泄露查找句柄。

如果你可以使用 std::inplace_vector，就可以完全避免内存分配。

std::priority_queue<WIN32_FIND_DATA,
        std::inplace_vector<WIN32_FIND_DATA, files_to_keep + 1>,
        decltype(dateAscending)> names(dateAscending);

（这也更清晰地表明该算法是常量空间复杂度的。）

这是一个典型的在线算法（online algorithm）示例——这类算法能够逐步处理输入数据，而不需要等待所有输入就绪才开始工作。

练习：如果任务是删除最旧的 10 个文件呢？

作者

雷蒙德参与 Windows 的演进已超过 30 年。2003 年，他创建了一个名为 The Old New Thing 的网站，其受欢迎程度远超他的想象，这一发展至今仍让他感到一阵阵莫名的不安。该网站催生了一本同名书籍《The Old New Thing》（Addison Wesley, 2007）。他偶尔会在 Windows Dev Docs 的 Twitter 账号上出现，讲述一些毫无用处的故事。