无法从基于 libstdc++ 策略的数据结构中擦除

Question

在 C++ 中有一个关联的容器，它实际上是一个集合（multiset），它可以给出其中元素的顺序。

这是我如何使用容器：

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

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,
                              tree_order_statistics_node_update>;

问题是，我无法从中删除元素：

ordered_multiset<int> s;
s.insert(0);
s.erase(0);

cout << s.order_of_key(1); // returns number of elements less than x

// Outputs: 1

奇怪的是，如果您替换less_equal为less，那么您将能够毫无问题地完成这项工作，实际上如果您将容器用作多重集，那么您将无法从中删除元素，但是没有成套使用时的问题。

• 导致问题的原因是什么？
• 我该如何解决问题？

注意：请不要建议使用其他容器来解决问题。那不是解决办法。

Answer 1

使用std::less_equal，无法知道两个元素是否等效。std::set使用表达式!comp(a, b) && !comp(b, a)来确定a和b是否等价。如果您使用严格的弱排序（例如，std::less但在使用std::less_equal. 5和5是等价的但是!(5 <= 5) && !(5 <= 5)是false。所以擦除失败。

简而言之，您不能仅使用std::less_equal.

@Caleth描述了一种std::multiset在线性时间内使用和进行搜索的方法。您可以通过保持每个元素的顺序来确定对数时间的顺序。

template <typename Value>
struct ordered_value {
  size_t order;
  Value value;
};

template <typename Value>
using ordered_multiset = std::multiset<ordered_value<Value>>;

这样做的问题是每次插入或擦除（这是线性的）时都必须更新顺序。您确定您使用的容器在恒定时间内执行操作吗？这对我来说似乎是不可能的。

在红黑树中实现排序统计的方式实际上非常相似。每个节点中都有一些额外信息，每当您插入或删除时都会更新这些信息。关键是，这非常接近您可以做的最好的事情，而无需费心制作自己的红黑树。

Answer 2

是什么导致了这个问题？

您尚未提供Compare to tree。你的程序格式不正确。

我该如何解决这个问题？

使用std::multiset<T>和

template<typename Set, typename Key>
size_t order_of_key(const Set & set, const Key & key)
{
    return std::distance(set.begin(), set.lower_bound(key));
}