C++ 向量计算每个元素的出现次数

我有一个向量类型vector<unsigned>我想知道每个元素在这个向量中出现了多少次。

这个向量可能非常大，所以我想循环它不是一个好主意。

最有效的方法是什么？

Unless the vector is already sorted (or at least grouped so identical elements are all together), looking at every item in the vector is unavoidable (and even if it is sorted, unless you expect a lot of duplicates, chances are pretty good that looking at every item will be the preferred method anyway)¹.

一种明显的方法是遍历向量，并用std::unordered_map:

std::unordered_map<unsigned, size_t> counts;
for (auto v : your_vector)
    ++counts[v];

然后您可以（例如）打印出这些值：

for (auto const &p : counts)
    std::cout << "The value: " << p.first << " occurred " << p.second << "times\n";

1. 如果您确实（预计）有大量重复项，并且项目已排序，则可以使用二分搜索来查找当前值运行的末尾。理论上的盈亏平衡点是，如果给定值的平均重复次数等于总体大小的以 2 为底的对数，因此如果重复次数大于该值，二分查找将需要较少的比较。现代 CPU 从可预测的线性访问模式中获得了足够的收益，而您可能需要这种模式more不过，每个值的重复项（平均而言）对于二分搜索来说是胜利。