计算排序向量的向量中唯一值的计数

Question

我有一个类型为std::vector 的对象，称为V，其中每个子向量（每个std::vector )都是排序的。 我想计算出v的每个唯一size_t被找到的次数。 我在考虑使用std::map 并执行如下操作

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构建一个比较函子（这里我使用lambda表达式来完成）。

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