c++ - 使用正确工作的 find() 创建有序的多重集

Question

我尝试用这样的代码创建有序的多重集:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;

template <class type1>
using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>;

ordered_multiset <ll> kek;

int main()
{
    kek.insert(1); kek.insert(1);
    kek.insert(2); kek.insert(2); kek.insert(2);
    kek.insert(3);
    cout << (kek.find(2) == kek.end()) << endl;
}

但是find()由于使用 less_equal < ll > 找不到任何数字比较器而不是 less < ll > .那么，如何使用工作权在排序集中保存重复项 find() ？

Answer 1

来自 gnu 文档 here

Brace onself: this library does not contain containers like std::multimap or std::multiset. Instead, these data structures can be synthesized via manipulation of the Mapped template parameter.

如果没有您自己的一些样板，就无法将此数据结构用于多重集。例如你可能会做类似下面的事情(虽然这是一个不安全的不完整的实现)

template <class T>
class multiset_equal_list {
    friend operator<(const multiset_equal_list<T>&, const T&);
private:
    mutable std::vector<T> equals;
public:
    bool operator<(const T& arg) const { return equals[0] < arg; }
    void add_equal(const T& arg) const { equals.push_back(arg); }
}


template <class T>
class my_multiset {
private:
    std::set<multiset_equal_list<T>> values; //instead of set, you can use the __gnu_pbds tree
public:
    void insert(const T& arg) {
        auto it = values.lower_bound(arg);
        if (it == values.end() || (*it < arg)) {
            multiset_equal_list<T> to_add;
            to_add.add_equal(arg);
            values.insert(it, to_add);
        } else { //they are equal
            it->add_equal(arg);
        }
    }
}

该链接更多地介绍了您可能如何以不同的方式解决问题，但您最好自己动手或使用现有的库，该库以更可移植的标准方式提供您想要的所有功能。

请注意使用 std::less_equal 的原因对你不起作用是因为tree (以及 set 和 multiset 等)如果比较对两者的评估都是假的，则确定等价性。例如。 a相当于b如果!(a < b) && !(b < a) .所以使用 less_equal永远不会是这种情况(除非重载)