c++ - 根据频率对自定义结构的 vector 进行排序

Question

我需要找到自定义结构数组中出现频率最高的元素。它们没有自定义 ID，只是匹配属性。

我正在考虑按频率对 vector 进行排序，但我不知道该怎么做。

Answer 1

我假设您所说的频率是指相同结构在数组中出现的次数。

您可能想为您的自定义结构创建一个散列函数(或为您的类型重载 std::hash<>)。然后遍历你的数组，递增 unordered_map<mytype, int> 上的值对于数组中的每个结构。这将为您提供值字段中的频率。像下面这样的东西会起作用:

std::array<mytype> elements;
std::unordered_map<mytype, int> freq;
mytype most_frequent;
int max_frequency = 0;
for (const mytype &el : elements) {
    freq[el]++;
    if (freq[el] > max_frequency) {
        most_frequent = el;
    }
}

为此，映射需要能够为上述函数创建哈希。默认情况下，它尝试使用 std::hash<>。标准明确允许您在标准命名空间中为您自己的类型专门化此模板。您可以按如下方式执行此操作:

struct mytype {
    std::string name;
    double value;
};
namespace std {
    template <> struct hash<mytype> {
        size_t operator()(const mytype &t) const noexcept {
            // Use standard library hash implementations of member variable types
            return hash<string>()(t.name) ^ hash<double>()(t.value)
        }
    }

}

主要目标是确保不包含完全相同值的任何两个变量将生成不同的散列。上面的 XOR 将标准库的每种类型的哈希函数的结果放在一起，即 according to Mark Nelson可能与单独的哈希算法异或在一起一样好。 cppreference 的 hash reference 建议的替代算法是Fowler-Noll-Vo hash function .