我有一个类型为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迭代器。
我给出了一种重用插入点的方法。 我是利用插入很少的事实。
我将使用对的排序向量作为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
这需要进行性能测试，但假设向量的数量明显小于其中的数字，这种方法可能工作得更快:
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;
因此，我们的想法是让迭代器对不同的向量进行排序，按它们所指向的值进行排序，并对通过迭代器传递的相同值进行计数，而不是分别处理每个向量。
活生生的例子
