如何在C++中存储有序集中的重复元素？

在C++中，有序集可以使用STL库中的set或者multiset来实现。其中，set是一种红黑树实现的有序集，它保证了集合中元素唯一且有序。而multiset是set的衍生，可以存储重复元素。

然而，在multiset中存储重复元素时，我们往往需要知道每个元素在集合中出现的次数。下面，我们将分别介绍两种方法来实现这样的需求。

方法一：自定义存储结构

我们可以使用pair来存储元素和元素出现次数，代码如下：

#include <iostream>
#include <set>
#include <utility>

using namespace std;

int main() {
    multiset<pair<int, int>> ms;
    ms.insert({1, 1});
    ms.insert({2, 3});
    ms.insert({3, 2});
    ms.insert({4, 1});

    for(auto& p : ms) {
        cout << p.first << " appears " << p.second << " times." << endl;
    }
    return 0;
}

输出结果为：

1 appears 1 times.
2 appears 3 times.
3 appears 2 times.
4 appears 1 times.

在自定义存储结构时，我们需要手动实现比较运算符，来保证元素在集合中的顺序。比较的方式可以根据需求来定制。

struct myPair {
    int val;
    int cnt;

    bool operator < (const myPair& p) const {
        // 先按出现次数降序排序
        if(cnt != p.cnt) {
            return cnt > p.cnt;
        }
        // 如果出现次数相同，则按元素大小升序排序
        return val < p.val;
    }
};

使用自定义存储结构时，我们可以通过STL中自带的pair（或tuple）来快捷实现。

方法二：使用哈希表

我们可以使用unordered_map来实现哈希表，以记录每个元素出现的次数。代码如下：

#include <iostream>
#include <set>
#include <unordered_map>

using namespace std;

int main() {
    multiset<int> ms;
    unordered_map<int, int> cnt;

    ms.insert(1);
    ms.insert(2);
    ms.insert(3);
    ms.insert(2);
    ms.insert(1);

    for(auto& x : ms) {
        if(cnt[x]++ == 0) {
            cout << x << " appears " << cnt[x] << " time." << endl;
        }
        else {
            cout << x << " appears " << cnt[x] << " times." << endl;
        }
    }
    return 0;
}

输出结果为：

1 appears 1 time.
2 appears 2 times.
3 appears 1 time.

在使用哈希表时，我们需要注意哈希函数的设计以及冲突解决机制的选择。根据实际场景来选择不同的解决方案，以达到最优的性能表现。

结论

我们介绍了两种方法来存储multiset中的重复元素，分别是自定义存储结构和使用哈希表。可以根据实际需求来选择适合自己的方式。