sort，它还跟踪每个级别上的唯一项的数量

Question

假设我有一个std::vector。假设向量包含数字。我们取std::vector

1、3、5、4、3、4、5、1、6、3

std::sort<std::less<int>> will sort this into

1, 1, 3, 3, 3, 4, 4日,5日,5日,6日,

我该如何修改sort，以便在排序的同时，它也计算同一级别的数字数量。因此，除了排序，它还将编译以下字典[level is also int]

std::map<level, int>
<1, 2>
<2, 3>
<3, 2>
<4, 2>
<5, 1>
<6, 1>

有2个1,3个3,2个4，等等

我[认为]我需要这个的原因是因为我不想对向量进行排序，然后再一次计算每一层的重复数。似乎一次做两件事更快?

谢谢大家!bjskishore123是最接近我的问题，但所有的回答都让我受益匪浅。再次感谢。

Answer 1

正如@bjskishore123所述，您可以使用映射来保证集合的正确顺序。作为奖励，您将有一个优化的结构来搜索(当然是地图)。

在映射中插入/搜索需要O(log(n))时间，而遍历向量需要O(n)时间。所以算法是O(n*log(n))这与任何需要比较元素的排序算法(例如归并排序或快速排序)的复杂度相同。

下面是一个示例代码:

int tmp[] = {5,5,5,5,5,5,2,2,2,2,7,7,7,7,1,1,1,1,6,6,6,2,2,2,8,8,8,5,5};
std::vector<int> values(tmp, tmp + sizeof(tmp) / sizeof(tmp[0]));
std::map<int, int> map_values;
for_each(values.begin(), values.end(), [&](int value)
{
    map_values[value]++;
});
for(std::map<int, int>::iterator it = map_values.begin();  it != map_values.end(); it++)
{
    std::cout << it->first << ": " << it->second << "times";
}

输出:

1: 4times
2: 7times
5: 8times
6: 3times
7: 4times
8: 3times

Answer 2

我认为你不可能一蹴而就。假设您为排序提供了自己的自定义comparator，它以某种方式尝试计数重复项。

然而，您可以在排序器中捕获的唯一东西是当前正在比较的两个元素的的值(可能是引用，但无关紧要)。您没有其他信息，因为std::sort没有向排序器传递任何其他信息。

现在std::sort的工作方式，它将继续交换元素，直到它们在排序向量中到达适当的位置。这意味着单个成员可以多次发送到排序器，从而无法精确计数。你可以计算一个特定的元素和其他所有等于它的值被移动了多少次，但不能计算其中有多少个。

Answer 3

不使用vector，

在逐个存储数字时，使用std::multiset容器

内部按顺序存储

在存储每个数字时，使用映射来跟踪每个数字出现的次数。

map<int, int> m;

每次添加一个数字时，执行

m[num]++; 

因此，不需要另一次传递来计算出现的次数，尽管您需要在map中迭代以获得每次出现的计数。

=============================================================================

下面是一个替代的解决方案不推荐。按照你的要求给出一个使用STD::SORT的方法。

下面的代码使用比较函数来计算出现次数。

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct Elem
{
    int index;
    int num;
};
std::map<int, int> countMap; //Count map
std::map<int, bool> visitedMap;
bool compare(Elem a, Elem b)
{
    if(visitedMap[a.index] == false)
    {
        visitedMap[a.index] = true;
        countMap[a.num]++;
    }
    if(visitedMap[b.index] == false)
    {
        visitedMap[b.index] = true;
        countMap[b.num]++;
    }
    return a.num < b.num;
}
int main()
{
    vector<Elem> v;
    Elem e[5] = {{0, 10}, {1, 20}, {2, 30}, {3, 10}, {4, 20} };
    for(size_t i = 0; i < 5; i++)
        v.push_back(e[i]);
    std::sort(v.begin(), v.end(), compare);
    for(map<int, int>::iterator it = countMap.begin(); it != countMap.end(); it++)
        cout<<"Element : "<<it->first<<" occurred "<<it->second<<" times"<<endl;
} 

输出:

Element : 10 occurred 2 times
Element : 20 occurred 2 times
Element : 30 occurred 1 times

Answer 4

如果您有很多重复项，完成此任务的最快方法可能是首先使用散列映射计算重复项，这是O(n)，然后对映射进行排序，这是O(m log m)，其中m是唯一值的数量。

像这样(在c++11中):

#include <algorithm>
#include <unordered_map>
#include <utility>
#include <vector>
std::vector<std::pair<int, int>> uniqsort(const std::vector<int>& v) {
  std::unordered_map<int, int> count;
  for (auto& val : v) ++count[val];
  std::vector<std::pair<int, int>> result(count.begin(), count.end());
  std::sort(result.begin(), result.end());
  return result;
}

这个主题有很多变化，这完全取决于你需要什么。例如，也许您甚至不需要对结果进行排序;也许有计数图就足够了。或者，您可能希望结果是一个从int到int的排序映射，在这种情况下，您可以构建一个常规的std::map。(这就是O(n log m)。)或者你可能知道一些关于这些值的知识，这些值可以使它们更快地排序(比如它们是已知范围内的小整数)。等等