时间戳

首页 > 解决方案 > 使用 STL 在 C++ 中计算分区

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

问题描述

想象一下，我有一个容器C，其中包含某种类型的元素T和一个谓词，用于确定任何两个类型的变量T是否“等价”。例如 if Tis intI 可能有一个谓词eqv = [](int a, int b){ return a % 5 == b % 5; }，使得两个整数eqv在除以 5 时具有相同余数的情况下是等价的。

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

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

标签： c++stl

解决方案

两种方法，取决于您还可以做什么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;
}

毕竟，这不是很多代码。

推荐阅读