如何用C++标准算法库实现基于二元关系的等价去重？

好问题！针对你需要保留每个等价类首次出现元素的需求，我们可以利用C标准库的算法来避免显式编写for循环，下面分不同C版本给出实现方案：

C++11 实现 #

虽然C++11没有更高级的范围特性，但可以通过std::copy_if结合Lambda表达式来实现，核心思路是用Lambda捕获结果容器，每次检查当前元素是否已存在等价元素在结果中：

#include <algorithm>
#include <vector>

std::vector<T> filter_all_but_one_for_each_set_of_equivalent_T(std::vector<T> const& ts) {
    std::vector<T> result;
    std::copy_if(ts.begin(), ts.end(), std::back_inserter(result),
        [&result](T const& elem) {
            // 检查当前元素是否与结果中已有元素等价
            return !std::any_of(result.begin(), result.end(),
                [&elem](T const& existing) {
                    return equivalent(existing, elem);
                });
        });
    return result;
}

这里没有显式的for循环，完全通过标准库算法组合完成逻辑，符合C++11的特性要求。

C++20 及以上版本实现 #

C++20引入了**范围(Ranges)**特性，可以让代码更简洁直观，用std::views::filter来过滤元素，同样通过Lambda捕获结果容器跟踪已保留的等价类：

#include <ranges>
#include <vector>

std::vector<T> filter_all_but_one_for_each_set_of_equivalent_T(std::vector<T> const& ts) {
    std::vector<T> result;
    // 生成过滤后的视图
    auto filtered_view = ts | std::views::filter([&result](T const& elem) {
        if (std::ranges::any_of(result, [&elem](T const& existing) {
            return equivalent(existing, elem);
        })) {
            return false;
        }
        result.push_back(elem);
        return true;
    });
    // 将视图转换为vector返回
    return std::vector<T>(filtered_view.begin(), filtered_view.end());
    // C++23 可以更简洁：return filtered_view | std::ranges::to<std::vector<T>>();
}

关于std::unique的说明 #

你提到std::unique无法满足需求是完全正确的：std::unique（包括其范围版本）的作用是移除连续相邻的等价元素，而你的需求是移除所有之前出现过的等价元素（无论是否相邻），因此std::unique无法直接完成这个全局去重的逻辑。

性能提示 #

需要注意的是，上述方案的时间复杂度都是O(n²)，因为每个元素都需要和结果容器中已有的所有元素进行等价性检查。如果需要优化性能，你可以考虑：

• 为类型T提供兼容等价关系的哈希函数，配合std::unordered_set（需要自定义哈希和等价谓词），将时间复杂度降至O(n)
• 如果能为T定义严格弱序关系，也可以用std::set来跟踪已见元素，时间复杂度为O(n log n)

内容的提问来源于stack exchange，提问作者Elrond1337