Вычислить количество уникальных значений в векторе отсортированных векторов

Question

У меня есть объект типа std::vector<std::vector<size_t>> с именем v, где каждый подвектор (каждый std::vector<size_t>) сортируется. Я хотел бы подсчитать, сколько раз обнаруживается каждый уникальный size_t из v. Я думал об использовании std::map<size_t, size_t> и сделать что-то вроде

int main()
{
    const std::vector<std::vector<size_t>> v = {
        {4, 10, 12, 18, 20, 28, 34},
        {4, 12, 18, 20, 28},
        {4, 17, 18, 20, 28},
        {4, 17, 18, 20, 28, 37}
    };


    std::map<size_t, size_t> counts;
    for (const auto& a : v)
    {
        for (const auto& b : a)
        {
            auto it = counts.lower_bound(b);
            if (it != counts.end() && !(counts.key_comp()(b, it->first)))
            {
                // mut already exist
                ++(it->second);
            } else
            {
                // mut is new
                counts.insert(it, std::map<size_t, size_t>::value_type(b, 1));
            }
        }   
    }

    for (auto it = counts.begin() ; it != counts.end() ; ++it)
        std::cout << it->first << ": " << it->second << "\n";
}

, которое выводит

4: 4
10: 1
12: 2
17: 2
18: 4
20: 4
28: 4
34: 1
37: 1

, как ожидалось.

На практике значения одинаковы распределяется между 0 и 4e9, что подталкивает меня к использованию std::map вместо std::vector. Если значение присутствует в одном векторе, это увеличивает вероятность того, что это значение будет найдено снова и снова в последовательных векторах, что делает вставки относительно редкими по сравнению с приращением уже вставленных значений. Кроме того, части векторов, как правило, идентичны.

Есть ли лучший метод? Например, при вычислении lower_bound было бы быстрее использовать точку вставки предыдущего элемента при сортировке элементов. Что-то вроде

    for (const auto& a : v)
    {
        MapType::iterator it = a.begin();
        for (const auto& b : a)
        {
            auto it = counts.lower_bound(it, b); // Use `it` to avoid searching in elements that precedes its position
            
            // etc..
        }   
    }

, однако я не думаю, что std :: map :: lower_bound может использовать итератор from.

Answer 1

Это необходимо проверить на производительность, но если предположить, что количество векторов значительно меньше, чем числа в них, этот метод может работать быстрее:

using szvec = std::vector<size_t>;
using range = std::pair<szvec::const_iterator,szvec::const_iterator>;

const std::vector<szvec> v = {
    {4, 10, 12, 18, 20, 28, 34},
    {4, 12, 18, 20, 28},
    {4, 17, 18, 20, 28},
    {4, 17, 18, 20, 28, 37}
};

// we use greater so iterator with smallest value will be on top of queue
auto sort_range = []( const range &r1, const range &r2 ) { 
    return *(r1.first) > *(r2.first);
};
std::priority_queue<range,std::vector<range>,decltype(sort_range)> q( sort_range );

// we assume all vectors are not empty on start
// otherwise we need to check for empty range before pushing
for( const auto &vec : v ) q.push( std::make_pair( vec.cbegin(), vec.cend() ) );
std::vector<std::pair<size_t,size_t>> counters;
while( !q.empty() ) {
    auto r = q.top();
    q.pop();
    if( counters.empty() || counters.back().first != *(r.first) ) 
        counters.emplace_back( *(r.first), 1 );
    else 
        counters.back().second++;
    if( ++r.first != r.second ) q.push( r );
}

for( const auto &p : counters ) 
    std::cout << p.first << ":" << p.second << std::endl;

Итак, идея состоит в том, чтобы иметь итераторы для разных векторов, отсортированных по значение, на которое они указывают, и подсчитывают одни и те же значения, проходящие через итераторы, а не обрабатывают каждый вектор отдельно.

Живой пример

Answer 2

Я представляю один способ повторно использовать точку вставки. Я использую тот факт, что вставки редки.

Я бы использовал отсортированный вектор пар в качестве MapType.

typedef std::vector<std::pair<size_t, size_t>> MapType;

Предполагая, что векторы отсортированы в соответствии с функтором key_comp. Затем вы можете создать функтор сравнения для своего MapType (здесь я использую лямбда-выражение для этого).

auto comp = [&](std::pair<size_t, size_t>& p1, std::pair<size_t, size_t> const& p2)
    {
        return key_comp(p1.first,p2.first);
    };

Теперь для каждого вектора в v вы можете повторно использовать свои прошлые точки вставки, потому что вы знаете, что элементы отсортированы.

Вот полный код

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

typedef std::vector<std::pair<size_t, size_t>> MapType;

int main()
{
    const std::vector<std::vector<size_t>> v = {
        {4, 10, 12, 18, 20, 28, 34},
        {4, 12, 18, 20, 28},
        {4, 17, 18, 20, 28},
        {4, 17, 18, 20, 28, 37}
    };

    auto key_comp = [](std::size_t v1, std::size_t v2) {
        return v1 < v2;
    };

    auto comp = [&](std::pair<size_t, size_t>& p1, std::pair<size_t, size_t> const& p2)
    {
        return key_comp(p1.first,p2.first);
    };


    MapType counts;
    for (const auto& a : v)
    {
        auto it = counts.begin();
        for (const auto& b : a)
        {
            // You can start from it instead of counts.begin() because vector a is sorted
            it = std::lower_bound(it, counts.end(), MapType::value_type(b, 1), comp);
            if (it != counts.end() && !(key_comp(b, it->first)))
            {
                // mut already exist
                ++(it->second);
            } else
            {
                // mut is new
                // Insertion may invalidate iterators so you need to reassign it
                it = counts.insert(it, MapType::value_type(b, 1));
            }
        }   
    }

    for (auto it = counts.begin() ; it != counts.end() ; ++it)
        std::cout << it->first << ": " << it->second << "\n";
}

Вывод:

4: 4
10: 1
12: 2
17: 2
18: 4
20: 4
28: 4
34: 1
37: 1

Ссылка на проводник компилятора: https://godbolt.org/z/zoY7KG