A constant-space linear-time algorithm for deleting all but the 10 most recent files in a directory
Summary
This article describes a constant-space linear-time algorithm using a min-priority queue to delete all but the 10 most recent files in a directory, avoiding the O(n) space of sorting all entries.
<p>Say you have a directory full of files, and you want to delete all but the 10 most recent files. Is there a way to tell <code>FindFirstFile</code> to enumerate the files in date order?</p>
<p>No, there is no way to tell <code>FindFirstFile</code> to enumerate the files in date order. The files enumerated by <code>FindFirstFile</code> are produced in whatever order the file system driver wants. For example, FAT typically enumerates them in the order the files appear in the directory listing, which could be in order of creation if the files were added sequentially, or some mishmash order if there were renames or deletions mixed in.</p>
<p>Since you can’t control the order in which the files are enumerated, you’ll have to do the sorting yourself. The naïve solution is to read in all the entries, sort them by last-modified date, and then delete all but the last ten. This is <var>O</var>(<var>n</var>) space and <var>O</var>(<var>n</var> log <var>n</var>) running time.</p>
<p>But you can do better.</p>
<p>This job calls for a priority queue. A priority queue is a data structure that supports these operations, where <var>n</var> is the number of items in the priority queue.</p>
<ul>
<li>Add sorted: <var>O</var>(log <var>n</var>)</li>
<li>Find largest: <var>O</var>(1)</li>
<li>Remove largest: <var>O</var>(log <var>n</var>)</li>
</ul>
<p>The above description is for a max-priority queue. There is also a min-priority queue where the final two operations are “find smallest” and “remove smallest”. The two versions are equivalent because you can just use a reverse-sense comparison to switch from one to the other.</p>
<p>What we can do is enumerate all the files and add them one by one to a min-priority queue sorted by modified date. The priority queue holds the newest items. If the priority queue size exceeds 10, then we delete the file corresponding to the “smallest” (earliest) entry in the priority queue, and the remove that entry from the priority queue.</p>
<p>Since the priority queue size has a fixed cap, all of the operations run in <var>O</var>(1) time because the value of <var>n</var> is bounded by a predetermined constant. (Of course, the larger the cap, the larger the constant in <var>O</var>(1).) The overall algorithm then runs in <var>O</var>(<var>n</var>) times, where <var>n</var> is the number of files in the directory.</p>
<p>Here’s a sketch of a solution. To get a min-priority heap, we have to reverse the sense of the comparison in <code>dateAscending</code>.</p>
<pre>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));
}
</pre>
<p>It’s unfortunate that <code>std::<wbr />priority_<wbr />queue</code> doesn’t have a deduction guide that deduces the <code>Comparator</code>. We have to specify it explicitly, and since it comes after the <code>Container</code>, we have to write out the container type manually instead of allowing it to be deduced.</p>
<p>It’s also unfortunate that it’s hard to call <code>reserve()</code> on the vector hiding inside the <code>priority_<wbr />queue</code>. This means that the <code>names.push()</code> could throw an exception. At least we use an RAII type (<code>wil::<wbr />unique_<wbr />hfind</code>) to ensure that the find handle is not leaked.</p>
<p>If you have access to <code>std::<wbr />inplace_<wbr />vector</code>, you could use a</p>
<pre>std::priority_queue<WIN32_FIND_DATA,
std::inplace_vector<WIN32_FIND_DATA, files_to_keep + 1>,
decltype(dateAscending)> names(dateAscending);
</pre>
<p>to avoid memory allocations entirely. (It also makes it clearer that the algorithm is constant-space.)</p>
<p>This is an example of a so-called <a href="https://en.wikipedia.org/wiki/Online_algorithm">online algorithm</a>, an algorithm that does its work incrementally rather than requiring all of the input before it can start working.</p>
<p><b>Exercise</b>: What if the task was to delete the 10 oldest files?</p>
<p>The post <a href="https://devblogs.microsoft.com/oldnewthing/20260514-00/?p=112322">A constant-space linear-time algorithm for deleting all but the 10 most recent files in a directory</a> appeared first on <a href="https://devblogs.microsoft.com/oldnewthing">The Old New Thing</a>.</p>
View Cached Full Text
Cached at: 05/16/26, 03:31 AM
# A constant-space linear-time algorithm for deleting all but the 10 most recent files in a directory - The Old New Thing
Source: [https://devblogs.microsoft.com/oldnewthing/20260514-00?p=112322](https://devblogs.microsoft.com/oldnewthing/20260514-00?p=112322)
Say you have a directory full of files, and you want to delete all but the 10 most recent files\. Is there a way to tell`FindFirstFile`to enumerate the files in date order?
No, there is no way to tell`FindFirstFile`to enumerate the files in date order\. The files enumerated by`FindFirstFile`are produced in whatever order the file system driver wants\. For example, FAT typically enumerates them in the order the files appear in the directory listing, which could be in order of creation if the files were added sequentially, or some mishmash order if there were renames or deletions mixed in\.
Since you can’t control the order in which the files are enumerated, you’ll have to do the sorting yourself\. The naïve solution is to read in all the entries, sort them by last\-modified date, and then delete all but the last ten\. This isO\(n\) space andO\(nlogn\) running time\.
But you can do better\.
This job calls for a priority queue\. A priority queue is a data structure that supports these operations, wherenis the number of items in the priority queue\.
- Add sorted:O\(logn\)
- Find largest:O\(1\)
- Remove largest:O\(logn\)
The above description is for a max\-priority queue\. There is also a min\-priority queue where the final two operations are “find smallest” and “remove smallest”\. The two versions are equivalent because you can just use a reverse\-sense comparison to switch from one to the other\.
What we can do is enumerate all the files and add them one by one to a min\-priority queue sorted by modified date\. The priority queue holds the newest items\. If the priority queue size exceeds 10, then we delete the file corresponding to the “smallest” \(earliest\) entry in the priority queue, and the remove that entry from the priority queue\.
Since the priority queue size has a fixed cap, all of the operations run inO\(1\) time because the value ofnis bounded by a predetermined constant\. \(Of course, the larger the cap, the larger the constant inO\(1\)\.\) The overall algorithm then runs inO\(n\) times, wherenis the number of files in the directory\.
Here’s a sketch of a solution\. To get a min\-priority heap, we have to reverse the sense of the comparison in`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));
}
```
It’s unfortunate that`std::priority\_queue`doesn’t have a deduction guide that deduces the`Comparator`\. We have to specify it explicitly, and since it comes after the`Container`, we have to write out the container type manually instead of allowing it to be deduced\.
It’s also unfortunate that it’s hard to call`reserve\(\)`on the vector hiding inside the`priority\_queue`\. This means that the`names\.push\(\)`could throw an exception\. At least we use an RAII type \(`wil::unique\_hfind`\) to ensure that the find handle is not leaked\.
If you have access to`std::inplace\_vector`, you could use a
```
std::priority_queue<WIN32_FIND_DATA,
std::inplace_vector<WIN32_FIND_DATA, files_to_keep + 1>,
decltype(dateAscending)> names(dateAscending);
```
to avoid memory allocations entirely\. \(It also makes it clearer that the algorithm is constant\-space\.\)
This is an example of a so\-called[online algorithm](https://en.wikipedia.org/wiki/Online_algorithm), an algorithm that does its work incrementally rather than requiring all of the input before it can start working\.
**Exercise**: What if the task was to delete the 10 oldest files?
### Category
### Topics
## Author
Raymond has been involved in the evolution of Windows for more than 30 years\. In 2003, he began a Web site known as The Old New Thing which has grown in popularity far beyond his wildest imagination, a development which still gives him the heebie\-jeebies\. The Web site spawned a book, coincidentally also titled The Old New Thing \(Addison Wesley 2007\)\. He occasionally appears on the Windows Dev Docs Twitter account to tell stories which convey no useful information\.
Similar Articles
The Sync Heap: Delete First, Ask Questions Later
The paper introduces the sync heap, a novel data structure that decouples deletion from revealing the deleted element, enabling constant amortized time for insertions and deletions under limited inspections, and improving a textbook scheduling problem from O(n log n) to O(n).
@grgerwcwetwet: Recommend an open-source project WindowsCleaner, designed to fix insufficient space on Windows C drive. Temporary files, system cache, update leftovers, app junk, etc. can all be cleaned with one click. It also supports deep cleaning and log viewing, has a simple interface, and is completely free and open source. Suitable for Windows 10/11, daily C drive cleanup...
Recommending the open-source project WindowsCleaner, a C drive cleanup tool for Windows 10/11. It can clean temporary files, system cache, update leftovers, and app junk with one click, supports deep cleaning and log viewing, and is completely free and open source.
15 sorting algorithms in 6 minutes (2013) [video]
A 2013 video visualizing and audibilizing 15 sorting algorithms in 6 minutes, including selection sort, quick sort, and bogo sort.
@iluciddreaming: Disk cleanup tool recommendation: Czkawka (written in Rust, 31.7k Stars on GitHub). It can find duplicate files, similar images/videos/music, empty folders, large files, temporary files, clear Exif, and optimize videos. Extremely fast, multi-threaded, supports caching for faster subsequent scans. Cross-platform Wi…
Recommendation for an open-source disk cleanup tool written in Rust: Czkawka. It is feature-rich, supports finding duplicate files, similar media files, empty folders, etc., and is cross-platform and free.
Sorting, hashing, and sketches on 370,103 words
A technical blog post that explores sorting, hashing, and sketching algorithms on a dataset of 370,103 English words, measuring time and memory costs, with a focus on practical implementations like binary search, quicksort, and HyperLogLog.