c++ - 链表中的频率计数

Question

我有以下链表结构:

struct Node {
    int type;
    int otherInfo;
    Node * next;
}

我想创建一个排序的(最终)链表来跟踪每个“类型”出现的次数。一个示例节点是:

struct Node2 {
    int type;
    int frequency;
    //A linked list to keep track of the "otherInfo"
    Node2 * next;
}

我现在的算法是O(n^2)，这是不合理的，因为原始链表有时可以有超过30,000个元素。有没有更有效的方法来做到这一点？

注意:类型几乎可以是任何正整数，所以我不能简单地创建一个以类型作为索引的静态数组。

编辑:频率列表不必是链表。我举了个例子。稍后在程序中，我使用堆对频率列表进行排序。我只需要稍后能够遍历频率列表。

Answer 1

听起来您真正需要的是 map 或基本的二叉搜索树。键类型将是您的类型值，而值类型将保存您的频率。