Подсчет разделов в C ++ с использованием STL

Question

Представьте, что у меня есть контейнер C, содержащий элементы некоторого типа T и предикат, с помощью которого можно определить, являются ли какие-либо две переменные типа T «эквивалентными». Например, если T равно int, у меня может быть предикат eqv = [](int a, int b){ return a % 5 == b % 5; } такой, что два целых числа эквивалентны под eqv, если они имеют одинаковый остаток при делении на пять.

Учитывая такой контейнер и предикат, есть ли какая-то функция 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 должна быть неполным порядком, когда все элементы, эквивалентные согласно вашему предикату, не меньше и не меньше других элементов своего класса. Вставьте все элементы, затем подсчитайте размер набора.

• если вы можете каким-то образом вычислить ha sh этих классов эквивалентности, затем создайте 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;
}

Isn ' В конце концов, столько кода.