c++ - 无法从基于 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，那么您将能够毫无问题地完成这项工作，实际上如果您将容器用作multiset，那么你将无法从中删除元素，但是当你将它作为一个集合使用时没有问题。

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

注意:请不要建议使用其他容器来解决问题。这不是解决方案。

Answer 1

使用 std::less_equal ，没有办法知道两个元素是否等价。 std::set使用表达式 !comp(a, b) && !comp(b, a)确定是否a和 b是等价的。如果您使用 strict weak ordering，则此方法有效。喜欢 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>>;

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

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