c++ - 使用 STL 在 C++ 中计算分区

Question

假设我有一个容器 C包含某种类型的元素 T和一个谓词，用于确定是否有任何两个类型为 T 的变量是“等价的”。例如。如果T是int我可能有一个谓词 eqv = [](int a, int b){ return a % 5 == b % 5; }这样两个整数在 eqv 下是等价的如果它们除以 5 的余数相同。

给定这样一个容器和一个谓词，是否有一些 STL 函数(例如来自 algorithm )我可以优雅地(即我自己无需编写大量代码)确定 C 的分区数在 eqv 下？

例如，如果 eqv如上和C是std::vector<int>{1,2,3,6,7,8}我想获得结果 3 (因为等价类是 {1,6} 、 {2,7} 和 {3,8} )。

Answer 1

两种方法，取决于您还可以用 T 做什么:

• 如果您能以某种方式对这些等价类进行排序，则创建一个 std::set。 T 类型的对象的排序需要是非全序的，其中在您的谓词下等效的所有元素既不小于也不小于其类的其他元素。插入所有元素，然后计算集合的大小。

• 如果您能以某种方式计算这些等价类的散列，则创建一个 std::unordered_set 并将模板参数 KeyEqual 设置为您的谓词。插入所有元素，然后计算集合的大小。

如果你只有谓词，那么我猜你被困在计数上了:

#include <algorithm>
#include <iostream>
#include <vector>



int main() {
    std::vector<int> elements = {1, 2, 3, 6, 7, 8};
    
    unsigned int size = 0;
    while (elements.size() > 0)
    {
        int const current = elements.front();
        auto pred = [&current] (auto const & other) {
            return (current % 5) == (other % 5);
        };
        elements.erase(std::remove_if(begin(elements), end(elements), pred), end(elements));
        ++size;
    }
    
    std::cout << size << " equivalence classes" << std::endl;
}

毕竟不是那么多代码。