Hier jetzt ein aktualisiertes Beispielprogramm:
#include <array>
#include <cstring>
#include <filesystem>
#include <fstream>
#include <iostream>
#include <unordered_map>
#include <vector>
namespace fs = std::filesystem;
static constexpr std::streamsize BufSize{ 4096 };
template<std::streamsize BufSize>
bool is_duplicate_file(const fs::directory_entry& file_a, const fs::directory_entry& file_b) {
if (!file_a.is_regular_file() || !file_b.is_regular_file()) {
return false;
}
if (fs::equivalent(file_a, file_b)) {
return true;
}
if (file_a.file_size() != file_b.file_size()) {
return false;
}
std::ifstream a_in{ file_a.path(), std::ios::binary };
std::ifstream b_in{ file_b.path(), std::ios::binary };
if (!a_in || !b_in) {
throw std::runtime_error("is_duplicate_file: Unable to open file(s) for reading");
}
if (a_in.peek() != b_in.peek()) {
return false;
}
std::array<char, BufSize> buf_a{};
std::array<char, BufSize> buf_b{};
while (a_in && b_in) {
a_in.read(buf_a.data(), BufSize);
b_in.read(buf_b.data(), BufSize);
/* Seems superfluous since what can fail besides hitting EOF on ifstream::read().
if (a_in.fail() && !a_in.eof() || a_in.bad() || b_in.fail() && !b_in.eof() || b_in.bad()) {
throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
}
*/
if (std::memcmp(buf_a.data(), buf_b.data(), BufSize))
return false;
}
return true;
}
auto build_file_index(const fs::path& start_path) {
std::unordered_multimap<std::uintmax_t, fs::directory_entry> files_by_size;
for (const auto& entry : fs::recursive_directory_iterator{ start_path }) {
if (entry.is_regular_file()) {
files_by_size.emplace(entry.file_size(), entry);
}
}
return files_by_size;
}
auto find_duplicate_files(const auto& files) {
std::unordered_map<fs::path, std::vector<fs::path>> dupes;
for (auto entry = files.begin(); entry != files.end(); ) {
auto range{ files.equal_range(entry->first) };
int idx_i{};
std::vector<bool> matched(std::distance(range.first, range.second), false); // std::unordered_map<fs::path, bool> works, too!
for (auto i = range.first; i != range.second; ++i, ++idx_i) {
int idx_j{ idx_i + 1 };
for (auto j = std::next(i); j != range.second; ++j, ++idx_j) {
if (!matched[idx_i] && !matched[idx_j] && is_duplicate_file<BufSize>(i->second, j->second)) {
dupes[i->second.path()].emplace_back(j->second.path());
matched[idx_j] = true;
}
}
}
entry = range.second;
}
return dupes;
}
void print_dupes(const auto& dupes) {
for (const auto& a : dupes) {
std::cout << "\nReference: " << a.first << '\n';
for (const auto& b : a.second) {
std::cout << "Duplicate: " << b << '\n';
}
}
std::cout << "\nFound a total of " << dupes.size() << " duplicate groups.\n\n";
}
int main(int argc, char* argv[])
try {
if (argc != 2) {
std::cout << "Program expects one argument: <Starting path>\n";
return 1;
}
fs::path start_path{ argv[1] };
if (!fs::exists(start_path)) {
std::cout << "Provided argument is not an existing path.\n";
return 2;
}
print_dupes(
find_duplicate_files(
build_file_index(start_path)));
}
catch (const fs::filesystem_error& e) {
std::cerr << e.what() << '\n';
return e.code().value();
}
catch (const std::runtime_error& e) {
std::cerr << e.what() << '\n';
return -2;
}
catch (...) {
std::cerr << "Unhandled exception!\n";
return -1;
}
Edit 1: Ich hatte beim Programmieren auch an std::unordered_map<fs::path, bool> gedacht, was sich performance-technisch nicht viel schenkt mit std::vector<bool>. Inzwischen wurde ich darauf hingewiesen, dass man auch einfach std::unordered_set<fs::path> verwenden könnte - auch von der Performance her ähnlich, aber wahrscheinlich eleganter als dieser Pfusch mit den Indizes.
Die Idee war klar, wenn z. B. Dateien A, B, C mit Größe X geprüft werden, und ich habe bereits erkannt, dass Datei B mit A identisch sind, dann brauche ich gar nicht erst versuchen, Datei B auch noch mit C zu vergleichen (das wäre sinnlos, wenn B==C, dann wäre C bereits gegen A gefunden worden).
Edit 2:
Jetzt so:
auto find_duplicate_files(const auto& files) {
std::unordered_map<fs::path, std::vector<fs::path>> duplicates;
std::unordered_set<fs::path> matched;
for (auto left = files.begin(); left != files.end(); ) {
auto range = files.equal_range(left->first);
left = range.second;
for (auto ref_it = range.first; ref_it != range.second; ++ref_it) {
if (matched.contains(ref_it->second.path())) {
continue;
}
for (auto file_it = std::next(ref_it); file_it != range.second; ++file_it) {
if (!matched.contains(file_it->second.path()) && is_duplicate_file<BufSize>(ref_it->second, file_it->second)) {
matched.emplace(file_it->second.path());
duplicates[ref_it->second.path()].emplace_back(file_it->second.path());
}
}
}
}
return duplicates;
}
