使用正确工作的find()创建有序多重集 [英] Creating ordered multiset with correctly working find()

问题描述

我尝试使用以下代码创建有序多集:

I tried to create ordered multiset with such code:

#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()保存排序集中的重复项?

But find() cant find any number because of using less_equal < ll > comparator instead of less < ll >. So, how to save dublicates in sorted set with working right find()?

推荐答案

来自gnu docs

From the gnu docs here

自我支撑:该库不包含类似的容器std :: multimap或std :: multiset.相反，这些数据结构可以是通过操作映射的模板"参数合成.

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.

如果没有您自己的样板，就无法对多集使用此数据结构.例如，您可能会执行以下操作(尽管这是不安全的不完整实现)

There is no way to use this data structure for a multiset without some boiler plate of your own. For example your might do something like the following (though this is an unsafe incomplete implementation)

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);
        }
    }
}

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

The link goes more into how you might approach the problem in different ways, but you are likely better off rolling your own or using an existing library that has all the functionality you want in a more portable standard way.

请注意，使用 std :: less_equal 的原因对您不起作用是因为 tree (以及 set 和 multiset 等.)确定比较是否对等都为假.例如.如果！(a< b)&&！(b< a).因此，使用 less_equal 绝对不可能(禁止超载)

Note that the reason using std::less_equal does not work for you is because tree (and set and multiset etc.) determine equivalence if the comparison evaluates false for both. eg. a is equivalent to b if !(a < b) && !(b < a). So using less_equal that can never be the case (barring overloading)

这篇关于使用正确工作的find()创建有序多重集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！